Me fije en el plan de ejecución y tal cual, el índice no funcionaba.
Logré solucionarlo aplicando las siguientes modificaciones:
- Aplicando el índice tal cual me lo sugería el plan de ejecución
- Cambiando Between por =
- Utilizando CONVERT(DATE, @Fecha) y CONVERT(DATE, columnaFecha) en lugar de lo que hacía antes
Llego a la conclusión que Between demora mucho más que EQUAL.
Para el mismo rango Desde Hasta utilizar Between la consulta demora muchisimo más que hacerlo igualando.
Para el caso en cuestión, al ser un job que se ejecuta a diario ambas formas son válidas.
Gracias Libras me sirvió de mucho tu ayuda.