Вам поможет такое эмпирическое правило - увеличение размеры таблицы в 10 раз замедляет поиск по индексу не более, чем вдвое. Увеличение таблицы в 100 раз уменьшает поиск не более, чем в 4 раза.
На самом деле это абсолютно неточно, мы не учитываем размещения промежуточных результатов разных соединений на диске и так далее. Но главное - тут становится очевидным, что партиционирование таблицы вам скорее во вред, чем на пользу.
Что я вам рекомендовал бы - просто вычитать EXPLAIN.
Далее просто сменить MySQL на Postgres.
И только после этого заниматься denormalization, NoSQL etc.
