0

I have a table in postgres 13, declaratively range partitioned by ID.

I am selecting a small number of rows in descending ID order and I was hoping it would reliably use ordered partition scans, where the partitions are searched in reverse order until the required number of rows are found. I know that in nearly every case, the results will be found in the most recent partition and the older partitions can be skipped.

I get ordered partition scans sometimes, but other times the planner decides to query every partition and it performs worse than if only the most recent partition was checked. I'm interested to learn why, and if there's anything i can do to influence the planner

Test setup:

CREATE SEQUENCE public.measurements_id_seq
    START WITH 1
    INCREMENT BY 1
    NO MINVALUE
    NO MAXVALUE
    CACHE 1;

ALTER SEQUENCE measurements_id_seq RESTART WITH 1;
    
CREATE TABLE measurements (
    id integer DEFAULT nextval('public.measurements_id_seq'::regclass) PRIMARY KEY,
    uuid uuid NOT NULL,
    num integer NOT NULL,
    created_at timestamp without time zone NOT NULL
)
PARTITION BY RANGE (id);

CREATE INDEX ON measurements (num);
CREATE INDEX ON measurements (uuid);


CREATE TABLE measurements_p0 PARTITION OF measurements FOR VALUES FROM (0) TO (1000000);
CREATE TABLE measurements_p1 PARTITION OF measurements FOR VALUES FROM (1000000) TO (2000000);
CREATE TABLE measurements_p2 PARTITION OF measurements FOR VALUES FROM (2000000) TO (3000000);
CREATE TABLE measurements_p3 PARTITION OF measurements FOR VALUES FROM (3000000) TO (4000000);
CREATE TABLE measurements_p4 PARTITION OF measurements FOR VALUES FROM (4000000) TO (5000000);
CREATE TABLE measurements_p5 PARTITION OF measurements FOR VALUES FROM (5000000) TO (6000000);

I then insert bulk sample data, with 100 random numbers (1% of table each), and 10 random UUIDs (10% of table each):

with uuids AS (
  select gen_random_uuid() as uuid from generate_series(1, 10) s(i)
)
insert into measurements (
    num, uuid, created_at
)
select
    random() * 100, 
    (select array_agg(uuid) from uuids)[floor(random() * 10 + 1)],
    clock_timestamp()
from generate_series(1, 4999999) s(i);

Finally I add some extra sample data with UUIDs that are much less than 10% of the rows, then analyze:

with uuids AS (
  select gen_random_uuid() as uuid from generate_series(1, 10) s(i)
)
insert into measurements (
    num, uuid, created_at
)
select
    random() * 100, 
    (select array_agg(uuid) from uuids)[floor(random() * 10 + 1)],
    clock_timestamp()
from generate_series(1, 10000) s(i);

analyze measurements;

✅ I get an ordered partition scan if I select 1% of rows, ordered by id desc

# explain (analyze, buffers) select * from measurements where num=5 order by id desc limit 4;
                                                                                  QUERY PLAN                                                                                  
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=2.41..16.66 rows=4 width=32) (actual time=0.266..0.540 rows=4 loops=1)
   Buffers: shared hit=11
   ->  Append  (cost=2.41..179806.71 rows=50464 width=32) (actual time=0.260..0.531 rows=4 loops=1)
         Buffers: shared hit=11
         ->  Index Scan Backward using measurements_p5_pkey on measurements_p5 measurements_6  (cost=0.29..372.29 rows=97 width=32) (actual time=0.257..0.525 rows=4 loops=1)
               Filter: (num = 5)
               Rows Removed by Filter: 533
               Buffers: shared hit=11
         ->  Index Scan Backward using measurements_p4_pkey on measurements_p4 measurements_5  (cost=0.42..35836.43 rows=8400 width=32) (never executed)
               Filter: (num = 5)
         ->  Index Scan Backward using measurements_p3_pkey on measurements_p3 measurements_4  (cost=0.42..35836.43 rows=10900 width=32) (never executed)
               Filter: (num = 5)
         ->  Index Scan Backward using measurements_p2_pkey on measurements_p2 measurements_3  (cost=0.42..35836.43 rows=9867 width=32) (never executed)
               Filter: (num = 5)
         ->  Index Scan Backward using measurements_p1_pkey on measurements_p1 measurements_2  (cost=0.42..35836.43 rows=10200 width=32) (never executed)
               Filter: (num = 5)
         ->  Index Scan Backward using measurements_p0_pkey on measurements_p0 measurements_1  (cost=0.42..35836.41 rows=11000 width=32) (never executed)
               Filter: (num = 5)
 Planning Time: 1.227 ms
 Execution Time: 0.827 ms

