Для просмотра, что можно оптимизировать подойдет следующий sql запрос:
SELECT *
FROM `table_name`
PROCEDURE ANALYSE ( )

Оценка производительности отдельного запроса происходит так:
EXPLAIN EXTENDED {ВАШ_ЗАПРОС}

Периодически нужно делать :
OPTIMIZE TABLE `table_name`
, что позволяет упорядочить данные если было удалено много записей.

При оптимизации важно измерять время без кэширование запросов. Данного можно добиться следующей конструкцией:
SELECT SQL_NO_CACHE *
FROM `table_name`