Eu me deparei com o mesmo problema recentemente:o MySQL começou a engasgar (preso no estado 'estatísticas') em consultas com muitas tabelas unidas. Encontrei uma boa postagem de blog explicando por que isso acontece e como resolvê-lo.

Basicamente, pelo menos no MySQL 5.5, o valor padrão para o parâmetro de configuração optimizer_search_depth é 62, o que fará com que o otimizador de consulta demore exponencialmente mais tempo à medida que o número de tabelas na consulta aumenta. Depois de um certo ponto, começará a levar dias ou até mais para concluir a consulta.

No entanto, se você definir o optimizer_search_depth para 0 em seu my.cnf , o MySQL escolhe automaticamente a profundidade adequada, mas a limita a 7, o que ainda não é muito complexo.

Aparentemente, esse problema foi corrigido no MySQL 5.6, mas ainda não testei.