несколько моментов: - это было давно и использовались достаточно старые версии MySQL - там требовался LIKE (это важно) и искалось введённое пользователем (т.е. попаданий в MySQL кэш было мало, в вашем случае возможно почти все SELECT COUNT(*) будут кешироваться сервером) - записей в основной таблице было 300 000 (по которым делался LIKE)
=> в вашем случае я попробовал бы для начала два запроса
