Time Complexity: Partial indexes with filter
O(m)
0
0
Partial indexes with filter in MongoDB - Time & Space Complexity
Understanding Time Complexity
When using partial indexes with filters in MongoDB, we want to know how fast queries run as data grows.
We ask: How does the filter affect the number of operations MongoDB does?
Scenario Under Consideration
Analyze the time complexity of the following MongoDB partial index creation and query.
db.orders.createIndex(
{ status: 1 },
{ partialFilterExpression: { status: { $eq: "pending" } } }
)
db.orders.find({ status: "pending" })
This code creates an index only on documents where status is "pending" and then queries those documents.
Identify Repeating Operations
Look for repeated work MongoDB does when using this partial index.
- Primary operation: Scanning the partial index entries matching the filter.
- How many times: Once per matching document with status "pending".
How Execution Grows With Input
As the number of "pending" documents grows, the work grows too, but only for those documents.
| Input Size (m) | Approx. Operations |
|---|---|
| 10 (pending docs) | About 10 index lookups |
| 100 (pending docs) | About 100 index lookups |
| 1000 (pending docs) | About 1000 index lookups |
Pattern observation: The cost grows linearly with the number of documents matching the filter, not total documents.
Final Time Complexity
Time Complexity: O(m)
This means the query time grows in a straight line with the number of documents that match the filter, not all documents.
Common Mistake
[X] Wrong: "The partial index speeds up queries on all documents equally."
[OK] Correct: The partial index only covers documents matching the filter, so queries on other documents don't benefit from it.
Interview Connect
Understanding how partial indexes limit work to relevant data shows you can write efficient queries and indexes that scale well.
Self-Check
"What if we changed the filter to include more fields? How would that affect the time complexity?"