Index usage verification in MongoDB - Time & Space Complexity

Time Complexity: Index usage verification

O(log n)

Understanding Time Complexity

When we check if a database uses an index, we want to know how fast it finds data as the collection grows.

We ask: How does the search time change when more records are added?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Check if query uses index
db.collection.find({ age: 30 }).explain("executionStats")

// Example output shows if index was used and how many documents scanned
    

This code runs a query on the "age" field and shows if MongoDB uses an index to speed up the search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning documents to find matches.
• How many times: Without index, it checks each document one by one; with index, it jumps directly to matches.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	10 checks without index, few with index
100	100 checks without index, few with index
1000	1000 checks without index, few with index

Pattern observation: Without index, operations grow directly with data size; with index, operations stay small even as data grows.

Final Time Complexity

Time Complexity: O(log n)

This means using an index lets MongoDB find data much faster, growing slowly as data grows.

Common Mistake

[X] Wrong: "Indexes always make queries instant, no matter what."

[OK] Correct: Some queries don't use indexes if fields aren't indexed or conditions don't match, so search can still scan many documents.

Interview Connect

Understanding how indexes affect query speed shows you know how databases handle data efficiently, a key skill for real projects.

Self-Check

"What if we changed the query to search on a field without an index? How would the time complexity change?"

Practice

1. What does the IXSCAN stage in MongoDB's explain('executionStats') output indicate?

easy

A. The query is updating documents.

B. The query is scanning all documents without an index.

C. The query is using an index to find documents.

D. The query has a syntax error.

Solution

1. Step 1: Understand the meaning of IXSCAN

   The IXSCAN stage means MongoDB is scanning an index to find matching documents.

2. Step 2: Compare with other stages

   If the query was scanning all documents, it would show a COLLSCAN stage instead.

3. Final Answer:

   The query is using an index to find documents. -> Option C

4. Quick Check:

   IXSCAN = index used [OK]

Hint: Look for IXSCAN in explain output to confirm index use [OK]

Common Mistakes:

• Confusing IXSCAN with COLLSCAN
• Assuming IXSCAN means a full collection scan
• Thinking IXSCAN means query error

2. Which of the following is the correct way to run an explain plan with execution stats for a MongoDB query on collection users?

easy

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

B. db.users.find({age: 25}).explain('executionStats')

C. db.users.explain('executionStats').find({age: 25})

D. db.users.find().explain('stats')

Solution

1. Step 1: Recall the correct syntax for explain

   The correct syntax is to call explain('executionStats') on the cursor returned by find().

2. Step 2: Check each option

   db.users.find({age: 25}).explain('executionStats') correctly calls find() then explain('executionStats'). db.users.explain('executionStats').find({age: 25}) calls explain before find, which is invalid. db.users.find({age: 25}).explain() calls explain without argument, which defaults to 'queryPlanner' not 'executionStats'. db.users.find().explain('stats') uses wrong argument 'stats'.

3. Final Answer:

   db.users.find({age: 25}).explain('executionStats') -> Option B

4. Quick Check:

   find().explain('executionStats') correct [OK]

Hint: Call explain on the find() cursor with 'executionStats' argument [OK]

Common Mistakes:

• Calling explain before find()
• Using wrong explain argument
• Omitting parentheses on find()

3. Given the index on { username: 1 } exists, what will the explain('executionStats') output stage be for this query?

db.users.find({username: 'alice'}).explain('executionStats')

medium

A. IXSCAN

B. COLLSCAN

C. FETCH

D. SORT

Solution

1. Step 1: Check if index matches query field

   The query filters on username, and an index on { username: 1 } exists, so MongoDB can use this index.

2. Step 2: Identify the explain stage for index use

   When an index is used, the explain output shows IXSCAN stage indicating index scan.

3. Final Answer:

   IXSCAN -> Option A

4. Quick Check:

   Index on username = IXSCAN [OK]

Hint: If query matches indexed field, expect IXSCAN stage [OK]

Common Mistakes:

• Expecting COLLSCAN despite index presence
• Confusing FETCH with index scan
• Assuming SORT appears without sort query

4. You run db.orders.find({status: 'shipped'}).explain('executionStats') but see COLLSCAN instead of IXSCAN. What is the most likely cause?

medium

A. The query syntax is incorrect.

B. The collection is empty.

C. MongoDB does not support indexes on string fields.

D. There is no index on the status field.

Solution

1. Step 1: Understand COLLSCAN meaning

   COLLSCAN means MongoDB scanned all documents because no suitable index was found.

2. Step 2: Identify cause for no index use

   If the query filters on status but no index exists on that field, MongoDB must scan the whole collection.

3. Final Answer:

   There is no index on the status field. -> Option D

4. Quick Check:

   COLLSCAN = no index on query field [OK]

Hint: COLLSCAN means no index matches query filter [OK]

Common Mistakes:

• Assuming syntax error causes COLLSCAN
• Believing MongoDB can't index strings
• Thinking empty collection causes COLLSCAN

5. You have a compound index on { category: 1, price: -1 }. Which query will use this index efficiently according to explain('executionStats')?

hard

A. db.products.find({category: 'books', price: 20}).sort({price: -1})

B. db.products.find({price: {$lt: 20}})

C. db.products.find({category: 'books'}).sort({price: 1})

D. db.products.find({category: 'books', price: {$lt: 20}})

Solution

1. Step 1: Understand compound index usage

   A compound index on { category: 1, price: -1 } can be used efficiently if the query filters on category first, then optionally on price, and the sort matches the index order.

2. Step 2: Analyze each query

   db.products.find({category: 'books', price: 20}).sort({price: -1}) filters on both category and price with equality and sorts price descending, matching the index order, so it uses the index efficiently. db.products.find({price: {$lt: 20}}) filters only on price, which is the second field, so index is not used efficiently. db.products.find({category: 'books'}).sort({price: 1}) sorts price ascending but index has price descending, so sort won't use index efficiently. db.products.find({category: 'books', price: {$lt: 20}}) filters on both but does not specify sort matching index order, so less efficient than A.

3. Final Answer:

   db.products.find({category: 'books', price: 20}).sort({price: -1}) -> Option A

4. Quick Check:

   Compound index needs prefix field filter and matching sort order [OK]

Hint: Filter on first index field and match sort order to use compound index efficiently [OK]

Common Mistakes:

• Filtering only on second index field
• Ignoring sort direction in compound index
• Assuming any filter uses compound index fully