Так автоинкремент, это индекс на id, если ты ищешь например по полю user_name то индексировать надо поле user_name
Погугли про индексы в таблицах mysql. Там ничего сложного нет, минут за 30 разберешься. Еще можешь почитать про EXPLAIN, это если вдруг выяснится что индексы все же есть, поможет понять что конкретно тормозит в запросе, там тоже ничего сложного нет.
Но я ставлю на то что ты ишешь по либо по неиндексируемым полям, либо по подстрокам, типо user_name LIKE '%azaza%'
Либо ты криво написал подзапросы