Array of embedded documents queries in MongoDB - Time & Space Complexity

Time Complexity: Array of embedded documents queries

O(n * m)

Understanding Time Complexity

When querying arrays inside documents in MongoDB, it's important to know how the query time changes as the data grows.

We want to understand how the number of operations grows when searching embedded arrays.

Scenario Under Consideration

Analyze the time complexity of the following MongoDB query.

db.orders.find({
  items: { $elemMatch: { productId: 123, quantity: { $gt: 2 } } }
})
.limit(5)

This query searches for orders where the items array has at least one element with productId 123 and quantity greater than 2, returning up to 5 results.

Identify Repeating Operations

Look for repeated checks inside the array of embedded documents.

• Primary operation: Scanning each document's items array to check each embedded document for matching conditions.
• How many times: For each order document, the query examines each item in the items array until it finds a match or reaches the end.

How Execution Grows With Input

As the number of orders and the size of each items array grow, the query checks more embedded documents.

Input Size (n)	Approx. Operations
10 orders with 5 items each	Up to 50 item checks
100 orders with 10 items each	Up to 1,000 item checks
1,000 orders with 20 items each	Up to 20,000 item checks

Pattern observation: The total checks grow roughly with the number of orders times the average number of items per order.

Final Time Complexity

Time Complexity: O(n * m)

This means the query time grows proportionally with the number of documents (n) times the average size of the embedded array (m).

Common Mistake

[X] Wrong: "The query only checks one item per document, so it runs in O(n)."

[OK] Correct: The query must check each item in the array until it finds a match, so it depends on the array size too, making it O(n * m).

Interview Connect

Understanding how queries on embedded arrays scale helps you design efficient data models and write performant queries, a valuable skill in real projects.

Self-Check

What if we added an index on the embedded document fields? How would the time complexity change?

Practice

1.

Which MongoDB query operator is used to match documents where at least one element in an array of embedded documents meets multiple conditions?

easy

A. $exists

B. $all

C. $in

D. $elemMatch

Solution

1. Step 1: Understand the need for multiple conditions on one embedded document

   When querying arrays of embedded documents, multiple conditions on the same element require a special operator.

2. Step 2: Identify the correct operator for matching multiple conditions on one element

   $elemMatch matches documents where at least one array element satisfies all specified conditions.

3. Final Answer:

   $elemMatch -> Option D

4. Quick Check:

   Multiple conditions on one embedded doc = $elemMatch [OK]

Hint: Use $elemMatch for multiple conditions on one array element [OK]

Common Mistakes:

• Using $all which matches all elements separately
• Using $in which matches any value but not multiple conditions
• Confusing $exists with array element matching

2.

Which of the following is the correct MongoDB query syntax to find documents where the comments array contains an embedded document with author equal to "Alice"?

{ comments: { ? } }

easy

A. { $in: { author: "Alice" } }

B. { author: "Alice" }

C. { $elemMatch: { author: "Alice" } }

D. { $all: { author: "Alice" } }

Solution

1. Step 1: Identify simple query for matching one field in embedded documents

   To find documents where any embedded document in an array has a field equal to a value, use $elemMatch or direct matching.

2. Step 2: Recognize that { comments: { $elemMatch: { author: "Alice" } } } matches if any embedded document has author "Alice"

   This syntax matches documents where at least one element in comments array has author "Alice".

3. Final Answer:

   { $elemMatch: { author: "Alice" } } -> Option C

4. Quick Check:

   Use $elemMatch for embedded document match [OK]

Hint: Use $elemMatch for embedded document match [OK]

Common Mistakes:

• Using $in or $all incorrectly with embedded documents
• Confusing array field with embedded document field
• Using direct object without $elemMatch may not always work as expected

3.

Given the collection posts with documents like:

{ _id: 1, comments: [ { author: "Bob", likes: 5 }, { author: "Alice", likes: 3 } ] }

What will the query db.posts.find({ comments: { $elemMatch: { author: "Alice", likes: { $gt: 2 } } } }) return?

medium

A. [{ _id: 1, comments: [...] }]

B. [] (empty array)

C. Syntax error

D. All documents in posts collection

Solution

