Partition types (range, list, hash) in PostgreSQL - Time & Space Complexity

Time Complexity: Partition types (range, list, hash)

O(n) for range/list, O(1) for hash

Understanding Time Complexity

When using partitions in a database, it is important to understand how the time to find data grows as the table gets bigger.

We want to know how different partition types affect the speed of searching and inserting data.

Scenario Under Consideration

Analyze the time complexity of querying data from a partitioned table using different partition types.

-- Create a range partitioned table
CREATE TABLE sales (
  id SERIAL PRIMARY KEY,
  sale_date DATE NOT NULL,
  amount NUMERIC
) PARTITION BY RANGE (sale_date);

-- Create partitions for each year
CREATE TABLE sales_2022 PARTITION OF sales
  FOR VALUES FROM ('2022-01-01') TO ('2023-01-01');

CREATE TABLE sales_2023 PARTITION OF sales
  FOR VALUES FROM ('2023-01-01') TO ('2024-01-01');

-- Query data for a specific date
SELECT * FROM sales WHERE sale_date = '2023-06-15';

This code sets up a range partition on sale_date and queries data for one date.

Identify Repeating Operations

Look at what repeats when the database searches or inserts data.

• Primary operation: Checking which partition holds the data by comparing partition keys.
• How many times: Depends on the number of partitions; the system checks partitions until it finds the right one.

How Execution Grows With Input

As the number of partitions grows, the time to find the right partition changes differently for each type.

Input Size (Partitions)	Range/List Partition Checks	Hash Partition Checks
10	Up to 10 checks	1 check (direct)
100	Up to 100 checks	1 check (direct)
1000	Up to 1000 checks	1 check (direct)

Pattern observation: Range and list partitions may require checking many partitions, growing linearly with the number of partitions. Hash partitions use a formula to jump directly to the right partition, so checks stay constant.

Final Time Complexity

Time Complexity: O(n) for range and list partitions, O(1) for hash partitions

This means range and list partitions take longer as partitions increase, but hash partitions find data quickly no matter how many partitions exist.

Common Mistake

[X] Wrong: "All partition types find data equally fast regardless of partition count."

[OK] Correct: Range and list partitions may need to check many partitions one by one, so their search time grows with more partitions. Hash partitions use a direct calculation to find the right partition quickly.

Interview Connect

Understanding how partition types affect query speed helps you design databases that stay fast as data grows. This skill shows you can think about real-world data challenges and choose the right tools.

Self-Check

"What if we added an index on the partition key columns? How would that affect the time complexity of searching within partitions?"

Practice

1. Which partition type in PostgreSQL is best suited for dividing a table based on continuous ranges of values, such as dates or numbers?

easy

A. HASH partitioning

B. LIST partitioning

C. RANGE partitioning

D. NONE partitioning

Solution

1. Step 1: Understand partition types

   RANGE partitions split data into continuous ranges, like dates or numeric intervals.

2. Step 2: Match partition type to use case

   Since the question asks about continuous ranges, RANGE partitioning fits best.

3. Final Answer:

   RANGE partitioning -> Option C

4. Quick Check:

   Continuous ranges = RANGE partitioning [OK]

Hint: Continuous values? Choose RANGE partitioning [OK]

Common Mistakes:

• Confusing LIST with RANGE for continuous data
• Thinking HASH is for ordered ranges
• Assuming NONE is a valid partition type

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

easy

A. CREATE TABLE sales (id INT, region TEXT) PARTITION BY LIST (region);

B. CREATE TABLE sales PARTITION BY LIST region (id INT, region TEXT);

C. CREATE TABLE sales (id INT, region TEXT) PARTITION BY RANGE (region);

D. CREATE TABLE sales (id INT, region TEXT) PARTITION BY HASH (region);

Solution

1. Step 1: Identify correct PARTITION BY syntax

   PostgreSQL syntax requires PARTITION BY followed by partition type and column in parentheses after table columns.

2. Step 2: Check each option

   CREATE TABLE sales (id INT, region TEXT) PARTITION BY LIST (region); uses correct syntax: columns first, then PARTITION BY LIST (region). Options A, B, C have syntax errors or wrong partition type.

3. Final Answer:

   CREATE TABLE sales (id INT, region TEXT) PARTITION BY LIST (region); -> Option A

