List partitioning by category in PostgreSQL - Time & Space Complexity

Time Complexity: List partitioning by category

O(m)

Understanding Time Complexity

When we split a big table into smaller parts based on categories, it helps us find data faster.

We want to know how the time to find data changes as the table grows when using list partitioning.

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL list partitioning setup.

CREATE TABLE orders (
  order_id SERIAL PRIMARY KEY,
  category TEXT NOT NULL,
  amount NUMERIC
) PARTITION BY LIST (category);

CREATE TABLE orders_electronics PARTITION OF orders FOR VALUES IN ('electronics');
CREATE TABLE orders_clothing PARTITION OF orders FOR VALUES IN ('clothing');
CREATE TABLE orders_books PARTITION OF orders FOR VALUES IN ('books');

SELECT * FROM orders WHERE category = 'electronics';
    

This code creates a main table partitioned by category and queries one category's data.

Identify Repeating Operations

Look at what repeats when querying data.

• Primary operation: Searching inside the partition matching the category.
• How many times: The search happens once inside the chosen partition, not the whole table.

How Execution Grows With Input

As the total data grows, only the relevant partition is searched.

Input Size (n)	Approx. Operations
10	About 10 operations inside one partition
100	About 100 operations inside one partition
1000	About 1000 operations inside one partition

Pattern observation: The search cost grows with the size of the partition, not the whole table.

Final Time Complexity

Time Complexity: O(m)

This means the time to find data depends on the size of the category's partition (m), not the total data size.

Common Mistake

[X] Wrong: "Querying a partitioned table always takes the same time as scanning the whole table."

[OK] Correct: Because the query only looks inside the matching partition, it avoids scanning unrelated data, making it faster.

Interview Connect

Understanding how partitioning affects query time shows you can design databases that handle large data efficiently, a useful skill in many projects.

Self-Check

"What if we changed list partitioning to range partitioning by date? How would the time complexity change when querying a specific date range?"