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?"