Вопрос:
Что такое в профилировании "statistics" и как лечить если большое?

Большая, тяжелая таблица которая не влезает в память.
Читаем в ней конкретный PK 1шт.
explain SELECT SQL_NO_CACHE test_id FROM test WHERE test_id=6337999
Первый запуск время выполнения 0.01 сек.
Следующие запуски 0.0001 сек.

Профилирование показывает, что в первом запуске 99% времени уходит на "statistics"
Explain показывает, что используется PK (разумеется)

Подробности:
Виртуальная машина, обычный HDD, mysql 5.5.27, объем ОЗУ 3.5 Гб
Тестовая таблица, innodb, несколько полей int, varchar, text со случайными данными.
13 000 000 строк, объем 5.5 Гб
Есть primary key - test_id (int, 4 байта)
Есть еще ключи, все вместе весят 300мб.

Игрался с размером кеша ключей, не помогает.
Создал аналог таблицы в myisam - эффект такой же.