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

Practice

1. What does a range query in Elasticsearch do?

easy

A. It updates documents with new values.

B. It counts the total number of documents in the index.

C. It finds documents with field values between specified limits.

D. It deletes documents matching a condition.

Solution

1. Step 1: Understand the purpose of range query

   A range query filters documents where a field's value falls within given boundaries like greater than or less than.

2. Step 2: Compare with other query types

   Counting, updating, or deleting documents are different operations, not done by range queries.

3. Final Answer:

   It finds documents with field values between specified limits. -> Option C

4. Quick Check:

   Range query = filter by value limits [OK]

Hint: Range query filters values between limits using gte, lte, gt, lt [OK]

Common Mistakes:

• Confusing range query with count or update operations
• Thinking range query modifies data
• Assuming range query deletes documents

2. Which of the following is the correct syntax for a range query filtering documents where price is greater than or equal to 10 and less than 20?

easy

A. { "range": { "price": { "gte": 10, "lte": 20 } } }

B. { "range": { "price": { "gt": 10, "lte": 20 } } }

C. { "range": { "price": { "gt": 10, "lt": 20 } } }

D. { "range": { "price": { "gte": 10, "lt": 20 } } }

Solution

1. Step 1: Identify the boundary conditions

   The question asks for price >= 10 and price < 20, which means gte:10 and lt:20.

2. Step 2: Match syntax with conditions

   { "range": { "price": { "gte": 10, "lt": 20 } } } uses gte and lt correctly matching the condition.

3. Final Answer:

   { "range": { "price": { "gte": 10, "lt": 20 } } } -> Option D

4. Quick Check:

   gte=10 and lt=20 syntax = { "range": { "price": { "gte": 10, "lt": 20 } } } [OK]

Hint: Match gte/gt and lte/lt exactly to the question limits [OK]

Common Mistakes:

• Mixing up gte with gt or lte with lt
• Using wrong operators for boundaries
• Syntax errors like missing braces

3. Given this Elasticsearch query, what documents will it match?

{ "query": { "range": { "age": { "gt": 30, "lte": 40 } } } }

medium

A. Documents where age is greater than 30 and less than or equal to 40.

B. Documents where age is between 30 and 40 inclusive.

C. Documents where age is greater than or equal to 30 and less than 40.

D. Documents where age is exactly 30 or 40.

Solution

1. Step 1: Interpret the range operators

   "gt": 30 means age > 30 (not including 30), "lte": 40 means age ≤ 40 (including 40).

2. Step 2: Understand the matching documents

   Documents with age greater than 30 and less than or equal to 40 will match.

3. Final Answer:

   Documents where age is greater than 30 and less than or equal to 40. -> Option A

4. Quick Check:

   gt=30 and lte=40 means age >30 and ≤ 40 [OK]

Hint: Remember gt excludes boundary, lte includes boundary [OK]

Common Mistakes:

• Confusing gt with gte or lte with lt
• Assuming boundaries are inclusive when they are not
• Misreading the query operators

4. Identify the error in this range query that tries to find documents with date between '2023-01-01' and '2023-12-31':

{ "range": { "date": { "gte": "2023-01-01", "lt": "2023-12-31" } }

medium

A. The field name 'date' must be inside a 'query' object.

B. The query is missing a closing brace '}' at the end.

C. The range query cannot use 'gte' and 'lt' together.

D. The date format is incorrect; it should be timestamps.

Solution

1. Step 1: Check JSON syntax

   The query is missing the final closing brace '}' to close the outer object.

2. Step 2: Validate other parts

   Date format as string is valid in Elasticsearch; using gte and lt together is allowed; 'date' field can be directly inside range.

3. Final Answer:

   The query is missing a closing brace '}' at the end. -> Option B

4. Quick Check:

   Missing closing brace = syntax error [OK]

Hint: Always check JSON braces and commas carefully [OK]

Common Mistakes:

• Forgetting to close JSON objects
• Assuming date strings must be timestamps
• Thinking gte and lt cannot be combined

5. You want to filter products priced between 50 and 100 inclusive, but exclude those exactly priced at 75. Which Elasticsearch query correctly applies this logic?

hard

A. { "bool": { "must": { "range": { "price": { "gte": 50, "lte": 100 } } }, "must_not": { "term": { "price": 75 } } } }

B. { "range": { "price": { "gte": 50, "lte": 100, "neq": 75 } } }

C. { "range": { "price": { "gt": 50, "lt": 100 } }, "must_not": { "term": { "price": 75 } } }

D. { "bool": { "should": { "range": { "price": { "gte": 50, "lte": 100 } } }, "must_not": { "term": { "price": 75 } } } }

Solution

1. Step 1: Understand the filtering requirements

   We want prices between 50 and 100 inclusive, so gte:50 and lte:100 in a range query.

2. Step 2: Exclude price exactly 75

   Use a bool query with must for range and must_not for term price=75 to exclude it.

3. Step 3: Check options

   { "bool": { "must": { "range": { "price": { "gte": 50, "lte": 100 } } }, "must_not": { "term": { "price": 75 } } } } uses bool with must range and must_not term correctly. { "range": { "price": { "gte": 50, "lte": 100, "neq": 75 } } } uses invalid 'neq'. { "range": { "price": { "gt": 50, "lt": 100 } }, "must_not": { "term": { "price": 75 } } } misses bool wrapper. { "bool": { "should": { "range": { "price": { "gte": 50, "lte": 100 } } }, "must_not": { "term": { "price": 75 } } } } uses should which is incorrect here.

4. Final Answer:

   { "bool": { "must": { "range": { "price": { "gte": 50, "lte": 100 } } }, "must_not": { "term": { "price": 75 } } } } -> Option A

5. Quick Check:

   Use bool must + must_not for inclusive range excluding a value [OK]

Hint: Use bool must for range and must_not to exclude values [OK]

Common Mistakes:

• Using invalid operators like 'neq' in range
• Not wrapping queries in bool for combining conditions
• Using should instead of must for filtering