Bucket aggregations (terms, histogram) in Elasticsearch - Time & Space Complexity

Time Complexity: Bucket aggregations (terms, histogram)

O(n)

Understanding Time Complexity

When using bucket aggregations like terms or histogram in Elasticsearch, it's important to know how the work grows as data grows.

We want to understand how the number of operations changes when we group data into buckets.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /sales/_search
{
  "size": 0,
  "aggs": {
    "sales_per_category": {
      "terms": { "field": "category.keyword", "size": 10 }
    }
  }
}
    

This code groups sales documents by category, returning the top 10 categories with their counts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each document once to assign it to a bucket.
• How many times: Once per document in the index.

How Execution Grows With Input

As the number of documents grows, Elasticsearch processes each document to place it in the right bucket.

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 directly with the number of documents.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the aggregation grows linearly with the number of documents.

Common Mistake

[X] Wrong: "Bucket aggregations only look at the top N buckets, so time stays the same no matter how many documents."

[OK] Correct: Even if we limit buckets, Elasticsearch must scan all documents to count and assign them before picking the top buckets.

Interview Connect

Understanding how bucket aggregations scale helps you explain how search engines handle grouping and counting large data sets efficiently.

Self-Check

What if we changed the aggregation to a histogram on a numeric field with many buckets? How would the time complexity change?

Practice

1.

What does the terms aggregation do in Elasticsearch?

easy

A. Sorts documents by date in ascending order

B. Groups documents by unique values of a field and counts them

C. Filters documents based on a numeric range

D. Calculates the average value of a numeric field

Solution

1. Step 1: Understand the purpose of terms aggregation

   The terms aggregation groups documents by unique values of a specified field.

2. Step 2: Recognize the output of terms aggregation

   It counts how many documents fall into each unique value group.

3. Final Answer:

   Groups documents by unique values of a field and counts them -> Option B

4. Quick Check:

   terms aggregation = grouping by unique values [OK]

Hint: Remember: terms = group by unique values and count [OK]

Common Mistakes:

• Confusing terms with filtering
• Thinking terms sorts documents
• Mixing terms with metric aggregations

2.

Which of the following is the correct syntax for a histogram aggregation on a field named price with interval 50?

{
  "aggs": {
    "price_ranges": {
      "histogram": {
        "field": "price",
        "interval": 50
      }
    }
  }
}

easy

A. Correct as shown

B. Use "interval": "50" (string instead of number)

C. Use "terms" instead of "histogram"

D. Place "interval" outside "histogram" block

Solution

1. Step 1: Check the structure of histogram aggregation

   The histogram aggregation requires a field and a numeric interval inside its block.

2. Step 2: Verify the given JSON syntax

   The example correctly places field and interval inside the histogram object with interval as a number.

3. Final Answer:

   Correct as shown -> Option A

4. Quick Check:

   Histogram syntax with numeric interval = correct [OK]

Hint: Interval must be a number inside histogram block [OK]

Common Mistakes:

• Using string instead of number for interval
• Confusing terms and histogram aggregations
• Placing interval outside histogram object

3.

Given this aggregation query:

{
  "aggs": {
    "by_category": {
      "terms": { "field": "category.keyword" }
    }
  }
}

What will the aggregation return?

medium

A. The average value of the category field

B. A histogram of categories grouped by numeric ranges

C. A list of unique categories with document counts for each

D. A filtered list of documents matching category.keyword

Solution

1. Step 1: Identify the aggregation type and field

   The query uses a terms aggregation on the category.keyword field, which groups by unique values.

2. Step 2: Understand the output of terms aggregation

   It returns buckets for each unique category with counts of documents in each bucket.

3. Final Answer:

   A list of unique categories with document counts for each -> Option C

4. Quick Check:

   Terms aggregation output = unique value buckets with counts [OK]

Hint: Terms aggregation returns unique values with counts [OK]

Common Mistakes:

• Thinking histogram groups string fields
• Expecting average instead of counts
• Confusing filtering with aggregation

4.

Identify the error in this aggregation query:

{
  "aggs": {
    "price_buckets": {
      "histogram": {
        "field": "price",
        "interval": "100"
      }
    }
  }
}

medium

A. The field name "price" is invalid

B. Missing "size" parameter for histogram

C. Histogram aggregation cannot be nested inside aggs

D. The interval value should be a number, not a string

Solution

1. Step 1: Check the type of the interval parameter

   The interval must be a numeric value, but here it is given as a string "100".

2. Step 2: Understand impact of wrong interval type

   Using a string instead of a number causes a syntax error or unexpected behavior in Elasticsearch.

3. Final Answer:

   The interval value should be a number, not a string -> Option D

4. Quick Check:

   Interval must be numeric, not string [OK]

Hint: Interval must be numeric, not quoted string [OK]

Common Mistakes:

• Using string instead of number for interval
• Assuming field name is wrong without checking
• Thinking histogram can't be inside aggs

5.

You want to group sales data by price ranges of 100 units and then within each price range, group by product category. Which aggregation structure should you use?

hard

A. { "aggs": { "price_ranges": { "histogram": { "field": "price", "interval": 100 }, "aggs": { "by_category": { "terms": { "field": "category.keyword" } } } } } }

B. { "aggs": { "by_category": { "terms": { "field": "category.keyword" }, "aggs": { "price_ranges": { "histogram": { "field": "price", "interval": 100 } } } } } }

C. { "aggs": { "price_ranges": { "terms": { "field": "price" }, "aggs": { "by_category": { "histogram": { "field": "category.keyword", "interval": 100 } } } } } }

D. { "aggs": { "by_category": { "histogram": { "field": "category.keyword", "interval": 100 }, "aggs": { "price_ranges": { "terms": { "field": "price" } } } } } }

Solution

1. Step 1: Identify the primary grouping by price ranges

   The outer aggregation should be a histogram on the price field with interval 100 to group sales by price ranges.

2. Step 2: Nest the category grouping inside each price range bucket

   Inside each price range bucket, use a terms aggregation on category.keyword to group by product category.

3. Final Answer:

   Aggregation with histogram on price and nested terms on category -> Option A

4. Quick Check:

   Histogram outer, terms nested = correct structure [OK]

Hint: Nest terms inside histogram for grouped sub-buckets [OK]

Common Mistakes:

• Reversing the order of aggregations
• Using terms for numeric price instead of histogram
• Using histogram on keyword fields