Partition pruning behavior in PostgreSQL - Time & Space Complexity

Time Complexity: Partition pruning behavior

O(1)

Understanding Time Complexity

When using partitioned tables, the database can skip checking some parts to speed up queries.

We want to see how this skipping affects the work done as data grows.

Scenario Under Consideration

Analyze the time complexity of the following query on a partitioned table.

SELECT * FROM sales
WHERE sale_date = '2024-01-01';
-- sales is partitioned by sale_date
-- partitions are by month
    

This query fetches sales for one day, using partitions by month to limit data scanned.

Identify Repeating Operations

Look for repeated work done by the query.

• Primary operation: Scanning partitions that match the date condition.
• How many times: Only the partition for January 2024 is scanned, not all partitions.

How Execution Grows With Input

As the total number of partitions grows, the query only checks the relevant ones.

Input Size (partitions)	Approx. Partitions Scanned
10	1
100	1
1000	1

Pattern observation: The number of partitions scanned stays the same, no matter how many partitions exist.

Final Time Complexity

Time Complexity: O(1)

This means the query work stays constant because it only looks at the needed partitions.

Common Mistake

[X] Wrong: "The query scans all partitions every time, so it gets slower as partitions grow."

[OK] Correct: Partition pruning lets the database skip irrelevant partitions, so it does not scan all partitions.

Interview Connect

Understanding partition pruning shows you know how databases handle big data efficiently, a useful skill for real projects.

Self-Check

"What if the query uses a condition that does not match the partition key? How would the time complexity change?"

Practice

1. What is the main purpose of partition pruning in PostgreSQL?

easy

A. To merge all partitions into one table

B. To create new partitions automatically

C. To skip scanning partitions that cannot contain matching rows

D. To backup partitions separately

Solution

1. Step 1: Understand partition pruning concept

   Partition pruning means the database avoids scanning partitions that do not match the query filter.

2. Step 2: Identify the main benefit

   This skipping reduces query time by focusing only on relevant partitions.

3. Final Answer:

   To skip scanning partitions that cannot contain matching rows -> Option C

4. Quick Check:

   Partition pruning = skip irrelevant partitions [OK]

Hint: Partition pruning skips irrelevant partitions to speed queries [OK]

Common Mistakes:

• Thinking pruning merges partitions
• Assuming pruning creates partitions
• Confusing pruning with backup

2. Which of the following WHERE clauses will enable partition pruning on a table partitioned by column region?

easy

A. WHERE region = 'US'

B. WHERE UPPER(region) = 'US'

C. WHERE LENGTH(region) > 2

D. WHERE region LIKE '%US%'

Solution

1. Step 1: Identify pruning conditions

   Partition pruning works best with simple direct comparisons on the partition key.

2. Step 2: Analyze each option

   WHERE region = 'US' uses a direct equality on region, enabling pruning. Options A, B, and D use functions or patterns, preventing pruning.

3. Final Answer:

   WHERE region = 'US' -> Option A

4. Quick Check:

   Simple equality on partition key enables pruning [OK]

Hint: Use simple column = value filters on partition keys [OK]

Common Mistakes:

• Using functions on partition keys disables pruning
• Using LIKE patterns disables pruning
• Assuming any WHERE clause prunes partitions

3. Given a table sales partitioned by year with partitions for 2021 and 2022, what will the query below scan?

SELECT * FROM sales WHERE year = 2021;

medium

A. Only the 2021 partition

B. Both 2021 and 2022 partitions

C. No partitions, query returns empty

D. All partitions plus a full table scan

Solution

1. Step 1: Understand partition pruning with equality filter

   The query filters on year = 2021, which matches exactly one partition.

2. Step 2: Determine scanned partitions

   PostgreSQL will prune and scan only the 2021 partition, skipping 2022.

3. Final Answer:

   Only the 2021 partition -> Option A

4. Quick Check:

   Filter on partition key = value scans matching partition only [OK]

Hint: Equality on partition key scans only matching partition [OK]

Common Mistakes:

• Assuming all partitions scan regardless of filter
• Thinking query returns empty if filter matches a partition
• Believing full table scan always happens

4. You wrote this query on a partitioned table orders partitioned by order_date:

SELECT * FROM orders WHERE EXTRACT(YEAR FROM order_date) = 2023;

Why might partition pruning NOT occur?

medium

A. Partition pruning only works with numeric columns

B. Using a function on the partition key disables pruning

C. The query syntax is invalid

D. Partition pruning requires an index on order_date

Solution

1. Step 1: Identify pruning limitation

   Partition pruning requires direct use of the partition key in filters without wrapping functions.

2. Step 2: Analyze the query

   The query uses EXTRACT(YEAR FROM order_date), a function on the partition key, preventing pruning.

3. Final Answer:

   Using a function on the partition key disables pruning -> Option B

4. Quick Check:

   Functions on partition keys disable pruning [OK]

Hint: Avoid functions on partition keys for pruning [OK]

Common Mistakes:

• Thinking pruning needs indexes
• Believing pruning works with any filter
• Assuming query syntax error causes pruning failure

5. A table events is range partitioned by event_date with monthly partitions. You want to query events in March 2023. Which query will maximize partition pruning?

hard

A. SELECT * FROM events WHERE event_date BETWEEN '2023-02-28' AND '2023-03-31';

B. SELECT * FROM events WHERE EXTRACT(MONTH FROM event_date) = 3 AND EXTRACT(YEAR FROM event_date) = 2023;

C. SELECT * FROM events WHERE TO_CHAR(event_date, 'YYYY-MM') = '2023-03';

D. SELECT * FROM events WHERE event_date >= '2023-03-01' AND event_date < '2023-04-01';

Solution

1. Step 1: Understand pruning with range partitions

   Range partitions work best with direct range conditions on the partition key.

2. Step 2: Evaluate each query

   SELECT * FROM events WHERE event_date >= '2023-03-01' AND event_date < '2023-04-01'; uses a direct range filter on event_date, enabling pruning. Options B and C use functions, disabling pruning. SELECT * FROM events WHERE event_date BETWEEN '2023-02-28' AND '2023-03-31'; includes dates outside March, scanning extra partitions.

3. Final Answer:

   SELECT * FROM events WHERE event_date >= '2023-03-01' AND event_date < '2023-04-01'; -> Option D

4. Quick Check:

   Direct range filters maximize pruning [OK]

Hint: Use direct range filters on partition keys for pruning [OK]

Common Mistakes:

• Using functions disables pruning
• Including extra dates scans more partitions
• Assuming BETWEEN always prunes perfectly