Async search for expensive queries in Elasticsearch - Time & Space Complexity

Time Complexity: Async search for expensive queries

O(n)

Understanding Time Complexity

When running expensive searches in Elasticsearch, it is important to understand how the time to get results grows as the data or query size increases.

We want to know how the cost of running an asynchronous search changes with bigger or more complex queries.

Scenario Under Consideration

Analyze the time complexity of the following async search request.

POST /_async_search
{
  "query": {
    "bool": {
      "must": [
        { "match": { "field1": "value1" } },
        { "range": { "field2": { "gte": 10, "lte": 100 } } }
      ]
    }
  }
}
    

This code starts an asynchronous search that runs a complex query combining text match and numeric range filters.

Identify Repeating Operations

Look for parts that repeat work as input grows.

• Primary operation: Elasticsearch scans matching documents to check query conditions.
• How many times: It processes each document that matches filters, which depends on data size and query selectivity.

How Execution Grows With Input

As the number of documents or query complexity grows, the search takes longer.

Input Size (n)	Approx. Operations
10	About 10 document checks
100	About 100 document checks
1000	About 1000 document checks

Pattern observation: The work grows roughly in direct proportion to the number of documents checked.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the async search grows linearly with the number of documents it needs to examine.

Common Mistake

[X] Wrong: "Async search makes the query run instantly regardless of data size."

[OK] Correct: Async search runs the query in the background but still processes documents one by one, so bigger data means longer time.

Interview Connect

Understanding how async search scales helps you explain how to handle large data queries efficiently in real projects.

Self-Check

"What if we added more filters to the query? How would the time complexity change?"

Practice

1. What is the main benefit of using async search in Elasticsearch for expensive queries?

easy

A. It caches all query results permanently.

B. It automatically speeds up the query execution time.

C. It disables query logging to improve performance.

D. It allows running slow queries without blocking the application.

Solution

1. Step 1: Understand async search purpose

   Async search lets you run slow or heavy queries without making your app wait or freeze.

2. Step 2: Identify the main benefit

   This means your app can continue working while the query runs in the background.

3. Final Answer:

   It allows running slow queries without blocking the application. -> Option D

4. Quick Check:

   Async search = non-blocking query execution [OK]

Hint: Async search runs queries in background, so app doesn't wait [OK]

Common Mistakes:

• Thinking async search speeds up queries automatically
• Assuming async search caches results permanently
• Believing async search disables logging

2. Which of the following is the correct way to start an async search request in Elasticsearch using the REST API?

easy

A. POST /_async_search
{
"query": { "match_all": {} }
}

B. GET /_async_search
{
"query": { "match_all": {} }
}

C. POST /_search/async
{
"query": { "match_all": {} }
}

D. PUT /_async_search
{
"query": { "match_all": {} }
}

Solution

1. Step 1: Recall async search API endpoint

   The correct endpoint to start an async search is POST /_async_search with the query in the body.

2. Step 2: Check HTTP method and path

   GET is not used to start async search, and /_search/async or PUT are incorrect paths or methods.

3. Final Answer:

   POST /_async_search with query body -> Option A

4. Quick Check:

   Start async search = POST /_async_search [OK]

Hint: Use POST method on /_async_search to start async search [OK]

Common Mistakes:

• Using GET instead of POST to start async search
• Using wrong endpoint like /_search/async
• Using PUT method which is invalid here

3. Given this async search response snippet, what does the id field represent?

{
  "id": "r1A2B3C4D5E6F7G8H9I",
  "is_running": true,
  "response": null
}

medium

A. The timeout duration for the async search.

B. The total number of documents matched by the query.

C. The unique identifier to check status or fetch results later.

D. The Elasticsearch node handling the query.

Solution

1. Step 1: Understand the async search response fields

   The id is a unique string to identify this async search request.

2. Step 2: Purpose of the id

   You use this id to check if the search is done or to get the results later.

3. Final Answer:

   The unique identifier to check status or fetch results later. -> Option C

4. Quick Check:

   Async search id = unique query handle [OK]

Hint: Async search id tracks query status and results [OK]

Common Mistakes:

• Confusing id with document count
• Thinking id is timeout or node info
• Assuming id changes during query

4. You wrote this code to start an async search but get an error:

POST /_async_search
{
  "query": {
    "match": {
      "title": "Elasticsearch"
    }
  },
  "wait_for_completion_timeout": "1s"
}

What is the error in this request?

medium

A. Missing comma between query and wait_for_completion_timeout fields.

B. Using POST instead of GET method.

C. wait_for_completion_timeout cannot be set in the request body.

D. The field name "title" is invalid in match query.

Solution

1. Step 1: Check JSON syntax

   The JSON body is missing a comma after the closing brace of the "query" object.

2. Step 2: Validate method and fields

   POST is correct method, wait_for_completion_timeout is valid in body, and "title" is a valid field name.

3. Final Answer:

   Missing comma between query and wait_for_completion_timeout fields. -> Option A

4. Quick Check:

   JSON syntax error = missing comma [OK]

Hint: Check commas between JSON fields carefully [OK]

Common Mistakes:

• Forgetting commas between JSON objects
• Confusing HTTP methods for async search
• Misplacing wait_for_completion_timeout outside body

5. You want to run a very expensive aggregation query on a large dataset without timing out. Which approach using async search is best to get the final results efficiently?

hard

A. Run a normal search with a very high timeout value to wait for results.

B. Start async search with a long wait_for_completion_timeout and poll using the returned id until results are ready.

C. Start async search and immediately request results without waiting for completion.

D. Run the query multiple times with smaller timeouts and merge results manually.

Solution

1. Step 1: Understand async search timeout and polling

   Setting a reasonable wait_for_completion_timeout lets the server try to finish quickly but returns control if it takes longer.

2. Step 2: Use the returned id to poll for completion

   You can check the status later using the id until the results are ready, avoiding timeouts and blocking.

3. Final Answer:

   Start async search with a long wait_for_completion_timeout and poll using the returned id until results are ready. -> Option B

4. Quick Check:

   Async search + polling = efficient for expensive queries [OK]

Hint: Use wait_for_completion_timeout + poll with id for big queries [OK]

Common Mistakes:

• Using normal search with high timeout risking app freeze
• Requesting results immediately before completion
• Manually merging partial results instead of async search