Sub-partitioning in PostgreSQL - Time & Space Complexity

Time Complexity: Sub-partitioning

O(log n)

Understanding Time Complexity

When using sub-partitioning in a database, we want to understand how the time to find or insert data changes as the data grows.

We ask: How does the work increase when we add more data to sub-partitions?

Scenario Under Consideration

Analyze the time complexity of querying a sub-partitioned table.

CREATE TABLE sales (
  sale_id SERIAL,
  region TEXT,
  sale_date DATE,
  amount NUMERIC
) PARTITION BY LIST (region);

CREATE TABLE sales_us PARTITION OF sales FOR VALUES IN ('US') PARTITION BY RANGE (sale_date);

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

SELECT * FROM sales WHERE region = 'US' AND sale_date >= '2023-06-01';
    

This code creates a table partitioned by region, then sub-partitioned by date range, and queries data from a specific sub-partition.

Identify Repeating Operations

Look for repeated steps in how the database finds data.

• Primary operation: Searching partitions and sub-partitions to find matching rows.
• How many times: The database checks the main partitions (regions), then within the chosen partition, it checks sub-partitions (date ranges).

How Execution Grows With Input

As data grows, the number of partitions and sub-partitions may increase.

Input Size (n)	Approx. Operations
10	About 2-3 checks (partitions + sub-partitions)
100	Still a few checks due to partition pruning
1000	More partitions, but query still targets few sub-partitions

Pattern observation: The work grows slowly because the query only looks at relevant partitions, not all data.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find data grows slowly, roughly like the steps needed to find a page in a book index.

Common Mistake

[X] Wrong: "Sub-partitioning makes queries scan all data, so time grows linearly with data size."

[OK] Correct: The database uses partition pruning to skip irrelevant partitions, so it does not scan all data.

Interview Connect

Understanding how sub-partitioning affects query time shows you know how databases handle big data efficiently.

Self-Check

"What if we removed sub-partitioning and only used one level of partitioning? How would the time complexity change?"