ты ещё посмотри какой тип таблицы на которой долго работает select
innodb или myisam
и какой тип у той тестовой таблицы которую ты создавал и на которой у тебя быстро запрос отработал.
может дело всё таки в mysql, а не в самих таблицах.

а ты просто сам руками создай новую базу и в ней новую таблицу с двумя полями и одним индексом
потом попробуй вытащить чтото из этой таблицы SELECT * FROM новаятаблица WHERE первоеполе = 'чемуто'
и посмотри как всё это выполнится. Если будет долго, значит проблемма с самим mysql, если нет.
Значит нужно лечить таблицы в твоей базе, возможно пересоздавать индексы.