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/[email protected]/
[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
From 6000b9cafe4b648ebc4906d4a552e41acde9348a Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Fri, 23 Oct 2026 07:36:30 -0400
Subject: [PATCH v1 2/2] Add debug_topn_quickselect GUC (for testing, not for
commit)
Setting it to off makes bounded sorts use the heap as before, so the two
methods can be compared on one server without a rebuild.
---
src/backend/utils/misc/guc_parameters.dat | 7 +++++++
src/backend/utils/sort/tuplesort.c | 3 ++-
src/include/utils/guc.h | 1 +
3 files changed, 10 insertions(+), 1 deletion(-)
diff --git a/src/backend/utils/misc/guc_parameters.dat
b/src/backend/utils/misc/guc_parameters.dat
index 380679a76c0..756d19a6680 100644
--- a/src/backend/utils/misc/guc_parameters.dat
+++ b/src/backend/utils/misc/guc_parameters.dat
@@ -731,6 +731,13 @@
ifdef => 'DEBUG_NODE_TESTS_ENABLED',
},
+{ name => 'debug_topn_quickselect', type => 'bool', context => 'PGC_USERSET',
group => 'DEVELOPER_OPTIONS',
+ short_desc => 'Uses quickselect instead of a heap for large bounded (top-N)
sorts.',
+ flags => 'GUC_NOT_IN_SAMPLE',
+ variable => 'debug_topn_quickselect',
+ boot_val => 'true',
+},
+
{ name => 'debug_write_read_parse_plan_trees', type => 'bool', context =>
'PGC_SUSET', group => 'DEVELOPER_OPTIONS',
short_desc => 'Set this to force all parse and plan trees to be passed
through outfuncs.c/readfuncs.c, to facilitate catching errors and omissions in
those modules.',
flags => 'GUC_NOT_IN_SAMPLE',
diff --git a/src/backend/utils/sort/tuplesort.c
b/src/backend/utils/sort/tuplesort.c
index 80189302101..7f8d4643080 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -122,6 +122,7 @@
/* GUC variables */
bool trace_sort = false;
+bool debug_topn_quickselect = true;
#ifdef DEBUG_BOUNDED_SORT
bool optimize_bounded_sort = true;
@@ -1146,7 +1147,7 @@ tuplesort_puttuple_common(Tuplesortstate *state,
SortTuple *tuple,
* Below a bound of 8 the buffer refills too
often to pay for
* itself, and the heap wins.
*/
- if (state->bound >= 8 && !LACKMEM(state))
+ if (debug_topn_quickselect && state->bound >= 8
&& !LACKMEM(state))
{
if (trace_sort)
elog(LOG, "switching to bounded
quickselect at %d tuples: %s",
diff --git a/src/include/utils/guc.h b/src/include/utils/guc.h
index 164efba6b51..13171f97c3c 100644
--- a/src/include/utils/guc.h
+++ b/src/include/utils/guc.h
@@ -327,6 +327,7 @@ extern PGDLLIMPORT int tcp_user_timeout;
extern PGDLLIMPORT char *role_string;
extern PGDLLIMPORT bool in_hot_standby_guc;
extern PGDLLIMPORT bool trace_sort;
+extern PGDLLIMPORT bool debug_topn_quickselect;
#ifdef DEBUG_BOUNDED_SORT
extern PGDLLIMPORT bool optimize_bounded_sort;
--
2.54.0
From c0387fd7845b60b1f4759f34593aa30db2b21444 Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Fri, 23 Oct 2026 07:36:15 -0400
Subject: [PATCH v1 1/2] Use quickselect instead of a heap for large bounded
sorts
A bounded sort (ORDER BY ... LIMIT N) switches to a heap of N tuples
once it has 2 * N tuples in memory, and pays O(log N) comparisons for
every tuple that gets into the heap. When N is large most tuples get
in, and the heap is slower than an unbounded quicksort.
Instead, keep a buffer of up to 2 * N tuples. Whenever it fills, use
quickselect to keep the N smallest and free the rest; that costs O(N)
per N admitted tuples, so O(1) amortized per tuple. An incoming tuple
is still rejected with one comparison, against the largest survivor of
the last prune, as the heap does with its root. At the end the
survivors are sorted with tuplesort_sort_memtuples(), which picks radix
sort or the specialized qsort the same way an unbounded sort does.
The buffer never holds more tuples than were in memory when the heap
would have been built, so peak memory is unchanged. If wider tuples
later push us over work_mem, prune to N and finish with the heap as
before. Bounds below 8 keep using the heap: there the buffer refills
every few tuples and the heap is faster.
Quickselect uses median-of-3 (ninther above 40 elements) pivots and
Hoare partitioning, which splits runs of equal keys evenly. If it has
not converged after 2 * log2(n) rounds it sorts the remaining range, so
the worst case is O(n log n) per prune.
---
src/backend/utils/sort/tuplesort.c | 185 ++++++++++++++++++++++++
src/test/regress/expected/tuplesort.out | 51 +++++++
src/test/regress/sql/tuplesort.sql | 41 ++++++
3 files changed, 277 insertions(+)
diff --git a/src/backend/utils/sort/tuplesort.c
b/src/backend/utils/sort/tuplesort.c
index 37c40763ee0..80189302101 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -155,6 +155,8 @@ typedef enum
{
TSS_INITIAL, /* Loading tuples; still within
memory limit */
TSS_BOUNDED, /* Loading tuples into
bounded-size heap */
+ TSS_BOUNDED_SELECT, /* Loading tuples into a 2 *
bound buffer that
+ * quickselect
prunes back to bound */
TSS_BUILDRUNS, /* Loading tuples; writing to
tape */
TSS_SORTEDINMEM, /* Sort completed entirely in
memory */
TSS_SORTEDONTAPE, /* Sort completed, final run is
on tape */
@@ -460,6 +462,7 @@ static bool mergereadnext(Tuplesortstate *state,
LogicalTape *srcTape, SortTuple
static void dumptuples(Tuplesortstate *state, bool alltuples);
static void make_bounded_heap(Tuplesortstate *state);
static void sort_bounded_heap(Tuplesortstate *state);
+static void prune_bounded_select(Tuplesortstate *state);
static void tuplesort_sort_memtuples(Tuplesortstate *state);
static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple);
static void tuplesort_heap_replace_top(Tuplesortstate *state, SortTuple
*tuple);
@@ -1137,6 +1140,24 @@ tuplesort_puttuple_common(Tuplesortstate *state,
SortTuple *tuple,
(state->memtupcount > state->bound * 2 ||
(state->memtupcount > state->bound &&
LACKMEM(state))))
{
+ /*
+ * If 2 * bound tuples fit in memory, keep that
many and prune
+ * back to bound with quickselect whenever the
buffer fills.
+ * Below a bound of 8 the buffer refills too
often to pay for
+ * itself, and the heap wins.
+ */
+ if (state->bound >= 8 && !LACKMEM(state))
+ {
+ if (trace_sort)
+ elog(LOG, "switching to bounded
quickselect at %d tuples: %s",
+ state->memtupcount,
+
pg_rusage_show(&state->ru_start));
+ prune_bounded_select(state);
+ state->status = TSS_BOUNDED_SELECT;
+ MemoryContextSwitchTo(oldcontext);
+ return;
+ }
+
if (trace_sort)
elog(LOG, "switching to bounded
heapsort at %d tuples: %s",
state->memtupcount,
@@ -1190,6 +1211,37 @@ tuplesort_puttuple_common(Tuplesortstate *state,
SortTuple *tuple,
}
break;
+ case TSS_BOUNDED_SELECT:
+
+ /*
+ * memtuples[bound - 1] is the largest of the bound
smallest
+ * tuples seen so far, so nothing >= it can make the
cut.
+ */
+ if (COMPARETUP(state, tuple,
&state->memtuples[state->bound - 1]) >= 0)
+ {
+ free_sort_tuple(state, tuple);
+ CHECK_FOR_INTERRUPTS();
+ break;
+ }
+ state->memtuples[state->memtupcount++] = *tuple;
+ if (state->memtupcount > state->bound * 2)
+ prune_bounded_select(state);
+ else if (LACKMEM(state))
+ {
+ /*
+ * Tuples got wider than when we started. Keep
just bound of
+ * them and finish with the heap, which never
holds more.
+ */
+ if (trace_sort)
+ elog(LOG, "switching from bounded
quickselect to heapsort at %d tuples: %s",
+ state->memtupcount,
+
pg_rusage_show(&state->ru_start));
+ prune_bounded_select(state);
+ state->status = TSS_INITIAL;
+ make_bounded_heap(state);
+ }
+ break;
+
case TSS_BUILDRUNS:
/*
@@ -1319,6 +1371,18 @@ tuplesort_performsort(Tuplesortstate *state)
state->markpos_eof = false;
break;
+ case TSS_BOUNDED_SELECT:
+ if (state->memtupcount > state->bound)
+ prune_bounded_select(state);
+ tuplesort_sort_memtuples(state);
+ state->status = TSS_SORTEDINMEM;
+ state->boundUsed = true;
+ state->current = 0;
+ state->eof_reached = false;
+ state->markpos_offset = 0;
+ state->markpos_eof = false;
+ break;
+
case TSS_BUILDRUNS:
/*
@@ -2562,6 +2626,127 @@ sort_bounded_heap(Tuplesortstate *state)
state->boundUsed = true;
}
+/* Index of the median of memtuples[i], [j], [k] */
+static inline int
+med3_index(Tuplesortstate *state, int i, int j, int k)
+{
+ SortTuple *a = state->memtuples;
+
+ return COMPARETUP(state, &a[i], &a[j]) < 0 ?
+ (COMPARETUP(state, &a[j], &a[k]) < 0 ? j :
+ (COMPARETUP(state, &a[i], &a[k]) < 0 ? k : i)) :
+ (COMPARETUP(state, &a[j], &a[k]) > 0 ? j :
+ (COMPARETUP(state, &a[i], &a[k]) < 0 ? i : k));
+}
+
+/*
+ * Rearrange memtuples[0 .. n-1] so that memtuples[k] holds the tuple it would
+ * hold if the array were sorted, with nothing larger before it and nothing
+ * smaller after it.
+ *
+ * Hoare partitioning stops on keys equal to the pivot, so runs of equal keys
+ * still split evenly. If pivots keep coming out badly, sort what is left.
+ */
+static void
+tuplesort_select(Tuplesortstate *state, int n, int k)
+{
+ SortTuple *a = state->memtuples;
+ int lo = 0;
+ int hi = n - 1;
+ int budget = 2 * (pg_leftmost_one_pos32((uint32) n)
+ 1);
+
+ Assert(k >= 0 && k < n);
+
+ while (hi > lo)
+ {
+ int len = hi - lo + 1;
+ int mid = lo + len / 2;
+ int p;
+ int i;
+ int j;
+ SortTuple tmp;
+
+ CHECK_FOR_INTERRUPTS();
+
+ if (--budget < 0)
+ {
+ qsort_tuple(a + lo, len, state->base.comparetup, state);
+ return;
+ }
+
+ /* median of three, or pseudo-median of nine for larger ranges
*/
+ if (len > 40)
+ {
+ int d = len / 8;
+
+ p = med3_index(state,
+ med3_index(state, lo, lo +
d, lo + 2 * d),
+ med3_index(state, mid - d,
mid, mid + d),
+ med3_index(state, hi - 2 *
d, hi - d, hi));
+ }
+ else
+ p = med3_index(state, lo, mid, hi);
+
+ tmp = a[lo];
+ a[lo] = a[p];
+ a[p] = tmp;
+
+ i = lo;
+ j = hi + 1;
+ for (;;)
+ {
+ while (COMPARETUP(state, &a[++i], &a[lo]) < 0)
+ if (i == hi)
+ break;
+ while (COMPARETUP(state, &a[lo], &a[--j]) < 0)
+ if (j == lo)
+ break;
+ if (i >= j)
+ break;
+ tmp = a[i];
+ a[i] = a[j];
+ a[j] = tmp;
+ }
+ tmp = a[lo];
+ a[lo] = a[j];
+ a[j] = tmp;
+
+ /* a[lo .. j-1] <= a[j] <= a[j+1 .. hi] */
+ if (j == k)
+ return;
+ if (j > k)
+ hi = j - 1;
+ else
+ lo = j + 1;
+ }
+}
+
+/*
+ * Keep only the bound smallest memtuples, leaving the largest of them at
+ * memtuples[bound - 1].
+ */
+static void
+prune_bounded_select(Tuplesortstate *state)
+{
+ Assert(state->bounded);
+ Assert(state->memtupcount > state->bound);
+ Assert(SERIAL(state));
+
+ tuplesort_select(state, state->memtupcount, state->bound - 1);
+#ifdef USE_ASSERT_CHECKING
+ for (int i = 0; i < state->memtupcount; i++)
+ {
+ int c = COMPARETUP(state,
&state->memtuples[i],
+
&state->memtuples[state->bound - 1]);
+
+ Assert(i < state->bound ? c <= 0 : c >= 0);
+ }
+#endif
+ for (int i = state->bound; i < state->memtupcount; i++)
+ free_sort_tuple(state, &state->memtuples[i]);
+ state->memtupcount = state->bound;
+}
+
/* radix sort routines */
diff --git a/src/test/regress/expected/tuplesort.out
b/src/test/regress/expected/tuplesort.out
index fc1321bf443..35925a11e30 100644
--- a/src/test/regress/expected/tuplesort.out
+++ b/src/test/regress/expected/tuplesort.out
@@ -703,3 +703,54 @@ EXPLAIN (COSTS OFF) :qry;
(10 rows)
COMMIT;
+----
+-- Bounded sorts. Once 2 * bound tuples are in memory, bounds of at least
+-- 8 use quickselect and smaller ones use a heap. Compare each with a full
+-- sort, which is what a bound above INT_MAX / 2 gets.
+----
+CREATE TEMP TABLE bounded_sort AS
+ SELECT g AS id, (g * 7919) % 1000 AS k, md5(g::text) AS t
+ FROM generate_series(1, 5000) g;
+-- true if ORDER BY ... LIMIT returns the same rows, in the same order, as a
+-- full sort cut to the same length
+CREATE FUNCTION bounded_sort_ok(ord text, lim int) RETURNS bool
+LANGUAGE plpgsql AS $$
+DECLARE
+ bounded int[];
+ full_sort int[];
+BEGIN
+ EXECUTE format('SELECT array(SELECT id FROM bounded_sort ORDER BY %s LIMIT
%s)',
+ ord, lim) INTO bounded;
+ EXECUTE format('SELECT array(SELECT id FROM (SELECT id FROM bounded_sort
ORDER BY %s LIMIT 1073741824) f LIMIT %s)',
+ ord, lim) INTO full_sort;
+ RETURN bounded = full_sort;
+END $$;
+SELECT o, l
+FROM unnest(ARRAY['k, id', 'k DESC, id', 't', 't DESC', 'id DESC']) o,
+ unnest(ARRAY[1, 7, 8, 9, 100, 1250, 2499, 2500]) l
+WHERE NOT bounded_sort_ok(o, l);
+ o | l
+---+---
+(0 rows)
+
+-- duplicates: the bound falls inside a run of equal keys
+SELECT count(*), count(DISTINCT k), min(k), max(k)
+FROM (SELECT k FROM bounded_sort ORDER BY k LIMIT 2000) s;
+ count | count | min | max
+-------+-------+-----+-----
+ 2000 | 400 | 0 | 399
+(1 row)
+
+-- rescan with a different bound each time
+SELECT l, max(s.k), count(*)
+FROM generate_series(10, 50, 20) l,
+ LATERAL (SELECT k FROM bounded_sort ORDER BY k, id LIMIT l) s
+GROUP BY l ORDER BY l;
+ l | max | count
+----+-----+-------
+ 10 | 1 | 10
+ 30 | 5 | 30
+ 50 | 9 | 50
+(3 rows)
+
+DROP FUNCTION bounded_sort_ok(text, int);
diff --git a/src/test/regress/sql/tuplesort.sql
b/src/test/regress/sql/tuplesort.sql
index 8476e594e6c..997b12ab7c3 100644
--- a/src/test/regress/sql/tuplesort.sql
+++ b/src/test/regress/sql/tuplesort.sql
@@ -305,3 +305,44 @@ EXPLAIN (COSTS OFF) :qry;
:qry;
COMMIT;
+
+----
+-- Bounded sorts. Once 2 * bound tuples are in memory, bounds of at least
+-- 8 use quickselect and smaller ones use a heap. Compare each with a full
+-- sort, which is what a bound above INT_MAX / 2 gets.
+----
+CREATE TEMP TABLE bounded_sort AS
+ SELECT g AS id, (g * 7919) % 1000 AS k, md5(g::text) AS t
+ FROM generate_series(1, 5000) g;
+
+-- true if ORDER BY ... LIMIT returns the same rows, in the same order, as a
+-- full sort cut to the same length
+CREATE FUNCTION bounded_sort_ok(ord text, lim int) RETURNS bool
+LANGUAGE plpgsql AS $$
+DECLARE
+ bounded int[];
+ full_sort int[];
+BEGIN
+ EXECUTE format('SELECT array(SELECT id FROM bounded_sort ORDER BY %s LIMIT
%s)',
+ ord, lim) INTO bounded;
+ EXECUTE format('SELECT array(SELECT id FROM (SELECT id FROM bounded_sort
ORDER BY %s LIMIT 1073741824) f LIMIT %s)',
+ ord, lim) INTO full_sort;
+ RETURN bounded = full_sort;
+END $$;
+
+SELECT o, l
+FROM unnest(ARRAY['k, id', 'k DESC, id', 't', 't DESC', 'id DESC']) o,
+ unnest(ARRAY[1, 7, 8, 9, 100, 1250, 2499, 2500]) l
+WHERE NOT bounded_sort_ok(o, l);
+
+-- duplicates: the bound falls inside a run of equal keys
+SELECT count(*), count(DISTINCT k), min(k), max(k)
+FROM (SELECT k FROM bounded_sort ORDER BY k LIMIT 2000) s;
+
+-- rescan with a different bound each time
+SELECT l, max(s.k), count(*)
+FROM generate_series(10, 50, 20) l,
+ LATERAL (SELECT k FROM bounded_sort ORDER BY k, id LIMIT l) s
+GROUP BY l ORDER BY l;
+
+DROP FUNCTION bounded_sort_ok(text, int);
--
2.54.0
