Hash partitioning for distribution in PostgreSQL - Time & Space Complexity

Time Complexity: Hash partitioning for distribution

O(1) + O(n/k)

Understanding Time Complexity

When we use hash partitioning in a database, we split data into parts based on a hash function. Understanding how this affects the time to find or insert data helps us see how well the system scales.

We want to know how the work grows as we add more data and partitions.

Scenario Under Consideration

Analyze the time complexity of this hash partitioning setup in PostgreSQL.

CREATE TABLE sales (
  id SERIAL PRIMARY KEY,
  customer_id INT,
  amount NUMERIC
) PARTITION BY HASH (customer_id);

CREATE TABLE sales_part_1 PARTITION OF sales FOR VALUES WITH (MODULUS 4, REMAINDER 0);
CREATE TABLE sales_part_2 PARTITION OF sales FOR VALUES WITH (MODULUS 4, REMAINDER 1);
CREATE TABLE sales_part_3 PARTITION OF sales FOR VALUES WITH (MODULUS 4, REMAINDER 2);
CREATE TABLE sales_part_4 PARTITION OF sales FOR VALUES WITH (MODULUS 4, REMAINDER 3);

This code creates a main table partitioned by hashing the customer_id into 4 parts.

Identify Repeating Operations

Look at what repeats when we search or insert data.

• Primary operation: The hash function calculation on customer_id to find the right partition.
• How many times: Once per query or insert, then a search inside one partition.

How Execution Grows With Input

As data grows, the hash function still runs once per operation, but each partition holds less data compared to one big table.

Input Size (n)	Approx. Operations
10	Hash once + search in ~2-3 rows
100	Hash once + search in ~25 rows
1000	Hash once + search in ~250 rows

Pattern observation: The hash step stays constant, but the search inside a partition grows roughly with the size of that partition, which is smaller than the whole data.

Final Time Complexity

Time Complexity: O(1) + O(n/k)

This means the hash calculation is constant time, and the search inside one partition grows with the size of that partition, which is total data divided by number of partitions.

Common Mistake

[X] Wrong: "Hash partitioning makes every query run in constant time regardless of data size."

[OK] Correct: The hash function is constant time, but searching inside the chosen partition still depends on how much data is in that partition.

Interview Connect

Understanding how hash partitioning affects query time shows you can think about data distribution and scaling. This skill helps you design systems that stay fast as data grows.

Self-Check

"What if we increased the number of partitions k? How would that change the time complexity for searching inside partitions?"

Practice

1. What is the main purpose of hash partitioning in PostgreSQL?

easy

A. To split data into parts using a hash function on a column

B. To sort data alphabetically in each partition

C. To store data only on one server

D. To encrypt data for security

Solution

1. Step 1: Understand hash partitioning concept

   Hash partitioning divides data by applying a hash function to a column value, distributing rows into partitions.

2. Step 2: Compare options with concept

   Only To split data into parts using a hash function on a column correctly describes this purpose; others describe unrelated features.

3. Final Answer:

   To split data into parts using a hash function on a column -> Option A

4. Quick Check:

   Hash partitioning = split data by hash [OK]

Hint: Hash partitioning splits data by hashing a column [OK]

Common Mistakes:

• Confusing hash partitioning with sorting
• Thinking it stores data on one server only
• Mixing partitioning with encryption

2. Which of the following is the correct syntax to create a hash partitioned table in PostgreSQL?

easy

A. CREATE TABLE sales PARTITION BY COLUMN (region);

B. CREATE TABLE sales PARTITION BY RANGE (region);

C. CREATE TABLE sales PARTITION BY LIST (region);

D. CREATE TABLE sales PARTITION BY HASH (region);

Solution

1. Step 1: Identify partitioning syntax

   PostgreSQL uses PARTITION BY HASH(column) to create hash partitions.

2. Step 2: Match syntax with options

   Only CREATE TABLE sales PARTITION BY HASH (region); uses PARTITION BY HASH correctly; others use different partition types or invalid syntax.

