Есть несколько переменных, которые вступают в игру при оптимизации веб-приложения. Исходя из того, что вы заявили, предоставление пользователю возможности выбрать несколько опций для «построения запроса» приводит меня к мысли, что вы, возможно, выполняете некоторые операции MySQL, которые являются дорогостоящими. Вы хотите держаться подальше от OR, и если вам нужно сделать какой-либо ORDER BY, вы можете сделать это на прикладном уровне, просто заполнив массив результатов, затем отсортировав массив.
Вы также можете рассмотреть возможность добавления слоя кэша, который расположен над слоем MySQL, чтобы вам не приходилось каждый раз обращаться к базе данных.
Как упомянул Керрек в своем комментарии, вы можете профилировать свое приложение, чтобы увидеть, где находятся узкие места, посмотрите XDebug (http://xdebug.org/) и KCacheGrind (http://kcachegrind.sourceforge.net/html/Home.html)
)
Несколько идей, с чего можно начать.