Manual de Referência do MySQL :: A.6.1 Camo evitar o varredura da tabela,,,

EXPLAIN mostrará ALL na coluna type quando o MySQL usa uma busca na tabela para resolver uma consulta. Isto acontece normalmente quando:

A tabela é tão pequena que é mais rápido fazer uma varredura na tabela que uma busca nas chaves. Isto é um caso comum para tabelas com menos de 10 linhas e um tamanho de linha pequeno.
Não há nenhum restrição utilizável na cláusula ON ou WHERE para colunas indexadas.
Você está comparando colunas indexadas com constantes e o MySQL calculou (baseado na árvore de índices) que a constante cobre uma parte muito grande da tabela e uma busca na tabela seria mais rápido.. See Secção 5.2.4, “Como o MySQL Otimiza Cláusulas WHERE”.
Você está usando uma chave com baixa cardinalidade (= muitos registros coincidentes) através de outra coluna. O MySQL assumirá neste caso que usar a chave fará muitas pesquisas de chave e neste caso a varredura da tabela seria mais rápido.

O que você pode fazer para evita uma busca 'errada' em tabelas grandes é:

Use ANALYZE TABLE para a tabela em quastão atualizar a distribuição das chaves.. See Secção 4.6.2, “Sintaxe de ANALYZE TABLE”.
Use FORCE INDEX para a tabela em questão para dizer ao MySQL que uma busca na tabela é muito cara comparado com usar um dos índices dados. See Secção 6.4.1, “Sintaxe SELECT”.
```
SELECT * FROM t1,t2 force index(index_for_column) WHERE t1.column=t2.column;
```
Inicie o mysqld com --max-seeks-for-key=1000 ou faça SET MAX_SEEKS_FOR_KEY=1000 para dizer ao otimizador que nenhuma busca de chave fará mais que 1000 pesquisas nas chaves.