1000000 / (60*60*24) = 11.5 запроса в секунду. Вам уже не хватает скорости или Вы на будущее? Если на будущее - зря, преждевременная оптимизация почти всегда плохо. Проблемы нужно решать по мере поступления.
Андрей Мохов посоветовал перевести на InnoDB - по моему зря, если у Вас нет запросов на вставку и обновления и Вам не нужны транзакции, то лучше оставить MyISAM - он быстрее, но менее надежен, так что где-то должен всегда лежать свежий бэкап.