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.