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

Time Complexity: One-to-many referencing pattern

O(n)

Understanding Time Complexity

When using one-to-many referencing in MongoDB, we want to know how the time to get data changes as the number of related items grows.

We ask: How does fetching a document and its related many documents scale with more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find a user by ID
const user = db.users.findOne({ _id: userId });

// Find all posts referencing this user
const posts = db.posts.find({ userId: user._id }).toArray();
    

This code fetches one user and then fetches all posts linked to that user by userId.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all posts that match the userId.
• How many times: Once for the user, then once for each post linked to that user.

How Execution Grows With Input

As the number of posts for a user grows, the time to fetch all posts grows roughly the same way.

Input Size (n)	Approx. Operations
10 posts	About 10 operations to fetch posts
100 posts	About 100 operations to fetch posts
1000 posts	About 1000 operations to fetch posts

Pattern observation: The time grows directly with the number of posts linked to the user.

Final Time Complexity

Time Complexity: O(n)

This means the time to get all related posts grows linearly with how many posts there are for that user.

Common Mistake

[X] Wrong: "Fetching related posts is always fast no matter how many posts exist."

[OK] Correct: The more posts linked to a user, the longer it takes to fetch them all, so time grows with data size.

Interview Connect

Understanding how fetching related data scales helps you explain database design choices clearly and shows you think about real data growth.

Self-Check

"What if we stored all posts inside the user document instead of referencing? How would the time complexity change when fetching posts?"

Practice

1. What is the main purpose of the one-to-many referencing pattern in MongoDB?

easy

A. To create a backup of documents automatically

B. To store all related data inside a single document

C. To link one document to many related documents using their IDs

D. To encrypt documents for security

Solution

1. Step 1: Understand one-to-many referencing

   It connects one document to many others by storing their IDs, not embedding all data.

2. Step 2: Compare options

   Only To link one document to many related documents using their IDs describes linking documents by IDs, which is the core of one-to-many referencing.

3. Final Answer:

   To link one document to many related documents using their IDs -> Option C

4. Quick Check:

   One-to-many referencing = linking documents by IDs [OK]

Hint: One-to-many means one document points to many IDs [OK]

Common Mistakes:

• Thinking all data is stored inside one document
• Confusing referencing with embedding
• Assuming it creates backups automatically

2. Which of the following is the correct way to reference many comments in a post document using one-to-many referencing in MongoDB?

easy

A. { _id: 1, title: 'Post', comments: [ObjectId('abc123'), ObjectId('def456')] }

B. { _id: 1, title: 'Post', comments: { text: 'Nice post!' } }

C. { _id: 1, title: 'Post', comments: 'This is a comment' }

D. { _id: 1, title: 'Post', comments: ObjectId('abc123') }

Solution

1. Step 1: Identify referencing format

   One-to-many referencing stores an array of ObjectIds pointing to related documents.

2. Step 2: Check each option

   { _id: 1, title: 'Post', comments: [ObjectId('abc123'), ObjectId('def456')] } uses an array of ObjectIds, which is correct. Others embed data or use a single ID incorrectly.

3. Final Answer:

   { _id: 1, title: 'Post', comments: [ObjectId('abc123'), ObjectId('def456')] } -> Option A

4. Quick Check:

   Array of ObjectIds = correct referencing [OK]

Hint: Use array of ObjectIds to reference many documents [OK]

Common Mistakes:

• Embedding comment text instead of IDs
• Using a single ObjectId for many comments
• Storing comments as plain strings

3. Given these two collections:
posts: [{ _id: 1, title: 'Hello', comments: [101, 102] }]
comments: [{ _id: 101, text: 'Nice!' }, { _id: 102, text: 'Great!' }]
What will be the result of this query to find comments for post with _id 1?
db.comments.find({ _id: { $in: db.posts.findOne({ _id: 1 }).comments } })

medium

A. [] (empty array)

B. [{ _id: 1, title: 'Hello', comments: [101, 102] }]

C. SyntaxError due to nested query

D. [{ _id: 101, text: 'Nice!' }, { _id: 102, text: 'Great!' }]

Solution

1. Step 1: Understand the query

   The inner findOne gets the comments array [101, 102] from post _id 1.

2. Step 2: Use $in to find matching comments

   The outer find returns comments with _id in [101, 102], so both comment documents are returned.

3. Final Answer:

   [{ _id: 101, text: 'Nice!' }, { _id: 102, text: 'Great!' }] -> Option D

4. Quick Check:

   Find comments by IDs in post = matching comment docs [OK]

Hint: Use $in with IDs array to get related documents [OK]

Common Mistakes:

• Expecting post document instead of comments
• Thinking nested query causes syntax error
• Getting empty result by mistake

4. You have this post document:
{ _id: 1, title: 'Test', comments: ['abc', 'def'] }
But when you run db.comments.find({ _id: { $in: post.comments } }), it returns no results. What is the most likely problem?

medium

A. ObjectIds in post.comments are strings, not ObjectId type

B. The comments collection has no documents with those ObjectIds

C. The query syntax is incorrect for $in operator

D. The post document is missing the comments field

Solution

1. Step 1: Check data types of referenced IDs

   If post.comments contains strings instead of ObjectId objects, the query won't match.

2. Step 2: Confirm query correctness

   The query syntax is correct, so the mismatch is likely due to type difference.

3. Final Answer:

   ObjectIds in post.comments are strings, not ObjectId type -> Option A

4. Quick Check:

   Type mismatch in IDs causes no matches [OK]

Hint: Ensure referenced IDs are ObjectId type, not strings [OK]

Common Mistakes:

• Assuming empty results mean syntax error
• Ignoring data type differences
• Thinking missing field causes this error

5. You want to design a blog system with users, posts, and comments. Each user can write many posts, and each post can have many comments. Using one-to-many referencing, which is the best way to organize references?

hard

A. comments store userId; posts store arrays of commentIds

B. posts store userId; comments store postId; users do not store references

C. users embed all posts; posts embed all comments

D. users store arrays of postIds; posts store arrays of commentIds

Solution

1. Step 1: Understand one-to-many referencing best practice

   Usually, the 'many' side stores the reference to the 'one' side to avoid large arrays.

2. Step 2: Apply to blog system

   Posts store userId (one user, many posts), comments store postId (one post, many comments), users don't store arrays.

3. Final Answer:

   posts store userId; comments store postId; users do not store references -> Option B

4. Quick Check:

   Many side stores reference to one side [OK]

Hint: Store reference on 'many' side to 'one' side document [OK]

Common Mistakes:

• Embedding all posts or comments inside users or posts
• Storing large arrays on 'one' side documents
• Confusing which side stores the reference