✅ I get an ordered partition scan if I select 10% of rows, ordered by id desc:

# explain (analyze, buffers) select * from measurements where uuid='0a246187-edf6-44f3-8517-2a899667db0f' order by id desc limit 4;
                                                                                    QUERY PLAN                                                                                     
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=2.41..3.88 rows=4 width=32) (actual time=5.378..5.395 rows=4 loops=1)
   Buffers: shared hit=135
   ->  Append  (cost=2.41..182034.40 rows=496001 width=32) (actual time=5.374..5.389 rows=4 loops=1)
         Buffers: shared hit=135
         ->  Index Scan Backward using measurements_p5_pkey on measurements_p5 measurements_6  (cost=0.29..372.29 rows=1 width=32) (actual time=5.293..5.294 rows=0 loops=1)
               Filter: (uuid = '0a246187-edf6-44f3-8517-2a899667db0f'::uuid)
               Rows Removed by Filter: 10000
               Buffers: shared hit=131
         ->  Index Scan Backward using measurements_p4_pkey on measurements_p4 measurements_5  (cost=0.42..35836.43 rows=99400 width=32) (actual time=0.076..0.088 rows=4 loops=1)
               Filter: (uuid = '0a246187-edf6-44f3-8517-2a899667db0f'::uuid)
               Rows Removed by Filter: 42
               Buffers: shared hit=4
         ->  Index Scan Backward using measurements_p3_pkey on measurements_p3 measurements_4  (cost=0.42..35836.43 rows=100733 width=32) (never executed)
               Filter: (uuid = '0a246187-edf6-44f3-8517-2a899667db0f'::uuid)
         ->  Index Scan Backward using measurements_p2_pkey on measurements_p2 measurements_3  (cost=0.42..35836.43 rows=97567 width=32) (never executed)
               Filter: (uuid = '0a246187-edf6-44f3-8517-2a899667db0f'::uuid)
         ->  Index Scan Backward using measurements_p1_pkey on measurements_p1 measurements_2  (cost=0.42..35836.43 rows=97833 width=32) (never executed)
               Filter: (uuid = '0a246187-edf6-44f3-8517-2a899667db0f'::uuid)
         ->  Index Scan Backward using measurements_p0_pkey on measurements_p0 measurements_1  (cost=0.42..35836.41 rows=100467 width=32) (never executed)
               Filter: (uuid = '0a246187-edf6-44f3-8517-2a899667db0f'::uuid)
 Planning Time: 0.728 ms
 Execution Time: 5.630 ms

❌ I do not get an ordered partition scan if I select a UUID that only has a small number of rows in the final partition, ordered by id desc:

# explain (analyze, buffers) select * from measurements where uuid='1d58534d-c795-4f9b-b1d9-ab6316a8fb9a' order by id desc limit 4;
                                                                                 QUERY PLAN                                                                                 
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=164.31..164.32 rows=4 width=32) (actual time=1.952..1.960 rows=4 loops=1)
   Buffers: shared hit=91
   ->  Sort  (cost=164.31..166.80 rows=996 width=32) (actual time=1.949..1.954 rows=4 loops=1)
         Sort Key: measurements.id DESC
         Sort Method: top-N heapsort  Memory: 25kB
         Buffers: shared hit=91
         ->  Append  (cost=0.42..149.37 rows=996 width=32) (actual time=0.456..1.470 rows=991 loops=1)
               Buffers: shared hit=91
               ->  Index Scan using measurements_p0_uuid_idx on measurements_p0 measurements_1  (cost=0.42..8.39 rows=1 width=32) (actual time=0.057..0.058 rows=0 loops=1)
                     Index Cond: (uuid = '1d58534d-c795-4f9b-b1d9-ab6316a8fb9a'::uuid)
                     Buffers: shared hit=3
               ->  Index Scan using measurements_p1_uuid_idx on measurements_p1 measurements_2  (cost=0.42..8.41 rows=1 width=32) (actual time=0.073..0.073 rows=0 loops=1)
                     Index Cond: (uuid = '1d58534d-c795-4f9b-b1d9-ab6316a8fb9a'::uuid)
                     Buffers: shared hit=3
               ->  Index Scan using measurements_p2_uuid_idx on measurements_p2 measurements_3  (cost=0.42..8.40 rows=1 width=32) (actual time=0.038..0.038 rows=0 loops=1)
                     Index Cond: (uuid = '1d58534d-c795-4f9b-b1d9-ab6316a8fb9a'::uuid)
                     Buffers: shared hit=3
               ->  Index Scan using measurements_p3_uuid_idx on measurements_p3 measurements_4  (cost=0.42..8.40 rows=1 width=32) (actual time=0.047..0.047 rows=0 loops=1)
                     Index Cond: (uuid = '1d58534d-c795-4f9b-b1d9-ab6316a8fb9a'::uuid)
                     Buffers: shared hit=3
               ->  Index Scan using measurements_p4_uuid_idx on measurements_p4 measurements_5  (cost=0.42..8.44 rows=1 width=32) (actual time=0.041..0.042 rows=0 loops=1)
                     Index Cond: (uuid = '1d58534d-c795-4f9b-b1d9-ab6316a8fb9a'::uuid)
                     Buffers: shared hit=3
               ->  Bitmap Heap Scan on measurements_p5 measurements_6  (cost=15.97..102.35 rows=991 width=32) (actual time=0.195..0.961 rows=991 loops=1)
                     Recheck Cond: (uuid = '1d58534d-c795-4f9b-b1d9-ab6316a8fb9a'::uuid)
                     Heap Blocks: exact=74
                     Buffers: shared hit=76
                     ->  Bitmap Index Scan on measurements_p5_uuid_idx  (cost=0.00..15.72 rows=991 width=0) (actual time=0.146..0.146 rows=991 loops=1)
                           Index Cond: (uuid = '1d58534d-c795-4f9b-b1d9-ab6316a8fb9a'::uuid)
                           Buffers: shared hit=2
 Planning Time: 1.024 ms
 Execution Time: 2.280 ms

