One-to-many embedding pattern in MongoDB - Time & Space Complexity

Time Complexity: One-to-many embedding pattern

O(n)

Understanding Time Complexity

When using the one-to-many embedding pattern in MongoDB, it's important to understand how the time to run queries changes as the data grows.

We want to know how the number of embedded items affects the speed of reading or writing data.

Scenario Under Consideration

Analyze the time complexity of the following MongoDB query that finds a document and updates an embedded array.

    db.orders.updateOne(
      { _id: orderId, "items.productId": productId },
      { $inc: { "items.$.quantity": 1 } }
    )
    

This code finds an order by its ID and increases the quantity of a specific product inside the embedded items array.

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: Searching through the embedded items array to find the matching product.
• How many times: The search checks each item in the array until it finds the product or reaches the end.

How Execution Grows With Input

As the number of items in the embedded array grows, the search takes longer.

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

Pattern observation: The time grows roughly in direct proportion to the number of embedded items.

Final Time Complexity

Time Complexity: O(n)

This means the time to update grows linearly with the number of embedded items in the array.

Common Mistake

[X] Wrong: "Updating an embedded item is always fast and constant time because it's inside one document."

[OK] Correct: The database must still scan the embedded array to find the matching item, so the time depends on the array size.

Interview Connect

Understanding how embedded arrays affect query time helps you design better data models and explain your choices clearly in real projects.

Self-Check

"What if the embedded items array was indexed differently or split into separate documents? How would the time complexity change?"

Practice

1. What is the main advantage of using the one-to-many embedding pattern in MongoDB?

easy

A. It separates related data into different collections for better normalization.

B. It duplicates data across multiple documents to improve write speed.

C. It requires complex joins to retrieve related data.

D. It stores related data inside the main document for faster reads.

Solution

1. Step 1: Understand embedding in MongoDB

   Embedding means storing related data inside the main document instead of separate collections.

2. Step 2: Identify the advantage of embedding

   This approach makes reading related data faster and simpler because all data is in one place.

3. Final Answer:

   It stores related data inside the main document for faster reads. -> Option D

4. Quick Check:

   Embedding = faster reads [OK]

Hint: Embedding means related data inside main document for quick access [OK]

Common Mistakes:

• Confusing embedding with referencing (separate collections)
• Thinking embedding requires joins
• Assuming embedding duplicates data

2. Which of the following is the correct way to embed multiple comments inside a blog post document in MongoDB?

easy

A. { _id: 1, title: 'Post', comments: 'Alice: Nice!, Bob: Great!' }

B. { _id: 1, title: 'Post', comments: { user: 'Alice', text: 'Nice!' }, { user: 'Bob', text: 'Great!' } }

C. { _id: 1, title: 'Post', comments: [{ user: 'Alice', text: 'Nice!' }, { user: 'Bob', text: 'Great!' }] }

D. { _id: 1, title: 'Post', comments: [{ user: 'Alice' }, user: 'Bob', text: 'Great!' ] }

Solution

1. Step 1: Check the structure for embedding multiple comments

   Embedding many comments requires an array of objects inside the main document.

2. Step 2: Identify the correct JSON syntax

   { _id: 1, title: 'Post', comments: [{ user: 'Alice', text: 'Nice!' }, { user: 'Bob', text: 'Great!' }] } correctly uses an array of comment objects inside the comments field.

3. Final Answer:

   { _id: 1, title: 'Post', comments: [{ user: 'Alice', text: 'Nice!' }, { user: 'Bob', text: 'Great!' }] } -> Option C

4. Quick Check:

   Array of objects = correct embedding [OK]

Hint: Embed many items as an array of objects inside the document [OK]

Common Mistakes:

• Using multiple objects without array brackets
• Storing comments as a string instead of objects
• Incorrect JSON syntax with misplaced commas or braces

3. Given the following document in a posts collection:

