Quickselect instead of a heap for ORDER BY ... LIMIT N large bounded sorts

Hello,

At p99conf this week [1] and I learned of an interesting binary heap
algorithm optimized for SIMD [2], so naturally I took a look at the code
[3] and some docs from the author [4] went looking for places to use it
in Postgres, well I should say that I asked my friendly LLM to do an
exaustive sweep of our code looking for places it might be useful. Why
not, right?

The whole store is in the Appendix with references, no need to bore you
with that right now. After a late night of vibe coding and some more
this morning the patch seems like a good contribution.

I did also do a search of the archives [5] which turned up quickselect
for median and percentile back in 2010 [6], but not anything like this.

The crux of the issue is that a bounded sort (ORDER BY ... LIMIT N) has
2 * N tuples in memory, tuplesort builds a heap of N and pays O(log N)
comparisons for every tuple that gets in. With a large N most tuples
get in, and the "top-N heapsort" can lose to sorting the whole input: on
5M int8 rows at LIMIT 2.4M the heap takes 2.7x as long as a full sort.
The "a large LIMIT makes some sorts slower" thread [1] hit the other
half of this: bounded sorts also turn off abbreviated keys.

The attached patch drops the heap for N >= 8. It keeps up to 2 * N
tuples, and whenever the buffer fills it runs quickselect to keep the N
smallest and free the rest. That's O(N) work per N admitted tuples, so
O(1) per tuple instead of O(log N). A tuple is still rejected with one
comparison, against the largest survivor of the last prune, just as the
heap compares against its root. At the end the survivors go through
tuplesort_sort_memtuples(), so they get radix sort or the specialized
qsort exactly as an unbounded sort would.

Peak memory is unchanged: the buffer never holds more than the 2 * N
tuples already in memory when the heap would have been built. If wider
tuples later push the sort over work_mem, it prunes to N and finishes
with the existing heap code.

Numbers below are median ms over 5 runs, release build, 5M rows,
work_mem = 2GB, one backend pinned to one core (c7i.4xlarge, Fedora 44,
gcc 16). The times are client-side and include a ~360 ms scan, so the
sort itself improved more than the ratios show. Within each cell the
five runs spread by at most 7%, well short of the gaps below.

ORDER BY LIMIT heap quickselect
int8, random 1,000,000 1,852 807 0.44x
int8, random 2,400,000 3,184 1,186 0.37x
text, C 1,000,000 5,142 1,788 0.35x
text, en_US 1,000,000 9,691 3,851 0.40x
int, text 1,000,000 5,712 2,364 0.41x
int8, reversed 10,000 1,023 485 0.47x
random order, any key 100 364-541 368-548 0.98-1.01x

"reversed" is input that arrives in descending order, so every tuple is
admitted. At LIMIT 100 on random input almost nothing gets past the
first comparison, so there is nothing to win. With work_mem = 4MB, 2 *
N tuples don't fit, the heap is used as before, and timings match
master.

Quickselect broke even with the heap at N = 6 on that box, but the patch
switches at 8 to leave some margin. With N of 1 to 4 on reversed en_US
text, quickselect was up to 2.6x slower (797 ms vs 300 ms at LIMIT 1)
because the buffer refills every few tuples. Below 8 the patch keeps
the heap. There, int8 matches master, and en_US text at LIMIT 2-7 comes
out 2-3% slower in both patched builds, with quickselect on or off. With
it off only the heap runs, so I read that as a code-layout difference
between the two binaries, but I haven't proven it.

It also beats a full sort (what you get with a LIMIT above INT_MAX / 2,
as in [1]) in all but one case:

ORDER BY LIMIT heap full sort quickselect
text, en_US 1,000,000 9,619 11,425 3,728
int8 2,400,000 2,898 1,079 940
text, C 2,400,000 9,791 1,286 2,754

The exception is C-collation text at a large LIMIT, where the full sort
wins because it keeps abbreviated keys. tuplesort_set_bound() turns
those off for every bounded sort, and with a heap that made sense: most
tuples are compared to the root once and thrown away.

In quickselect mode the survivors are compared many times, so I expect
keeping abbreviation there would close the gap. John Naylor's caveat in
[7] applies, though: C collation is cheap to abbreviate, but other
collations go through strxfrm, so this may only pay off for C and the
builtin provider.

