deep paging is slow

Hi,

I don't know if this is the right place for this, but generally, this is a design of Lucene.

I have ~ 3M documents index, while trying to paginate and sort to page ~25K, the query takes about 3-4 seconds.
this is because the index can't skip the first 1M records, and need to do a full scan and sort all the items.

the issue is happening when nothing is filtered, hence the collection is very big.
Now, you would ask who will want page 25K - and the answer is: search engines. they don't care about filtering.
and they do this on parallel and this causes very high CPU usage.

yes, I know there is SearchAfter, but I don't have the last document from previous page.
yes, I know that I can use collector (which is a bit faster and uses only priority queue), but then the items won't be sorted.

currently, I solved this by holding an array with the relevant sorted docIds, then I can only slice the range that I need. O(1) because it's already sorted.

the downside is, of course, the need to maintain this to be consistent.
I wonder if there is a better way to do faster deep paging.

Start by reviewing Lucene.NET's paging and sorting entry points, then compare the issue's SearchAfter and collector options with the reported deep-page workload. The issue does not name files or tests, and completion criteria for a better approach are not defined; confirm the intended design and measurable performance target before implementation.

Written by the indexing model from the issue text.