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?"

Practice

1. What is the main purpose of using search_after in Elasticsearch pagination?

easy

A. To filter documents based on a query

B. To sort documents alphabetically by default

C. To efficiently paginate through large result sets without performance loss

D. To update documents in bulk

Solution

1. Step 1: Understand pagination challenges

   Deep pagination with large result sets can be slow and inefficient using traditional methods like from and size.

2. Step 2: Role of search_after

   search_after uses the last sort values from the previous page to fetch the next page efficiently, avoiding performance issues.

3. Final Answer:

   To efficiently paginate through large result sets without performance loss -> Option C

4. Quick Check:

   Purpose of search_after = Efficient pagination [OK]

Hint: Remember: search_after uses last sort values for fast paging [OK]

Common Mistakes:

• Confusing search_after with filtering
• Thinking search_after sorts results automatically
• Using search_after without sorting

2. Which of the following is the correct syntax snippet to use search_after in an Elasticsearch query?

easy

A. "search_after": ["last_sort_value"]

B. "search_after": "last_sort_value"

C. "search_after": {"value": "last_sort_value"}

D. "search_after": true

Solution

1. Step 1: Check the expected data type for search_after

   The search_after parameter expects an array of sort values, not a single string or object.

2. Step 2: Match syntax with correct format

   "search_after": ["last_sort_value"] correctly shows search_after as an array with the last sort value inside.

3. Final Answer:

   "search_after": ["last_sort_value"] -> Option A

4. Quick Check:

   search_after syntax = array of values [OK]

Hint: search_after always takes an array of sort values [OK]

Common Mistakes:

• Passing a single string instead of an array
• Using an object instead of an array
• Setting search_after to a boolean

3. Given this Elasticsearch query snippet, what will be the effect of adding "search_after": [1627891234567]?

{
  "size": 5,
  "sort": [{"timestamp": "asc"}],
  "search_after": [1627891234567]
}

medium

A. It causes a syntax error because search_after is not allowed here

B. It returns the first 5 documents sorted by timestamp ascending

C. It returns 5 documents with timestamp less than or equal to 1627891234567

D. It returns 5 documents with timestamp strictly greater than 1627891234567

Solution

1. Step 1: Understand sorting and search_after usage

   The query sorts documents by timestamp ascending and uses search_after with a timestamp value.

2. Step 2: Effect of search_after value

   search_after tells Elasticsearch to return documents after the given sort value, so only documents with timestamp greater than 1627891234567 are returned.

3. Final Answer:

   It returns 5 documents with timestamp strictly greater than 1627891234567 -> Option D

4. Quick Check:

   search_after filters results after given sort value [OK]

Hint: search_after returns results after the given sort values [OK]

Common Mistakes:

• Thinking it returns documents before the value
• Assuming it returns the first page always
• Confusing search_after with from/size pagination

4. You wrote this Elasticsearch query to paginate results:

{
  "size": 10,
  "sort": [{"date": "desc"}],
  "search_after": "2023-01-01T00:00:00"
}

But it returns an error. What is the likely cause?

medium

A. size cannot be 10 with search_after

B. search_after value must be an array, not a string

C. sort order must be ascending for search_after

D. date field cannot be used in sort

Solution

1. Step 1: Check the type of search_after value

   The search_after parameter requires an array of values, but here it is a string.

2. Step 2: Identify the error cause

   Passing a string instead of an array causes a syntax error in the query.

3. Final Answer:

   search_after value must be an array, not a string -> Option B

4. Quick Check:

   search_after requires array input [OK]

Hint: Always wrap search_after values in an array [OK]

Common Mistakes:

• Passing single value without array brackets
• Using unsupported sort order
• Misunderstanding size limits with search_after

5. You want to paginate through a large dataset sorted by user_id (ascending) and then timestamp (descending). Which search_after value correctly fetches the next page after user_id=42 and timestamp=1680000000?

hard

A. [42, 1680000000]

B. [42, -1680000000]

C. [1680000000, 42]

D. ["42", "1680000000"]

Solution

1. Step 1: Understand sort order and search_after values

   The sort is by user_id ascending, then timestamp descending. The search_after array must match this order.

2. Step 2: Match values to sort order

   The correct search_after is an array with user_id first, then timestamp. Since timestamp is descending, the value is used as is (no negation).

3. Final Answer:

   [42, 1680000000] -> Option A

4. Quick Check:

   search_after array matches sort fields order [OK]

Hint: search_after array order matches sort fields order exactly [OK]

Common Mistakes:

• Reversing order of values in search_after
• Negating timestamp for descending sort
• Using strings instead of numbers without need