Избавляйся от ... where fld like '%...%' это самые плохие по скорости запросы, хотя не всегда это возможно без увеличения размера базы, вообще полнотекстовый поиск можно отдавать на откуп стороннему приложению (это может расширить возможности фильтрации), считай это еще одной формой индекса, хотя лучше данные по другому хранить. Я встречал ситуации когда в varchar хранили значения справочника из десятка значений, но делали по нему like %% что грузило базу прилично, когда как сделать простой комбобокс на порядок эффективнее и удобнее - поиск по подстроке лучше по справочнику делать на клиенте.
Без индексов скорее всего никуда, если в запросе идет фильтрация по полю, то если не создать на него индекс, этот запрос и будет создавать нагрузку
В некоторых специфических случаях, можно делать запросы заранее (для более шустрой пагинации например), запрашивая сразу несколько страниц наперед, с учетом движения вперед (и возможно назад, в общем прогноз должен предполагать что перелистывание продолжится), запрос на будущие записи делать заранее, пока пользователь смотрит текущий результат. Недостаток подхода - при удачном прогнозе действий пользователя отзывчивость интерфейса повышается, как и средняя нагрузка на базу. Так же добавляет отзывчивости если окно запроса будет больше окна отображения (т.е. для отображения 10 строк запрашиваешь 30, начиная с предыдущей страницы)
Частный случай прогноза, не делать select ... limit ... на каждую страницу, а при смене фильтра запрашивать весь диапазон, но только идентификаторы, сохранив их либо в таблице на сервере либо на бакэенде, генерирующим запросы вида select ... id in (...), последнее если количество записей не больше тысяч. Кстати именно постраничная навигация с прогруженным списком id самая шустрая
Кешируй результаты запросов, можно на клиенте, можно даже средствами браузерного кеша, очень часто работа человека состоит в перемещении туда сюда по своим запросам, так зачем нагружать лишний раз сервер тем что уже известно. Осторожно с инвалидацией данных, и кстати не всегда она так уж и критична.
Некоторые фильтрации данных возможно эффективнее делать на клиенте, как бы это странно не звучало, но клиент по скорости работы может даже превосходить сервер, так почему бы часть данных не хранить в принципе на нем и не фильтровать там же, но это зависит от особенности данных, гонять и хранить гигабайты клиенту не удобно (особенно если это браузер). Это может сильно усложнить алгоритм пагинации, но подумай, так ли человеку нужно знать какой номер строки у него сейчас, обычно достаточно понимать общий прогресс (сколько примерно до конца списка и сколько данных в принципе).
p.s. диск на сервере hdd или ssd? если не хватает денег на большой ssd, настрой маленький ssd как кеш к медленному hdd (linux bcache), даже когда данные полностью не влезают в кеш, это дает заметный прирост, потому что hdd начинает менее случайно двигаться, плюс добавляется буферизация записи (данные записываются на ssd и лежат там пока hdd не освободится), так же дает эффект ускорения записи вынос журнала файловой системы (если ext4) на ssd (требуется пара гигабайт от силы).
Осторожно, если высокие требования к надежности хранения, кеширующий ssd в режиме записи лучше пусть будет хотя бы raid1, так как иначе при смерти ssd починить данные, размазанные по диску и кешу будет очень сложно. Для кеша только для чтения это не так критично (при смерти ssd сервер просто упадет, не убивая данные).
Но мне больше нравится резервирование на лету (настроить онлайн репликацию, пусть и на слабый, бакап сервер)