Покажи стуктуру таблицы с таким количеством записей( desc <table name>), далее покажи индексы, которые в ней есть и покажи наиболее часто исполняемые запросы к ней.
1. Структура таблицы? Индексы? (show create table table_name)
2. Топ твоих запросы к ней?
3. QPS? (queries per second) - утилитка mytop покажет
4. Статус мускуля? (show global status)
5. В конце концов, OS? На фре при некоторых определенных условиях наблюдаются генетические глюки с мускулем.
Имея эту инфу можно делать какие то выводы. Скорей всего просто неправильно индексы стоят.
