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