Query demorada demais

Meu problema é o seguinte, eu gostaria de saber se seria possível optimizar a consulta que estou fazendo. Ela faz o cross (com INNER JOIN) de 3 tabelas diferentes, e todas elas são muito grandes...

Segue o código SQL

 SELECT
 A.Gols as Gols,
 A.idAtleta,
 A.Sexo,
 A.idRosto,
 R.Cabelo,
 R.Olhos,
 R.Sombrancelha,
 R.Boca,
 R.Orelha,
 R.Nariz,
 R.Cor,
 A.Nome,
 A.Nivel,
 A.Concentracao,
 A.Chute,
 A.Ataque,
 A.Velocidade,
 A.Tecnica,
 A.Resistencia,
 A.Defesa,
 Eq.Nome as Equipe
 FROM Atleta A
 INNER JOIN Equipe Eq ON Eq.idEquipe = A.idEquipe
 INNER JOIN Rosto R ON R.idRosto = A.idRosto
 WHERE A.Gols > 0 AND A.Nome LIKE "%%" AND A.Sexo LIKE "M"
 ORDER BY A.Gols DESC, A.Nivel DESC, A.Nome DESC
 LIMIT 0, 15;

Acontece que a tabela Atleta possui 440.000 ocorrências, a tabela Rosto possui 35.000 ocorrências e a tabela Equipe possui 10.000 ocorrências.

Pensei em gravar estes dados em uma outra tabela e executar apenas o SELECT dessa nova tabela, mas mesmo assim demora muito pois são muitas informações... Se tivesse como INDEXAR esta tabela para a busca retornar os resultados mais rápidos, por mais que eles retornassem desatualizados, já seria de muita ajuda.

Qualquer solução serve, dicas, referências, puxões de orelha, links e artigos são muito bem vindos!

Obrigado desde já pela atenção!!