Time Complexity: Index intersection behavior
O(k * m)
0
0
Index intersection behavior in MongoDB - Time & Space Complexity
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?"