Why is the result on later pages slow

Let's imagine that we have an index with several millions of documents. We already know how to build our query, when to use filters, and so on. But looking at query logs, we see that particular kinds of queries are significantly slower than the other ones. These queries may be using paging. The from parameter indicates that the offsets have large values. From the application side, this can mean that users go through an enormous number of results. Often this doesn't make sense—if a user doesn't find desirable results on first few pages, he/she gives up. Because this particular activity can mean something bad (possible data theft), many applications limit paging to dozens of pages. In our case, we assume that this is a different scenario and we have to provide this functionality.

What is the problem?

When ElasticSearch generates a response, it must determine the order of documents forming the result. If we are on the first page, this is not a big problem...