Для кэширования можно использовать memcache.
Т.е. проверяем есть ли подстрока поиска в базе, например "мос", если нет то делаем select `id`,`name` where `name` like 'мос%', делаем объединение всех id в строку с разделителем запятая, например "1,2,5,18,10", записываем в memcache ["мос"] = "1,2,5,18,10"
и потом при следующем запросе подстроки начинающейся с "мос" берем эту запись и запрос будет уже select `id`,`name` where `id` in ("1,2,5,18,10") and `name` like 'моск%' т.е. запрос будет уже по двум индексам идти, что значительно быстрее.
Т.е. проверяем есть ли подстрока поиска в базе, например "мос", если нет то делаем select `id`,`name` where `name` like 'мос%', делаем объединение всех id в строку с разделителем запятая, например "1,2,5,18,10", записываем в memcache ["мос"] = "1,2,5,18,10"
и потом при следующем запросе подстроки начинающейся с "мос" берем эту запись и запрос будет уже select `id`,`name` where `id` in ("1,2,5,18,10") and `name` like 'моск%' т.е. запрос будет уже по двум индексам идти, что значительно быстрее.