MySQL query sometimes runs slow, sometimes fast

Try using MySql Table Partitioning features.