Долго выполняется запрос (Как ускорить?)

Здравствуйте.
Есть таблица, куда постоянно добавляются новые записи, удаляются записи от туда крайне редко, и единицы. Пока записей было не много, запрос выполнялся быстро, как количество записей переводило за 10000 так начались жуткие тормоза. Запрос может выполнятся около 10 секунд. Очищать таблицу ни в коем случае нельзя, но и с тормозами жить не вариант. Как можно ускорить выполнение запрос?

Индексы имеются для столбцов? Если их нет, установите индексы и будет вам счастье.

Скорпион, где и как можно установить индексы?

Зайдите в phpMyAdmin, откройте таблицу, где необходимо добавить индексы столбцам. Перейдите на вкладку "Структура", с правой стороны, на против названия полей, наведите курсор на "Ещё" и в появившемся меню выберите "Индекс":