Why distributed databases handle scale in DBMS Theory - Performance Analysis

Time Complexity: Why distributed databases handle scale

O(n / k)

Understanding Time Complexity

When databases grow large, how fast they handle data matters a lot.

We want to see how distributed databases manage more data and users efficiently.

Scenario Under Consideration

Analyze the time complexity of this simplified distributed query process.

-- Assume data is split across 3 servers
SELECT * FROM users WHERE age > 30;
-- Query runs on each server in parallel
-- Results are combined and returned
    

This shows a query running on multiple servers at once, then merging results.

Identify Repeating Operations

Look for repeated work done by the system.

• Primary operation: Each server scans its part of the data.
• How many times: Once per server, all running at the same time.

How Execution Grows With Input

As total data grows, it is split across servers, so each server handles approximately n/k data items.

Input Size (n)	Approx. Operations per Server
10,000	~3,333
100,000	~33,333
1,000,000	~333,333

Pattern observation: Total work grows with data size, but each server's work grows slower because data is shared.

Final Time Complexity

Time Complexity: O(n / k)

This means the work per server grows with data size divided by number of servers, so adding servers helps handle more data efficiently.

Common Mistake

[X] Wrong: "Adding more servers always makes queries instantly faster."

[OK] Correct: Some work like combining results or network delays still take time, so speed improves but not infinitely.

Interview Connect

Understanding how distributed databases split work helps you explain real systems that handle big data smoothly.

Self-Check

What if the data was not evenly split across servers? How would that affect the time complexity?

Practice

1. Why do distributed databases handle scale better than single-server databases?

easy

A. Because they spread data and workload across multiple machines

B. Because they use only one powerful computer

C. Because they store data in a single location

D. Because they limit the number of users accessing data

Solution

1. Step 1: Understand the concept of distributed databases

   Distributed databases store data on many computers instead of just one.

2. Step 2: Recognize how spreading data helps scale

   Spreading data and workload means many machines share the work, so the system can handle more data and users.

3. Final Answer:

   Because they spread data and workload across multiple machines -> Option A

4. Quick Check:

   Distributed databases = spread data/workload = better scale [OK]

Hint: Think: More machines share work, so system handles more [OK]

Common Mistakes:

• Thinking a single powerful computer is enough
• Believing data stored in one place scales well
• Assuming limiting users improves scaling

2. Which of the following is a correct reason why distributed databases improve reliability?

easy

A. They store all data on a single server

B. They replicate data across multiple nodes

C. They delete old data regularly

D. They restrict access to one user at a time

Solution

1. Step 1: Identify how reliability is improved in distributed systems

   Reliability means data is safe and accessible even if one machine fails.

2. Step 2: Understand data replication

   Replicating data means copying it to multiple machines, so if one fails, others still have the data.

3. Final Answer:

   They replicate data across multiple nodes -> Option B

4. Quick Check:

   Replication = data copies = better reliability [OK]

Hint: Replication means copies on many machines, so safer data [OK]

Common Mistakes:

• Thinking storing data on one server improves reliability
• Confusing deleting data with reliability
• Believing restricting users improves reliability

3. Consider a distributed database system with 4 nodes. If each node can handle 1000 queries per second, what is the total query capacity of the system?

medium

A. 250 queries per second

B. 1000 queries per second

C. 4000 queries per second

D. 5000 queries per second

Solution

1. Step 1: Understand capacity per node

   Each node can handle 1000 queries per second.

2. Step 2: Calculate total capacity by adding all nodes

   4 nodes x 1000 queries = 4000 queries per second total capacity.

3. Final Answer:

   4000 queries per second -> Option C

4. Quick Check:

   4 x 1000 = 4000 queries/sec [OK]

Hint: Multiply nodes by capacity per node for total [OK]

Common Mistakes:

• Using capacity of one node as total
• Dividing instead of multiplying
• Adding extra queries beyond node capacity

4. A distributed database is not scaling well. Which of the following is a likely cause?

medium

A. The database uses multiple machines

B. Data is replicated on all nodes

C. There are too many nodes handling queries

D. Data is not evenly distributed across nodes

Solution

1. Step 1: Identify what causes poor scaling

   Poor scaling happens if some nodes have too much data or work, causing bottlenecks.

2. Step 2: Understand uneven data distribution

   If data is not spread evenly, some nodes get overloaded while others are idle, hurting performance.

3. Final Answer:

   Data is not evenly distributed across nodes -> Option D

4. Quick Check:

   Uneven data = overloaded nodes = poor scaling [OK]

Hint: Check if data is balanced across nodes for good scale [OK]

Common Mistakes:

• Thinking more nodes always cause poor scaling
• Believing replication causes poor scaling
• Assuming multiple machines hurt scaling

5. A company wants to handle a sudden increase in users without slowing down their database. Which distributed database feature should they focus on to handle this scale?

hard

A. Adding more nodes to share the workload

B. Reducing data replication to save space

C. Storing all data on a single powerful server

D. Limiting user access during peak times

Solution

1. Step 1: Understand the need to handle more users

   More users mean more queries and data requests, requiring more processing power.

2. Step 2: Identify how distributed databases handle increased load

   Adding more nodes spreads the workload, so the system can handle more users without slowing down.

3. Final Answer:

   Adding more nodes to share the workload -> Option A

4. Quick Check:

   More nodes = shared workload = better scaling [OK]

Hint: Add nodes to share work and handle more users [OK]

Common Mistakes:

• Thinking reducing replication improves scaling
• Believing one powerful server can handle all load
• Assuming limiting users is the best scaling method