On Wed, Jan 21, 2026 at 1:40 PM John Naylor <[email protected]> wrote: > Attached is v6, which seems pretty close to committable. The temporary > GUC is gone, as are all the integer-like qsort specializations. There > are a few cosmetic rearrangements, but the algorithm is pretty much > the same as v5. The only visible behavior difference should be the > addition of a presorted check just like qsort has.
I did some more self-review after a couple weeks and made some more minor cosmetic adjustments for v7. I will commit 0001 and 0002 in a few days unless there are objections. > * The only things I have doubts about are the user-visible messages > mentioning "qsort". For trace_sort, it seemed logical to re-use the > term "internal sort" from other such messages, so I've done that for > v6. EXPLAIN ANALYZE is a bit harder: Do we want to even change > anything here? When things like this come up, there is the question of > tools that parse the output. It doesn't seem particularly important to > try to display exact info here, especially since radix sort must > divert to qsort for multiple keys etc. I decided to split this out to a separate patch, 0003. It doesn't seem important, and may not be desirable after all. There is also a 0004 which is just verifying sort order in assert builds on the existing qsort calls and not just the new sort. Looks better this way. > Speaking of the NULL partitioning step, I've tried to add some > comments that make sense, but the pictures in the linked blog are more > helpful than any words I can come up with. It's easier to understand > than to describe. I tried to improve readability here and added missing CHECK_FOR_INTERRUPTS(). Also ran UB sanitizer and Valgrind. On Wed, Jan 21, 2026 at 3:12 PM zengman <[email protected]> wrote: > I wanted to point out a small detail: the line `extern PGDLLIMPORT bool > wip_radix_sort;` > in v6-0001 appears to not have been fully cleaned up — I suspect it might > have been overlooked. Fixed as well. -- John Naylor Amazon Web Services
From dfefff9d2e28979dee92f3b61e954c3c8b1ee236 Mon Sep 17 00:00:00 2001 From: John Naylor <[email protected]> Date: Wed, 12 Nov 2025 14:31:24 +0700 Subject: [PATCH v7 2/4] Detect common prefix to avoid wasted work during radix sort Start radix sort at the most significant byte position that has more than one distinct byte in the input. This skips passes where radix sort would count the distinct bytes just to find only a single one, in which case there is nothing further to do for that pass. This can give a few percent speedup for integers that have some zero upper bytes, which is common for those that didn't arrive via abbreviation. Reviewed-by: Chengpeng Yan <[email protected]> Discussion: https://postgr.es/m/canwcazypgmdsswaa18foxjgxapzvdypswpokfcx32dwh3qz...@mail.gmail.com --- src/backend/utils/sort/tuplesort.c | 66 ++++++++++++++++++++++++++++-- 1 file changed, 62 insertions(+), 4 deletions(-) diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index 07fa83c7944..7b22546a811 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -104,6 +104,7 @@ #include "commands/tablespace.h" #include "miscadmin.h" #include "pg_trace.h" +#include "port/pg_bitutils.h" #include "storage/shmem.h" #include "utils/guc.h" #include "utils/memutils.h" @@ -2928,10 +2929,67 @@ sort_byvalue_datum(SortTuple *data, size_t n, Tuplesortstate *state) } else { - radix_sort_tuple(not_null_start, - not_null_count, - 0, - state); + int common_prefix; + Datum first_datum = 0; + Datum common_upper_bits = 0; + + /* + * Compute the common prefix to skip unproductive recursion steps + * during radix sort. + */ + for (SortTuple *st = not_null_start; + st < not_null_start + not_null_count; + st++) + { + Datum this_datum = st->datum1; + + if (st == not_null_start) + { + /* + * Need to start with some value, may as well be the first + * one. + */ + first_datum = this_datum; + } + else + { + /* + * Accumulate bits that represent a difference from the + * reference datum. + */ + common_upper_bits |= first_datum ^ this_datum; + } + } + + if (common_upper_bits == 0) + { + /* + * All NOT NULL tuples have the same datum, so we can skip radix + * sort. Sort using the tiebreak comparator if necessary. + */ + if (state->base.onlyKey == NULL) + { + qsort_tuple(not_null_start, + not_null_count, + state->base.comparetup_tiebreak, + state); + } + } + else + { + /* + * The upper bits of common_upper_bits are zero where all datums + * have the same bits. The byte position of the leftmost one bit + * is the byte where radix sort should start. + */ + common_prefix = SIZEOF_DATUM - 1 - + (pg_leftmost_one_pos64(common_upper_bits) / BITS_PER_BYTE); + + radix_sort_tuple(not_null_start, + not_null_count, + common_prefix, + state); + } } } -- 2.53.0
From 81be72e69208b155f5619630043690157871a755 Mon Sep 17 00:00:00 2001 From: John Naylor <[email protected]> Date: Fri, 17 Oct 2025 09:57:43 +0700 Subject: [PATCH v7 1/4] Perform radix sort on SortTuples with pass-by-value Datums MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Radix sort can be much faster than quicksort, but for our purposes it is limited to sequences of unsigned bytes. To make tuples with other types amenable to this technique, several features of tuple comparison must be accounted for, i.e. the sort keys must be "normalized": 1. Signedness -- It's possible to modify a signed integer such that it can be compared as unsigned. For example, a signed char has range -128 to 127. If we cast that to unsigned char and add 128, the range of values becomes 0 to 255 while preserving order. 2. Direction -- SQL allows specification of ASC or DESC. The descending case is easily handled by taking the complement of the unsigned representation. 3. NULL values -- NULLS FIRST and NULLS LAST must work correctly. This commmit only handles the case where datum1 is pass-by-value Datum (possibly abbreviated) that compares like an ordinary integer. (Abbreviations of values of type "numeric" are a convenient counterexample.) First, tuples are partitioned by nullness in the correct NULL ordering. Then the NOT NULL tuples are sorted with radix sort on datum1. For tiebreaks on subsequent sortkeys (including the first sort key if abbreviated), we divert to the usual qsort. ORDER BY queries on pre-warmed buffers are up to 2x faster on high cardinality inputs with radix sort than the sort specializations added by commit 697492434, so get rid of them. It's sufficient to fall back to qsort_tuple() for small arrays. Moderately low cardinality inputs show more modest improvents. Our qsort is strongly optimized for very low cardinality inputs, but radix sort is usually comparable there. The changes to the regression tests are caused by under-specified sort orders, e.g. "SELECT a, b from mytable order by a;". For unstable sorts, such as our qsort and this in-place radix sort, there is no guarantee of the order of "b" within each group of "a". The implementation is taken from ska_byte_sort() (Boost licensed), which is similar to American flag sort (an in-place radix sort) with modifications to make it better suited for modern pipelined CPUs. The technique of normalization described above can also be extended to the case of multiple keys. That is left for future work (Thanks to Peter Geoghegan for the suggestion to look into this area). Reviewed-by: Chengpeng Yan <[email protected]> Reviewed-by: Álvaro Herrera <[email protected]> Reviewed-by: zengman <[email protected]> Reviewed-by: Chao Li <[email protected]> (earlier version) Discussion: https://postgr.es/m/canwcazyzx7a7e9ay16jt_u3+gvkdadfgapz-42syniig8dt...@mail.gmail.com --- src/backend/utils/sort/tuplesort.c | 556 ++++++++++++++++++------ src/include/utils/sortsupport.h | 101 ----- src/include/utils/tuplesort.h | 1 + src/test/regress/expected/tuplesort.out | 6 +- src/tools/pgindent/typedefs.list | 1 + 5 files changed, 427 insertions(+), 238 deletions(-) diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index 1edcad89c88..07fa83c7944 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -7,8 +7,8 @@ * applied to different kinds of sortable objects. Implementation of * the particular sorting variants is given in tuplesortvariants.c. * This module works efficiently for both small and large amounts - * of data. Small amounts are sorted in-memory using qsort(). Large - * amounts are sorted using temporary files and a standard external sort + * of data. Small amounts are sorted in-memory. Large amounts are + * sorted using temporary files and a standard external sort * algorithm. * * See Knuth, volume 3, for more than you want to know about external @@ -26,16 +26,16 @@ * Historically, we divided the input into sorted runs using replacement * selection, in the form of a priority tree implemented as a heap * (essentially Knuth's Algorithm 5.2.3H), but now we always use quicksort - * for run generation. + * or radix sort for run generation. * * The approximate amount of memory allowed for any one sort operation * is specified in kilobytes by the caller (most pass work_mem). Initially, * we absorb tuples and simply store them in an unsorted array as long as * we haven't exceeded workMem. If we reach the end of the input without - * exceeding workMem, we sort the array using qsort() and subsequently return + * exceeding workMem, we sort the array in memory and subsequently return * tuples just by scanning the tuple array sequentially. If we do exceed * workMem, we begin to emit tuples into sorted runs in temporary tapes. - * When tuples are dumped in batch after quicksorting, we begin a new run + * When tuples are dumped in batch after in-memory sorting, we begin a new run * with a new output tape. If we reach the max number of tapes, we write * subsequent runs on the existing tapes in a round-robin fashion. We will * need multiple merge passes to finish the merge in that case. After the @@ -476,121 +476,15 @@ static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup); static void tuplesort_free(Tuplesortstate *state); static void tuplesort_updatemax(Tuplesortstate *state); -/* - * Specialized comparators that we can inline into specialized sorts. The goal - * is to try to sort two tuples without having to follow the pointers to the - * comparator or the tuple. - * - * XXX: For now, there is no specialization for cases where datum1 is - * authoritative and we don't even need to fall back to a callback at all (that - * would be true for types like int4/int8/timestamp/date, but not true for - * abbreviations of text or multi-key sorts. There could be! Is it worth it? - */ - -/* Used if first key's comparator is ssup_datum_unsigned_cmp */ -static pg_attribute_always_inline int -qsort_tuple_unsigned_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state) -{ - int compare; - - compare = ApplyUnsignedSortComparator(a->datum1, a->isnull1, - b->datum1, b->isnull1, - &state->base.sortKeys[0]); - if (compare != 0) - return compare; - - /* - * No need to waste effort calling the tiebreak function when there are no - * other keys to sort on. - */ - if (state->base.onlyKey != NULL) - return 0; - - return state->base.comparetup_tiebreak(a, b, state); -} - -/* Used if first key's comparator is ssup_datum_signed_cmp */ -static pg_attribute_always_inline int -qsort_tuple_signed_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state) -{ - int compare; - - compare = ApplySignedSortComparator(a->datum1, a->isnull1, - b->datum1, b->isnull1, - &state->base.sortKeys[0]); - - if (compare != 0) - return compare; - - /* - * No need to waste effort calling the tiebreak function when there are no - * other keys to sort on. - */ - if (state->base.onlyKey != NULL) - return 0; - - return state->base.comparetup_tiebreak(a, b, state); -} - -/* Used if first key's comparator is ssup_datum_int32_cmp */ -static pg_attribute_always_inline int -qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state) -{ - int compare; - - compare = ApplyInt32SortComparator(a->datum1, a->isnull1, - b->datum1, b->isnull1, - &state->base.sortKeys[0]); - - if (compare != 0) - return compare; - - /* - * No need to waste effort calling the tiebreak function when there are no - * other keys to sort on. - */ - if (state->base.onlyKey != NULL) - return 0; - - return state->base.comparetup_tiebreak(a, b, state); -} /* * Special versions of qsort just for SortTuple objects. qsort_tuple() sorts * any variant of SortTuples, using the appropriate comparetup function. * qsort_ssup() is specialized for the case where the comparetup function * reduces to ApplySortComparator(), that is single-key MinimalTuple sorts - * and Datum sorts. qsort_tuple_{unsigned,signed,int32} are specialized for - * common comparison functions on pass-by-value leading datums. + * and Datum sorts. */ -#define ST_SORT qsort_tuple_unsigned -#define ST_ELEMENT_TYPE SortTuple -#define ST_COMPARE(a, b, state) qsort_tuple_unsigned_compare(a, b, state) -#define ST_COMPARE_ARG_TYPE Tuplesortstate -#define ST_CHECK_FOR_INTERRUPTS -#define ST_SCOPE static -#define ST_DEFINE -#include "lib/sort_template.h" - -#define ST_SORT qsort_tuple_signed -#define ST_ELEMENT_TYPE SortTuple -#define ST_COMPARE(a, b, state) qsort_tuple_signed_compare(a, b, state) -#define ST_COMPARE_ARG_TYPE Tuplesortstate -#define ST_CHECK_FOR_INTERRUPTS -#define ST_SCOPE static -#define ST_DEFINE -#include "lib/sort_template.h" - -#define ST_SORT qsort_tuple_int32 -#define ST_ELEMENT_TYPE SortTuple -#define ST_COMPARE(a, b, state) qsort_tuple_int32_compare(a, b, state) -#define ST_COMPARE_ARG_TYPE Tuplesortstate -#define ST_CHECK_FOR_INTERRUPTS -#define ST_SCOPE static -#define ST_DEFINE -#include "lib/sort_template.h" - #define ST_SORT qsort_tuple #define ST_ELEMENT_TYPE SortTuple #define ST_COMPARE_RUNTIME_POINTER @@ -612,6 +506,23 @@ qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state) #define ST_DEFINE #include "lib/sort_template.h" +/* state for radix sort */ +typedef struct RadixSortInfo +{ + union + { + size_t count; + size_t offset; + }; + size_t next_offset; +} RadixSortInfo; + +/* + * Threshold below which qsort_tuple() is generally faster than a radix sort. + */ +#define QSORT_THRESHOLD 40 + + /* * tuplesort_begin_xxx * @@ -1363,7 +1274,7 @@ tuplesort_performsort(Tuplesortstate *state) */ if (SERIAL(state)) { - /* Just qsort 'em and we're done */ + /* Sort in memory and we're done */ tuplesort_sort_memtuples(state); state->status = TSS_SORTEDINMEM; } @@ -2337,7 +2248,7 @@ dumptuples(Tuplesortstate *state, bool alltuples) /* * Sort all tuples accumulated within the allowed amount of memory for - * this run using quicksort + * this run. */ tuplesort_sort_memtuples(state); @@ -2652,10 +2563,395 @@ sort_bounded_heap(Tuplesortstate *state) state->boundUsed = true; } + +/* radix sort routines */ + +/* + * Retrieve byte from datum, indexed by 'level': 0 for LSB, 7 for MSB + */ +static inline uint8 +current_byte(Datum key, int level) +{ + int shift = (SIZEOF_DATUM - 1 - level) * BITS_PER_BYTE; + + return (key >> shift) & 0xFF; +} + /* - * Sort all memtuples using specialized qsort() routines. + * Normalize datum such that unsigned comparison is order-preserving, + * taking ASC/DESC into account as well. + */ +static inline Datum +normalize_datum(Datum orig, SortSupport ssup) +{ + Datum norm_datum1; + + if (ssup->comparator == ssup_datum_signed_cmp) + { + norm_datum1 = orig + ((uint64) PG_INT64_MAX) + 1; + } + else if (ssup->comparator == ssup_datum_int32_cmp) + { + /* + * First truncate to uint32. Technically, we don't need to do this, + * but it forces the upper half of the datum to be zero regardless of + * sign. + */ + uint32 u32 = DatumGetUInt32(orig) + ((uint32) PG_INT32_MAX) + 1; + + norm_datum1 = UInt32GetDatum(u32); + } + else + { + Assert(ssup->comparator == ssup_datum_unsigned_cmp); + norm_datum1 = orig; + } + + if (ssup->ssup_reverse) + norm_datum1 = ~norm_datum1; + + return norm_datum1; +} + +/* + * radix_sort_tuple + * + * Radix sort by the pass-by-value datum in datum1. This is a modification of + * ska_byte_sort() from https://github.com/skarupke/ska_sort + * The original copyright notice follows: + * + * Copyright Malte Skarupke 2016. + * Distributed under the Boost Software License, Version 1.0. + * + * Boost Software License - Version 1.0 - August 17th, 2003 + * + * Permission is hereby granted, free of charge, to any person or organization + * obtaining a copy of the software and accompanying documentation covered by + * this license (the "Software") to use, reproduce, display, distribute, + * execute, and transmit the Software, and to prepare derivative works of the + * Software, and to permit third-parties to whom the Software is furnished to + * do so, all subject to the following: + * + * The copyright notices in the Software and this entire statement, including + * the above license grant, this restriction and the following disclaimer, + * must be included in all copies of the Software, in whole or in part, and + * all derivative works of the Software, unless such copies or derivative + * works are solely in the form of machine-executable object code generated by + * a source language processor. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT + * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE + * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, + * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ +static void +radix_sort_tuple(SortTuple *begin, size_t n_elems, int level, Tuplesortstate *state) +{ + RadixSortInfo partitions[256] = {0}; + uint8 remaining_partitions[256]; + size_t total = 0; + int num_partitions = 0; + int num_remaining; + SortSupport ssup = &state->base.sortKeys[0]; + size_t start_offset = 0; + SortTuple *partition_begin = begin; + + /* count number of occurrences of each byte */ + for (SortTuple *st = begin; st < begin + n_elems; st++) + { + uint8 this_partition; + + /* extract the byte for this level from the normalized datum */ + this_partition = current_byte(normalize_datum(st->datum1, ssup), + level); + + /* save it for the permutation step */ + st->curbyte = this_partition; + + partitions[this_partition].count++; + + CHECK_FOR_INTERRUPTS(); + } + + /* compute partition offsets */ + for (int i = 0; i < 256; i++) + { + size_t count = partitions[i].count; + + if (count != 0) + { + partitions[i].offset = total; + total += count; + remaining_partitions[num_partitions] = i; + num_partitions++; + } + partitions[i].next_offset = total; + } + + /* + * Swap tuples to correct partition. + * + * In traditional American flag sort, a swap sends the current element to + * the correct partition, but the array pointer only advances if the + * partner of the swap happens to be an element that belongs in the + * current partition. That only requires one pass through the array, but + * the disadvantage is we don't know if the pointer can advance until the + * swap completes. Here lies the most interesting innovation from the + * upstream ska_byte_sort: After initiating the swap, we immediately + * proceed to the next element. This makes better use of CPU pipelining, + * but also means that we will often need multiple iterations of this + * loop. ska_byte_sort() maintains a separate list of which partitions + * haven't finished, which is updated every loop iteration. Here we simply + * check each partition during every iteration. + * + * If we started with a single partition, there is nothing to do. If a + * previous loop iteration results in only one partition that hasn't been + * counted as sorted, we know it's actually sorted and can exit the loop. + */ + num_remaining = num_partitions; + while (num_remaining > 1) + { + /* start the count over */ + num_remaining = num_partitions; + + for (int i = 0; i < num_partitions; i++) + { + uint8 idx = remaining_partitions[i]; + + for (SortTuple *st = begin + partitions[idx].offset; + st < begin + partitions[idx].next_offset; + st++) + { + size_t offset = partitions[st->curbyte].offset++; + SortTuple tmp; + + /* swap current tuple with destination position */ + Assert(offset < n_elems); + tmp = *st; + *st = begin[offset]; + begin[offset] = tmp; + + CHECK_FOR_INTERRUPTS(); + }; + + /* Is this partition sorted? */ + if (partitions[idx].offset == partitions[idx].next_offset) + num_remaining--; + } + } + + /* recurse */ + for (uint8 *rp = remaining_partitions; + rp < remaining_partitions + num_partitions; + rp++) + { + size_t end_offset = partitions[*rp].next_offset; + SortTuple *partition_end = begin + end_offset; + ptrdiff_t num_elements = end_offset - start_offset; + + if (num_elements > 1) + { + if (level < SIZEOF_DATUM - 1) + { + if (num_elements < QSORT_THRESHOLD) + { + qsort_tuple(partition_begin, + num_elements, + state->base.comparetup, + state); + } + else + { + radix_sort_tuple(partition_begin, + num_elements, + level + 1, + state); + } + } + else if (state->base.onlyKey == NULL) + { + /* + * We've finished radix sort on all bytes of the pass-by-value + * datum (possibly abbreviated), now sort using the tiebreak + * comparator. + */ + qsort_tuple(partition_begin, + num_elements, + state->base.comparetup_tiebreak, + state); + } + } + + start_offset = end_offset; + partition_begin = partition_end; + } +} + +/* + * Sort tuples having a pass-by-value Datum in datum1 + * + * Partition tuples by NULL and NOT NULL first sort key. + * Then dispatch to either radix sort or quicksort. + */ +static void +sort_byvalue_datum(SortTuple *data, size_t n, Tuplesortstate *state) +{ + bool nulls_first = state->base.sortKeys[0].ssup_nulls_first; + SortTuple *null_start; + SortTuple *not_null_start; + size_t d1 = 0, + d2, + null_count, + not_null_count; + bool presorted = true; + + /* presorted check */ + for (SortTuple *st = data + 1; st < data + n; st++) + { + CHECK_FOR_INTERRUPTS(); + + if (COMPARETUP(state, st - 1, st) > 0) + { + presorted = false; + break; + } + } + if (presorted) + return; + + /* + * Partition by NULL-ness of the leading sort key, since we can only radix + * sort on NOT NULL pass-by-value datums. + */ + + /* + * Find the first NOT NULL if NULLS FIRST, or first NULL if NULLS LAST. + * This also serves as a quick check for the common case where all tuples + * are NOT NULL in the first sort key. + */ + while (d1 < n && data[d1].isnull1 == nulls_first) + { + CHECK_FOR_INTERRUPTS(); + d1++; + } + + /* + * If we have more than one tuple left after the quick check, partition + * the remainder using branchless cyclic permutation, based on + * https://orlp.net/blog/branchless-lomuto-partitioning/ + */ + Assert(n > 0); + if (d1 < n - 1) + { + size_t i = d1, + j = d1; + SortTuple tmp = data[d1]; /* create gap at front */ + + while (j < n - 1) + { + CHECK_FOR_INTERRUPTS(); + + /* gap is at j, move i's element to gap */ + data[j] = data[i]; + /* advance j to the first unknown element */ + j += 1; + /* move the first unknown element back to i */ + data[i] = data[j]; + /* advance i if this element belongs in the left partition */ + i += (data[i].isnull1 == nulls_first); + } + + /* place gap between left and right partitions */ + data[j] = data[i]; + /* restore the saved element */ + data[i] = tmp; + /* assign it to the correct partition */ + i += (data[i].isnull1 == nulls_first); + + /* d1 is now the number of elements in the left partition */ + d1 = i; + } + + d2 = n - d1; + + /* set pointers and counts for each partition */ + if (nulls_first) + { + null_start = state->memtuples; + null_count = d1; + not_null_start = state->memtuples + d1; + not_null_count = d2; + } + else + { + not_null_start = state->memtuples; + not_null_count = d1; + null_start = state->memtuples + d1; + null_count = d2; + } + + for (SortTuple *st = null_start; + st < null_start + null_count; + st++) + Assert(st->isnull1 == true); + for (SortTuple *st = not_null_start; + st < not_null_start + not_null_count; + st++) + Assert(st->isnull1 == false); + + /* + * Sort the NULL partition using tiebreak comparator, if necessary. This + * will repeat the comparison on isnull1 if the first sort key was + * abbreviated, but it's not worth adding complexity to avoid that. + */ + if (state->base.onlyKey == NULL && null_count > 1) + { + qsort_tuple(null_start, + null_count, + state->base.comparetup_tiebreak, + state); + } + + /* + * Sort the NOT NULL partition, using radix sort if large enough, + * otherwise fall back to quicksort. + */ + if (not_null_count < QSORT_THRESHOLD) + { + qsort_tuple(not_null_start, + not_null_count, + state->base.comparetup, + state); + } + else + { + radix_sort_tuple(not_null_start, + not_null_count, + 0, + state); + } +} + +/* Verify in-memory sort using standard comparator. */ +static void +verify_memtuples_sorted(Tuplesortstate *state) +{ +#ifdef USE_ASSERT_CHECKING + for (SortTuple *st = state->memtuples + 1; + st < state->memtuples + state->memtupcount; + st++) + Assert(COMPARETUP(state, st - 1, st) <= 0); +#endif +} + +/* + * Sort all memtuples using specialized routines. * - * Quicksort is used for small in-memory sorts, and external sort runs. + * Quicksort or radix sort is used for small in-memory sorts, + * and external sort runs. */ static void tuplesort_sort_memtuples(Tuplesortstate *state) @@ -2665,30 +2961,22 @@ tuplesort_sort_memtuples(Tuplesortstate *state) if (state->memtupcount > 1) { /* - * Do we have the leading column's value or abbreviation in datum1, - * and is there a specialization for its comparator? + * Do we have the leading column's value or abbreviation in datum1? */ if (state->base.haveDatum1 && state->base.sortKeys) { - if (state->base.sortKeys[0].comparator == ssup_datum_unsigned_cmp) - { - qsort_tuple_unsigned(state->memtuples, - state->memtupcount, - state); - return; - } - else if (state->base.sortKeys[0].comparator == ssup_datum_signed_cmp) + SortSupportData ssup = state->base.sortKeys[0]; + + /* Does it compare as an integer? */ + if (state->memtupcount >= QSORT_THRESHOLD && + (ssup.comparator == ssup_datum_unsigned_cmp || + ssup.comparator == ssup_datum_signed_cmp || + ssup.comparator == ssup_datum_int32_cmp)) { - qsort_tuple_signed(state->memtuples, + sort_byvalue_datum(state->memtuples, state->memtupcount, state); - return; - } - else if (state->base.sortKeys[0].comparator == ssup_datum_int32_cmp) - { - qsort_tuple_int32(state->memtuples, - state->memtupcount, - state); + verify_memtuples_sorted(state); return; } } diff --git a/src/include/utils/sortsupport.h b/src/include/utils/sortsupport.h index 0083756bbdb..a8f8f9f026a 100644 --- a/src/include/utils/sortsupport.h +++ b/src/include/utils/sortsupport.h @@ -229,107 +229,6 @@ ApplySortComparator(Datum datum1, bool isNull1, return compare; } -static inline int -ApplyUnsignedSortComparator(Datum datum1, bool isNull1, - Datum datum2, bool isNull2, - SortSupport ssup) -{ - int compare; - - if (isNull1) - { - if (isNull2) - compare = 0; /* NULL "=" NULL */ - else if (ssup->ssup_nulls_first) - compare = -1; /* NULL "<" NOT_NULL */ - else - compare = 1; /* NULL ">" NOT_NULL */ - } - else if (isNull2) - { - if (ssup->ssup_nulls_first) - compare = 1; /* NOT_NULL ">" NULL */ - else - compare = -1; /* NOT_NULL "<" NULL */ - } - else - { - compare = datum1 < datum2 ? -1 : datum1 > datum2 ? 1 : 0; - if (ssup->ssup_reverse) - INVERT_COMPARE_RESULT(compare); - } - - return compare; -} - -static inline int -ApplySignedSortComparator(Datum datum1, bool isNull1, - Datum datum2, bool isNull2, - SortSupport ssup) -{ - int compare; - - if (isNull1) - { - if (isNull2) - compare = 0; /* NULL "=" NULL */ - else if (ssup->ssup_nulls_first) - compare = -1; /* NULL "<" NOT_NULL */ - else - compare = 1; /* NULL ">" NOT_NULL */ - } - else if (isNull2) - { - if (ssup->ssup_nulls_first) - compare = 1; /* NOT_NULL ">" NULL */ - else - compare = -1; /* NOT_NULL "<" NULL */ - } - else - { - compare = DatumGetInt64(datum1) < DatumGetInt64(datum2) ? -1 : - DatumGetInt64(datum1) > DatumGetInt64(datum2) ? 1 : 0; - if (ssup->ssup_reverse) - INVERT_COMPARE_RESULT(compare); - } - - return compare; -} - -static inline int -ApplyInt32SortComparator(Datum datum1, bool isNull1, - Datum datum2, bool isNull2, - SortSupport ssup) -{ - int compare; - - if (isNull1) - { - if (isNull2) - compare = 0; /* NULL "=" NULL */ - else if (ssup->ssup_nulls_first) - compare = -1; /* NULL "<" NOT_NULL */ - else - compare = 1; /* NULL ">" NOT_NULL */ - } - else if (isNull2) - { - if (ssup->ssup_nulls_first) - compare = 1; /* NOT_NULL ">" NULL */ - else - compare = -1; /* NOT_NULL "<" NULL */ - } - else - { - compare = DatumGetInt32(datum1) < DatumGetInt32(datum2) ? -1 : - DatumGetInt32(datum1) > DatumGetInt32(datum2) ? 1 : 0; - if (ssup->ssup_reverse) - INVERT_COMPARE_RESULT(compare); - } - - return compare; -} - /* * Apply a sort comparator function and return a 3-way comparison using full, * authoritative comparator. This takes care of handling reverse-sort and diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h index 5fe229e211b..da68f45acf2 100644 --- a/src/include/utils/tuplesort.h +++ b/src/include/utils/tuplesort.h @@ -116,6 +116,7 @@ typedef struct void *tuple; /* the tuple itself */ Datum datum1; /* value of first key column */ bool isnull1; /* is first key column NULL? */ + uint8 curbyte; /* chunk of datum1 for current radix sort pass */ int srctape; /* source tape number */ } SortTuple; diff --git a/src/test/regress/expected/tuplesort.out b/src/test/regress/expected/tuplesort.out index 6dd97e7427a..fc1321bf443 100644 --- a/src/test/regress/expected/tuplesort.out +++ b/src/test/regress/expected/tuplesort.out @@ -304,9 +304,9 @@ FROM abbrev_abort_uuids ORDER BY ctid DESC LIMIT 5; id | abort_increasing | abort_decreasing | noabort_increasing | noabort_decreasing -------+--------------------------------------+--------------------------------------+--------------------------------------+-------------------------------------- - 0 | | | | 20002 | | | | 20003 | | | | + 0 | | | | 10009 | 00000000-0000-0000-0000-000000010008 | 00000000-0000-0000-0000-000000009992 | 00010008-0000-0000-0000-000000010008 | 00009992-0000-0000-0000-000000009992 10008 | 00000000-0000-0000-0000-000000010007 | 00000000-0000-0000-0000-000000009993 | 00010007-0000-0000-0000-000000010007 | 00009993-0000-0000-0000-000000009993 (5 rows) @@ -335,9 +335,9 @@ FROM abbrev_abort_uuids ORDER BY ctid DESC LIMIT 5; id | abort_increasing | abort_decreasing | noabort_increasing | noabort_decreasing -------+--------------------------------------+--------------------------------------+--------------------------------------+-------------------------------------- - 0 | | | | - 20003 | | | | 20002 | | | | + 20003 | | | | + 0 | | | | 9993 | 00000000-0000-0000-0000-000000009992 | 00000000-0000-0000-0000-000000010008 | 00009992-0000-0000-0000-000000009992 | 00010008-0000-0000-0000-000000010008 9994 | 00000000-0000-0000-0000-000000009993 | 00000000-0000-0000-0000-000000010007 | 00009993-0000-0000-0000-000000009993 | 00010007-0000-0000-0000-000000010007 (5 rows) diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index 9f5ee8fd482..4e494bdc860 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -4058,6 +4058,7 @@ qsort_comparator query_pathkeys_callback radius_attribute radius_packet +RadixSortInfo rangeTableEntry_used_context rank_context rbt_allocfunc -- 2.53.0
From 872819673cfd85153cc5e3b8482321a6dfb98f32 Mon Sep 17 00:00:00 2001 From: John Naylor <[email protected]> Date: Tue, 10 Feb 2026 19:10:20 +0700 Subject: [PATCH v7 4/4] WIP Call verify_memtuples_sorted() after qsort for consistency The regression test changes are from a user defined function that is now called a couple more times. --- src/backend/utils/sort/tuplesort.c | 1 + src/test/regress/expected/namespace.out | 2 ++ 2 files changed, 3 insertions(+) diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index deb02eb5ee5..4bb7bcf7814 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -3052,6 +3052,7 @@ tuplesort_sort_memtuples(Tuplesortstate *state) state->base.comparetup, state); } + verify_memtuples_sorted(state); } } diff --git a/src/test/regress/expected/namespace.out b/src/test/regress/expected/namespace.out index dbbda72d395..b78abdf21ea 100644 --- a/src/test/regress/expected/namespace.out +++ b/src/test/regress/expected/namespace.out @@ -149,6 +149,8 @@ NOTICE: current search_path: pg_catalog, pg_temp NOTICE: current search_path: pg_catalog, pg_temp NOTICE: current search_path: pg_catalog, pg_temp NOTICE: current search_path: pg_catalog, pg_temp +NOTICE: current search_path: pg_catalog, pg_temp +NOTICE: current search_path: pg_catalog, pg_temp REFRESH MATERIALIZED VIEW test_maint_search_path.test_maint_mv; NOTICE: current search_path: pg_catalog, pg_temp NOTICE: current search_path: pg_catalog, pg_temp -- 2.53.0
From 7f2e95ca483ce34e26f22d9bf466ccf9f4182241 Mon Sep 17 00:00:00 2001 From: John Naylor <[email protected]> Date: Tue, 10 Feb 2026 20:02:19 +0700 Subject: [PATCH v7 3/4] WIP Add possible message changes Not sure if necessary so kept out of main commit --- src/backend/utils/sort/tuplesort.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index 7b22546a811..deb02eb5ee5 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -2243,7 +2243,7 @@ dumptuples(Tuplesortstate *state, bool alltuples) state->currentRun++; if (trace_sort) - elog(LOG, "worker %d starting quicksort of run %d: %s", + elog(LOG, "worker %d starting internal sort of run %d: %s", state->worker, state->currentRun, pg_rusage_show(&state->ru_start)); @@ -2254,7 +2254,7 @@ dumptuples(Tuplesortstate *state, bool alltuples) tuplesort_sort_memtuples(state); if (trace_sort) - elog(LOG, "worker %d finished quicksort of run %d: %s", + elog(LOG, "worker %d finished internal sort of run %d: %s", state->worker, state->currentRun, pg_rusage_show(&state->ru_start)); -- 2.53.0
