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

On Wed, Oct 28, 2026 at 10:11 AM John Naylor <johncnaylorls(at)gmail(dot)com> wrote:
> Do we get any improvement with smaller numbers than 10k?

Depends on the input order. With random input almost every tuple loses
the first comparison, so neither method does much work and there's
little to win: int8 is within 3% of master up to LIMIT 10k, en_US text
starts to pull ahead at 5k (0.92x) and is 0.86x at 10k. When most
tuples get in, which is what you see on input arriving in reverse order,
the win starts small. v1, median ms of 5 runs, 2M rows:

LIMIT reversed int8 reversed en_US text
master v1 master v1
8 198 181 0.91x 997 812 0.81x
64 258 177 0.69x 1,688 757 0.45x
1000 362 174 0.48x 2,488 679 0.27x
10000 416 174 0.42x 2,884 625 0.22x (text: 5000)

> It's not reasonable IMO. If there are enough advantages to a new
> method, we should just switch. If not, then we won't. I do suspect the
> regression at small LIMITs is because N*2 is not enough room to
> accumulate enough tuples to make it worthwhile. Just a hunch, but
> maybe a floor would help.

Your hunch was right. v2-0001 drops the N >= 8 split and sizes the
buffer as Max(2 * N, 1000) tuples, so a small LIMIT prunes every ~1000
admitted tuples instead of every N. 1000 fits in the initial memtuples
array, so nothing grows. I swept floors of 0, 64, 256, 1024 and 4096
first. From LIMIT 2 up, 1024 got most of the gain and 4096 only a few
points more; at LIMIT 1 neither gets close to the heap. I went with
1000.

On the same reversed input, v2 against master:

LIMIT 1 2 3 4 8 16 256 10000
int8 1.13x 1.04x 0.98x 0.92x 0.81x 0.75x 0.52x 0.43x
en_US 1.63x 1.10x 0.82x 0.70x 0.52x 0.41x 0.28x 0.20x

So LIMIT 1 and 2 on reversed input are still slower than the heap (v1
at LIMIT 1 was 2.65x). For N = 1 the heap does one comparison and one
replace per tuple, and a select over 1000 tuples can't match that.
Random input at LIMIT 1 is 0.99x, because there the first comparison
rejects nearly everything. If that LIMIT 1/2 corner matters, I'd
rather special-case N = 1 as a running minimum than keep the heap for
it. The heap now only runs when bound tuples alone no longer fit in
work_mem, as a memory fallback. 0001 has a regress test that forces
that path.

Large N is unchanged from v1: int8 0.40x at 1M, C text 0.41x at 1M.

> Also, with quickselect, it seems like an easy prerequisite to Andres'
> idea of copying the survivors into a new context instead of
> individually freeing the losers? That would allow a bump context

Yes, and that's now in v2-0003. At each prune it copies the bound
survivors into a spare aset context and resets the old one. The reset
drops the losers, and everything the admission check freed since the
last prune, in one go. It needs a tuplelen callback, which only the
MinimalTuple and Datum variants (the only bounded-sort users) get. It's
still aset, because a rejected tuple is copied into tuplecontext before
the bounded check runs, so it still has to be pfree'd. A bump context
needs that pre-check from Andres' mail too, which I haven't done.

On its own the swap is mixed (same build, swap vs free):

ORDER BY LIMIT free swap
en_US text 1,000,000 3,833 3,158 0.82x
C text 1,000,000 1,711 1,489 0.87x
int8 2,400,000 981 1,112 1.13x
int8 rev 10,000 166 194 1.17x

perf stat lines up: for en_US at 1M, L1d misses drop 15% and cycles 19%
for the same instruction count. The packed survivors help when
comparisons chase into the tuples. For int8 the key sits in datum1 and
the copy is pure overhead. So I'd keep 0003 out of the main patch for
now. It might turn positive once rejected tuples stop being copied (no
pfree at all), but I'd want to measure that rather than guess.

> Well, if you can't be bothered read them, why should I?

Just to close this off, the code itself comes down to Hoare's partition
and the Bentley/McIlroy pivot choice that our qsort already uses.

These numbers are from a c7i.4xlarge on Debian 13 (gcc 14, release
builds, one backend pinned to a core), so different hardware from v1.

0001 passes make check on its own and with the series;
0002 is still the A/B GUC and not for commit.

best.

-greg