Paging, Performance and ADODB

I want to do paging with my VB.NET app. I have a large with table
over 5 million records. I've read numerous articles on how to page
using TOP, ROW_COUNT, etc. I've tried the examples that they have
provided. Performance is fine if you are paging the "top" part of the
data set.
However, if I want to go to the last "page" of my data set, and
traverse "backwards" though it, performance is terrible. In my tests,
I have been returning 10 records a page. When I try to traverse
backwards, the best I can get is the 10 records returning in 10+
seconds for each page.
How can I do this efficiently?
Oooops, forgot to mention the ADODB part.
I wrote some ADODB code in a test VB.NET app. I used a Recordset to
basically do the same thing that the paging was doing. The page of
results returned back in milliseconds for both the "front" and "back"
end of the data set.
How can I get this kind of performance? I don't want to use ADODB for
doing this.
|||I meant to say ROW_NUMBER and OVER rather than ROW_COUNT in my first
post. Sorry for so many posts.