Range partitioning by date in PostgreSQL - Time & Space Complexity

Time Complexity: Range partitioning by date

O(p + r)

Understanding Time Complexity

When using range partitioning by date in a database, we want to understand how query speed changes as data grows.

We ask: How does the time to find data change when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of this PostgreSQL range partitioning setup and query.

CREATE TABLE sales (
  id SERIAL PRIMARY KEY,
  sale_date DATE NOT NULL,
  amount NUMERIC
) PARTITION BY RANGE (sale_date);

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

SELECT * FROM sales WHERE sale_date = '2023-06-15';
    

This code creates a main sales table partitioned by date and queries data for one day.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Checking partitions to find the right date range.
• How many times: Once per partition, but only until the matching partition is found.

How Execution Grows With Input

As more partitions are added for new date ranges, the database checks fewer rows inside each partition.

Input Size (n)	Approx. Operations
10 partitions	Checks about 10 partitions, but scans fewer rows per partition
100 partitions	Checks about 100 partitions, still scans fewer rows per partition
1000 partitions	Checks about 1000 partitions, but each partition is small

Pattern observation: The number of partitions checked grows linearly, but each partition is smaller, so total work stays manageable.

Final Time Complexity

Time Complexity: O(λ + r)

This means the time grows with the number of partitions λ checked plus the rows r scanned in the matching partition.

Common Mistake

[X] Wrong: "Partitioning always makes queries run in constant time regardless of data size."

[OK] Correct: The database still needs to find the right partition, which takes time proportional to the number of partitions, and then scan rows inside it.

Interview Connect

Understanding how partitioning affects query time shows you can design databases that handle growing data smoothly.

Self-Check

"What if we changed range partitioning by date to list partitioning by region? How would the time complexity change?"