Time Complexity: Choosing a good shard key
O(m)
0
0
Choosing a good shard key in MongoDB - Time & Space Complexity
Understanding Time Complexity
When we choose a shard key in MongoDB, it affects how fast queries run as data grows.
We want to know how the choice of shard key changes the work needed to find data.
Scenario Under Consideration
Analyze the time complexity of querying a sharded collection using a shard key.
// Assume a sharded collection with shard key "userId"
// Query to find documents for a specific userId
const result = db.collection.find({ userId: 12345 });
This query uses the shard key to target a specific shard and find matching documents.
Identify Repeating Operations
Look at what repeats when the query runs:
- Primary operation: Searching documents on one shard by userId.
- How many times: The search happens once on the targeted shard, scanning matching documents.
How Execution Grows With Input
As the total data grows, the query only looks at one shard thanks to the shard key.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 documents on one shard |
| 100 | About 100 documents on one shard |
| 1000 | About 1000 documents on one shard |
Pattern observation: The work grows with the number of documents on the shard, not the whole database.
Final Time Complexity
Time Complexity: O(m)
This means the query time grows with the number of documents on the shard holding the key, not the total data.
Common Mistake
[X] Wrong: "Choosing any shard key will make queries fast everywhere."
[OK] Correct: If the shard key is not selective or balanced, queries may hit many shards or scan large parts, slowing down.
Interview Connect
Understanding shard keys helps you design databases that stay fast as they grow, a key skill for real projects.
Self-Check
"What if we changed the shard key to a field with many repeated values? How would the time complexity change?"