Isso deve ajudá-lo. Reescreva sua consulta da seguinte forma:
SELECT c1, Sum(c2)
FROM table
WHERE c4 = 2011
AND c5 = 0
AND c6 In (6,9,11)
AND c3 IS NOT NULL
GROUP BY c1
Agora crie um índice composto nas colunas (c4, c5, c6) com as colunas NESTA ORDEM. As colunas em seu índice devem aparecer na mesma ordem que as colunas em sua cláusula WHERE. Caso contrário, o índice não funcionará. A seletividade desse índice é estreita o suficiente para que uma classificação de arquivos na tabela temporária (para o grupo por) seja rápida.
A razão para mover c3 para o final da consulta é a seguinte. Como exemplo, vamos supor que c3 pode assumir valores entre 0 e 100 (ou pode ser NULL). Se você executar uma consulta "IS NOT NULL", o Mysql precisará percorrer quase todo o índice B-Tree, exceto as arestas que correspondem a NULL. Portanto, o MySQL decide que uma varredura completa da tabela é uma opção mais fácil do que percorrer todos os diferentes caminhos no índice. Por outro lado, você verá que se sua consulta for "IS NULL" e seu índice for (c3, c4, c5, c6), o Mysql usará esse índice de fato. Isto porque neste caso o Mysql só precisa percorrer a parte da árvore de índice correspondente ao valor NULL.
O tipo de índices que o MySQL precisa depende muito da consulta em questão. Criar índices em todas as colunas, como @louis sugeriu, NÃO é uma boa ideia!
