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