Identifying missing indexes in MongoDB - Time & Space Complexity

Time Complexity: Identifying missing indexes

O(n)

Understanding Time Complexity

When we look for missing indexes in MongoDB, we want to understand how the time to find data grows as the data grows.

We ask: How does the search time change if we don't have the right index?

Scenario Under Consideration

Analyze the time complexity of the following MongoDB query without an index.

db.orders.find({ customerId: 12345 })

This query searches for all orders from a specific customer in the orders collection.

Identify Repeating Operations

Look at what repeats when the query runs without an index.

• 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 time to find matching orders grows too.

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 search time grows linearly with the number of documents when no index is used.

Common Mistake

[X] Wrong: "The database will find the data instantly even without indexes."

[OK] Correct: Without indexes, the database must look at every document, so it takes longer as data grows.

Interview Connect

Understanding how missing indexes affect query time helps you explain why indexes matter in real projects.

Self-Check

"What if we add an index on customerId? How would the time complexity change?"

Practice

1. What is the main reason to create indexes in MongoDB collections?

easy

A. To store more data in the database

B. To make queries run faster by helping MongoDB find data quickly

C. To backup the database automatically

D. To encrypt the data for security

Solution

1. Step 1: Understand the purpose of indexes

   Indexes are special data structures that help MongoDB quickly locate data without scanning the entire collection.

2. Step 2: Compare options with index purpose

   Only To make queries run faster by helping MongoDB find data quickly correctly states that indexes speed up queries by helping find data faster.

3. Final Answer:

   To make queries run faster by helping MongoDB find data quickly -> Option B

4. Quick Check:

   Indexes improve query speed = A [OK]

Hint: Indexes speed up data search, not storage or security [OK]

Common Mistakes:

• Thinking indexes store more data
• Confusing indexes with backups
• Assuming indexes encrypt data

2. Which MongoDB command lists all indexes on a collection named users?

easy

A. db.users.showIndexes()

B. db.users.getIndex()

C. db.users.findIndexes()

D. db.users.listIndexes()

Solution

1. Step 1: Recall the correct method to list indexes

   The correct MongoDB method to list indexes on a collection is listIndexes().

2. Step 2: Check each option's validity

   Only db.users.listIndexes() is a valid MongoDB command; others are incorrect or do not exist.

3. Final Answer:

   db.users.listIndexes() -> Option D

4. Quick Check:

   List indexes command = listIndexes() [OK]

Hint: Use listIndexes() to see all indexes on a collection [OK]

Common Mistakes:

• Using getIndex() which is not a MongoDB method
• Trying findIndexes() which does not exist
• Confusing showIndexes() with listIndexes()

3. Given the query db.orders.find({ customerId: 123 }) and the collection has no index on customerId, what will explain('executionStats') likely show?

medium

A. A COLLSCAN (collection scan) with high number of documents examined

B. An IXSCAN (index scan) using the customerId index

C. A syntax error because explain cannot be used here

D. No documents returned because no index exists

Solution

1. Step 1: Understand query behavior without index

   Without an index on customerId, MongoDB must scan the entire collection (COLLSCAN) to find matching documents.

2. Step 2: Interpret explain output

   The explain('executionStats') will show a COLLSCAN and a high number of documents examined, indicating no index was used.

3. Final Answer:

   A COLLSCAN (collection scan) with high number of documents examined -> Option A

4. Quick Check:

   No index means COLLSCAN = B [OK]

Hint: No index means full collection scan in explain output [OK]

Common Mistakes:

• Expecting an index scan without an index
• Thinking explain causes syntax error
• Assuming no documents returned without index

4. You notice a slow query on db.products.find({ category: 'books', price: { $lt: 20 } }). The collection has an index only on category. What is the best fix?

medium

A. Rewrite the query to remove the price filter

B. Remove the existing index on category

C. Add a compound index on { category: 1, price: 1 }

D. Add an index only on price

Solution

1. Step 1: Analyze existing index and query filters

   The query filters on both category and price, but only category is indexed, so the price filter is not optimized.

2. Step 2: Choose the best index to optimize query

   A compound index on { category: 1, price: 1 } allows MongoDB to efficiently filter by both fields, speeding up the query.

3. Final Answer:

   Add a compound index on { category: 1, price: 1 } -> Option C

4. Quick Check:

   Compound index matches query fields = D [OK]

Hint: Use compound indexes for queries filtering multiple fields [OK]

Common Mistakes:

• Removing useful indexes
• Adding index on only one field when query filters multiple
• Changing query to remove filters instead of indexing

5. A MongoDB collection logs has slow queries filtering by userId and sorting by timestamp. Which index best improves performance?

hard

A. A compound index on { userId: 1, timestamp: -1 }

B. An index on { timestamp: 1 }

C. An index on { userId: 1 }

D. No index needed; increase RAM instead

Solution

1. Step 1: Understand query pattern with filter and sort

   The query filters by userId and sorts by timestamp, so both fields affect performance.

2. Step 2: Select index that supports filter and sort

   A compound index on { userId: 1, timestamp: -1 } supports efficient filtering by userId and sorting by timestamp in descending order.

3. Final Answer:

   A compound index on { userId: 1, timestamp: -1 } -> Option A

4. Quick Check:

   Compound index matches filter and sort = C [OK]

Hint: Compound index with sort field improves filter + sort queries [OK]

Common Mistakes:

• Using single-field index ignoring sort
• Choosing wrong sort order in index
• Ignoring indexing and blaming hardware