Compound index and field order in MongoDB - Time & Space Complexity

Time Complexity: Compound index and field order

O(log n + m)

Understanding Time Complexity

When using compound indexes in MongoDB, the order of fields affects how fast queries run.

We want to understand how the query speed changes as data grows, depending on field order.

Scenario Under Consideration

Analyze the time complexity of this MongoDB query using a compound index.

    db.collection.createIndex({ age: 1, score: -1 })
    db.collection.find({ age: 25, score: { $gt: 80 } })
    

This code creates a compound index on age and score, then queries documents with age 25 and score greater than 80.

Identify Repeating Operations

Look at what repeats when MongoDB uses this index to find matching documents.

• Primary operation: Scanning index entries for matching age and score.
• How many times: Once per matching age value, then scanning score values in order.

How Execution Grows With Input

As the number of documents grows, the index helps limit how many entries we check.

Input Size (n)	Approx. Operations
10	Few index entries scanned for age=25, then score filtered quickly
100	More entries for age=25, but still efficient due to index order
1000	Still scanning only entries with age=25, score range scanned grows with matches

Pattern observation: The query scans a small subset of the index, growing mostly with matching score values for the fixed age.

Final Time Complexity

Time Complexity: O(log n + m)

This means MongoDB quickly finds the start point in the index (log n), then scans matching entries (m) for the score condition.

Common Mistake

[X] Wrong: "Changing the order of fields in the compound index does not affect query speed."

[OK] Correct: The order controls how MongoDB can use the index to filter quickly; wrong order can cause full scans or ignore parts of the index.

Interview Connect

Understanding how compound index order affects query speed shows you know how databases handle data efficiently, a key skill for real projects.

Self-Check

"What if we reversed the index to { score: -1, age: 1 }? How would the time complexity change for the same query?"

Practice

1. What does a compound index in MongoDB do?

easy

A. Speeds up queries that filter or sort on multiple fields together

B. Stores data in multiple collections

C. Automatically backs up the database

D. Encrypts data for security

Solution

1. Step 1: Understand what an index is

   An index helps MongoDB find data faster by organizing it.

2. Step 2: Understand compound index purpose

   A compound index uses more than one field to speed up queries that use those fields together.

3. Final Answer:

   Speeds up queries that filter or sort on multiple fields together -> Option A

4. Quick Check:

   Compound index = Speeds up multi-field queries [OK]

Hint: Compound index = multiple fields speed up queries [OK]

Common Mistakes:

• Thinking it stores data in multiple collections
• Confusing with backup or encryption features
• Believing it only indexes one field

2. Which is the correct way to create a compound index on fields age ascending and score descending in MongoDB?

easy

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

B. db.collection.createIndex({ age: -1, score: 1 })

C. db.collection.createIndex(["age", "score"])

D. db.collection.createIndex({ age: 'asc', score: 'desc' })

Solution

1. Step 1: Recall syntax for createIndex

   MongoDB uses an object with field names and 1 or -1 for ascending/descending.

2. Step 2: Match field order and directions

   Age ascending is 1, score descending is -1, so { age: 1, score: -1 } is correct.

3. Final Answer:

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

4. Quick Check:

   Use 1/-1 for asc/desc in object [OK]

Hint: Use {field: 1/-1} object for compound index [OK]

Common Mistakes:

• Using array instead of object for fields
• Using strings like 'asc' or 'desc' instead of 1/-1
• Mixing ascending and descending incorrectly

3. Given a compound index on { city: 1, rating: -1 }, which query will use the index efficiently?

medium

A. db.collection.find({ rating: { $gt: 4 } })

B. db.collection.find({ city: 'NYC' }).sort({ rating: 1 })

C. db.collection.find({ city: 'NYC' }).sort({ rating: -1 })

D. db.collection.find({ rating: -1, city: 'NYC' })

Solution

1. Step 1: Understand index field order and directions

   The index is on city ascending, then rating descending.

2. Step 2: Check query filter and sort usage

   Query B filters on city (first field) and sorts rating descending (matching index direction).

3. Final Answer:

   db.collection.find({ city: 'NYC' }).sort({ rating: -1 }) -> Option C

4. Quick Check:

   Filter first field, sort second field matching index [OK]

Hint: Filter first field, sort second field matching index order [OK]

Common Mistakes:

• Sorting rating ascending when index is descending
• Filtering only on rating without city
• Ignoring field order in index

4. You created a compound index { a: 1, b: 1 } but your query { b: 5 } is slow. What is the likely issue?

medium

A. MongoDB does not support compound indexes

B. The query does not filter on the first indexed field a

C. The index fields are in wrong order; should be { b: 1, a: 1 }

D. The index must use -1 for descending order

Solution

1. Step 1: Recall how compound indexes work

   Compound indexes work best when queries filter on the first field in the index.

2. Step 2: Analyze query filter

   The query filters only on b, the second field, so index on a then b is not used efficiently.

3. Final Answer:

   The query does not filter on the first indexed field a -> Option B

4. Quick Check:

   Filter must include first index field [OK]

Hint: Query must filter first indexed field to use compound index [OK]

Common Mistakes:

• Thinking MongoDB doesn't support compound indexes
• Believing field order doesn't matter
• Assuming descending order is always required

5. You want to optimize queries filtering by category and sorting by price ascending. Which compound index is best?

hard

A. db.collection.createIndex({ price: -1, category: 1 })

B. db.collection.createIndex({ price: 1, category: 1 })

C. db.collection.createIndex({ category: -1, price: -1 })

D. db.collection.createIndex({ category: 1, price: 1 })

Solution

1. Step 1: Identify query pattern

   Queries filter by category and sort by price ascending.

2. Step 2: Choose index field order and direction

   Index should have category first (filter), then price ascending (sort) to match query.

3. Final Answer:

   db.collection.createIndex({ category: 1, price: 1 }) -> Option D

4. Quick Check:

   Filter field first, sort field second with matching order [OK]

Hint: Filter field first, sort field second with matching order [OK]

Common Mistakes:

• Putting sort field before filter field in index
• Using descending order when query sorts ascending
• Ignoring field order importance