первое: WHERE `title` LIKE '%".$query."%' - уберите полный вайлдкард, LIKE '".$query."%'будет работать быстрее и использовать индекс, в отличие от первого варианта. У вас же не нужно выбирать "Калининград" по "град".
Второе - индексы подлиннее на текстовые поля, там где помещается в варчар - делайте варчар с индексом. Тогда скорее всего кеш не понадобится.
