При запросе к базе данных всё тормазит

Добрый день. У меня такой вопрос. Если например есть таблица в базе данных (пользователи) в которой больше чем пол ляма записей (тоесть больше чем пол миллиона зарегестрированых пользователей). И есть админка, в которой каждого пользователя можно редактировать. Чтобы вывести ссыкли на пользователей в админке делаются такие запросы SELECT * FROM users WHERE <условия фильтра (например нужный ник юзера)> LIMIT 0, 15; При этом когда мы делаем такой запрос у всех пользователей всё начинает тормазить. Есть ли какие соображения почему всё так, и как можно это исправить?

-----
Таран - оружие героев!

1) Если Вы указываете ник юзера (а он теоретически должен быть уникальным), то лимит ставить не нужно.
2) Запрос SELECT сам по себе работает очень быстро с условием WHERE даже в таблицах с миллионом записей.
3) Проставьте индексы в таблице по всем главным полям, которые участвуют в условиях выборки. Например на поля id, login, status. Индексы должны быть обязательны для таких таблиц.
4) Для крупных проектов нужно и ресурсов побольше. Чем пользуетесь Вы?

-----
____________________________________________________________________
Ну как то так, наверное.
http://grefon[dot]com

Думаю дело в индексах, точнее в их отсутствии.
Вот спробовал - 122 тыс записей, нужные индексы, select * from thistable where = ... возвращает 18 записей (но то не суть), время выборки 0,090 сек.
MySQL-5.0.1, MyISAM, CPU: Turion-x2 1900 MHz

С уважением.
P.S. Да, кстати, <условие фильтра> тоже важно для работы индексов.