Вы не поверите, но mysql умеет и кэширует запросы. Но в вашем случае либо проблема в таблице (индексы), либо в данных (если там text то прощай индексация). В любом случае прочитайте explain и если там нет проблем или вас ничего не смутило - кэшируйте результаты в memcached, например, самостоятельно