Just a comment here:
if user want to see middle rows they have to browse to deep page.
The question is often: why a user would need to do that.
I'm often taking the example of google... I never ever click on page 1000 to see the results on that page. Because I'm expecting the search engine to give me the most important information on page 1 or 2...
That's really something you should think about. It's not about technical details but usability. If a user has to go randomly to page 1000 to see a record, then something looks wrong to me in term of design.
I prefer adding graphical representation of aggregations where the user can visualize the distribution of the data on different fields like date, price average, ... And then be able to filter the resultset by clicking on those graphics. Faceted navigation that is.
Or help the user by sorting on different keys.
Or worse case, help the user to export all data locally where he will be able to read millions of records if he really needs to. For this, you use the Scroll API.
Just my thoughts here.