Index intersection behavior in MongoDB - Time & Space Complexity

Time Complexity: Index intersection behavior

O(k * m)

Understanding Time Complexity

When MongoDB uses multiple indexes together, it combines their results to find matching documents.

We want to understand how the work grows as the data and indexes get bigger.

Scenario Under Consideration

Analyze the time complexity of this MongoDB query using index intersection.

db.collection.createIndex({ fieldA: 1 })
db.collection.createIndex({ fieldB: 1 })

const query = { fieldA: 5, fieldB: 10 }
db.collection.find(query).explain("executionStats")
    

This query uses two separate indexes on fieldA and fieldB, then intersects their results to find documents matching both conditions.

Identify Repeating Operations

Look at what repeats when MongoDB uses index intersection.

• Primary operation: Scanning each index separately to find matching document IDs.
• How many times: Once per index involved (here, two indexes).
• Then intersecting the sets of document IDs found from each index.

How Execution Grows With Input

As the number of documents grows, each index scan takes longer, and intersecting larger sets takes more work.

Input Size (n)	Approx. Operations
10	Scan small sets from 2 indexes, intersect small sets
100	Scan larger sets from 2 indexes, intersect larger sets
1000	Scan much larger sets from 2 indexes, intersect much larger sets

Pattern observation: The work grows roughly with the size of the index results and the cost to intersect them.

Final Time Complexity

Time Complexity: O(k * m)

This means the time grows with the number of indexes used (k) times the size of the index results (m) that need to be scanned and intersected.

Common Mistake

[X] Wrong: "Using multiple indexes always makes queries faster because each index is small."

[OK] Correct: Sometimes the combined work of scanning multiple indexes and intersecting results can be more than scanning one good index, especially if indexes return many matches.

Interview Connect

Understanding how index intersection affects query time helps you explain real database behavior clearly and shows you think about efficiency in practical ways.

Self-Check

"What if we added a compound index on both fields instead of two single-field indexes? How would the time complexity change?"

Practice

1. What does index intersection in MongoDB allow the database to do?

easy

A. Combine multiple indexes to answer a single query

B. Create a new index automatically

C. Merge two collections into one

D. Delete unused indexes to save space

Solution

1. Step 1: Understand the purpose of index intersection

   Index intersection allows MongoDB to use more than one index together to satisfy a query efficiently.

2. Step 2: Differentiate from other index operations

   It does not create or delete indexes, nor merge collections; it only combines existing indexes for query optimization.

3. Final Answer:

   Combine multiple indexes to answer a single query -> Option A

4. Quick Check:

   Index intersection = combining indexes [OK]

Hint: Index intersection means using multiple indexes together [OK]

Common Mistakes:

• Thinking index intersection creates new indexes
• Confusing index intersection with collection merging
• Assuming it deletes indexes automatically

2. Which of the following is the correct way to check if MongoDB used index intersection for a query?

easy

A. Check the size of the indexes with db.collection.indexSize()

B. Run db.collection.stats() to see index usage

C. Use db.collection.aggregate() without any options

D. Use db.collection.find().explain() and look for indexIntersection in the plan

Solution

1. Step 1: Identify the method to analyze query plans

   The explain() method shows how MongoDB executes a query, including index usage.

2. Step 2: Look for index intersection details

   Within the explain output, the indexIntersection field indicates if multiple indexes were combined.

3. Final Answer:

   Use db.collection.find().explain() and look for indexIntersection in the plan -> Option D

4. Quick Check:

   Explain() shows index intersection [OK]

Hint: Use explain() to see index intersection in query plan [OK]

Common Mistakes:

• Using stats() which shows collection info, not query plan
• Running aggregate() without explain() does not show index use
• Checking index size does not reveal intersection

3. Given a collection with indexes on { age: 1 } and { city: 1 }, what will MongoDB do for this query?

db.users.find({ age: 30, city: "NY" })

medium

A. Use index intersection combining both age and city indexes

B. Use only the index on city

C. Use only the index on age

D. Perform a full collection scan ignoring indexes

Solution

1. Step 1: Analyze the query filter fields

   The query filters on both age and city, and there are separate indexes on each field.

2. Step 2: Understand MongoDB's index intersection behavior

   MongoDB can combine these two indexes to efficiently find documents matching both conditions using index intersection.

3. Final Answer:

   Use index intersection combining both age and city indexes -> Option A

4. Quick Check:

   Query on two indexed fields = index intersection [OK]

Hint: Multiple single-field indexes on query fields trigger index intersection [OK]

Common Mistakes:

• Assuming MongoDB uses only one index per query
• Thinking MongoDB always does full scan if multiple indexes exist
• Confusing index intersection with compound indexes

4. You wrote this query:

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

Indexes exist on { category: 1 } and { price: 1 }. But explain() shows no index intersection used. What is a likely cause?

medium

A. MongoDB does not support index intersection on range queries

B. MongoDB prefers a single index that covers both fields if available

C. The query syntax is incorrect for index intersection

D. Index intersection only works with compound indexes

Solution

1. Step 1: Understand MongoDB's index selection logic

   MongoDB chooses the most efficient index plan. If a single index covers both fields, it prefers that over intersection.

2. Step 2: Consider the indexes present

   Since only single-field indexes exist, MongoDB may pick one index if it estimates it is more efficient than combining both.

3. Final Answer:

   MongoDB prefers a single index that covers both fields if available -> Option B

4. Quick Check:

   MongoDB picks best index, not always intersection [OK]

Hint: MongoDB picks best index plan, not always intersection [OK]

Common Mistakes:

• Believing index intersection requires compound indexes
• Thinking query syntax disables index intersection
• Assuming range queries never use index intersection

5. You have a collection with indexes:

{ author: 1 }, { year: 1 }, { genre: 1 }

To optimize this query:

db.books.find({ author: "Alice", year: 2020, genre: "fiction" })

Which index strategy will most likely improve performance using index intersection?

hard

A. Create a compound index on { author: 1, year: 1, genre: 1 }

B. Keep single-field indexes and let MongoDB intersect them

C. Create compound indexes on pairs like { author: 1, year: 1 } and { genre: 1 }

D. Drop all indexes and create a single index on { author: 1 }

Solution

1. Step 1: Understand index intersection limits

   MongoDB can combine multiple single-field indexes, but compound indexes on multiple fields are often more efficient.

2. Step 2: Evaluate index strategies

   A full compound index on all three fields is best but costly to maintain; compound indexes on pairs plus a single index can help MongoDB intersect efficiently.

3. Step 3: Compare options

   Create compound indexes on pairs like { author: 1, year: 1 } and { genre: 1 } creates compound indexes on pairs, enabling better intersection than only single-field indexes, improving query speed without full compound index overhead.

4. Final Answer:

   Create compound indexes on pairs like { author: 1, year: 1 } and { genre: 1 } -> Option C

5. Quick Check:

   Compound pairs + intersection = better performance [OK]

Hint: Compound indexes on pairs plus single indexes improve intersection [OK]

Common Mistakes:

• Assuming only single-field indexes are enough
• Dropping indexes reduces performance
• Believing full compound index is always best