Time Complexity: Scroll API for deep pagination
O(n)
0
0
Scroll API for deep pagination in Elasticsearch - Time & Space Complexity
Understanding Time Complexity
When using Elasticsearch's Scroll API, we want to understand how the time to get results changes as we ask for more data.
We ask: How does the work grow when we scroll through many pages of results?
Scenario Under Consideration
Analyze the time complexity of the following Scroll API usage.
POST /my_index/_search?scroll=1m
{
"size": 100,
"query": { "match_all": {} }
}
POST /_search/scroll
{
"scroll": "1m",
"scroll_id": "DXF1ZXJ5QW5kRmV0Y2gBAAAAAAA..."
}
This code first requests the first 100 results and then uses the scroll ID to fetch the next batches of results repeatedly.
Identify Repeating Operations
Look at what repeats when scrolling through results.
- Primary operation: Each scroll request fetches a batch of results from the server.
- How many times: The scroll request repeats once per batch until all results are retrieved.
How Execution Grows With Input
As you ask for more results, the number of scroll requests grows roughly in proportion to the total results divided by batch size.
| Input Size (total results) | Approx. Operations (scroll requests) |
|---|---|
| 10 | 1 (one batch) |
| 100 | 1 (one batch) |
| 1000 | 10 (ten batches) |
Pattern observation: The number of operations grows linearly with the total number of results requested.
Final Time Complexity
Time Complexity: O(n)
This means the time to get all results grows directly in proportion to how many results you want.
Common Mistake
[X] Wrong: "Scrolling through results is a single fast operation regardless of result size."
[OK] Correct: Each scroll request fetches a batch, so more results mean more requests and more time.
Interview Connect
Understanding how scrolling scales helps you explain how to handle large data sets efficiently in real projects.
Self-Check
What if we increased the batch size in each scroll request? How would the time complexity change?