{ _id: 1, title: 'Hello', comments: [{ user: 'Alice', text: 'Hi' }, { user: 'Bob', text: 'Hello' }] }

What will be the result of the query db.posts.find({ _id: 1 }, { 'comments.user': 1, _id: 0 })?

medium

A. { comments: [{ user: 'Alice' }, { user: 'Bob' }] }

B. { comments: [{ text: 'Hi' }, { text: 'Hello' }] }

C. { _id: 1, comments: [{ user: 'Alice' }, { user: 'Bob' }] }

D. { comments: ['Alice', 'Bob'] }

Solution

1. Step 1: Understand the projection in the query

   The query projects only the comments.user field and excludes _id.

2. Step 2: Determine the output structure

   It returns the comments array with only the user fields inside each comment object.

3. Final Answer:

   { comments: [{ user: 'Alice' }, { user: 'Bob' }] } -> Option A

4. Quick Check:

   Projection of comments.user = array of user objects [OK]

Hint: Projection with dot notation returns array of objects with that field [OK]

Common Mistakes:

• Expecting full comment objects instead of only user fields
• Including _id when excluded in projection
• Getting array of strings instead of objects

4. You have this document:

{ _id: 1, name: 'Store', products: [{ name: 'Pen', price: 1.5 }, { name: 'Pencil', price: 1.0 }] }

Which update query correctly adds a new product { name: 'Eraser', price: 0.5 } to the products array?

medium

A. db.stores.updateOne({ _id: 1 }, { $push: { products: { name: 'Eraser', price: 0.5 } } })

B. db.stores.updateOne({ _id: 1 }, { $addToSet: { products: 'Eraser' } })

C. db.stores.updateOne({ _id: 1 }, { $set: { products: { name: 'Eraser', price: 0.5 } } })

D. db.stores.updateOne({ _id: 1 }, { $push: { products: ['Eraser', 0.5] } })

Solution

1. Step 1: Identify the correct operator to add an object to an array

   The $push operator adds an element to an array field.

2. Step 2: Check the value being pushed

   db.stores.updateOne({ _id: 1 }, { $push: { products: { name: 'Eraser', price: 0.5 } } }) pushes the correct object { name: 'Eraser', price: 0.5 } into the products array.

3. Final Answer:

   db.stores.updateOne({ _id: 1 }, { $push: { products: { name: 'Eraser', price: 0.5 } } }) -> Option A

4. Quick Check:

   $push with object adds to array [OK]

Hint: Use $push with full object to add to embedded array [OK]

Common Mistakes:

• Using $set replaces whole array instead of adding
• Using $addToSet with a string instead of object
• Pushing array instead of object inside array

5. You want to store a user's orders in a single document using one-to-many embedding. Each order has an orderId, date, and a list of items. Which schema design is best to handle up to 100 orders per user efficiently?

hard

A. Separate orders collection with userId reference for each order

B. { _id: userId, name: 'User', orders: [{ orderId, date, items: [{ productId, qty }] }] }

C. { _id: userId, name: 'User', orderIds: [orderId1, orderId2], orders: [] }

D. { _id: userId, name: 'User', orders: { orderId, date, items: [{ productId, qty }] } }

Solution

1. Step 1: Understand embedding for one-to-many with moderate size

   Embedding up to 100 orders inside a user document is reasonable for fast reads.

2. Step 2: Check schema design for correct embedding

   { _id: userId, name: 'User', orders: [{ orderId, date, items: [{ productId, qty }] }] } embeds an array of order objects, each with its own items array, which fits the one-to-many embedding pattern well.

3. Final Answer:

   { _id: userId, name: 'User', orders: [{ orderId, date, items: [{ productId, qty }] }] } -> Option B

4. Quick Check:

   Embed array of orders with nested items for one-to-many [OK]

Hint: Embed arrays of objects for moderate related data size [OK]

Common Mistakes:

• Using object instead of array for multiple orders
• Separating orders into another collection unnecessarily
• Storing only order IDs without details inside user