Hola,
yo trabajo con postgres, pero he tenido el mismo problema en algunos sistemas. La consulta al motor de base de datos la mejore MUCHISIMO creando un indice sobre el campo que tenia en el WHERE.
Ej. tengo un sistema de estadisticas con una tabla con 6 millones de registros. Una consulta me tardaba en devolver el resultado 45 segundos, después del indice me tardaba aproximadamente entre 5 y 10 segundos.
Tratando de resolver el problema, me di cuenta que perdía muchisimo mas tiempo trabajando los cursores una vez traidos, que si lo podía resolver en la consulta al motor de bases de datos.
Esta es mi experiencia, espero te de un puntapie para lograr resolver el problema.
Saludos
PD: casi todos los motores tienen algun comando o alguna utilidad para medir las consultas, como ser la cantidad de registros que tuvo que leer para lograr el resultado, y de esa forma darte cuenta si tenes que crear un indice, ojo con irte de mambo con los indices, a la larga y si es muy grande la tabla te lentifica los procesos de insert y delete demasiados indices.