Search after for efficient pagination in Elasticsearch - Time & Space Complexity

Time Complexity: Search after for efficient pagination

O(n)

Understanding Time Complexity

When using Elasticsearch to get many pages of results, how fast the search runs matters a lot.

We want to know how the time to get results changes as we ask for more pages using the search after method.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /my-index/_search
{
  "size": 10,
  "query": { "match_all": {} },
  "sort": [ { "timestamp": "asc" }, { "_id": "asc" } ],
  "search_after": ["2023-01-01T00:00:00", "abc123"]
}
    

This query fetches 10 results after a given sort position, using search after for pagination.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Elasticsearch scans documents sorted by the given fields to find the next page.
• How many times: For each page requested, it performs a search starting after the last result of the previous page.

How Execution Grows With Input

As you request more pages, the search after method does not re-scan all previous results but continues from the last position.

Input Size (pages)	Approx. Operations
10	About 10 times the cost of one page scan
100	About 100 times the cost of one page scan
1000	About 1000 times the cost of one page scan

Pattern observation: The cost grows linearly with the number of pages requested.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows directly in proportion to how many pages you fetch.

Common Mistake

[X] Wrong: "Using search after means the query time stays the same no matter how many pages I fetch."

[OK] Correct: Each new page requires a new search starting after the last result, so the total time adds up with more pages.

Interview Connect

Understanding how search after scales helps you explain efficient pagination in Elasticsearch, a useful skill for real projects and interviews.

Self-Check

"What if we replaced search after with from and size for pagination? How would the time complexity change?"