Тут вопрос с кол-ве динамический параметров, по которым может идти поиск. Если это парочка, то ставишь индекс и никаких проблем нет. Если их 5+, то уже беда
Я делал поиск и на 6-8 таблицах с суммарным кол-вом строк до 250 млн. (tecdoc) без сторонней индексации. Таблицы myisam? правда были, другие не тянут и сильно раздутые получаются.
Да я не пугаю. Там весьма несложно, просто осознать нужно, что на одну таблицу - один индекс. И работать он будет очень быстро. А все, что вне индекса - медленно. Хоть 50 таблиц джойни