Time Complexity: Compound index and field order
O(log n + m)
0
0
Compound index and field order in MongoDB - Time & Space Complexity
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?"