Re: [PATCH] Incremental sort (was: PoC: Partial sort)

The following review has been posted through the commitfest application:
make installcheck-world:  tested, failed
Implements feature:       tested, passed
Spec compliant:           not tested
Documentation:            not tested

A fairly common planning problem for us is what we call "most recent first" queries; i.e., "the 50 most recent <table> rows for a <foreign key>".

Here's a basic setup:

-- created_at has very high cardinality
create table foo(pk serial primary key, owner_fk integer, created_at timestamp);
create index idx_foo_on_owner_and_created_at on foo(owner_fk, created_at);

-- technically this data guarantees unique created_at values,
-- but there's no reason it couldn't be modified to have a few
-- random non-unique values to prove the point
insert into foo(owner_fk, created_at)
  select i % 100, now() - (i::text || ' minutes')::interval
  from generate_series(1, 1000000) t(i);


And here's the naive query to get the results we want:

select *
from foo
where owner_fk = 23
-- pk is only here to disambiguate/guarantee a stable sort
-- in the rare case that there are collisions in the other
-- sort field(s)
order by created_at desc, pk desc
limit 50;


On stock Postgres this ends up being pretty terrible for cases where the fk filter represents a large number of rows, because the planner generates a sort node under the limit node and therefore fetches all matches, sorts them, and then applies the limit. Here's the plan:

 Limit  (cost=61386.12..61391.95 rows=50 width=16) (actual time=187.814..191.653 rows=50 loops=1)
   ->  Gather Merge  (cost=61386.12..70979.59 rows=82224 width=16) (actual time=187.813..191.647 rows=50 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Sort  (cost=60386.10..60488.88 rows=41112 width=16) (actual time=185.639..185.642 rows=42 loops=3)
               Sort Key: created_at DESC, pk DESC
               Sort Method: top-N heapsort  Memory: 27kB
               Worker 0:  Sort Method: top-N heapsort  Memory: 27kB
               Worker 1:  Sort Method: top-N heapsort  Memory: 27kB
               ->  Parallel Bitmap Heap Scan on foo  (cost=3345.24..59020.38 rows=41112 width=16) (actual time=25.150..181.804 rows=33333 loops=3)
                     Recheck Cond: (owner_fk = 23)
                     Heap Blocks: exact=18014
                     ->  Bitmap Index Scan on idx_foo_on_owner_and_created_at  (cost=0.00..3320.57 rows=98668 width=0) (actual time=16.992..16.992 rows=100000 loops=1)
                           Index Cond: (owner_fk = 23)
 Planning Time: 0.384 ms
 Execution Time: 191.704 ms


I have a recursive CTE that implements the algorithm:
- Find first n+1 results
- If result at n+1’s created_at value differs from the n’s value, return first n values.
- If those equal, gather more results until a new created_at value is encountered.
- Sort all results by created_at and a tie-breaker (e.g., pk) and return the first n values.
But nobody wants to use/write that normally (it's quite complex).

This patch solves the problem presented; here's the plan:

 Limit  (cost=2.70..2.76 rows=50 width=16) (actual time=0.233..0.367 rows=50 loops=1)
   ->  Incremental Sort  (cost=2.70..111.72 rows=98668 width=16) (actual time=0.232..0.362 rows=50 loops=1)
         Sort Key: created_at DESC, pk DESC
         Presorted Key: created_at
         Sort Method: quicksort  Memory: 26kB
         Sort Groups: 2
         ->  Index Scan Backward using idx_foo_on_owner_and_created_at on foo  (cost=0.56..210640.79 rows=98668 width=16) (actual time=0.054..0.299 rows=65 loops=1)
               Index Cond: (owner_fk = 23)
 Planning Time: 0.428 ms
 Execution Time: 0.393 ms


While check world fails, the only failure appears to be a plan output change in test/isolation/expected/drop-index-concurrently-1.out that just needs to be updated (incremental sort is now used in this plan); I don't see any functionality breakage.