Здравые размышления приводят к выводу - нужно табличку поделить, чтобы индексы стали поменьше и помещались в память без проблем. В тоже время шардить табличку не хочется, периодически она нужна целиком. Ну и расширяться пока возможностей нет.
Вариантом временного решения может стать VIEW. Мы разделим таблицу на несколько поменьше, которые будут содержать данные в некоторых заранее известных границах. Создадим VIEW, в котором укажем на эти пределы:
CREATE VIEW table AS
SELECT * FROM table1 WHERE created_at BETWEEN '2014-02-01 00:00:00.000' AND '2014-03-01 00:00:00.000'
UNION ALL
SELECT * FROM table2 WHERE created_at BETWEEN '2014-03-01 00:00:00.000' AND '2014-04-01 00:00:00.000'
Фокус в том, что если запросить данные с указанием условия, присутствующего во VIEW, таблица, не удовлетворяющая этому условию затронута не будет вовсе. Например:
SELECT * FROM table WHERE created_at > '2014-03-01 00:00:00.000'
заденет только вторую таблицу, соответственно поднимет только ее индекс. Как-то так.