Query patterns that cause collection scans in MongoDB - Time & Space Complexity

Time Complexity: Query patterns that cause collection scans

O(n)

Understanding Time Complexity

When MongoDB runs a query without using an index, it looks at every document in the collection. This is called a collection scan.

We want to understand how the time to run such queries grows as the collection gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following MongoDB query.

db.products.find({ price: { $gt: 100 } })

This query finds all products with a price greater than 100. Assume there is no index on the price field.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each document in the collection one by one.
• How many times: Once for every document in the collection.

How Execution Grows With Input

As the number of documents grows, the query looks at each document once.

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

Pattern observation: The work grows directly with the number of documents. Double the documents, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows in a straight line as the collection size grows.

Common Mistake

[X] Wrong: "MongoDB always uses indexes, so query time stays the same no matter how big the collection is."

[OK] Correct: If there is no index on the queried field, MongoDB must check every document, so query time grows with collection size.

Interview Connect

Understanding when queries cause collection scans helps you explain performance issues clearly and shows you know how databases work under the hood.

Self-Check

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

Practice

1. Which of the following query patterns in MongoDB is most likely to cause a collection scan?

easy

A. Querying a field without an index

B. Querying a field with a single-field index

C. Using an indexed field with equality operator

D. Using a covered index query

Solution

1. Step 1: Understand collection scan causes

   A collection scan happens when MongoDB must check every document because no index supports the query.

2. Step 2: Analyze query patterns

   Querying a field without an index forces MongoDB to scan the entire collection, unlike queries using indexed fields.

3. Final Answer:

   Querying a field without an index -> Option A

4. Quick Check:

   No index = collection scan [OK]

Hint: No index on field? Expect collection scan [OK]

Common Mistakes:

• Assuming all queries use indexes automatically
• Confusing covered index with collection scan
• Thinking equality queries always cause scans

2. Which of the following MongoDB query syntaxes is correct and avoids collection scans by using an index on the field age?

easy

A. db.users.find({ age: { $gt: 25 } })

B. db.users.find({ $where: 'this.age > 25' })

C. db.users.find({ age: { $regex: '^2' } })

D. db.users.find({ $text: { $search: '25' } })

Solution

1. Step 1: Check query syntax correctness

   All queries are syntactically valid, but some use operators that prevent index use.

2. Step 2: Identify index-friendly query

   Query with { age: { $gt: 25 } } uses range operator on indexed field, avoiding collection scan. Queries with $where or $regex often cause scans.

3. Final Answer:

   db.users.find({ age: { $gt: 25 } }) -> Option A

4. Quick Check:

   Range query on indexed field = no scan [OK]

Hint: Use simple operators on indexed fields to avoid scans [OK]

Common Mistakes:

• Using $where causes collection scan
• Assuming $regex always uses index
• Confusing $text search with field index

3. Given a collection products with an index on category, what will be the result of this query?

db.products.find({ category: { $in: ['electronics', 'books'] } })

medium

A. Throws a syntax error due to $in usage

B. Performs a collection scan and returns all documents

C. Returns no documents because $in is unsupported

D. Uses index on category and returns matching documents

Solution

1. Step 1: Understand $in operator with indexes

   The $in operator can use indexes on the queried field to find matching values efficiently.

2. Step 2: Analyze query behavior

   Since category is indexed, MongoDB uses the index to find documents where category is 'electronics' or 'books'.

3. Final Answer:

   Uses index on category and returns matching documents -> Option D

4. Quick Check:

   $in + indexed field = index used [OK]

Hint: Indexed field + $in uses index, no scan [OK]

Common Mistakes:

• Thinking $in disables index use
• Assuming $in causes syntax error
• Believing collection scan always happens

4. You have a MongoDB collection orders with an index on status. Which query will cause a collection scan and how can you fix it?

db.orders.find({ $where: 'this.status === "shipped"' })

medium

A. Syntax error; fix by removing $where

B. Uses index; no fix needed

C. Causes collection scan; fix by using { status: 'shipped' }

D. Causes collection scan; fix by adding $regex

Solution

1. Step 1: Identify $where impact on query

   The $where operator runs JavaScript on each document, forcing a collection scan regardless of indexes.

2. Step 2: Fix query to use index

   Replacing $where with a direct field query { status: 'shipped' } uses the index on status, avoiding collection scan.

3. Final Answer:

   Causes collection scan; fix by using { status: 'shipped' } -> Option C

4. Quick Check:

   $where disables index; direct query fixes [OK]

Hint: Avoid $where; use direct field queries for indexes [OK]

Common Mistakes:

• Assuming $where uses indexes
• Trying to fix with $regex instead of direct query
• Confusing syntax error with collection scan

5. You want to optimize this MongoDB query to avoid collection scans on a large users collection:

db.users.find({ $or: [ { age: { $gt: 30 } }, { name: /John/ } ] })

Given indexes on age and name, which change will prevent collection scans?

hard

A. Remove indexes and rely on collection scan for speed

B. Rewrite query to separate $or into two queries using indexed fields

C. Use $where with JavaScript to filter documents

D. Change regex to case-insensitive without anchors

Solution

1. Step 1: Understand $or with mixed operators

   Regex queries often prevent index use, causing collection scans even if other fields are indexed.

2. Step 2: Optimize by splitting queries

   Running two separate queries--one on age and one on name--each using indexes, then combining results in application avoids scans.

3. Final Answer:

   Rewrite query to separate $or into two queries using indexed fields -> Option B

4. Quick Check:

   Split queries + indexes avoid scans [OK]

Hint: Split $or queries to use indexes separately [OK]

Common Mistakes:

• Believing regex always uses index
• Using $where increases scans
• Removing indexes reduces performance