Nested aggregations in Elasticsearch - Time & Space Complexity

Time Complexity: Nested aggregations

O(n + k * m)

Understanding Time Complexity

When using nested aggregations in Elasticsearch, we want to know how the work grows as we add more data or more levels of aggregation.

We ask: How does the time to get results change when the input size or nesting increases?

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch nested aggregation query.

{
  "size": 0,
  "aggs": {
    "by_category": {
      "terms": { "field": "category" },
      "aggs": {
        "by_subcategory": {
          "terms": { "field": "subcategory" }
        }
      }
    }
  }
}
    

This query groups documents first by category, then within each category by subcategory.

Identify Repeating Operations

Look at the repeated steps in this nested aggregation.

• Primary operation: Grouping documents by category, then grouping each category's documents by subcategory.
• How many times: The subcategory grouping runs once for each category group found.

How Execution Grows With Input

As the number of documents and groups grow, the work increases.

Input Size (n)	Approx. Operations
10 documents, 2 categories, 3 subcategories	About 10 grouping steps plus 2 times 3 sub-groupings
100 documents, 5 categories, 10 subcategories	About 100 grouping steps plus 5 times 10 sub-groupings
1000 documents, 20 categories, 50 subcategories	About 1000 grouping steps plus 20 times 50 sub-groupings

Pattern observation: The total work grows roughly with the number of documents plus the product of category and subcategory groups.

Final Time Complexity

Time Complexity: O(n + k * m)

This means the time grows with the number of documents n plus the number of category groups k times the number of subcategory groups m.

Common Mistake

[X] Wrong: "Nested aggregations always take time proportional only to the number of documents."

[OK] Correct: The number of groups created at each level also affects time, so more groups mean more work beyond just counting documents.

Interview Connect

Understanding how nested aggregations scale helps you explain how search engines handle grouped data efficiently, a useful skill in many data-related roles.

Self-Check

"What if we added a third level of nested aggregation? How would the time complexity change?"

Practice

1. What is the main purpose of nested aggregations in Elasticsearch?

easy

A. To sort documents by a single field

B. To group data inside other groups for multi-level analysis

C. To filter documents based on a condition

D. To update documents in bulk

Solution

1. Step 1: Recall aggregation basics

   Aggregations group data to summarize or analyze it.

2. Step 2: Examine nested aggregations

   Nested aggregations group data inside other groups for detailed multi-level insights.

3. Final Answer:

   To group data inside other groups for multi-level analysis -> Option B

4. Quick Check:

   Nested aggregations = multi-level grouping [OK]

Hint: Nested aggs always use 'aggs' inside another aggregation [OK]

Common Mistakes:

• Confusing nested aggregations with filters
• Thinking nested aggregations sort data
• Assuming nested aggregations update documents

2. Which of the following is the correct syntax to add a nested aggregation inside a terms aggregation in Elasticsearch?

easy

A. "aggs": { "country": { "terms": { "field": "country" }, "aggs": { "city": { "terms": { "field": "city" } } } } }

B. "nested": { "aggs": { "terms": { "field": "city" } } }

C. "aggs": { "nested_agg": { "terms": { "field": "city" } } }

D. "aggs": { "terms": { "field": "city" }, "aggs": { "nested_agg": { "terms": { "field": "country" } } } }

Solution

1. Step 1: Identify correct nested aggregation structure

   Nested aggregations are placed inside the "aggs" key of a parent aggregation.

2. Step 2: Check "aggs": { "country": { "terms": { "field": "country" }, "aggs": { "city": { "terms": { "field": "city" } } } } } structure

   "aggs": { "country": { "terms": { "field": "country" }, "aggs": { "city": { "terms": { "field": "city" } } } } } shows a terms aggregation on "country" with a nested terms aggregation on "city" inside its "aggs" key, which is correct syntax.

3. Final Answer:

   "aggs": { "country": { "terms": { "field": "country" }, "aggs": { "city": { "terms": { "field": "city" } } } } } -> Option A

4. Quick Check:

   Nested aggs inside parent's "aggs" key = "aggs": { "country": { "terms": { "field": "country" }, "aggs": { "city": { "terms": { "field": "city" } } } } } [OK]

Hint: Nested aggs go inside parent's "aggs" key, not outside [OK]

