Индексы само собой.
Юзните сами.
Создайте большую таблицу 100000 записей.
Далее
CREATE TEMPORARY TABLE tmp_table SELECT..... WHERE col2 LIKE \'sdgsd\'
И SELECT * FROM tmp_table ORDER BY col
Или
SELECT..... WHERE col2 LIKE \'sdgsd\' ORDER BY col
И скажите о своих находках....