3. Final Answer:

   CREATE TABLE sales PARTITION BY HASH (region); -> Option D

4. Quick Check:

   Hash partition syntax = PARTITION BY HASH [OK]

Hint: Use PARTITION BY HASH(column) for hash partitioning [OK]

Common Mistakes:

• Using RANGE or LIST instead of HASH
• Writing PARTITION BY COLUMN which is invalid
• Omitting parentheses around column

3. Given the table definition:

CREATE TABLE users (id INT, name TEXT) PARTITION BY HASH (id);
CREATE TABLE users_p0 PARTITION OF users FOR VALUES WITH (MODULUS 4, REMAINDER 0);
CREATE TABLE users_p1 PARTITION OF users FOR VALUES WITH (MODULUS 4, REMAINDER 1);
CREATE TABLE users_p2 PARTITION OF users FOR VALUES WITH (MODULUS 4, REMAINDER 2);
CREATE TABLE users_p3 PARTITION OF users FOR VALUES WITH (MODULUS 4, REMAINDER 3);

Which partition will the row with id = 7 be stored in?

medium

A. users_p3

B. users_p1

C. users_p2

D. users_p0

Solution

1. Step 1: Calculate hash partition remainder

   Partition is chosen by (hash(id) % modulus). Assuming hash(id) = id for simplicity, 7 % 4 = 3.

2. Step 2: Match remainder to partition

   Remainder 3 corresponds to partition users_p3.

3. Final Answer:

   users_p3 -> Option A

4. Quick Check:

   7 % 4 = 3 -> users_p3 [OK]

Hint: Compute id % modulus to find partition remainder [OK]

Common Mistakes:

• Confusing remainder with modulus
• Using id directly without modulo
• Mixing partition numbers

4. You try to create a hash partition with this command:

CREATE TABLE orders_p0 PARTITION OF orders FOR VALUES WITH (MODULUS 3, REMAINDER 3);

What is the error in this statement?

medium

A. MODULUS must be a prime number

B. REMAINDER cannot be equal to or greater than MODULUS

C. Partition name must start with 'orders_'

D. FOR VALUES WITH is not valid syntax for hash partitions

Solution

1. Step 1: Understand modulus and remainder rules

   Remainder must be less than modulus because remainder is result of modulo operation.

2. Step 2: Check given values

   MODULUS is 3, REMAINDER is 3, which is invalid since remainder must be 0, 1, or 2.

3. Final Answer:

   REMAINDER cannot be equal to or greater than MODULUS -> Option B

4. Quick Check:

   Remainder < Modulus rule violated [OK]

Hint: Remainder must be less than modulus in partitions [OK]

Common Mistakes:

• Setting remainder equal to modulus
• Thinking modulus must be prime
• Misunderstanding syntax for hash partitions

5. You want to distribute a large logs table by hashing the user_id column into 5 partitions. Which of the following is the correct way to define the partitions?

hard

A. Create 5 partitions with MODULUS 6 and REMAINDER values from 0 to 5

B. Create 5 partitions with MODULUS 4 and REMAINDER values from 0 to 4

C. Create 5 partitions with MODULUS 5 and REMAINDER values from 0 to 4

D. Create 5 partitions with MODULUS 5 and REMAINDER values from 1 to 5

Solution

1. Step 1: Understand modulus and remainder for partitions

   MODULUS is total partitions count; REMAINDER ranges from 0 to MODULUS-1.

2. Step 2: Apply to 5 partitions

   MODULUS must be 5; REMAINDER values must be 0,1,2,3,4 for 5 partitions.

3. Final Answer:

   Create 5 partitions with MODULUS 5 and REMAINDER values from 0 to 4 -> Option C

4. Quick Check:

   Partitions = MODULUS 5, REMAINDER 0-4 [OK]

Hint: Use MODULUS = partitions count; REMAINDER from 0 to MODULUS-1 [OK]

Common Mistakes:

• Setting remainder range incorrectly
• Using wrong modulus number
• Starting remainder at 1 instead of 0