Indexando tablas en MySQL

[Ronruby]

Saludos,

Mi duda es la siguiente:
Cree una tabla con 8,657,154 registros para practicar como optimizar las tablas.
La tabla que contiene los registros, tiene los campos: idorders, fecha, customerid, productid, amount
(Solamente la cree para probar, en cuanto a diseño se que hay cositas que deben cambiar)
Ahora bien, hago la siguiente consulta SIN INDICES:

Código MySQL:

SELECT
        COUNT(orders.idorders) AS numero
    FROM
        orders
    WHERE
        orders.fecha > '2011-05-01'
    AND
        orders.productid = 1
    ;
 

Y toma alrededor de 1 - 2 segundos. Ahora bien, cree 2 INDICES. Uno para la fecha y otro para el productid pero al correr la MISMA consulta toma de 8 - 10 segundos.

¿Que estoy haciendo mal o que esta pasando?

Nota: Sin embargo al poner EXPLAIN al principio de la consulta claramente se puede ver que usando indices busca en la mínima cantidad de filas que cumplen con el criterio (1,435,812) y que realmente si esta optimizada la consulta. Sin los indices tiene que recorrer los 8,657,154 registros