Correctness: on a cassert build, the regression suite passes, and I
compared the output with quickselect on and off for 11 sort keys and 10
limits (DESC, NULLS FIRST, two collations, multi-column, OFFSET, LATERAL
rescans with a changing bound). All matched. A forced work_mem
fallback also matched, and trace_sort shows it taking the fallback path.
An assert after each prune checks that nothing discarded sorts before
anything kept. 0001 adds a regression test that runs both the
quickselect and the heap paths and compares each against a full sort. It
fails if the prune keeps the wrong rank.

The patches:

0001 the change inspired by simdquickheap, plus the regression test
0002 debug_topn_quickselect, a GUC to switch back to the heap for A/B
testing. Not for commit.

topn-bench.sql has the data set and queries.

What I'd like to know before going further:

1. Is it reasonable to keep two strategies here, or should it be
quickselect only and accept the loss at LIMIT 1-4?
2. EXPLAIN says "top-N heapsort" whichever method ran. Add a method,
or reuse the name? A new one touches TuplesortMethod,
NUM_TUPLESORTMETHODS and explain.c.
3. cost_sort() still charges the heap's tuples * log2(2 * N). If
quickselect is what runs, that over-costs large-N plans. Change it
in this patch, or leave it for later?
4. Should abbreviated keys stay on when the bound is large enough that
quickselect will run, given that the decision is made in
tuplesort_set_bound() before any tuples arrive?

A few things remain unfinished, most important to me is testing on
aarch64, parallel and incremental sort, very wide tuples at a large
LIMIT, and other machines (the cutoff of 8 comes from one box). I'm
happy to run any of those, or whatever workload you think breaks this.

best.

-greg

[1] https://p99conf.io/session/the-simdquickheap-the-fastest-priority-queue-by-2x/ [registration required to watch]
[2] https://arxiv.org/abs/2604.25681
[3] https://github.com/priceds/SIMDQuickHeap
[4] https://curiouscoding.nl/posts/quickheap
[5] https://pg.ddx.io/search?q=quickselect+media+percentile
https://pg.ddx.io/search?q=quickheap+simdquickheap+https%3A%2F%2Farxiv.org%2Fabs%2F2604.25681
[6] https://postgr.es/m/AANLkTikSw+8M36zWaxr+o7jgj4KizeTxXQYt54mcaXgs@mail.gmail.com/
[7] https://www.postgresql.org/message-id/CA%2BCOZaAT5WbEOUwjmw2RHGDyYf%3DhPnnR-xf%3DFh7S-_x4cg9Zmg%40mail.gmail.com

Appendix:

With the LLM we moved from simd-quickheap to quickselect by taking a few
steps:

1. A QuickHeap is incremental quickselect. Take away the SIMD and the
pivot array and that's what's left: it keeps data partly partitioned and
only partitions further when it needs the next minimum. Its speed comes
from replacing a binary heap's scattered sift steps with linear
partition passes over memory. That only matters when the heap is large.

2. Only one Postgres heap gets large. Going through the call sites,
nearly every heap was small: workers, tablespaces, partitions, at most
500 merge tapes. The exception was tuplesort's hand-written top-N heap,
whose size is the LIMIT and can reach millions. That's the only place
we could find where the paper's argument applies.

3. Top-N doesn't need a priority queue. A bounded sort never asks for
the minimum until the very end. It only has to keep the N smallest
tuples seen so far, then output them sorted. So QuickHeap's buckets and
saved pivots aren't needed. What remains is batch quickselect: fill a
buffer, select, discard, repeat. This is also why dropping SIMD didn't
lose the win. The paper's scalar QuickHeap is slower than a binary heap
at 2^20 elements and only ahead at 2^25, but it's doing a full priority
queue's job. Batch quickselect does strictly less work.

4. The memory objection didn't apply here, it ruled out SimdQuickHeap.
Heikki's 2014 point that tuplesort can't allocate a new structure at the
moment it runs out of work_mem. But tuplesort already holds 2×N tuples
in memtuples before building its heap. A 2×N buffer pruned in place uses
exactly that memory and no more, a good fit.

5. This was already a known slow case. The July hackers thread showed
the top-N heap losing to a plain sort at large LIMITs, which gave me
something concrete to measure against.

