Range buckets in Elasticsearch - Time & Space Complexity

Time Complexity: Range buckets

O(n * r)

Understanding Time Complexity

When using range buckets in Elasticsearch, we group data into ranges to analyze it better.

We want to know how the time to create these buckets changes as we add more data or ranges.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch aggregation using range buckets.

{
  "aggs": {
    "price_ranges": {
      "range": {
        "field": "price",
        "ranges": [
          { "to": 50 },
          { "from": 50, "to": 100 },
          { "from": 100 }
        ]
      }
    }
  }
}
    

This code groups documents by their price into three ranges: below 50, 50 to 100, and above 100.

Identify Repeating Operations

Look at what repeats when Elasticsearch processes this aggregation.

• Primary operation: Checking each document's price to see which range it fits.
• How many times: Once for every document in the data set.

How Execution Grows With Input

As you add more documents, Elasticsearch checks each one against the ranges.

Input Size (n)	Approx. Operations
10	About 30 checks
100	About 300 checks
1000	About 3000 checks

Pattern observation: The number of checks grows directly with the number of documents times the number of ranges.

Final Time Complexity

Time Complexity: O(n * r)

This means the time to create range buckets grows linearly with the number of documents and the number of ranges.

Common Mistake

[X] Wrong: "Adding more ranges will multiply the time by the number of ranges squared."

[OK] Correct: Each document is checked against each range, so time grows with documents times ranges, but ranges are usually few and fixed, so the main growth depends on documents.

Interview Connect

Understanding how range buckets scale helps you explain how Elasticsearch handles grouping large data sets efficiently.

Self-Check

What if we increased the number of ranges significantly? How would the time complexity change?

Practice

1.

What is the main purpose of range buckets in Elasticsearch aggregations?

easy

A. To update documents in the index

B. To sort documents alphabetically

C. To filter documents by exact match

D. To group documents into specified numeric or date ranges

Solution

1. Step 1: Understand range buckets concept

   Range buckets group documents based on numeric or date values falling within specified ranges.

2. Step 2: Compare options

   Only To group documents into specified numeric or date ranges describes grouping by ranges. Others describe unrelated operations.

3. Final Answer:

   To group documents into specified numeric or date ranges -> Option D

4. Quick Check:

   Range buckets = grouping by ranges [OK]

Hint: Range buckets group data by intervals, not sorting or filtering [OK]

Common Mistakes:

• Confusing range buckets with sorting
• Thinking range buckets filter exact matches
• Assuming range buckets update documents

2.

Which of the following is the correct syntax snippet to define a range bucket in Elasticsearch?

{ "range": { "field": "price", "ranges": [ { "from": 0, "to": 50 }, { "from": 50, "to": 100 } ] }}

easy

A. { "range": { "field": "price", "ranges": [ { "from": 0, "to": 50 } ] }}

B. { "range": { "field": "price", "buckets": [ { "from": 0, "to": 50 } ] }}

C. { "range": { "field": "price", "ranges": [ { "start": 0, "end": 50 } ] }}

D. { "range": { "field": "price", "intervals": [ { "from": 0, "to": 50 } ] }}

Solution

1. Step 1: Check correct keys for range buckets

   Elasticsearch uses "ranges" array with objects having "from" and "to" keys.

2. Step 2: Compare options

   Only { "range": { "field": "price", "ranges": [ { "from": 0, "to": 50 } ] }} uses "ranges" with "from" and "to" correctly. Others use incorrect keys like "start", "buckets", or "intervals".

3. Final Answer:

   { "range": { "field": "price", "ranges": [ { "from": 0, "to": 50 } ] }} -> Option A

4. Quick Check:

   Use "ranges" with "from" and "to" keys [OK]

Hint: Use "ranges" array with "from" and "to" keys for range buckets [OK]

Common Mistakes:

• Using "start" and "end" instead of "from" and "to"
• Using wrong key names like "buckets" or "intervals"
• Placing ranges outside the "range" object

3.

Given this aggregation query snippet, what will be the count of documents in the bucket with from: 10 and to: 20?

{
  "aggs": {
    "price_ranges": {
      "range": {
        "field": "price",
        "ranges": [
          { "to": 10 },
          { "from": 10, "to": 20 },
          { "from": 20 }
        ]
      }
    }
  }
}

