Hello, v3 attached, rebased on master (4f89416c9db). One fix: v2 fails the contrib/cube regression test. I only ran the core regression suite before posting v2, sorry about that.
The cube test runs ORDER BY c~>2 LIMIT 15 once as a GiST ordered index scan and once as a seq scan plus sort, and expects the same output. Two rows tie on c~>2 = 270. SQL leaves their order unspecified, and the heap happened to return them in the same order the index does. Quickselect returns them the other way around. Same build with debug_topn_quickselect=off passes, so it is the patch and not something else. 0001 now adds c~>4 as a tiebreaker to that one query in the seq-scan block, which keeps both blocks' expected output identical. The commit message mentions the tie order change. Nothing else in the full suite changed. The code in 0001-0003 is the same as v2. All meson suites, with cassert and PG_TEST_EXTRA="ssl ldap kerberos load_balance libpq_encryption wal_consistency_checking xid_wraparound oauth" on Debian 13 (gcc 14): 414 pass, 0 fail, 20 skipped (Windows-only or opt-in tests). CI on the fork is green as well. best. -greg
From 225a70f2ddb2bc04496e43f8fd65766ecfde588a Mon Sep 17 00:00:00 2001 From: Greg Burd <[email protected]> Date: Fri, 23 Oct 2026 07:36:30 -0400 Subject: [PATCH v3 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 1718645d67584f9e73eb964ee84d8108626d331c Mon Sep 17 00:00:00 2001 From: Greg Burd <[email protected]> Date: Fri, 23 Oct 2026 07:36:15 -0400 Subject: [PATCH v3 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. Rows that tie on every sort key can come out in a different order than the heap produced; SQL leaves that order unspecified. contrib/cube's regression test compared a sort-based ORDER BY c~>2 LIMIT 15 against the GiST-ordered result and depended on the heap's order for one tie, so add c~>4 as a tiebreaker there. --- contrib/cube/expected/cube.out | 2 +- contrib/cube/sql/cube.sql | 2 +- src/backend/utils/sort/tuplesort.c | 203 ++++++++++++++++++++++++ src/test/regress/expected/tuplesort.out | 73 +++++++++ src/test/regress/sql/tuplesort.sql | 59 +++++++ 5 files changed, 337 insertions(+), 2 deletions(-) diff --git a/contrib/cube/expected/cube.out b/contrib/cube/expected/cube.out index 47787c50bd9..5eb3d8f8fdc 100644 --- a/contrib/cube/expected/cube.out +++ b/contrib/cube/expected/cube.out @@ -1832,7 +1832,7 @@ SELECT c~>1, c FROM test_cube ORDER BY c~>1 LIMIT 15; -- ascending by left bound 240 | (337, 455),(240, 359) (15 rows) -SELECT c~>2, c FROM test_cube ORDER BY c~>2 LIMIT 15; -- ascending by right bound +SELECT c~>2, c FROM test_cube ORDER BY c~>2, c~>4 LIMIT 15; -- ascending by right bound (c~>4 breaks the tie at 270) ?column? | c ----------+--------------------------- 0 | (0, 100000) diff --git a/contrib/cube/sql/cube.sql b/contrib/cube/sql/cube.sql index eec90d21ee3..c4a83e95238 100644 --- a/contrib/cube/sql/cube.sql +++ b/contrib/cube/sql/cube.sql @@ -428,7 +428,7 @@ RESET extra_float_digits; SELECT *, c <=> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <=> '(100, 100),(500, 500)'::cube LIMIT 5; SELECT *, c <#> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <#> '(100, 100),(500, 500)'::cube LIMIT 5; SELECT c~>1, c FROM test_cube ORDER BY c~>1 LIMIT 15; -- ascending by left bound -SELECT c~>2, c FROM test_cube ORDER BY c~>2 LIMIT 15; -- ascending by right bound +SELECT c~>2, c FROM test_cube ORDER BY c~>2, c~>4 LIMIT 15; -- ascending by right bound (c~>4 breaks the tie at 270) SELECT c~>3, c FROM test_cube ORDER BY c~>3 LIMIT 15; -- ascending by lower bound SELECT c~>4, c FROM test_cube ORDER BY c~>4 LIMIT 15; -- ascending by upper bound SELECT c~>(-1), c FROM test_cube ORDER BY c~>(-1) LIMIT 15; -- descending by left bound 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 988660835d94a911d6561f6f133a8f91f43552a0 Mon Sep 17 00:00:00 2001 From: Greg Burd <[email protected]> Date: Thu, 29 Oct 2026 08:50:53 -0400 Subject: [PATCH v3 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
