Range-based sharding in MongoDB - Time & Space Complexity

Time Complexity: Range-based sharding

O(n)

Understanding Time Complexity

When using range-based sharding in MongoDB, we want to understand how the time to find and store data changes as the data grows.

We ask: How does the number of operations grow when the amount of data increases?

Scenario Under Consideration

Analyze the time complexity of a query on a range-sharded collection.

// Assume a collection sharded by a range key
// Query to find documents in a range
db.collection.find({ shardKey: { $gte: 100, $lt: 200 } })

This query fetches documents where the shard key is between 100 and 199, using range-based sharding.

Identify Repeating Operations

Look for repeated work done by the query.

• Primary operation: Scanning documents within the specified range on the relevant shard(s).
• How many times: The number of documents in the range determines how many times the scan happens.

How Execution Grows With Input

As the range size or data grows, the work grows roughly with how many documents match.

Input Size (n)	Approx. Operations
10	Scan about 10 documents
100	Scan about 100 documents
1000	Scan about 1000 documents

Pattern observation: The work grows linearly with the number of documents in the range.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows directly with how many documents are in the requested range.

Common Mistake

[X] Wrong: "Range queries on sharded collections always run in constant time because data is split."

[OK] Correct: Even though data is split, the query still scans all matching documents in the range, so time grows with the number of matches.

Interview Connect

Understanding how range-based sharding affects query time helps you explain real database behavior clearly and confidently.

Self-Check

"What if the query used an equality match on the shard key instead of a range? How would the time complexity change?"

Practice

1. What is the main idea behind range-based sharding in MongoDB?

easy

A. Data is randomly distributed across shards.

B. Data is split into ranges based on shard key values.

C. Data is duplicated on all shards for backup.

D. Data is stored only on a single shard.

Solution

1. Step 1: Understand range-based sharding concept

   Range-based sharding divides data into continuous ranges based on shard key values.

2. Step 2: Compare with other options

   Random distribution or duplication are not characteristics of range-based sharding.

3. Final Answer:

   Data is split into ranges based on shard key values. -> Option B

4. Quick Check:

   Range-based sharding = Data split by ranges [OK]

Hint: Remember: range-based means splitting by value ranges [OK]

Common Mistakes:

• Confusing range-based with hash-based sharding
• Thinking data is duplicated on all shards
• Assuming data is randomly distributed

2. Which of the following is the correct way to enable range-based sharding on a collection in MongoDB?

easy

A. sh.shardRangeCollection("db.collection", { "field": 1 })

B. sh.enableRangeSharding("db.collection")

C. db.collection.shardRange({ "field": 1 })

D. sh.shardCollection("db.collection", { "field": 1 })

Solution

1. Step 1: Recall MongoDB sharding command

   The correct command to shard a collection by a key is sh.shardCollection() with the shard key.

2. Step 2: Verify syntax correctness

   sh.shardCollection("db.collection", { "field": 1 }) uses the correct syntax: sh.shardCollection("db.collection", { "field": 1 }). Other options are invalid commands.

3. Final Answer:

   sh.shardCollection("db.collection", { "field": 1 }) -> Option D

4. Quick Check:

   Use sh.shardCollection() to enable sharding [OK]

Hint: Use sh.shardCollection() with shard key object [OK]

Common Mistakes:

• Using non-existent commands like sh.enableRangeSharding
• Incorrect method names like shardRangeCollection
• Passing wrong parameters or missing shard key

3. Given a collection sharded by the field age with ranges: { age: { $lt: 20 } }, { age: { $gte: 20, $lt: 40 } }, and { age: { $gte: 40 } }, which shard will store a document with { age: 35 }?

medium

A. Shard with range { age: { $gte: 20, $lt: 40 } }

B. Shard with range { age: { $lt: 20 } }

C. Shard with range { age: { $gte: 40 } }

D. Document will be stored on all shards

Solution

1. Step 1: Identify the correct range for age 35

   Age 35 fits in the range where age is greater or equal to 20 and less than 40.

2. Step 2: Match the range to the shard

   The shard with range { age: { $gte: 20, $lt: 40 } } will store the document.

3. Final Answer:

   Shard with range { age: { $gte: 20, $lt: 40 } } -> Option A

4. Quick Check:

   35 is between 20 and 40, so goes to that shard [OK]

Hint: Match value to shard range boundaries carefully [OK]

Common Mistakes:

• Choosing the shard with $lt: 20 incorrectly
• Assuming document is stored on all shards
• Confusing range boundaries (gte vs lt)

4. You have a range-based sharded collection on score with ranges: { score: { $lt: 50 } } and { score: { $gte: 50 } }. You try to insert { score: "high" } but get an error. What is the likely cause?

medium

A. The shard key ranges overlap causing conflict.

B. The shard key field is missing in the document.

C. The shard key value type does not match the defined range type.

D. MongoDB does not support string values in shard keys.

Solution

1. Step 1: Understand shard key type requirements

   Shard key values must match the type used in range definitions. Here, ranges expect numeric scores.

2. Step 2: Identify the error cause

   Inserting a string "high" for a numeric shard key causes a type mismatch error.

3. Final Answer:

   The shard key value type does not match the defined range type. -> Option C

4. Quick Check:

   Shard key types must match range types [OK]

Hint: Shard key values must match range data types [OK]

Common Mistakes:

• Assuming missing shard key field causes this error
• Thinking overlapping ranges cause insert errors
• Believing MongoDB disallows strings in shard keys

5. You want to shard a large user collection by signupDate using range-based sharding. Which shard key choice will best support queries filtering users by recent signup dates?

hard

A. Use { signupDate: 1 } as shard key to split by date ranges.

B. Use { userId: 1 } as shard key for even data distribution.

C. Use { signupDate: "hashed" } to hash dates for randomness.

D. Use { lastLogin: 1 } as shard key for login-based queries.

Solution

1. Step 1: Identify query pattern

   Queries filter users by recent signup dates, so shard key should support range queries on signupDate.

2. Step 2: Choose shard key matching query pattern

   Using { signupDate: 1 } enables range-based sharding by date, optimizing these queries.

3. Step 3: Evaluate other options

   Hashing or using unrelated fields won't support efficient range queries on signupDate.

4. Final Answer:

   Use { signupDate: 1 } as shard key to split by date ranges. -> Option A

5. Quick Check:

   Shard key matches query field for best performance [OK]

Hint: Match shard key to common query field for range queries [OK]

Common Mistakes:

• Choosing hashed shard key when range queries are needed
• Picking unrelated fields like userId or lastLogin
• Ignoring query patterns when selecting shard key