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