How MongoDB scans documents - Performance & Efficiency

Time Complexity: How MongoDB scans documents

O(n)

Understanding Time Complexity

When MongoDB looks for data, it scans documents to find matches. Understanding how long this takes helps us know how fast queries run.

We want to see how the time to scan grows as the number of documents grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find all documents where age is 25
db.users.find({ age: 25 })

This query scans the users collection to find documents with age equal to 25.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each document in the collection to check the age field.
• How many times: Once for every document in the collection.

How Execution Grows With Input

As the number of documents grows, MongoDB checks more documents one by one.

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

Pattern observation: The number of checks grows directly with the number of documents.

Final Time Complexity

Time Complexity: O(n)

This means the time to find matching documents grows in a straight line as the collection gets bigger.

Common Mistake

[X] Wrong: "MongoDB instantly finds matching documents no matter the collection size."

[OK] Correct: Without indexes, MongoDB must look at each document one by one, so bigger collections take more time.

Interview Connect

Knowing how MongoDB scans documents helps you explain query speed and shows you understand how databases work behind the scenes.

Self-Check

"What if we added an index on the age field? How would the time complexity change?"

Practice

1. What does MongoDB do when there is no index for a query?

easy

A. It uses a cached result from previous queries.

B. It immediately returns an error.

C. It only scans the first document.

D. It scans every document one by one.

Solution

1. Step 1: Understand MongoDB scanning without indexes

   Without indexes, MongoDB must check each document to find matches.

2. Step 2: Recognize the scanning method

   This means MongoDB performs a full collection scan, checking documents one by one.

3. Final Answer:

   It scans every document one by one. -> Option D

4. Quick Check:

   No index means full scan = It scans every document one by one. [OK]

Hint: No index means MongoDB scans all documents [OK]

Common Mistakes:

• Thinking MongoDB returns an error without indexes
• Assuming MongoDB uses cached results automatically
• Believing MongoDB scans only part of the collection

2. Which of the following is the correct way to create an index on the field age in MongoDB?

easy

A. db.collection.createIndex({age: 1})

B. db.collection.createIndex('age')

C. db.collection.index({age: 'asc'})

D. db.collection.create({index: age})

Solution

1. Step 1: Recall MongoDB index creation syntax

   The correct syntax uses createIndex with a document specifying field and order.

2. Step 2: Match syntax to options

   db.collection.createIndex({age: 1}) uses {age: 1} which means ascending order, the correct format.

3. Final Answer:

   db.collection.createIndex({age: 1}) -> Option A

4. Quick Check:

   Index creation uses createIndex({field: order}) = db.collection.createIndex({age: 1}) [OK]

Hint: Use createIndex with {field: 1 or -1} for ascending/descending [OK]

Common Mistakes:

• Using a string instead of an object for fields
• Using incorrect method names like create or index
• Passing field name without order direction

3. Given a collection with 3 documents: {name: 'A', age: 25}, {name: 'B', age: 30}, {name: 'C', age: 35}, and an index on age, what documents will MongoDB scan for the query {age: {$gt: 28}}?

medium

A. Only documents with age 30 and 35

B. All 3 documents

C. Only the document with age 35

D. No documents scanned because index is used

Solution

1. Step 1: Understand query and index usage

   The query asks for documents where age is greater than 28. The index on age helps MongoDB find matching documents efficiently.

2. Step 2: Identify matching documents

   Documents with age 30 and 35 satisfy the condition, so MongoDB scans only these two.

3. Final Answer:

   Only documents with age 30 and 35 -> Option A

4. Quick Check:

   Index filters to matching docs = Only documents with age 30 and 35 [OK]

Hint: Index narrows scan to matching documents only [OK]

Common Mistakes:

• Thinking index scans no documents at all
• Assuming all documents are scanned despite index
• Selecting only one matching document incorrectly

4. You wrote this query: db.users.find({age: {$lt: 20}}) but it scans all documents even though you created an index on age. What is the likely problem?

medium

A. MongoDB does not support indexes on numeric fields.

B. The index was created on a different field, not age.

C. The query syntax is incorrect and causes full scan.

D. Indexes only work for equality, not range queries.

Solution

1. Step 1: Check index field correctness

   If the index is not on the age field, MongoDB cannot use it for this query.

2. Step 2: Confirm MongoDB capabilities

   MongoDB supports indexes on numeric fields and range queries ($lt, $gt, etc.). The provided query syntax is correct.

3. Final Answer:

   The index was created on a different field, not age. -> Option B

4. Quick Check:

   Index field mismatch causes full scan = The index was created on a different field, not age. [OK]

Hint: Check index field matches query field exactly [OK]

Common Mistakes:

• Believing MongoDB can't index numeric fields
• Assuming range queries never use indexes
• Thinking query syntax is invalid when it is correct

5. You have a collection with 1 million documents and an index on status. You run db.collection.find({status: 'active', score: {$gt: 50}}). MongoDB scans many documents even though status is indexed. Why?

hard

A. Indexes only speed up queries with one condition.

B. MongoDB cannot use indexes with multiple conditions.

C. Because score is not indexed, MongoDB scans documents matching status to check score condition.

D. The query syntax is invalid and causes full scan.

Solution

1. Step 1: Analyze query with multiple conditions

   The query filters on status and score. Only status is indexed.

2. Step 2: Understand index usage with multiple fields

   MongoDB uses the index on status to find matching documents, but must scan those documents to check score because it is not indexed.

3. Final Answer:

   Because score is not indexed, MongoDB scans documents matching status to check score condition. -> Option C

4. Quick Check:

   Partial index use requires scanning for other conditions = Because score is not indexed, MongoDB scans documents matching status to check score condition. [OK]

Hint: Index only helps on indexed fields; others need document scan [OK]

Common Mistakes:

• Thinking MongoDB can't use indexes with multiple conditions
• Assuming query syntax is wrong when it is correct
• Believing indexes speed up all conditions automatically