When finished, I asked the LLM to outline the set of things influencing
this approach I got this impressive list of resources. I've not read
everything listed myself, only skip read enough to validate it, and I
can see how these papers influenced the way the code turned out.

Quickselect itself
- C. A. R. Hoare, "Algorithm 65: Find", Communications of the ACM 4(7), 1961, pp. 321–322. This is the original quickselect. https://doi.org/10.1145/366622.366647
- C. A. R. Hoare, "Quicksort", The Computer Journal 5(1), 1962, pp. 10–16. It describes the partition scheme the patch uses. https://doi.org/10.1093/comjnl/5.1.10

The ninther and the 40-element cutoff
- J. W. Tukey, "The Ninther, a Technique for Low-Effort Robust (Resistant) Location in Large Samples", in Contributions to Survey Sampling and Applied Statistics, Academic Press, 1978, pp. 251–257. This is where the
ninther comes from. https://doi.org/10.1016/b978-0-12-204750-3.50024-1
- J. L. Bentley and M. D. McIlroy, "Engineering a Sort Function", Software: Practice and Experience 23(11), 1993, pp. 1249–1265. It uses median-of-3 for small ranges and the ninther above 40 elements, which is the rule
the patch copies. Postgres's src/include/lib/sort_template.h cites this paper as the basis of its qsort. https://doi.org/10.1002/spe.4380231105

Partitioning when keys are equal
- R. Sedgewick, "Quicksort with Equal Keys", SIAM Journal on Computing 6(2), 1977, pp. 240–267. It shows why the partition loop should stop on keys equal to the pivot, which is what the patch's "runs of equal keys still
split evenly" comment relies on. https://doi.org/10.1137/0206018
- R. Sedgewick, "Implementing Quicksort Programs", Communications of the ACM 21(10), 1978, pp. 847–857. https://doi.org/10.1145/359619.359631

The fallback to sorting after 2·log₂(n) rounds
- D. R. Musser, "Introspective Sorting and Selection Algorithms", Software: Practice and Experience 27(8), 1997, pp. 983–993. This is introsort/introselect: run quickselect and switch to a guaranteed method if it
recurses too deep. https://doi.org/10.1002/(SICI)1097-024X(199708)27:8%3C983::AID-SPE117%3E3.0.CO;2-%23

Better pivots (the gaps from my earlier answer)
- R. W. Floyd and R. L. Rivest, "Expected Time Bounds for Selection", Communications of the ACM 18(3), 1975, pp. 165–172. It samples pivots around the target rank rather than the middle, which is what I said later prune
rounds would benefit from. https://doi.org/10.1145/360680.360691
- C. Martínez and S. Roura, "Optimal Sampling Strategies in Quicksort and Quickselect", SIAM Journal on Computing 31(3), 2001, pp. 683–705. It works out how large the pivot sample should be.
https://doi.org/10.1137/S0097539700382108
- M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest and R. E. Tarjan, "Time Bounds for Selection", Journal of Computer and System Sciences 7(4), 1973, pp. 448–461. This is median-of-medians, the guaranteed linear-time
selection the lazy-partition-heap paper uses. https://doi.org/10.1016/S0022-0000(73)80033-9
- A. Alexandrescu, "Fast Deterministic Selection", 2016, a practical median-of-medians variant. https://arxiv.org/abs/1606.00484

Where the QuickHeap line started
- R. Paredes and G. Navarro, "Optimal Incremental Sorting", ALENEX 2006, pp. 171–182. https://doi.org/10.1137/1.9781611972863.16
- G. Navarro and R. Paredes, "On Sorting, Heaps, and Minimum Spanning Trees", Algorithmica, 2010, pp. 585–620. This is the QuickHeap paper that SimdQuickHeap builds on. https://doi.org/10.1007/s00453-010-9400-6

Websites
- Sedgewick and Wayne, Algorithms (4th ed.), Section 2.3 on quicksort, covering partitioning, equal keys and selection: https://algs4.cs.princeton.edu/23quicksort/
- cppreference on std::nth_element, the standard library's quickselect (introselect in common implementations): https://en.cppreference.com/w/cpp/algorithm/nth_element
- cppreference on std::partial_sort, the standard top-N operation: https://en.cppreference.com/w/cpp/algorithm/partial_sort
- Postgres's sort_template.h, which cites Bentley and McIlroy: https://github.com/postgres/postgres/blob/master/src/include/lib/sort_template.h