Sharding and partitioning in DBMS Theory - Time & Space Complexity

Time Complexity: Sharding and partitioning

O(n/k)

Understanding Time Complexity

When we split a large database into smaller parts, it helps us handle data faster. We want to know how this splitting affects the time it takes to find or store data.

How does dividing data into shards or partitions change the work needed as data grows?

Scenario Under Consideration

Analyze the time complexity of querying data in a sharded database.

-- Assume data is split into 4 shards
SELECT * FROM users WHERE user_id = 12345;
-- Query is routed to one shard based on user_id
-- Each shard holds roughly n/4 records

This query looks for a user in one shard instead of the whole database.

Identify Repeating Operations

Look at what repeats when searching data.

• Primary operation: Searching records in one shard.
• How many times: Once per query, but only in one shard, not all.

How Execution Grows With Input

As total data grows, each shard holds less data compared to searching all data at once.

Input Size (n)	Approx. Operations per Shard
10,000	2,500
100,000	25,000
1,000,000	250,000

Pattern observation: Operations grow with data size but are divided by the number of shards, reducing work per query.

Final Time Complexity

Time Complexity: O(n/k)

This means the time to search grows with data size but is divided by the number of shards, making each search faster.

Common Mistake

[X] Wrong: "Sharding always makes queries instant regardless of data size."

[OK] Correct: Sharding reduces data per search but the time still grows as total data grows; it just grows slower.

Interview Connect

Understanding how splitting data affects search time shows you can design systems that handle growth well. This skill helps you explain how big systems stay fast as they get bigger.

Self-Check

"What if we increased the number of shards as data grows? How would that change the time complexity?"

Practice

1. What is the main difference between sharding and partitioning in databases?

easy

A. Sharding divides data within one database; partitioning spreads data across multiple servers.

B. Partitioning divides data within one database; sharding spreads data across multiple servers.

C. Both sharding and partitioning mean the same and are used interchangeably.

D. Partitioning is used only for backups, while sharding is for data security.

Solution

1. Step 1: Understand partitioning

   Partitioning splits data inside a single database into smaller parts for easier management and faster queries.

2. Step 2: Understand sharding

   Sharding spreads data across multiple servers or machines to handle very large datasets and improve performance.

3. Final Answer:

   Partitioning divides data within one database; sharding spreads data across multiple servers. -> Option B

4. Quick Check:

   Partitioning = single database, Sharding = multiple servers [OK]

Hint: Partitioning = one DB; Sharding = many servers [OK]

Common Mistakes:

• Confusing sharding with partitioning
• Thinking both are the same
• Assuming partitioning involves multiple servers

2. Which of the following is a correct way to describe horizontal partitioning in a database?

easy

A. Splitting a table into multiple tables with the same columns but different rows.

B. Splitting a table into multiple tables with different columns but same rows.

C. Combining multiple tables into one large table.

D. Backing up the entire database to a separate server.

Solution

1. Step 1: Define horizontal partitioning

   Horizontal partitioning means dividing a table by rows, so each partition has the same columns but different sets of rows.

2. Step 2: Check options

   Splitting a table into multiple tables with the same columns but different rows. matches this definition exactly, while others describe different concepts or unrelated actions.

3. Final Answer:

   Splitting a table into multiple tables with the same columns but different rows. -> Option A

4. Quick Check:

   Horizontal partitioning = split rows [OK]

Hint: Horizontal partitioning splits rows, not columns [OK]

Common Mistakes:

• Mixing horizontal with vertical partitioning
• Thinking partitioning means backup
• Confusing rows with columns

3. Consider a database sharded by user ID across three servers: Server 1 stores users with IDs ending in 0-3, Server 2 stores 4-6, and Server 3 stores 7-9. If a query requests data for user ID 27, which server will handle the request?

medium

A. Server 3

B. Server 2

C. Server 1

D. All servers

Solution

1. Step 1: Identify the shard key and ranges

   The sharding is based on the last digit of user ID: 0-3 on Server 1, 4-6 on Server 2, 7-9 on Server 3.

2. Step 2: Find the last digit of user ID 27

   The last digit of 27 is 7, which falls in the 7-9 range assigned to Server 3.

3. Final Answer:

   Server 3 -> Option A

4. Quick Check:

   User ID 27 ends with 7, so Server 3 [OK]

Hint: Check last digit of ID to find server [OK]

Common Mistakes:

• Ignoring the last digit and guessing server
• Choosing all servers instead of one
• Mixing up the shard ranges

4. A database administrator tries to shard a database but notices that some shards have much more data than others, causing slow queries. What is the most likely problem?

medium

A. The backup process is running during queries.

B. The database is not partitioned vertically.

C. The database server hardware is outdated.

D. The shard key is not chosen properly, causing uneven data distribution.

Solution

1. Step 1: Understand shard key role

   The shard key determines how data is split across shards. A poor choice can cause uneven data distribution.

2. Step 2: Analyze the problem

   Uneven shard sizes causing slow queries usually mean the shard key is not distributing data evenly.

3. Final Answer:

   The shard key is not chosen properly, causing uneven data distribution. -> Option D

4. Quick Check:

   Uneven shards = bad shard key choice [OK]

Hint: Uneven shards? Check shard key choice [OK]

Common Mistakes:

• Blaming hardware without checking shard key
• Confusing sharding with partitioning issues
• Ignoring data distribution patterns

5. You have a large customer database that is partitioned by region within a single server. To improve performance and handle growth, you want to shard the data across multiple servers. Which approach best combines partitioning and sharding?

hard

A. Use only partitioning by region on one server; sharding is unnecessary.

B. Partition the database by customer type across servers, and shard data by region within each server.

C. Shard the database by region across servers, and within each server, partition data by customer type.

D. Backup the database regularly instead of sharding or partitioning.

Solution

1. Step 1: Understand combining sharding and partitioning

   Sharding splits data across servers; partitioning splits data inside each server for better management.

2. Step 2: Analyze the best approach

   Sharding by region spreads data geographically, and partitioning by customer type inside each shard improves query speed and organization.

3. Final Answer:

   Shard the database by region across servers, and within each server, partition data by customer type. -> Option C

4. Quick Check:

   Shard by region, partition by type inside servers [OK]

Hint: Shard first, then partition inside shards [OK]

Common Mistakes:

• Mixing up shard and partition levels
• Ignoring partitioning after sharding
• Thinking backup replaces sharding