$group stage for aggregation in MongoDB - Time & Space Complexity

Time Complexity: $group stage for aggregation

O(n)

Understanding Time Complexity

When using the $group stage in MongoDB aggregation, we want to know how the time to run the operation changes as the data grows.

We ask: How does grouping many documents affect the work MongoDB does?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.orders.aggregate([
  { $group: {
      _id: "$customerId",
      totalAmount: { $sum: "$amount" }
    }
  }
])
    

This groups orders by customer ID and sums the amount spent by each customer.

Identify Repeating Operations

Look for repeated work inside the aggregation.

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

How Execution Grows With Input

As the number of documents grows, the work grows roughly the same amount.

Input Size (n)	Approx. Operations
10	About 10 document checks and group assignments
100	About 100 document checks and group assignments
1000	About 1000 document checks and group assignments

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

Final Time Complexity

Time Complexity: O(n)

This means the time to group grows directly with the number of documents processed.

Common Mistake

[X] Wrong: "Grouping always takes the same time no matter how many documents there are."

[OK] Correct: Grouping must look at each document to decide its group, so more documents mean more work.

Interview Connect

Understanding how grouping scales helps you explain performance in real projects and shows you can think about data size effects clearly.

Self-Check

"What if we added a $match stage before $group to filter documents? How would that affect the time complexity?"

Practice

1. What is the main purpose of the $group stage in a MongoDB aggregation pipeline?

easy

A. To project specific fields from documents

B. To filter documents based on a condition

C. To sort documents in ascending or descending order

D. To group documents by a specified key and perform calculations on each group

Solution

1. Step 1: Understand the role of $group

   The $group stage collects documents into groups based on a key defined in the _id field.

2. Step 2: Identify what $group does with groups

   It allows performing calculations like sum, count, or average on each group.

3. Final Answer:

   To group documents by a specified key and perform calculations on each group -> Option D

4. Quick Check:

   $group groups and calculates [OK]

Hint: Remember: $group always groups and aggregates [OK]

Common Mistakes:

• Confusing $group with $match for filtering
• Thinking $group sorts documents
• Assuming $group projects fields without grouping

2. Which of the following is the correct syntax to group documents by the field category and count the number of documents in each group?

easy

A. { $group: { category: "$category", count: { $sum: 1 } } }

B. { $group: { _id: "$category", count: { $sum: 1 } } }

C. { $group: { _id: "$category", count: { $count: 1 } } }

D. { $group: { _id: "$category", count: { $add: 1 } } }

Solution

1. Step 1: Identify the grouping key field

   The grouping key must be assigned to _id, so _id: "$category" is correct.

2. Step 2: Use the correct accumulator for counting

   Counting documents uses $sum: 1 to add 1 for each document in the group.

3. Final Answer:

   { $group: { _id: "$category", count: { $sum: 1 } } } -> Option B

4. Quick Check:

   Group key in _id and count with $sum: 1 [OK]

Hint: Always use _id for group key and $sum: 1 to count [OK]

Common Mistakes:

• Using field name instead of _id for grouping key
• Using $count instead of $sum for counting
• Using $add which is not an accumulator

3. Given the collection documents:

{ "category": "A", "value": 10 }

{ "category": "B", "value": 20 }

{ "category": "A", "value": 15 }

What will be the output of this aggregation?

[{ $group: { _id: "$category", total: { $sum: "$value" } } }]

medium

A. [{ "_id": "A", "total": 25 }, { "_id": "B", "total": 20 }]

B. [{ "_id": "A", "total": 10 }, { "_id": "B", "total": 20 }, { "_id": "A", "total": 15 }]

C. [{ "_id": "A", "total": 15 }, { "_id": "B", "total": 20 }]

D. [{ "_id": null, "total": 45 }]

Solution

1. Step 1: Group documents by category

   Documents with category "A" are grouped together, and category "B" separately.

2. Step 2: Sum the value fields in each group

   For category "A": 10 + 15 = 25; for category "B": 20.

3. Final Answer:

   [{ "_id": "A", "total": 25 }, { "_id": "B", "total": 20 }] -> Option A

4. Quick Check:

   Sum values per category = correct totals [OK]

Hint: Sum values grouped by _id key field [OK]

Common Mistakes:

• Expecting separate documents without grouping
• Summing incorrectly or ignoring grouping
• Using _id: null which groups all documents together

4. Identify the error in this aggregation pipeline stage:

{ $group: { category: "$category", total: { $sum: "$amount" } } }

medium

A. Field names should not be in quotes

B. Incorrect use of $sum operator

C. Missing _id field for grouping key

D. Aggregation pipeline stage must be an array

Solution

1. Step 1: Check for required _id field in $group

   The _id field is mandatory to specify the grouping key.

2. Step 2: Verify other syntax elements

   The $sum operator and field references are correct; only _id is missing.

3. Final Answer:

   Missing _id field for grouping key -> Option C

4. Quick Check:

   _id is required in $group [OK]

Hint: Always include _id in $group stage [OK]

Common Mistakes:

• Omitting the _id field
• Confusing field names with grouping key
• Thinking $sum needs special syntax

5. You have a collection of sales documents with fields store, item, and quantity. You want to find the total quantity sold per store, but only for stores where the total quantity exceeds 100. Which aggregation pipeline correctly achieves this?

hard

A. [{ $group: { _id: "$store", totalQuantity: { $sum: "$quantity" } } }, { $match: { totalQuantity: { $gt: 100 } } }]

B. [{ $match: { quantity: { $gt: 100 } } }, { $group: { _id: "$store", totalQuantity: { $sum: "$quantity" } } }]

C. [{ $group: { _id: "$store", totalQuantity: { $sum: "$quantity" } } }, { $match: { _id: { $gt: 100 } } }]

D. [{ $group: { _id: "$store", totalQuantity: { $sum: "$quantity" } } }, { $sort: { totalQuantity: -1 } }]

Solution

1. Step 1: Group by store and sum quantity

   The $group stage groups documents by store and calculates total quantity sold per store.

2. Step 2: Filter groups where total quantity > 100

   The $match stage after grouping filters groups with totalQuantity greater than 100.

3. Final Answer:

   [{ $group: { _id: "$store", totalQuantity: { $sum: "$quantity" } } }, { $match: { totalQuantity: { $gt: 100 } } }] -> Option A

4. Quick Check:

   Group then filter by aggregated field [OK]

Hint: Filter after grouping using $match on aggregated fields [OK]

Common Mistakes:

• Filtering before grouping which filters documents, not groups
• Filtering on _id instead of aggregated field
• Using $sort instead of filtering