torsten

как много процессов у mysql?
что показывает «vmstat 1» во время тормозов и во время нормальной работы? сравните context switching.

партиционировать таблицу по полю score
тогда COUNT(*) FROM table WHERE score<? будет выполняться с использованием primary key на каждой из партиций, что должно работать очень быстро
)