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?

Practice

1.

What does the from parameter control in an Elasticsearch query?

easy

A. The total number of results to return

B. The starting index of the search results to return

C. The sorting order of the results

D. The fields to include in the results

Solution

1. Step 1: Understand the role of from

   The from parameter sets the offset, meaning it tells Elasticsearch where to start returning results from.

2. Step 2: Differentiate from size

   The size parameter controls how many results to return, not the starting point.

3. Final Answer:

   The starting index of the search results to return -> Option B

4. Quick Check:

   from = start index [OK]

Hint: Remember: from = start index, size = count [OK]

Common Mistakes:

• Confusing from with size
• Thinking from controls sorting
• Assuming from limits total results

2.

Which of the following is the correct way to request the second page of results with 10 items per page using from and size?

{ "from": ?, "size": 10 }

easy

A. 10

B. 1

C. 11

D. 20

Solution

1. Step 1: Calculate the starting index for page 2

   Page 1 has items 0-9, so page 2 starts at index 10 (10 items per page).

2. Step 2: Set from to 10 and size to 10

   This returns items 10 to 19, which is the second page.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Page 2 start = (2-1)*10 = 10 [OK]

Hint: from = (page_number - 1) * size [OK]

Common Mistakes:

• Using 1 instead of 10 for from
• Using 11 which skips one item
• Using 20 which is page 3 start

3.

Given this Elasticsearch query snippet, what range of results will be returned?

{ "from": 5, "size": 3 }

medium

A. Results 3 to 5

B. Results 0 to 3

C. Results 5 to 7

D. Results 6 to 8

Solution

1. Step 1: Identify the starting index

   The from value is 5, so results start from index 5.

2. Step 2: Calculate the ending index

   With size 3, results include indexes 5, 6, and 7.

3. Final Answer:

   Results 5 to 7 -> Option C

4. Quick Check:

   from=5, size=3 -> 5,6,7 [OK]

Hint: from + size - 1 = last result index [OK]

Common Mistakes:

• Assuming from is count, not start
• Off-by-one errors in range
• Mixing up start and end indexes

4.

Identify the error in this Elasticsearch pagination query:

{ "from": -5, "size": 10 }

medium

A. "from" must be zero or positive, but negative is allowed

B. "size" must be less than 10

C. No error, this query is valid

D. "from" cannot be negative

Solution

1. Step 1: Check the value of from

   The from parameter must be zero or positive; negative values are invalid.

2. Step 2: Validate size value

   The size value 10 is valid and does not cause error.

3. Final Answer:

   "from" cannot be negative -> Option D

4. Quick Check:

   Negative from is invalid [OK]

Hint: from must be ≥ 0, negative causes error [OK]

Common Mistakes:

• Allowing negative from values
• Confusing size limits
• Ignoring validation rules

5.

You want to display search results page by page with 15 results each. If the user requests page 4, what should the from and size values be to get the correct results?

hard

A. { "from": 45, "size": 15 }

B. { "from": 60, "size": 15 }

C. { "from": 30, "size": 15 }

D. { "from": 15, "size": 4 }

Solution

1. Step 1: Calculate the starting index for page 4

   Using the formula from = (page_number - 1) * size, we get (4 - 1) * 15 = 45.

2. Step 2: Set the size to 15

   Since each page shows 15 results, size remains 15.

3. Final Answer:

   { "from": 45, "size": 15 } -> Option A

4. Quick Check:

   from = 45, size = 15 for page 4 [OK]

Hint: Use from = (page-1)*size for correct pagination [OK]

Common Mistakes:

• Using from = page * size
• Swapping from and size values
• Setting size to page number