В своё время неплохо ускорил процесс поиска Sphinx, у него другая организация индекса, поэтому скорость резко отличается. Если на сервере мощности достаточно, то можно попробовать.
ну и базовая оптимизация - LIKE "%...%"работает в разы медленнее, чем LIKE "...%"
Вы мало сказали про состав типичной строки в БД и по какой её части планируете искать.
Если что, то запрос "explain select ...." полезная штука