Предполагая, что вы не можете оптимизировать саму операцию LIKE, вы должны попытаться оптимизировать базовый запрос без минимизации количества проверяемых строк.
Некоторые вещи, которые могут быть полезны для этого:
rows
столбец в EXPLAIN SELECT ... результат. Тогда
mysql> set profiling=1;
mysql> select sql_no_cache * from mytable;
...
mysql> show profile;
+--------------------+----------+
| Status | Duration |
+--------------------+----------+
| starting | 0.000063 |
| Opening tables | 0.000009 |
| System lock | 0.000002 |
| Table lock | 0.000005 |
| init | 0.000012 |
| optimizing | 0.000002 |
| statistics | 0.000007 |
| preparing | 0.000005 |
| executing | 0.000001 |
| Sending data | 0.001309 |
| end | 0.000003 |
| query end | 0.000001 |
| freeing items | 0.000016 |
| logging slow query | 0.000001 |
| cleaning up | 0.000001 |
+--------------------+----------+
15 rows in set (0.00 sec)
Тогда
mysql> FLUSH STATUS;
mysql> select sql_no_cache * from mytable;
...
mysql> SHOW SESSION STATUS LIKE 'Select%';
+------------------------+-------+
| Variable_name | Value |
+------------------------+-------+
| Select_full_join | 0 |
| Select_full_range_join | 0 |
| Select_range | 0 |
| Select_range_check | 0 |
| Select_scan | 1 |
+------------------------+-------+
5 rows in set (0.00 sec)
И еще одно интересное значение - last_query_cost
, которое показывает, насколько дорогой оптимизатор оценил запрос (значение равно числу случайных чтений страницы):
mysql> SHOW STATUS LIKE 'last_query_cost';
+-----------------+-------------+
| Variable_name | Value |
+-----------------+-------------+
| Last_query_cost | 2635.399000 |
+-----------------+-------------+
1 row in set (0.00 sec)
Документация MySQL - ваш друг.