Cardinality aggregation in Elasticsearch - Time & Space Complexity

Time Complexity: Cardinality aggregation

O(n)

Understanding Time Complexity

When using cardinality aggregation in Elasticsearch, we want to know how the time to count unique values changes as data grows.

We ask: How does the work increase when there are more documents or more unique values?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /my_index/_search
{
  "size": 0,
  "aggs": {
    "unique_users": {
      "cardinality": {
        "field": "user_id"
      }
    }
  }
}
    

This query counts the number of unique user IDs in the index using cardinality aggregation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each document's user_id field once.
• How many times: Once per document in the index.

How Execution Grows With Input

As the number of documents grows, the aggregation must look at more user_id values.

Input Size (n)	Approx. Operations
10	10 checks of user_id
100	100 checks of user_id
1000	1000 checks of user_id

Pattern observation: The work grows directly with the number of documents scanned.

Final Time Complexity

Time Complexity: O(n)

This means the time to find unique values grows in a straight line as the number of documents increases.

Common Mistake

[X] Wrong: "Cardinality aggregation is instant no matter how many documents there are."

[OK] Correct: The aggregation must check each document's field once, so more documents mean more work.

Interview Connect

Understanding how cardinality aggregation scales helps you explain performance in real search systems and shows you can reason about data size effects.

Self-Check

"What if we added a precision threshold to the cardinality aggregation? How would that affect the time complexity?"

Practice

1.

What does the cardinality aggregation in Elasticsearch do?

easy

A. Calculates the sum of values in a field

B. Sorts documents by a field

C. Finds the average value of a field

D. Counts the number of unique values in a field

Solution

1. Step 1: Understand the purpose of cardinality aggregation

   Cardinality aggregation is designed to count unique values in a specified field.

2. Step 2: Compare with other aggregations

   Sum and average aggregations calculate totals and averages, not unique counts. Sorting is unrelated.

3. Final Answer:

   Counts the number of unique values in a field -> Option D

4. Quick Check:

   Cardinality = Unique count [OK]

Hint: Cardinality = count unique values fast [OK]

Common Mistakes:

• Confusing cardinality with sum or average
• Thinking it returns exact counts always
• Mixing it with sorting or filtering

2.

Which of the following is the correct syntax to define a cardinality aggregation on the field user_id in Elasticsearch?

{
  "aggs": {
    "unique_users": {
      "cardinality": {
        "field": "user_id"
      }
    }
  }
}

easy

A. { "aggs": { "unique_users": { "cardinality": { "field": "user_id" } } } }

B. { "aggs": { "unique_users": { "terms": { "field": "user_id" } } } }

C. { "aggs": { "unique_users": { "sum": { "field": "user_id" } } } }

D. { "aggs": { "unique_users": { "avg": { "field": "user_id" } } } }

Solution

1. Step 1: Identify the aggregation type for unique counts

   The cardinality aggregation is used to count unique values, so the key must be "cardinality".

2. Step 2: Check the field name and structure

   The field is correctly specified as "user_id" inside the cardinality object.

3. Final Answer:

   { "aggs": { "unique_users": { "cardinality": { "field": "user_id" } } } } -> Option A

4. Quick Check:

   Correct syntax uses "cardinality" with "field" [OK]

Hint: Cardinality uses "cardinality" key with "field" [OK]

Common Mistakes:

• Using terms aggregation instead of cardinality
• Using sum or avg aggregations for unique counts
• Incorrect JSON structure or missing braces

3.

Given the following Elasticsearch aggregation query:

{
  "aggs": {
    "unique_countries": {
      "cardinality": {
        "field": "country"
      }
    }
  }
}

If the indexed documents have countries: ["US", "US", "FR", "DE", "FR", "JP"], what is the expected approximate output value for unique_countries?

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Identify unique countries in the list

   The countries are US, FR, DE, JP. Counting unique values gives 4.

2. Step 2: Understand cardinality output

   Cardinality aggregation returns approximate unique counts, which should be 4 here.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Unique countries count = 4 [OK]

Hint: Count distinct values in the field for cardinality [OK]

Common Mistakes:

• Counting duplicates as unique
• Confusing total documents with unique count
• Expecting exact count always (approximate)

4.

Identify the error in this cardinality aggregation query:

{
  "aggs": {
    "unique_users": {
      "cardinality": {
        "field_name": "user_id"
      }
    }
  }
}

medium

A. Aggregation name cannot be "unique_users"

B. Missing closing brace for "aggs"

C. "field_name" should be "field"

D. Cardinality aggregation requires a "size" parameter

Solution

1. Step 1: Check the field parameter name

   The correct key for specifying the field is "field", not "field_name".

2. Step 2: Verify JSON structure and parameters

   The braces are correctly closed, aggregation name is valid, and "size" is not required for cardinality.

3. Final Answer:

   "field_name" should be "field" -> Option C

4. Quick Check:

   Use "field" key for cardinality field [OK]

Hint: Use "field", not "field_name" in cardinality [OK]

Common Mistakes:

• Using wrong key "field_name" instead of "field"
• Adding unnecessary parameters like "size"
• Misnaming aggregation or missing braces

5.

You want to find the approximate number of unique products sold in each category using Elasticsearch. Which aggregation setup correctly combines terms and cardinality aggregations?

{
  "aggs": {
    "by_category": {
      "terms": { "field": "category" },
      "aggs": {
        "unique_products": {
          "cardinality": { "field": "product_id" }
        }
      }
    }
  }
}

hard

A. This setup groups by category and counts unique products per category

B. This setup counts unique categories per product

C. This setup sums product_id values per category

D. This setup finds average product_id per category

Solution

1. Step 1: Understand the terms aggregation

   "terms" groups documents by unique values in "category" field.

2. Step 2: Understand the nested cardinality aggregation

   Inside each category bucket, cardinality counts unique "product_id" values.

3. Final Answer:

   This setup groups by category and counts unique products per category -> Option A

4. Quick Check:

   Terms + cardinality = unique counts per group [OK]

Hint: Nest cardinality inside terms to count unique per group [OK]

Common Mistakes:

• Confusing aggregation order or nesting
• Using cardinality on category instead of product_id
• Expecting sum or average instead of unique count