Der Index wird ignoriert, wenn die Where-Klauses das Feld des Index nicht verwendet.

Ggf. kannst du noch einen Trick anwenden:

select count(*) over() Anzahl
,a.*
from MyTable a
where ....

Der Count liefert dir bei jedem Satz die Anzahl des Ergebnisses, dafür muss eher ein Tablescan durchgeführt werden, bevor der OrderBy angewendet werden kann.
Diese sog. Window-Funktionen sind besonders gut optimiert.