Questo dovrebbe aiutarti. Riscrivi la tua domanda come segue:
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
Ora crea un indice composto sulle colonne (c4, c5, c6) con le colonne IN QUELL'ORDINE. Le colonne nel tuo indice dovrebbero apparire nello stesso ordine delle colonne nella tua clausola WHERE. Altrimenti l'indice non funzionerà. La selettività di questo indice è sufficientemente ristretta da rendere veloce un filesort sulla tabella temporanea (per il raggruppamento).
Il motivo per spostare c3 alla fine della query è il seguente. Ad esempio, assumiamo che c3 possa assumere valori compresi tra 0 e 100 (oppure può essere NULL). Se esegui una query "IS NOT NULL", Mysql deve attraversare quasi tutto l'indice B-Tree ad eccezione dei bordi che corrispondono a NULL. Pertanto, MySQL decide che una scansione completa della tabella è un'opzione più semplice che percorrere tutti i diversi percorsi nell'indice. D'altra parte, vedrai che se la tua query era "IS NULL" e il tuo indice era (c3, c4, c5, c6), Mysql utilizzerà infatti questo indice. Questo perché in questo caso Mysql deve attraversare solo la parte dell'albero dell'indice corrispondente al valore NULL.
Il tipo di indici di cui MySQL ha bisogno dipende molto dalla query in questione. Creare indici su tutte le colonne, come suggerito da @louis, NON è una buona idea!