4. Quick Check:

   Correct syntax = CREATE TABLE sales (id INT, region TEXT) PARTITION BY LIST (region); [OK]

Hint: PARTITION BY type (column) after columns [OK]

Common Mistakes:

• Placing PARTITION BY before column definitions
• Using wrong partition type for LIST
• Missing parentheses around partition column

3. Given the following partitioned table and inserts:

CREATE TABLE orders (
  order_id INT,
  order_date DATE
) PARTITION BY RANGE (order_date);

CREATE TABLE orders_2023 PARTITION OF orders
  FOR VALUES FROM ('2023-01-01') TO ('2024-01-01');

INSERT INTO orders VALUES (1, '2023-06-15');
INSERT INTO orders VALUES (2, '2022-12-31');

What will happen when the second insert is executed?

medium

A. The row is inserted into orders_2023 partition

B. The row is rejected with a constraint violation error

C. The row is inserted into a default partition automatically

D. The row is inserted into the parent table without partition

Solution

1. Step 1: Understand RANGE partition boundaries

   The orders_2023 partition accepts dates from 2023-01-01 up to but not including 2024-01-01.

2. Step 2: Check the inserted date '2022-12-31'

   This date is before the partition range, so no matching partition exists for it.

3. Step 3: Behavior on no matching partition

   PostgreSQL rejects inserts that don't fit any partition unless a default partition exists (none here).

4. Final Answer:

   The row is rejected with a constraint violation error -> Option B

5. Quick Check:

   Out-of-range insert = error [OK]

Hint: Out-of-range insert without default partition causes error [OK]

Common Mistakes:

• Assuming automatic default partition insertion
• Thinking parent table stores unmatched rows
• Ignoring partition range boundaries

4. Consider this partitioned table creation:

CREATE TABLE employees (
  emp_id INT,
  department TEXT
) PARTITION BY LIST (department);

CREATE TABLE employees_sales PARTITION OF employees FOR VALUES IN ('Sales');
CREATE TABLE employees_hr PARTITION OF employees FOR VALUES IN ('HR');

Which error will occur if you try to insert INSERT INTO employees VALUES (1, 'Marketing');?

medium

A. No partition found for value 'Marketing', insert fails

B. Syntax error due to missing partition

C. Row inserted into employees_sales partition by default

D. Row inserted into parent table without partition

Solution

1. Step 1: Check defined partitions

   Partitions exist only for 'Sales' and 'HR' departments.

2. Step 2: Check inserted value 'Marketing'

   'Marketing' is not listed in any partition's VALUES list.

3. Step 3: PostgreSQL behavior on unmatched LIST value

   Without a default partition, insert fails with no matching partition error.

4. Final Answer:

   No partition found for value 'Marketing', insert fails -> Option A

5. Quick Check:

   Unlisted LIST value = insert failure [OK]

Hint: LIST partition needs matching value or default partition [OK]

Common Mistakes:

• Assuming insert goes to any partition by default
• Expecting parent table to store unmatched rows
• Confusing syntax error with runtime insert error

5. You want to evenly distribute a large table's rows across 4 partitions to improve query performance without caring about specific value ranges. Which partition type and setup is best in PostgreSQL?

hard

A. Use no partitioning and rely on indexes.

B. Use LIST partitioning with 4 specific values.

C. Use RANGE partitioning on a numeric column with 4 ranges.

D. Use HASH partitioning with 4 partitions.

Solution

1. Step 1: Understand partitioning goals

   The goal is even distribution across 4 partitions without caring about value ranges.

2. Step 2: Match partition type to goal

   HASH partitioning evenly distributes rows based on a hash function, ideal for this case.

3. Step 3: Evaluate other options

   RANGE and LIST require specific ranges or values, not suitable for even spread without criteria. No partitioning misses distribution benefits.

4. Final Answer:

   Use HASH partitioning with 4 partitions. -> Option D

5. Quick Check:

   Even distribution = HASH partitioning [OK]

Hint: Even spread without ranges? Choose HASH partitioning [OK]

Common Mistakes:

• Using RANGE or LIST when no value grouping needed
• Thinking indexes replace partitioning benefits
• Confusing HASH with LIST partitioning