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?