If I change that last query to target just the most recent partition, we can see it only hits a handful of buffers and would be a good candidate for an order partition scan:

# explain (analyze, buffers) select * from measurements_p5 where uuid='1d58534d-c795-4f9b-b1d9-ab6316a8fb9a' order by id desc limit 4;
                                                                        QUERY PLAN                                                                        
----------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.29..1.79 rows=4 width=32) (actual time=0.127..0.143 rows=4 loops=1)
   Buffers: shared hit=3
   ->  Index Scan Backward using measurements_p5_pkey on measurements_p5  (cost=0.29..372.29 rows=991 width=32) (actual time=0.123..0.137 rows=4 loops=1)
         Filter: (uuid = '1d58534d-c795-4f9b-b1d9-ab6316a8fb9a'::uuid)
         Rows Removed by Filter: 37
         Buffers: shared hit=3
 Planning Time: 0.245 ms
 Execution Time: 0.234 ms

One difference I can see is all the query plans with an ordered partition scan are using the primary key index, which is also the partition key. Do ordered partition scans only happen when the planner decides it's feasible to do a reverse scan down the partition key index?

Improve this question
5
  • Both plans have their merit, and it is typically very hard to decide which is better. PostgreSQL chooses the plan it thinks will be faster. Do you have reasons to suspect that it is wrong here?
    – Laurenz Albe
    Oct 14, 2022 at 6:16
  • Good question. In this contrived example there's not much difference between the execution time or buffer counts of the two plans. In the production schema where we're hoping to see benefits from ordered partition scans we have a historical 800Gb table that's been attached to a new partitioned table, and then pg_partman managing smaller partitions for new data. We hoped the historical partition would be skipped for queries that "order by id desc", but it's not happening in most cases
    – James Healy
    Oct 14, 2022 at 7:36
  • You should ask a question about your real data then, showing EXPLAIN (ANALYZE, BUFFERS) for the queries there.
    – Laurenz Albe
    Oct 14, 2022 at 10:12
  • You should come up with a better example, where the bad plan is actually truly bad. Your current example is just a case of trivial pursuit. Also, we can't even reproduce this without spelunking into which uuid to replace your hardcoded values with to make it work for us, it would be best to avoid that
    – jjanes
    Oct 14, 2022 at 15:03
  • Fair enough, thanks. I wonder if the final part of the question is answerable: "Do ordered partition scans only happen when the planner decides it's feasible to do a reverse scan down the partition key index?" Put another way, if the planner decides to use an index that's not sorted by the partition key (like measurements[uuid]), does that prevent ordered partition scans?
    – James Healy
    Oct 14, 2022 at 21:29

1 Answer 1

Reset to default
1

Yes, it will only do an ordered partition scan when there is a suitable index that can be used, which has a usable subset matching the partition/sort key. In this case, an index on (uuid, id) would work, as after testing uuid for equality it allows id to be delivered in order.

You could imagine cases where it might be worthwhile to inject a sort between the Append and the individual partition scans, which could then allow it benefit from an ordered partition scan even without such an index. But this is not implemented.

Improve this answer
1
  • Confirmed: for this particular setup, adding an index on (uuid, id) results in ordered partition scans consistently when I'm filtering by uuid. Thanks!
    – James Healy
    Oct 16, 2022 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.