Pagination (from/size) in Elasticsearch - Time & Space Complexity

Time Complexity: Pagination (from/size)

O(from + size)

Understanding Time Complexity

When using pagination with from and size in Elasticsearch, we want to know how the time to get results changes as we ask for later pages.

We ask: How does the search time grow when we skip more results?

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch pagination query.

GET /my_index/_search
{
  "from": 1000,
  "size": 10,
  "query": {
    "match_all": {}
  }
}
    

This query skips the first 1000 results and returns the next 10 matching documents.

Identify Repeating Operations

Look at what Elasticsearch does internally to get the results.

• Primary operation: It scans through documents to skip the first from results.
• How many times: It processes roughly from + size documents to return the page.

How Execution Grows With Input

As from grows, Elasticsearch must skip more documents before returning results.

Input Size (from)	Approx. Operations
10	About 20 documents processed (10 skipped + 10 returned)
100	About 110 documents processed
1000	About 1010 documents processed

Pattern observation: The work grows roughly linearly as from increases.

Final Time Complexity

Time Complexity: O(from + size)

This means the time to get a page grows roughly with how many results you skip plus how many you want to see.

Common Mistake

[X] Wrong: "Pagination time stays the same no matter how far we go in the results."

[OK] Correct: Elasticsearch must still scan and skip all earlier results, so more skipping means more work and longer time.

Interview Connect

Understanding how pagination affects search time helps you design better queries and explain performance in real projects.

Self-Check

What if we replaced from with a search_after parameter? How would the time complexity change?