Time Complexity: Partition pruning behavior
O(1)
0
0
Partition pruning behavior in PostgreSQL - Time & Space Complexity
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?"