Форум пользователей MySQL

Здравствуйте форумчане.
Опишу вопрос:
Есть база (около 500 000 записей) база изменяется ооочень редко. В ней некоторое количество полей, как текстовых так и числовых. Требуется сделать максимально быстрый поиск по этой базе. В 95% случаев поиск будет идти по одному текстовому полю(от одного до пяти слов в записи). Параметром запроса будет строка от трех символов длинны. Вот и встает вопрос как лучше реализовать данный запрос.
После часа гугла выделились два типа поиска через лайк или полнотекстный. На лайк везде ругаются что он медленный, а в полнотекстом как я понял еще считается релевантность, а это значит что привлекается какая-то логика(которая, как я понимаю, ведет к большей нагрузке). Здесь задача просто найти все строки, в которых слова начинаются с заданных символов. При необходимости могу сделать таблицу со словами по отдельности, так что в каждой строке будет только одно слово.
Так как данные оч статичны, то, как я понимаю, можно индексировать там все до посинения.
Посоветуйте пожалуйста какими операторами лучше организовать поиск.