В MySQL простые запросы стали выполняться неоправданно долго?
После миллиона записей MySQL начинает тупить со всем, что сложнее чем выборка по ключу. Действительно ли Вам тут нужен джойн? Я понимаю что он не сложный, но 3 селект запроса по ключу сработают быстрее чем джойн + гораздо больше шансов вытащить значения из кеша.

Еще у меня большое подозрения на блокировки, посмотрите в логах не ждут ли запросы большую часть времени права на лок таблицы.
Наблюдайте за глабальными status параметрами и разбирайтесь что там не так. Есть скрипты, помогающие в этом — mysqlreport и tuning-primer.sh — легко гугляться.

Обычно замедляют MyISAM блокировки и temp disk tables, может быть мало места под индексы и прочее, могут быть лимиты по файловым дескрипторам. 

Если не владеете темой — запустите упомянутые скрипты и внимательно разбирайтесь с тем что они скажут. Потом, если с памятью нет проблем, можно существенно увеличить возможные узкие места, если есть — ужать те что не используются… в общем это непростой итеративный процесс оптимизации :)