On Wed, Oct 28, 2026 at 10:11 AM John Naylor <[email protected]> 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
From 49c8592c9729ab26005fa53385759fbecc2de327 Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Fri, 23 Oct 2026 07:36:30 -0400
Subject: [PATCH v2 2/3] 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 7650c8ef806..7de34da217a 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -131,6 +131,7 @@ StaticAssertDecl(TOPN_SELECT_MIN_BUFFER <
INITIAL_MEMTUPSIZE,
/* GUC variables */
bool trace_sort = false;
+bool debug_topn_quickselect = true;
#ifdef DEBUG_BOUNDED_SORT
bool optimize_bounded_sort = true;
@@ -1153,7 +1154,7 @@ tuplesort_puttuple_common(Tuplesortstate *state,
SortTuple *tuple,
* If 2 * bound tuples fit in memory, keep a
buffer of them and
* prune it back to bound with quickselect
whenever it fills.
*/
- if (state->bound > 0 && !LACKMEM(state))
+ if (debug_topn_quickselect && state->bound > 0
&& !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 1cee9ec4d8487d277fd15f6827fbc610c3a2fccb Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Fri, 23 Oct 2026 07:36:15 -0400
Subject: [PATCH v2 1/3] Use quickselect instead of a heap for 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, or the input
arrives in an order that admits most tuples, the heap is slow; at large
N it can lose to an unbounded quicksort.
Instead, keep a buffer of up to Max(2 * N, 1000) tuples. Whenever it
fills, use quickselect to keep the N smallest and free the rest. That
costs O(buffer) per (buffer - 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 1000-tuple floor keeps small N from pruning every few tuples; it
fits in the initial memtuples array, so the array never grows past what
the sort already allocated. If the buffer fills work_mem before it
fills up, prune early; if N tuples alone no longer fit, prune to N and
finish with the existing heap code, which never holds more than N.
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 | 203 ++++++++++++++++++++++++
src/test/regress/expected/tuplesort.out | 73 +++++++++
src/test/regress/sql/tuplesort.sql | 59 +++++++
3 files changed, 335 insertions(+)
diff --git a/src/backend/utils/sort/tuplesort.c
b/src/backend/utils/sort/tuplesort.c
index da3c41d7084..7650c8ef806 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -120,6 +120,15 @@
#define INITIAL_MEMTUPSIZE Max(1024, \
ALLOCSET_SEPARATE_THRESHOLD / sizeof(SortTuple) + 1)
+/*
+ * A quickselect bounded sort buffers at least this many tuples between
+ * prunes, so that a small LIMIT does not prune every few tuples. It must fit
+ * in the initial memtuples array, which is never shrunk.
+ */
+#define TOPN_SELECT_MIN_BUFFER 1000
+StaticAssertDecl(TOPN_SELECT_MIN_BUFFER < INITIAL_MEMTUPSIZE,
+ "TOPN_SELECT_MIN_BUFFER must fit in the
initial memtuples array");
+
/* GUC variables */
bool trace_sort = false;
@@ -155,6 +164,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 +471,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 +1149,22 @@ 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 a
buffer of them and
+ * prune it back to bound with quickselect
whenever it fills.
+ */
+ if (state->bound > 0 && !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 +1218,48 @@ 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;
+ }
+ /* the buffer never outgrows the array; see
TOPN_SELECT_MIN_BUFFER */
+ Assert(state->memtupcount < state->memtupsize);
+ state->memtuples[state->memtupcount++] = *tuple;
+ if (state->memtupcount > Max(state->bound * 2,
TOPN_SELECT_MIN_BUFFER))
+ prune_bounded_select(state);
+ else if (LACKMEM(state) && state->memtupcount >
state->bound * 2)
+ {
+ /*
+ * The floor, not the bound, filled work_mem.
More than bound
+ * tuples arrived since the last prune, so
pruning early still
+ * costs O(1) per tuple.
+ */
+ 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 +1389,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 +2644,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..448eb73ee99 100644
--- a/src/test/regress/expected/tuplesort.out
+++ b/src/test/regress/expected/tuplesort.out
@@ -703,3 +703,76 @@ EXPLAIN (COSTS OFF) :qry;
(10 rows)
COMMIT;
+----
+-- Bounded sorts. Once 2 * bound tuples are in memory, the sort keeps a
+-- buffer of them (at least TOPN_SELECT_MIN_BUFFER, 1000) and prunes it to
+-- bound with quickselect. If work_mem runs out first it falls back to 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, 2, 7, 100, 499, 500, 501, 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)
+
+-- work_mem runs out after the buffer starts: narrow rows with large keys
+-- come first, then wide rows that sort before them, so the survivors get
+-- wider until bound of them no longer fit and the sort falls back to a heap
+CREATE TEMP TABLE bounded_sort_wide AS
+ SELECT g AS id,
+ CASE WHEN g > 3000 THEN g - 3000 ELSE 100000 + g END AS k,
+ CASE WHEN g > 3000 THEN repeat(md5(g::text), 16) ELSE 'x' END AS pad
+ FROM generate_series(1, 6000) g;
+BEGIN;
+SET LOCAL work_mem = '256kB';
+SELECT array(SELECT id FROM (SELECT id, pad FROM bounded_sort_wide
+ ORDER BY k, id LIMIT 400) s) =
+ array(SELECT id FROM (SELECT id FROM bounded_sort_wide
+ ORDER BY k, id LIMIT 1073741824) f LIMIT 400) AS
ok;
+ ok
+----
+ t
+(1 row)
+
+COMMIT;
+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..fa2da7f2f4f 100644
--- a/src/test/regress/sql/tuplesort.sql
+++ b/src/test/regress/sql/tuplesort.sql
@@ -305,3 +305,62 @@ EXPLAIN (COSTS OFF) :qry;
:qry;
COMMIT;
+
+----
+-- Bounded sorts. Once 2 * bound tuples are in memory, the sort keeps a
+-- buffer of them (at least TOPN_SELECT_MIN_BUFFER, 1000) and prunes it to
+-- bound with quickselect. If work_mem runs out first it falls back to 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, 2, 7, 100, 499, 500, 501, 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;
+
+-- work_mem runs out after the buffer starts: narrow rows with large keys
+-- come first, then wide rows that sort before them, so the survivors get
+-- wider until bound of them no longer fit and the sort falls back to a heap
+CREATE TEMP TABLE bounded_sort_wide AS
+ SELECT g AS id,
+ CASE WHEN g > 3000 THEN g - 3000 ELSE 100000 + g END AS k,
+ CASE WHEN g > 3000 THEN repeat(md5(g::text), 16) ELSE 'x' END AS pad
+ FROM generate_series(1, 6000) g;
+BEGIN;
+SET LOCAL work_mem = '256kB';
+SELECT array(SELECT id FROM (SELECT id, pad FROM bounded_sort_wide
+ ORDER BY k, id LIMIT 400) s) =
+ array(SELECT id FROM (SELECT id FROM bounded_sort_wide
+ ORDER BY k, id LIMIT 1073741824) f LIMIT 400) AS
ok;
+COMMIT;
+
+DROP FUNCTION bounded_sort_ok(text, int);
--
2.54.0
From 9287c3ffea38901654c33a3c20dfb90436df770e Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Thu, 29 Oct 2026 08:50:53 -0400
Subject: [PATCH v2 3/3] Experimental: copy bounded-sort survivors into a fresh
context
At each quickselect prune, copy the bound survivors into a spare tuple
context and reset the old one, instead of pfree'ing each discarded
tuple. The reset drops the losers and every tuple the admission check
freed since the last prune, and leaves the survivors packed together.
Only the MinimalTuple and Datum variants, the only ones used by bounded
sorts, provide the new tuplelen callback that this needs; others keep
the pfree path. datum1 is re-derived with removeabbrev after the move,
which is valid because bounded sorts never abbreviate.
This is a step toward a bump context for bounded sorts, which would
also need the rejected tuples not to be copied in the first place.
debug_topn_context_swap turns it off for A/B testing.
---
src/backend/utils/misc/guc_parameters.dat | 7 +++
src/backend/utils/sort/tuplesort.c | 69 +++++++++++++++++++++-
src/backend/utils/sort/tuplesortvariants.c | 18 ++++++
src/include/utils/guc.h | 1 +
src/include/utils/tuplesort.h | 8 +++
5 files changed, 100 insertions(+), 3 deletions(-)
diff --git a/src/backend/utils/misc/guc_parameters.dat
b/src/backend/utils/misc/guc_parameters.dat
index 756d19a6680..c5d99a4e993 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_context_swap', type => 'bool', context => 'PGC_USERSET',
group => 'DEVELOPER_OPTIONS',
+ short_desc => 'Copies bounded-sort survivors into a fresh memory context at
each quickselect prune.',
+ flags => 'GUC_NOT_IN_SAMPLE',
+ variable => 'debug_topn_context_swap',
+ boot_val => 'true',
+},
+
{ 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',
diff --git a/src/backend/utils/sort/tuplesort.c
b/src/backend/utils/sort/tuplesort.c
index 7de34da217a..4f862a5fecc 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -132,6 +132,7 @@ StaticAssertDecl(TOPN_SELECT_MIN_BUFFER <
INITIAL_MEMTUPSIZE,
/* GUC variables */
bool trace_sort = false;
bool debug_topn_quickselect = true;
+bool debug_topn_context_swap = true;
#ifdef DEBUG_BOUNDED_SORT
bool optimize_bounded_sort = true;
@@ -201,6 +202,8 @@ struct Tuplesortstate
bool bounded; /* did caller specify a maximum
number of
* tuples to
return? */
bool boundUsed; /* true if we made use of a
bounded heap */
+ MemoryContext sparetuplecontext; /* bounded quickselect copies
the
+
* survivors here at each prune */
int bound; /* if bounded, the
maximum number of tuples */
int64 tupleMem; /* memory consumed by
individual tuples.
* storing this
separately from what we track
@@ -473,6 +476,10 @@ 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 prune_bounded_select_swap(Tuplesortstate *state);
+#define PRUNE_BOUNDED(state) \
+ ((state)->sparetuplecontext ? prune_bounded_select_swap(state) : \
+ prune_bounded_select(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);
@@ -693,6 +700,7 @@ tuplesort_begin_batch(Tuplesortstate *state)
state->status = TSS_INITIAL;
state->bounded = false;
state->boundUsed = false;
+ state->sparetuplecontext = NULL;
state->availMem = state->allowedMem;
@@ -1160,7 +1168,12 @@ tuplesort_puttuple_common(Tuplesortstate *state,
SortTuple *tuple,
elog(LOG, "switching to bounded
quickselect at %d tuples: %s",
state->memtupcount,
pg_rusage_show(&state->ru_start));
- prune_bounded_select(state);
+ if (debug_topn_context_swap &&
state->base.tuplelen != NULL)
+ state->sparetuplecontext =
+
AllocSetContextCreate(state->base.sortcontext,
+
"Caller tuples",
+
ALLOCSET_DEFAULT_SIZES);
+ PRUNE_BOUNDED(state);
state->status = TSS_BOUNDED_SELECT;
MemoryContextSwitchTo(oldcontext);
return;
@@ -1235,7 +1248,7 @@ tuplesort_puttuple_common(Tuplesortstate *state,
SortTuple *tuple,
Assert(state->memtupcount < state->memtupsize);
state->memtuples[state->memtupcount++] = *tuple;
if (state->memtupcount > Max(state->bound * 2,
TOPN_SELECT_MIN_BUFFER))
- prune_bounded_select(state);
+ PRUNE_BOUNDED(state);
else if (LACKMEM(state) && state->memtupcount >
state->bound * 2)
{
/*
@@ -1243,7 +1256,7 @@ tuplesort_puttuple_common(Tuplesortstate *state,
SortTuple *tuple,
* tuples arrived since the last prune, so
pruning early still
* costs O(1) per tuple.
*/
- prune_bounded_select(state);
+ PRUNE_BOUNDED(state);
}
else if (LACKMEM(state))
{
@@ -2766,6 +2779,56 @@ prune_bounded_select(Tuplesortstate *state)
state->memtupcount = state->bound;
}
+/*
+ * Keep the bound smallest memtuples like prune_bounded_select(), but instead
+ * of freeing each discarded tuple, copy the survivors into the spare tuple
+ * context and reset the old one. That drops the losers, and every tuple the
+ * admission check freed since the last prune, in one step, and leaves the
+ * survivors packed together.
+ */
+static void
+prune_bounded_select_swap(Tuplesortstate *state)
+{
+ MemoryContext from = state->base.tuplecontext;
+ MemoryContext to = state->sparetuplecontext;
+
+ Assert(state->base.tuplelen != NULL && to != NULL);
+
+ tuplesort_select(state, state->memtupcount, state->bound - 1);
+
+ for (int i = 0; i < state->memtupcount; i++)
+ {
+ SortTuple *stup = &state->memtuples[i];
+ char *old = stup->tuple;
+ char *new;
+ Size len;
+
+ if (old == NULL)
+ continue;
+ FREEMEM(state, GetMemoryChunkSpace(old));
+ if (i >= state->bound)
+ continue;
+
+ len = state->base.tuplelen(state, stup);
+ new = MemoryContextAlloc(to, len);
+ memcpy(new, old, len);
+ USEMEM(state, GetMemoryChunkSpace(new));
+ stup->tuple = new;
+
+ /*
+ * datum1 may point into the old copy. Bounded sorts never
abbreviate
+ * (see tuplesort_set_bound), so removeabbrev just re-derives
it from
+ * the new copy.
+ */
+ REMOVEABBREV(state, stup, 1);
+ }
+ state->memtupcount = state->bound;
+
+ MemoryContextReset(from);
+ state->base.tuplecontext = to;
+ state->sparetuplecontext = from;
+}
+
/* radix sort routines */
diff --git a/src/backend/utils/sort/tuplesortvariants.c
b/src/backend/utils/sort/tuplesortvariants.c
index c648c78455a..4c163086723 100644
--- a/src/backend/utils/sort/tuplesortvariants.c
+++ b/src/backend/utils/sort/tuplesortvariants.c
@@ -59,6 +59,8 @@ static int comparetup_heap(const SortTuple *a, const
SortTuple *b,
Tuplesortstate *state);
static int comparetup_heap_tiebreak(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state);
+static Size tuplelen_heap(Tuplesortstate *state, SortTuple *stup);
+static Size tuplelen_datum(Tuplesortstate *state, SortTuple *stup);
static void writetup_heap(Tuplesortstate *state, LogicalTape *tape,
SortTuple *stup);
static void readtup_heap(Tuplesortstate *state, SortTuple *stup,
@@ -213,6 +215,7 @@ tuplesort_begin_heap(TupleDesc tupDesc,
base->comparetup_tiebreak = comparetup_heap_tiebreak;
base->writetup = writetup_heap;
base->readtup = readtup_heap;
+ base->tuplelen = tuplelen_heap;
base->haveDatum1 = true;
base->arg = tupDesc; /* assume we need not copy tupDesc */
@@ -696,6 +699,7 @@ tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid
sortCollation,
base->comparetup_tiebreak = comparetup_datum_tiebreak;
base->writetup = writetup_datum;
base->readtup = readtup_datum;
+ base->tuplelen = tuplelen_datum;
base->haveDatum1 = true;
base->arg = arg;
@@ -1296,6 +1300,12 @@ comparetup_heap_tiebreak(const SortTuple *a, const
SortTuple *b, Tuplesortstate
return 0;
}
+static Size
+tuplelen_heap(Tuplesortstate *state, SortTuple *stup)
+{
+ return ((MinimalTuple) stup->tuple)->t_len;
+}
+
static void
writetup_heap(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
{
@@ -2025,6 +2035,14 @@ comparetup_datum_tiebreak(const SortTuple *a, const
SortTuple *b, Tuplesortstate
return compare;
}
+static Size
+tuplelen_datum(Tuplesortstate *state, SortTuple *stup)
+{
+ TuplesortDatumArg *arg = (TuplesortDatumArg *)
TuplesortstateGetPublic(state)->arg;
+
+ return datumGetSize(PointerGetDatum(stup->tuple), false,
arg->datumTypeLen);
+}
+
static void
writetup_datum(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
{
diff --git a/src/include/utils/guc.h b/src/include/utils/guc.h
index 13171f97c3c..453ea182924 100644
--- a/src/include/utils/guc.h
+++ b/src/include/utils/guc.h
@@ -328,6 +328,7 @@ extern PGDLLIMPORT char *role_string;
extern PGDLLIMPORT bool in_hot_standby_guc;
extern PGDLLIMPORT bool trace_sort;
extern PGDLLIMPORT bool debug_topn_quickselect;
+extern PGDLLIMPORT bool debug_topn_context_swap;
#ifdef DEBUG_BOUNDED_SORT
extern PGDLLIMPORT bool optimize_bounded_sort;
diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h
index da68f45acf2..14629fbc593 100644
--- a/src/include/utils/tuplesort.h
+++ b/src/include/utils/tuplesort.h
@@ -179,6 +179,14 @@ typedef struct
*/
void (*freestate) (Tuplesortstate *state);
+ /*
+ * Optional: size in bytes of the self-contained allocation holding
+ * stup->tuple, so a bounded sort can copy survivors into a fresh memory
+ * context instead of freeing each discarded tuple. NULL if the
variant's
+ * tuples cannot be moved with a plain memcpy.
+ */
+ Size (*tuplelen) (Tuplesortstate *state, SortTuple *stup);
+
/*
* The subsequent fields are used in the implementations of the
functions
* above.
--
2.54.0
