[zasdffaa]

Gotcha. It's a very different scenario from what I imagined and my suggestions don't apply. Agreed also your limited control on rewriting is limited and with the comment on clustered indexes.

I do wonder how is it possible to run that query on a billion rows and typically get sub-millisecond response, but however you did it, well done!