Range query in Elasticsearch - Time & Space Complexity

Time Complexity: Range query

O(log n + k)

Understanding Time Complexity

When we use a range query in Elasticsearch, we want to find documents with values between certain limits.

We ask: how does the time to find these documents grow as the data size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /products/_search
{
  "query": {
    "range": {
      "price": {
        "gte": 10,
        "lte": 50
      }
    }
  }
}
    

This query finds all products with a price between 10 and 50 inclusive.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Elasticsearch scans the index to find matching documents within the price range.
• How many times: It checks each document's price once, but uses an index structure to avoid scanning all documents.

How Execution Grows With Input

As the number of documents grows, Elasticsearch uses its index to quickly find matches without checking every document.

Input Size (n)	Approx. Operations
10	About 3-4 checks using the index
100	About 7-8 checks using the index
1000	About 10-12 checks using the index

Pattern observation: The number of operations grows slowly, not directly with the number of documents.

Final Time Complexity

Time Complexity: O(log n + k)

This means the time to find documents grows slowly as the data grows, thanks to the index, plus a factor proportional to the number of matching documents.

Common Mistake

[X] Wrong: "Range queries check every document one by one, so time grows directly with data size."

[OK] Correct: Elasticsearch uses indexes that let it jump quickly to matching documents without scanning all data.

Interview Connect

Understanding how range queries scale helps you explain how search engines stay fast even with lots of data.

Self-Check

"What if we removed the index on the price field? How would the time complexity change?"