AFAIK, MySQL действительно плохо работает,
каково ваше решение?
Кстати, каково решение SO?
EDIT
Обратите внимание, что сам по себе свободный поиск в MySQL довольно быстр,
но не тот случай, когда результат также должен быть отсортирован по атрибуту!
Apache SOLR (Lucene) вполне способен.
Я думаю, что переполнение стека использует SQL Server в фоновом режиме со встроенными возможностями полнотекстового поиска, предлагаемыми базой данных. Oracle предлагает Oracle intermedia (Oracle 9i), позже названный Oracle Text, который очень хорошо интегрирован и эффективен. Postgresql предлагает стандартный встроенный модуль под названием tsearch2. Я не уверен насчет MySql, но, глядя на другие 3 базы данных, которые я упомянул, полнотекст - это нечто сложное, и для его развития требуется время.
Я рекомендую Sphinx Search : необходимо настроить и внести некоторые изменения в ваш код, но оно того стоит.
На форуме с 1+ миллионами сообщений полнотекстовый поиск занимает всего несколько миллисекунд.
SO использует возможности полнотекстового поиска Microsoft SQL Server, это было несколько раз упомянуто в подкасте и в блоге (например: http://blog.stackoverflow.com/2008/11/sql-2008-full-text-search-problems/) В этой записи блога Джефф упоминает о возможном переходе на Lucene.net в будущем.
В настоящее время я оцениваю Haystack и Solr на предмет поиска. в паре проектов.