Mongos router behavior in MongoDB - Time & Space Complexity

Time Complexity: Mongos router behavior

O(s)

Understanding Time Complexity

When using MongoDB sharding, the mongos router directs queries to the right shards. Understanding how the time to process queries grows helps us see how well the system scales.

We want to know how the mongos router's work changes as the data and shards grow.

Scenario Under Consideration

Analyze the time complexity of the following mongos routing logic.

// Simplified mongos routing logic
function routeQuery(query) {
  const shardKeys = getShardKeys(query);
  const targetShards = findShards(shardKeys); // lookup shards
  const results = [];
  for (const shard of targetShards) {
    results.push(sendQueryToShard(shard, query));
  }
  return mergeResults(results);
}
    

This code finds which shards to query based on shard keys, sends the query to each shard, and merges the results.

Identify Repeating Operations

Look for repeated steps that take time as input grows.

• Primary operation: Looping over each shard to send the query and collect results.
• How many times: Once for each shard involved in the query.

How Execution Grows With Input

As the number of shards involved grows, the router must send queries to more places.

Input Size (number of shards)	Approx. Operations (queries sent)
10	10
100	100
1000	1000

Pattern observation: The work grows directly with the number of shards the query touches.

Final Time Complexity

Time Complexity: O(s)

This means the router's work grows linearly with the number of shards involved in the query.

Common Mistake

[X] Wrong: "The mongos router always takes the same time no matter how many shards are involved."

[OK] Correct: The router must send queries to each shard involved, so more shards mean more work and longer time.

Interview Connect

Understanding how mongos routing scales helps you explain distributed query behavior clearly. This skill shows you grasp how systems handle growing data and complexity.

Self-Check

What if the query targets only one shard instead of many? How would the time complexity change?

Practice

1. What is the primary role of the mongos router in a sharded MongoDB cluster?

easy

A. It stores the actual data for the database.

B. It routes queries to the correct shard based on the shard key.

C. It manages user authentication and roles.

D. It backs up the database automatically.

Solution

1. Step 1: Understand mongos role

   The mongos acts as a query router in a sharded cluster, directing queries to the right shard.

2. Step 2: Differentiate from other components

   Data storage is handled by shards, not mongos. Authentication and backups are separate concerns.

3. Final Answer:

   It routes queries to the correct shard based on the shard key. -> Option B

4. Quick Check:

   mongos routes queries [OK]

Hint: Remember: mongos routes, shards store data [OK]

Common Mistakes:

• Thinking mongos stores data
• Confusing mongos with config servers
• Assuming mongos handles backups

2. Which of the following is the correct way for an application to connect in a sharded MongoDB setup?

easy

A. Connect to the primary replica set member.

B. Connect only to the config servers.

C. Connect directly to each shard individually.

D. Connect to the mongos router.

Solution

1. Step 1: Identify connection point in sharded cluster

   Applications connect to mongos which routes queries to shards transparently.

2. Step 2: Exclude other options

   Direct connection to shards or config servers is not recommended; primary replica set member is for replica sets, not sharding.

3. Final Answer:

   Connect to the mongos router. -> Option D

4. Quick Check:

   Apps connect to mongos [OK]

Hint: Always connect apps to mongos, not shards [OK]

Common Mistakes:

• Connecting directly to shards
• Using config servers for queries
• Confusing replica sets with sharding

3. Given a sharded cluster with two shards and a mongos router, what will happen when you run this query through mongos?

db.users.find({ userId: 12345 })

Assume userId is the shard key.

medium

A. mongos returns an error because shard key is missing.

B. mongos sends the query to all shards and merges results.

C. mongos routes the query only to the shard containing userId 12345.

D. mongos sends the query to the config servers.

Solution

1. Step 1: Check query uses shard key

   The query filters on userId, which is the shard key, so mongos can route precisely.

2. Step 2: Understand mongos routing behavior

   mongos sends the query only to the shard that holds the chunk for userId 12345, not all shards.

3. Final Answer:

   mongos routes the query only to the shard containing userId 12345. -> Option C

4. Quick Check:

   Query with shard key routes to one shard [OK]

Hint: Query with shard key goes to one shard only [OK]

Common Mistakes:

• Assuming mongos queries all shards always
• Thinking config servers handle queries
• Believing shard key is optional for routing

4. You wrote a query to find documents by userId in a sharded cluster but get slow results. You realize userId is not the shard key. What is the likely cause?

medium

A. mongos is routing the query to all shards (scatter-gather).

B. mongos is routing the query to only one shard.

C. mongos is ignoring the query and returning empty results.

D. mongos is connecting directly to config servers.

Solution

1. Step 1: Identify shard key usage in query

   The query filters on userId, which is not the shard key, so mongos cannot route precisely.

2. Step 2: Understand mongos scatter-gather behavior

   mongos sends the query to all shards (scatter-gather) causing slower results.

3. Final Answer:

   mongos is routing the query to all shards (scatter-gather). -> Option A

4. Quick Check:

   Query without shard key causes scatter-gather [OK]

Hint: Queries without shard key hit all shards, slowing response [OK]

Common Mistakes:

• Assuming query routes to one shard without shard key
• Thinking mongos returns empty results on missing shard key
• Confusing config servers with query routers

5. In a sharded MongoDB cluster, you want to optimize query performance for a collection frequently queried by email. The current shard key is userId. What is the best approach involving mongos behavior?

hard

A. Change the shard key to email so mongos routes queries efficiently.

B. Add an index on email and keep the shard key as userId.

C. Connect directly to shards to bypass mongos routing.

D. Disable sharding on the collection to improve query speed.

Solution

1. Step 1: Analyze query pattern and shard key

   Queries are frequent on email, but shard key is userId, causing scatter-gather queries via mongos.

2. Step 2: Optimize shard key for routing

   Changing shard key to email lets mongos route queries directly to relevant shards, improving performance.

3. Final Answer:

   Change the shard key to email so mongos routes queries efficiently. -> Option A

4. Quick Check:

   Shard key matches query field for efficient mongos routing [OK]

Hint: Match shard key to frequent query field for fast mongos routing [OK]

Common Mistakes:

• Thinking adding index alone fixes routing
• Connecting directly to shards bypasses mongos is not recommended
• Disabling sharding reduces scalability