1. Step 1: Understand $elemMatch with multiple conditions

   The query looks for documents where at least one comment has author "Alice" and likes greater than 2.

2. Step 2: Check the example document for matching embedded document

   The second comment has author "Alice" and likes 3, which is greater than 2, so it matches.

3. Final Answer:

   [{ _id: 1, comments: [...] }] -> Option A

4. Quick Check:

   Matching embedded doc with $elemMatch returns document [OK]

Hint: Check all conditions inside $elemMatch for one embedded doc [OK]

Common Mistakes:

• Assuming $elemMatch matches separate elements for each condition
• Expecting empty result when conditions are met
• Confusing $elemMatch with $all

4.

Identify the error in this MongoDB query to find documents where reviews array has an embedded document with rating greater than 4 and verified true:

db.collection.find({ reviews: { rating: { $gt: 4 }, verified: true } })

medium

A. reviews field should not be queried as an array

B. Missing $elemMatch to combine multiple conditions on one embedded document

C. Incorrect use of $gt operator

D. Syntax error due to missing commas

Solution

1. Step 1: Recognize multiple conditions on one embedded document

   Multiple conditions on fields inside an array element require $elemMatch to ensure they apply to the same element.

2. Step 2: Identify missing $elemMatch usage

   The query incorrectly tries to match multiple fields directly inside the array field, which matches documents with separate elements for each condition, not the same element.

3. Final Answer:

   Missing $elemMatch to combine multiple conditions on one embedded document -> Option B

4. Quick Check:

   Multiple conditions on one element need $elemMatch [OK]

Hint: Use $elemMatch for multiple conditions on same embedded doc [OK]

Common Mistakes:

• Omitting $elemMatch for multiple conditions
• Assuming direct object matches all conditions on one element
• Misunderstanding array query behavior

5.

You have a collection orders with documents like:

{ _id: 1, items: [ { product: "Pen", qty: 10 }, { product: "Notebook", qty: 5 } ] }

Write a query to find orders where items contains a product "Pen" with quantity at least 10, and also a product "Notebook" with quantity at least 5.

Which query correctly finds such orders?

hard

A. { items: { $elemMatch: { product: "Pen", qty: { $gte: 10 } } }, items: { $elemMatch: { product: "Notebook", qty: { $gte: 5 } } } }

B. { items: { $elemMatch: { product: "Pen", qty: { $gte: 10 }, product: "Notebook", qty: { $gte: 5 } } } }

C. { items: { product: "Pen", qty: { $gte: 10 }, product: "Notebook", qty: { $gte: 5 } } }

D. { items: { $in: [ { product: "Pen", qty: { $gte: 10 } }, { product: "Notebook", qty: { $gte: 5 } } ] } }

Solution

1. Step 1: Understand the need to match two different embedded documents in the array

   We want orders where items array has one element matching Pen with qty >= 10 and another element matching Notebook with qty >= 5.

2. Step 2: Use repeated array field with $elemMatch to require both conditions on separate elements

   Repeating the array field key with $elemMatch for each condition ensures at least one array element satisfies each set of conditions.

3. Step 3: Eliminate incorrect options

   { items: { $elemMatch: { product: "Pen", qty: { $gte: 10 }, product: "Notebook", qty: { $gte: 5 } } } } tries to match both products in one element (impossible). { items: { product: "Pen", qty: { $gte: 10 }, product: "Notebook", qty: { $gte: 5 } } } is invalid syntax. { items: { $in: [ { product: "Pen", qty: { $gte: 10 } }, { product: "Notebook", qty: { $gte: 5 } } ] } } uses $in which matches any element but not both conditions.

4. Final Answer:

   { items: { $elemMatch: { product: "Pen", qty: { $gte: 10 } } }, items: { $elemMatch: { product: "Notebook", qty: { $gte: 5 } } } } -> Option A

5. Quick Check:

   Repeated field + $elemMatch for multiple different embedded docs [OK]

Hint: Use repeated array field with $elemMatch for multiple different embedded docs [OK]

Common Mistakes:

• Trying to match multiple products in one embedded document
• Using $elemMatch alone for multiple different elements
• Using $in which matches any but not all conditions