Choosing a good shard key in MongoDB - Time & Space Complexity

Time Complexity: Choosing a good shard key

O(m)

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?"

Practice

1. Which of the following is the most important characteristic of a good shard key in MongoDB?

easy

A. It is the smallest field in the document.

B. It is always a string type.

C. It has many unique values to distribute data evenly.

D. It contains only numeric values.

Solution

1. Step 1: Understand shard key purpose

   A shard key is used to split data across servers to balance load and improve speed.

2. Step 2: Identify key characteristic for even distribution

   A good shard key has many unique values to avoid data being stored unevenly on shards.

3. Final Answer:

   It has many unique values to distribute data evenly. -> Option C

4. Quick Check:

   Unique values = balanced shards [OK]

Hint: Choose shard keys with many unique values for balance [OK]

Common Mistakes:

• Thinking shard key must be string
• Choosing small fields regardless of uniqueness
• Assuming numeric only keys are best

2. Which of the following is the correct syntax to create a sharded collection with shard key { userId: 1 } in MongoDB?

easy

A. sh.shardCollection('mydb.users', 'userId')

B. db.shardCollection('users', { userId: 1 })

C. sh.shardCollection('users', { userId: 1 })

D. sh.shardCollection('mydb.users', { userId: 1 })

Solution

1. Step 1: Recall syntax for sharding a collection

   The correct command is sh.shardCollection(namespace, shardKey), where namespace is 'database.collection'.

2. Step 2: Match options to syntax

   sh.shardCollection('mydb.users', { userId: 1 }) uses full namespace 'mydb.users' and correct shard key object { userId: 1 }.

3. Final Answer:

   sh.shardCollection('mydb.users', { userId: 1 }) -> Option D

4. Quick Check:

   Full namespace + shard key object = correct syntax [OK]

Hint: Use full 'db.collection' name and shard key object [OK]

Common Mistakes:

• Using db.shardCollection instead of sh.shardCollection
• Passing shard key as string instead of object
• Omitting database name in namespace

3. Given a collection sharded on { country: 1 }, which query will benefit most from the shard key?

medium

A. db.users.find({ age: { $gt: 30 } })

B. db.users.find({ country: 'USA' })

C. db.users.find({ name: 'Alice' })

D. db.users.find({ city: 'New York' })

Solution

1. Step 1: Understand shard key usage in queries

   Queries that include the shard key field can target specific shards, improving speed.

2. Step 2: Identify query with shard key field

   Only db.users.find({ country: 'USA' }) filters by country, the shard key, so it benefits most.

3. Final Answer:

   db.users.find({ country: 'USA' }) -> Option B

4. Quick Check:

   Query includes shard key field = faster query [OK]

Hint: Queries with shard key filter run faster [OK]

Common Mistakes:

• Assuming any query runs faster on sharded collection
• Ignoring shard key field in query
• Confusing shard key with indexed fields

4. You created a shard key on { userId: 1 } but notice all data is stored on one shard. What is the likely cause?

medium

A. The userId field has low cardinality (few unique values).

B. The shard key was created with descending order { userId: -1 }.

C. The collection is not sharded yet.

D. The shard key field is missing in some documents.

Solution

1. Step 1: Understand shard key distribution

   If the shard key has few unique values, data will cluster on few shards causing imbalance.

2. Step 2: Analyze options

   Low cardinality of userId causes data to be stored on one shard, matching the problem.

3. Final Answer:

   The userId field has low cardinality (few unique values). -> Option A

4. Quick Check:

   Low uniqueness = data imbalance [OK]

Hint: Low unique shard key values cause data to cluster [OK]

Common Mistakes:

• Thinking shard key order affects distribution
• Assuming collection is not sharded without checking
• Ignoring missing shard key fields in documents

5. You have a large collection of orders with fields orderId, customerId, and orderDate. You want to shard to optimize queries filtering by customerId and range queries on orderDate. Which shard key is best?

hard

A. { customerId: 1, orderDate: 1 }

B. { orderDate: 1 }

C. { orderId: 1 }

D. { customerId: 1 }

Solution

1. Step 1: Identify query patterns

   Queries filter by customerId and also use range on orderDate.

2. Step 2: Choose shard key matching query patterns

   A compound shard key with { customerId: 1, orderDate: 1 } supports both equality and range queries efficiently.

3. Final Answer:

   { customerId: 1, orderDate: 1 } -> Option A

4. Quick Check:

   Compound shard key matches query filters [OK]

Hint: Use compound shard key for multiple query filters [OK]

Common Mistakes:

• Choosing single field shard key ignoring query patterns
• Using orderId which is not queried
• Not using compound keys for combined filters