Итоги голосования для комментария:
Arris Перевести поиск на движок Sphinx.

livestreet.ru/blog/dev_documentation/13482.html
zaan.ru/ustanovka-sphinx-dlya-livestreet/

Правда он довольно требователен к ресурсам, для нормального поиска ему нужен хотя бы гигабайт оперативки под свои нужды. Зато он ищет реально мгновенно.

fulltext-поиск по полю типа text в базе на 9 млн записей занимает примерно 45-55 секунд. Поиск по тому же полю сфинксом — примерно 0.2-0.4 секунды
+