$lookup for joining collections in MongoDB - Time & Space Complexity

Time Complexity: $lookup for joining collections

O(n)

Understanding Time Complexity

When using $lookup in MongoDB, we want to know how the time it takes grows as the data grows.

We ask: How does joining two collections affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.orders.aggregate([
  {
    $lookup: {
      from: "products",
      localField: "product_id",
      foreignField: "_id",
      as: "product_details"
    }
  }
])

This code joins the orders collection with the products collection to add product details to each order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each order document, MongoDB searches the products collection for matching _id.
• How many times: Once per order document, so the number of orders times the cost to find matching products.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (orders)	Approx. Operations
10	About 10 lookups in products
100	About 100 lookups in products
1000	About 1000 lookups in products

Pattern observation: The work grows roughly in direct proportion to the number of orders.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the number of documents in the main collection.

Common Mistake

[X] Wrong: "The join time depends only on the size of the joined collection."

[OK] Correct: The join time depends mainly on how many documents you process in the main collection, because each triggers a lookup.

Interview Connect

Understanding how $lookup scales helps you explain database joins clearly and shows you can think about performance in real projects.

Self-Check

"What if the foreignField is indexed? How would the time complexity change?"

Practice

1. What does the $lookup stage do in a MongoDB aggregation pipeline?

easy

A. It deletes documents from a collection.

B. It joins documents from two collections based on a matching field.

C. It sorts documents in ascending order.

D. It updates documents with new values.

Solution

1. Step 1: Understand the purpose of $lookup

   $lookup is used to combine documents from two collections by matching fields.

2. Step 2: Compare with other options

   Deleting, sorting, or updating documents are different operations and not related to $lookup.

3. Final Answer:

   It joins documents from two collections based on a matching field. -> Option B

4. Quick Check:

   $lookup joins collections = A [OK]

Hint: Remember: $lookup is like a join in SQL [OK]

Common Mistakes:

• Confusing $lookup with update or delete operations
• Thinking $lookup sorts documents
• Assuming $lookup modifies documents instead of joining

2. Which of the following is the correct syntax for a basic $lookup stage in MongoDB?

easy

A. { $lookup: { from: 'other', localField: 'id', foreignField: 'userId', joinAs: 'joinedData' } }

B. { $lookup: { collection: 'other', localKey: 'id', foreignKey: 'userId', output: 'joinedData' } }

C. { $lookup: { from: 'other', localField: 'id', foreignField: 'userId', as: 'joinedData' } }

D. { $lookup: { from: 'other', localField: 'id', foreignField: 'userId' } }

Solution

1. Step 1: Identify correct field names in $lookup

   The correct keys are from, localField, foreignField, and as.

2. Step 2: Check each option

   { $lookup: { from: 'other', localField: 'id', foreignField: 'userId', as: 'joinedData' } } uses all correct keys and syntax. Options A, B, and C have incorrect or missing keys.

3. Final Answer:

   { $lookup: { from: 'other', localField: 'id', foreignField: 'userId', as: 'joinedData' } } -> Option C

4. Quick Check:

   Correct $lookup keys = D [OK]

Hint: Use keys: from, localField, foreignField, as [OK]

Common Mistakes:

• Using wrong key names like collection or joinAs
• Omitting the 'as' field for output array
• Missing foreignField or localField keys

3. Given two collections: orders with documents { _id: 1, productId: 101 } and products with documents { _id: 101, name: 'Pen' }, what will be the result of this aggregation on orders?

{ $lookup: { from: 'products', localField: 'productId', foreignField: '_id', as: 'productInfo' } }

medium

A. [{ _id: 1, productId: 101, productInfo: [{ _id: 101, name: 'Pen' }] }]

B. [{ _id: 1, productId: 101, productInfo: [] }]

C. [{ _id: 1, productId: 101 }]

D. SyntaxError

Solution

1. Step 1: Match localField and foreignField values

   The productId in orders is 101, which matches _id 101 in products.

2. Step 2: Understand $lookup output

   The matching product document is added as an array in productInfo.

3. Final Answer:

   [{ _id: 1, productId: 101, productInfo: [{ _id: 101, name: 'Pen' }] }] -> Option A

4. Quick Check:

   Matching product added in array = B [OK]

Hint: Matched docs appear in array named by 'as' [OK]

Common Mistakes:

• Expecting productInfo to be a single object, not an array
• Thinking no match means error instead of empty array
• Ignoring the 'as' field name in output

4. What is wrong with this $lookup stage?

{ $lookup: { from: 'users', localField: 'userId', foreignField: 'id', as: 'userDetails' } }

Assuming the users collection uses _id as the user ID field.

medium

A. The 'as' field cannot be 'userDetails'.

B. The localField should be 'id' instead of 'userId'.

C. The 'from' field should be 'user' not 'users'.

D. The foreignField should be '_id' instead of 'id'.

Solution

1. Step 1: Check foreignField correctness

   The users collection uses _id as the ID field, so foreignField must be '_id'.

2. Step 2: Verify other fields

   localField and as are valid; collection name 'users' is correct.

3. Final Answer:

   The foreignField should be '_id' instead of 'id'. -> Option D

4. Quick Check:

   foreignField must match actual field = C [OK]

Hint: Match foreignField to actual field name in other collection [OK]

Common Mistakes:

• Using wrong foreignField name
• Changing 'as' field unnecessarily
• Mistaking collection name pluralization

5. You have two collections: students with { _id: 1, name: 'Alice' } and grades with multiple documents per student like { studentId: 1, score: 85 }. How do you write a $lookup to get each student with all their grades in an array called allGrades?

hard

A. { $lookup: { from: 'grades', localField: '_id', foreignField: 'studentId', as: 'allGrades' } }

B. { $lookup: { from: 'grades', localField: 'studentId', foreignField: '_id', as: 'allGrades' } }

C. { $lookup: { from: 'grades', localField: 'name', foreignField: 'studentId', as: 'allGrades' } }

D. { $lookup: { from: 'grades', localField: '_id', foreignField: 'score', as: 'allGrades' } }

Solution

1. Step 1: Identify matching fields between collections

   students._id matches grades.studentId, so these are the fields to join on.

2. Step 2: Write $lookup with correct fields and output array name

   Use from: 'grades', localField: '_id', foreignField: 'studentId', and as: 'allGrades'.

3. Final Answer:

   { $lookup: { from: 'grades', localField: '_id', foreignField: 'studentId', as: 'allGrades' } } -> Option A

4. Quick Check:

   Match student _id to grades studentId = A [OK]

Hint: Join on matching ID fields, output array named by 'as' [OK]

Common Mistakes:

• Swapping localField and foreignField
• Using wrong fields like name or score for join
• Incorrect output array name