carbonariy

FULLTEXT должен снизить нагрузку, но если у вас используется таблицы типа InnoDB, то придется продублировать поисковый индекс в таблицу типа MyISAM. Если не поможет и доступ к серверу ограничен, то попробуйте Zend Lucene