Common Mistakes:

• Placing multiple "aggs" keys at the same level
• Using "nested" keyword incorrectly
• Missing the "aggs" key inside parent aggregation

3. Given this Elasticsearch aggregation query snippet:

{
  "aggs": {
    "by_country": {
      "terms": { "field": "country" },
      "aggs": {
        "by_city": {
          "terms": { "field": "city" }
        }
      }
    }
  }
}

What does the nested aggregation by_city do?

medium

A. Groups documents by city inside each country group

B. Filters documents only from one city

C. Sorts countries by city name

D. Counts total documents ignoring country

Solution

1. Step 1: Analyze the outer aggregation

   "by_country" groups documents by the "country" field.

2. Step 2: Analyze the nested aggregation

   Inside each country group, "by_city" groups documents by the "city" field.

3. Final Answer:

   Groups documents by city inside each country group -> Option A

4. Quick Check:

   Nested terms aggregation groups inside parent group [OK]

Hint: Nested terms aggs group data inside parent buckets [OK]

Common Mistakes:

• Thinking nested aggs filter data
• Assuming nested aggs sort data
• Ignoring the parent aggregation grouping

4. Identify the error in this nested aggregation query:

{
  "aggs": {
    "countries": {
      "terms": { "field": "country" },
      "terms": {
        "field": "city"
      }
    }
  }
}

medium

A. Using "terms" twice at the same level is correct

B. Aggregation names cannot be plural

C. Field names "country" and "city" must be the same

D. Missing nested "aggs" key for the city aggregation

Solution

1. Step 1: Check aggregation structure

   Each aggregation can have only one aggregation type key like "terms" at its level.

2. Step 2: Identify nested aggregation placement

   Nested aggregations must be inside an "aggs" key, but here "terms" is repeated instead of nesting inside "aggs".

3. Final Answer:

   Missing nested "aggs" key for the city aggregation -> Option D

4. Quick Check:

   Nested aggs require "aggs" key inside parent [OK]

Hint: Nested aggs must be inside "aggs", not repeated aggregation keys [OK]

Common Mistakes:

• Repeating aggregation type keys at same level
• Not nesting inside "aggs" key
• Confusing aggregation names with field names

5. You want to analyze sales data by region, then by product category, and finally by brand using nested aggregations. Which of the following query structures correctly implements this three-level nested aggregation?

hard

A. { "aggs": { "region": { "terms": { "field": "region" }, "terms": { "field": "category" }, "terms": { "field": "brand" } } } }

B. { "aggs": { "region": { "terms": { "field": "region" } }, "category": { "terms": { "field": "category" } }, "brand": { "terms": { "field": "brand" } } } }

C. { "aggs": { "region": { "terms": { "field": "region" }, "aggs": { "category": { "terms": { "field": "category" }, "aggs": { "brand": { "terms": { "field": "brand" } } } } } } } }

D. { "aggs": { "brand": { "terms": { "field": "brand" }, "aggs": { "category": { "terms": { "field": "category" }, "aggs": { "region": { "terms": { "field": "region" } } } } } } } }

Solution

1. Step 1: Identify the required nesting order

   We want to group first by region, then inside each region by category, then inside each category by brand.

2. Step 2: Check each option's structure

   { "aggs": { "region": { "terms": { "field": "region" }, "aggs": { "category": { "terms": { "field": "category" }, "aggs": { "brand": { "terms": { "field": "brand" } } } } } } } correctly nests "category" inside "region"'s "aggs", and "brand" inside "category"'s "aggs". Others either flatten or reverse order.

3. Final Answer:

   { "aggs": { "region": { "terms": { "field": "region" }, "aggs": { "category": { "terms": { "field": "category" }, "aggs": { "brand": { "terms": { "field": "brand" } } } } } } } -> Option C

4. Quick Check:

   Nested aggs inside parent's "aggs" in correct order = { "aggs": { "region": { "terms": { "field": "region" }, "aggs": { "category": { "terms": { "field": "category" }, "aggs": { "brand": { "terms": { "field": "brand" } } } } } } } [OK]

Hint: Nest each level inside previous level's "aggs" key [OK]

Common Mistakes:

• Placing all aggregations at top level without nesting
• Repeating aggregation keys at same level
• Reversing the desired grouping order