Partitioning best practices in PostgreSQL - Time & Space Complexity

Time Complexity: Partitioning best practices

O(k)

Understanding Time Complexity

When using partitioning in PostgreSQL, it is important to understand how query time grows as data increases.

We want to know how partitioning affects the speed of data access and management.

Scenario Under Consideration

Analyze the time complexity of querying a partitioned table by range.

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 sales table partitioned by date ranges and queries a specific date.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the relevant partition(s) for matching rows.
• How many times: Only the partitions that match the query condition are scanned, not all partitions.

How Execution Grows With Input

As the total data grows, the query only touches the relevant partition, so work grows with partition size, not total data size.

Input Size (n)	Approx. Operations
10,000 rows total	Scan ~1,000 rows in one partition
100,000 rows total	Scan ~10,000 rows in one partition
1,000,000 rows total	Scan ~100,000 rows in one partition

Pattern observation: Query cost grows with the size of the accessed partition, not the whole table.

Final Time Complexity

Time Complexity: O(k)

This means query time grows with the size of the relevant partition (k), not the entire dataset.

Common Mistake

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

[OK] Correct: Partitioning limits the data scanned but query time still grows with the size of the accessed partition.

Interview Connect

Understanding partitioning time complexity shows you can design databases that handle large data efficiently, a valuable skill in real projects.

Self-Check

"What if we changed from range partitioning to list partitioning on a low-cardinality column? How would the time complexity change?"

Practice

1. What is the main benefit of using table partitioning in PostgreSQL?

easy

A. It breaks a large table into smaller, manageable parts to improve performance.

B. It automatically creates backups of the table data.

C. It encrypts the table data for security.

D. It merges multiple tables into one large table.

Solution

1. Step 1: Understand what partitioning does

   Partitioning divides a big table into smaller pieces called partitions.

2. Step 2: Identify the benefit of smaller parts

   Smaller parts make queries faster and data easier to manage.

3. Final Answer:

   It breaks a large table into smaller, manageable parts to improve performance. -> Option A

4. Quick Check:

   Partitioning = smaller parts for performance [OK]

Hint: Partitioning splits big tables for easier handling [OK]

Common Mistakes:

• Thinking partitioning creates backups
• Confusing partitioning with encryption
• Believing partitioning merges tables

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

easy

A. CREATE TABLE sales (id INT, sale_date DATE) PARTITION BY LIST (sale_date);

B. CREATE TABLE sales PARTITION BY RANGE (sale_date) (id INT, sale_date DATE);

C. CREATE TABLE sales (id INT, sale_date DATE) PARTITION ON RANGE sale_date;

D. CREATE TABLE sales (id INT, sale_date DATE) PARTITION BY RANGE (sale_date);

Solution

1. Step 1: Recall correct partition syntax

   PostgreSQL uses PARTITION BY RANGE (column) after table columns.

2. Step 2: Check each option

   CREATE TABLE sales (id INT, sale_date DATE) PARTITION BY RANGE (sale_date); matches syntax: columns first, then PARTITION BY RANGE.

3. Final Answer:

   CREATE TABLE sales (id INT, sale_date DATE) PARTITION BY RANGE (sale_date); -> Option D

4. Quick Check:

   PARTITION BY RANGE after columns = correct syntax [OK]

Hint: Partition type follows column definitions in CREATE TABLE [OK]

Common Mistakes:

• Placing PARTITION BY before columns
• Using PARTITION ON instead of PARTITION BY
• Confusing RANGE with LIST partition type

3. Given the following partition setup:

CREATE TABLE orders (id INT, region TEXT, order_date DATE) PARTITION BY LIST (region);
CREATE TABLE orders_us PARTITION OF orders FOR VALUES IN ('US');
CREATE TABLE orders_eu PARTITION OF orders FOR VALUES IN ('EU');

What will be the result of this query?

INSERT INTO orders VALUES (1, 'US', '2024-01-01');
SELECT * FROM orders WHERE region = 'US';

medium

A. Returns the row with id 1, region 'US', and date '2024-01-01'.

B. Returns no rows because the partition is missing.

C. Causes a syntax error due to missing partition key.

D. Returns rows from all partitions regardless of region.

Solution

1. Step 1: Understand LIST partitioning by region

   Rows with region 'US' go to orders_us partition.

2. Step 2: Insert and select behavior

   Insert puts row in orders_us; select filters region='US', so row is returned.

3. Final Answer:

   Returns the row with id 1, region 'US', and date '2024-01-01'. -> Option A

4. Quick Check:

   List partition returns matching rows [OK]

Hint: Rows go to partition matching partition key value [OK]

Common Mistakes:

• Assuming insert fails without default partition
• Expecting syntax error on insert
• Thinking select ignores partition keys

4. You have this partitioned table:

CREATE TABLE logs (id SERIAL, log_date DATE) PARTITION BY RANGE (log_date);
CREATE TABLE logs_2023 PARTITION OF logs FOR VALUES FROM ('2023-01-01') TO ('2024-01-01');

Which error will occur if you run this?

INSERT INTO logs (log_date) VALUES ('2022-12-31');

medium

A. ERROR: syntax error near VALUES

B. ERROR: no partition found for row

C. The row is inserted into logs_2023 partition

D. The row is inserted into a default partition automatically

Solution

1. Step 1: Check partition ranges

   logs_2023 covers dates from 2023-01-01 to 2024-01-01 only.

2. Step 2: Insert date outside partition range

   2022-12-31 is before 2023-01-01, so no matching partition exists.

3. Final Answer:

   ERROR: no partition found for row -> Option B

4. Quick Check:

   Insert outside range = no partition error [OK]

Hint: Insert date must fit partition range or error occurs [OK]

Common Mistakes:

• Expecting automatic default partition
• Thinking syntax error occurs
• Assuming row goes to nearest partition

5. You want to optimize queries filtering by user_id and created_at date on a large table. Which partitioning strategy is best practice?

hard

A. Use HASH partitioning on created_at only.

B. Use LIST partitioning on user_id only.

C. Use RANGE partitioning on created_at and subpartition by HASH on user_id.

D. Do not partition; use a single large table with indexes.

Solution

1. Step 1: Analyze query filters

   Queries filter by user_id and created_at, so both should guide partitioning.

2. Step 2: Choose partitioning methods

   RANGE on created_at handles date ranges well; HASH subpartitioning on user_id balances data.

3. Step 3: Evaluate other options

   LIST on user_id alone is inefficient for many users; HASH on created_at is unusual; no partitioning misses benefits.

4. Final Answer:

   Use RANGE partitioning on created_at and subpartition by HASH on user_id. -> Option C

5. Quick Check:

   Combine RANGE and HASH for multi-column filtering [OK]

Hint: Combine RANGE for dates and HASH for IDs for best performance [OK]

Common Mistakes:

• Using LIST for high-cardinality user_id
• Hash partitioning on date column only
• Skipping partitioning on large tables