LIKE дает неймоверную нагрузку на СУБД.
Все зависит от кого какой engine таблицы вы испольуете. Для полнотекстовго поиска с учетом мофологии лучше всего использвать sphinx.
Если делать через match это лучше всего MyISAM.
SELECT word FROM table WHERE
MATCH (word) AGAINST ('cat*' IN BOOLEAN MODE)
а вообще
www.mysql.ru/docs/man/Fulltext_Search.html 
