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

Practice

1. What is the main purpose of list partitioning by category in PostgreSQL?

easy

A. To split a table into parts based on specific category values

B. To combine multiple tables into one large table

C. To encrypt data in the table for security

D. To create temporary tables for faster queries

Solution

1. Step 1: Understand list partitioning concept

   List partitioning divides a table into smaller parts based on specific category values.

2. Step 2: Identify the main purpose

   This helps organize data and speeds up queries by focusing on relevant partitions.

3. Final Answer:

   To split a table into parts based on specific category values -> Option A

4. Quick Check:

   List partitioning = split by category [OK]

Hint: List partitioning splits tables by category values [OK]

Common Mistakes:

• Confusing list partitioning with table joins
• Thinking it encrypts data
• Assuming it merges tables

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

easy

A. CREATE TABLE sales PARTITION BY GROUP (category);

B. CREATE TABLE sales PARTITION BY RANGE (category);

C. CREATE TABLE sales PARTITION BY HASH (category);

D. CREATE TABLE sales PARTITION BY LIST (category);

Solution

1. Step 1: Identify partition type syntax

   List partitioning uses PARTITION BY LIST in PostgreSQL.

2. Step 2: Match correct syntax

   Only CREATE TABLE sales PARTITION BY LIST (category); uses PARTITION BY LIST with the column name correctly.

3. Final Answer:

   CREATE TABLE sales PARTITION BY LIST (category); -> Option D

4. Quick Check:

   List partitioning syntax = PARTITION BY LIST [OK]

Hint: Use PARTITION BY LIST for list partitioning [OK]

Common Mistakes:

• Using PARTITION BY RANGE instead of LIST
• Using PARTITION BY HASH incorrectly
• Using non-existent PARTITION BY GROUP

3. Given the following setup:

CREATE TABLE products (
  id SERIAL PRIMARY KEY,
  name TEXT,
  category TEXT
) PARTITION BY LIST (category);

CREATE TABLE products_electronics PARTITION OF products FOR VALUES IN ('electronics');
CREATE TABLE products_clothing PARTITION OF products FOR VALUES IN ('clothing');

INSERT INTO products (name, category) VALUES ('Phone', 'electronics'), ('Shirt', 'clothing');

SELECT * FROM products WHERE category = 'electronics';

What will the SELECT query return?

medium

A. No rows because category is filtered incorrectly

B. All rows from both partitions

C. Only rows where category is 'electronics', here the 'Phone' row

D. An error because partitions are not queried directly

Solution

1. Step 1: Understand partition filtering

   Query filters category = 'electronics', so only that partition is scanned.

2. Step 2: Check inserted data

   Only 'Phone' has category 'electronics', so only that row is returned.

3. Final Answer:

   Only rows where category is 'electronics', here the 'Phone' row -> Option C

4. Quick Check:

   Partition filter returns matching rows [OK]

Hint: Query filters partition by category value [OK]

Common Mistakes:

• Expecting all rows without filter
• Thinking query causes error
• Assuming partitions must be queried separately

4. Consider this incorrect partition creation:

CREATE TABLE orders (
  id SERIAL PRIMARY KEY,
  product TEXT,
  category TEXT
) PARTITION BY LIST (category);

CREATE TABLE orders_electronics PARTITION OF orders FOR VALUES IN ('electronics', 'gadgets');

What is the error in this partition definition?

medium

A. FOR VALUES IN must list values as separate strings, not combined

B. Partitions cannot have multiple values in FOR VALUES IN clause

C. The partition table name is invalid

D. The parent table cannot be partitioned by LIST

Solution

1. Step 1: Check FOR VALUES IN syntax

   FOR VALUES IN expects a list of values as separate strings, e.g. ('electronics', 'gadgets').

2. Step 2: Identify error in given code

   The code uses multiple values in one partition which is not allowed in PostgreSQL list partitioning.

3. Final Answer:

   Partitions cannot have multiple values in FOR VALUES IN clause -> Option B

4. Quick Check:

   Each partition must have exactly one value [OK]

Hint: Each partition must have a single value in FOR VALUES IN clause [OK]

Common Mistakes:

• Using one string with commas inside
• Misnaming partition tables
• Thinking LIST partitioning is not allowed

5. You want to create a list partitioned table events by event_type with partitions for 'login', 'logout', and 'purchase'. Which of the following is the correct way to create the partitions and insert a new 'purchase' event?

hard

A. CREATE TABLE events PARTITION BY LIST (event_type);
CREATE TABLE events_login PARTITION OF events FOR VALUES IN ('login');
CREATE TABLE events_logout PARTITION OF events FOR VALUES IN ('logout');
CREATE TABLE events_purchase PARTITION OF events FOR VALUES IN ('purchase');
INSERT INTO events (event_type) VALUES ('purchase');

B. CREATE TABLE events PARTITION BY RANGE (event_type);
CREATE TABLE events_login PARTITION OF events FOR VALUES FROM ('login') TO ('logout');
INSERT INTO events (event_type) VALUES ('purchase');

C. CREATE TABLE events PARTITION BY LIST (event_type);
CREATE TABLE events_all PARTITION OF events FOR VALUES IN ('login', 'logout', 'purchase');
INSERT INTO events (event_type) VALUES ('purchase');

D. CREATE TABLE events PARTITION BY HASH (event_type);
CREATE TABLE events_hash PARTITION OF events FOR VALUES IN (1);
INSERT INTO events (event_type) VALUES ('purchase');

Solution

1. Step 1: Choose correct partition type and syntax

   List partitioning by event_type requires PARTITION BY LIST and partitions with FOR VALUES IN for each category.

2. Step 2: Verify partitions and insert

   CREATE TABLE events PARTITION BY LIST (event_type); CREATE TABLE events_login PARTITION OF events FOR VALUES IN ('login'); CREATE TABLE events_logout PARTITION OF events FOR VALUES IN ('logout'); CREATE TABLE events_purchase PARTITION OF events FOR VALUES IN ('purchase'); INSERT INTO events (event_type) VALUES ('purchase'); correctly creates partitions for 'login', 'logout', and 'purchase' and inserts a 'purchase' event into the parent table.

3. Final Answer:

   Option A with correct list partitions and insert -> Option A

4. Quick Check:

   List partitions per category + insert into parent [OK]

Hint: Create partitions per category, insert into parent table [OK]

Common Mistakes:

• Using RANGE or HASH instead of LIST
• Creating one partition for all values
• Inserting into partitions directly instead of parent