Assume documents have prices: [5, 7, 10, 15, 18, 20, 25]

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Identify which prices fall into the 10 to 20 range

   Prices are [5,7,10,15,18,20,25]. The bucket is from 10 (inclusive) to 20 (exclusive). So prices 10, 15, 18 count. Price 20 is excluded.

2. Step 2: Count matching documents

   Matching prices: 10, 15, 18 -> 3 documents.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Prices ≥10 and <20 count = 3 [OK]

Hint: Ranges include from (inclusive), exclude to (exclusive) by default [OK]

Common Mistakes:

• Counting price 20 in the 10-20 bucket
• Confusing inclusive/exclusive range ends
• Counting prices below 10 in this bucket

4.

Identify the error in this range bucket aggregation query:

{
  "aggs": {
    "age_ranges": {
      "range": {
        "field": "age",
        "ranges": [
          { "from": 0, "to": 19 },
          { "from": 18, "to": 30 },
          { "from": 30, "to": 50 }
        ]
      }
    }
  }
}

Why might the bucket counts be incorrect?

medium

A. Missing "key" field for each range

B. Ranges overlap at 18, causing double counting

C. The "field" name is invalid

D. Ranges must use "start" and "end" instead of "from" and "to"

Solution

1. Step 1: Check range boundaries for overlap

   Ranges are 0-19, 18-30, 30-50. The value 18 is included in both first (>=0 <19) and second (>=18 <30) ranges because "from" is inclusive and "to" is exclusive.

2. Step 2: Understand impact on counts

   Documents with age=18 will contribute to both buckets since Elasticsearch range aggregations place documents into all matching buckets, causing inflated counts (double counting).

3. Final Answer:

   Ranges overlap at 18, causing double counting -> Option B

4. Quick Check:

   Overlapping ranges cause docs to count in multiple buckets [OK]

Hint: Check if range edges overlap causing double counts [OK]

Common Mistakes:

• Assuming "to" is inclusive causing overlap
• Not verifying field name correctness
• Thinking "key" is mandatory for ranges

5.

You want to create a range bucket aggregation on a date field called created_at to group documents into these ranges:

• Before 2023-01-01
• From 2023-01-01 to 2023-06-30
• After 2023-06-30

Which of the following is the correct aggregation snippet?

hard

A. { "range": { "field": "created_at", "ranges": [ { "to": "2023-01-01" }, { "from": "2023-01-01", "to": "2023-06-30" }, { "to": "2023-06-30" } ] } }

B. { "range": { "field": "created_at", "ranges": [ { "from": "2023-01-01" }, { "to": "2023-06-30" }, { "from": "2023-06-30" } ] } }

C. { "range": { "field": "created_at", "ranges": [ { "to": "2023-01-01" }, { "from": "2023-01-01", "to": "2023-06-30" }, { "from": "2023-06-30" } ] } }

D. { "range": { "field": "created_at", "ranges": [ { "from": "2023-01-01" }, { "from": "2023-06-30" }, { "to": "2023-06-30" } ] } }

Solution

1. Step 1: Match ranges to requirements

   We want: before 2023-01-01 (use "to"), from 2023-01-01 to 2023-06-30 (use "from" and "to"), after 2023-06-30 (use "from").

2. Step 2: Check options for correct keys and values

   { "range": { "field": "created_at", "ranges": [ { "to": "2023-01-01" }, { "from": "2023-01-01", "to": "2023-06-30" }, { "from": "2023-06-30" } ] } } correctly uses "to" for before date, "from" and "to" for middle range, and "from" for after date. Others misuse keys or omit ranges.

3. Final Answer:

   { "range": { "field": "created_at", "ranges": [ { "to": "2023-01-01" }, { "from": "2023-01-01", "to": "2023-06-30" }, { "from": "2023-06-30" } ] } } -> Option C

4. Quick Check:

   Use "to" for before, "from" and "to" for between, "from" for after [OK]

Hint: Use "to" for before date, "from" for after date ranges [OK]

Common Mistakes:

• Using "from" without "to" for before range
• Using "to" without "from" for after range
• Mixing up date boundaries causing missing data