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.
* 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.
Other updates:
1) I wanted a better test for small input, in case the threshold
needed adjusting. I lost the test during a fumbled rebase, but it's
easy to describe: instead of calling tuplesort_sort_memtuples(), call
both radix sort and qsort on copies of the input, with RDTSC calls
around each. I've attached the results, which are average ticks per
element sorted, averaging a million runs. The threshold seems to be
fine at 40, even down to a cardinality of 6. It's important to be as
low as we can get away with, since "qsort" here is qsort_tuple, not
the former specialized variants for integer comparators.
2) We don't need to try harder in the NULL partitioning step
For example, the case below with all NULL in the first key. The
underlying behavioral difference is, with qsort the comparator tries
the NULL first key (which ties every time), and then tries the second
key. With radix sort, the first key NULLs are partitioned first, doing
no useful work since they're all NULL, then qsort is called with the
tiebreak comparator on the whole input.
By this test, there is only noise difference with low cardinality
(before I removed the GUC):
drop table if exists test;
create unlogged table test (a bigint, b bigint not null);
insert into test select
NULL,
(1_000_000_000 * random())::bigint % 8
from generate_series(1,1_000_000,1) i;
vacuum freeze test;
select pg_prewarm('test');
set work_mem = '500MB';
\timing
set wip_radix_sort = 'off'; select * from test order by a, b offset
1_000_000_000;
280ms
set wip_radix_sort = 'on'; select * from test order by a, b offset
1_000_000_000;
277ms
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.
--
John Naylor
Amazon Web Services
- num elem is actual size of input array sorted
- measurements are in RDTSC ticks per element sorted
*** means smallest input that radix sort measured equal or faster
select i % 2 as res from generate_series(1,100,1) i order by res offset 1000;
SET
NOTICE: num elem: 30 qsort: 26.6 radix: 49.3
NOTICE: num elem: 40 qsort: 29.4 radix: 43.2
NOTICE: num elem: 50 qsort: 28.3 radix: 37.7
NOTICE: num elem: 60 qsort: 27.6 radix: 35.1
NOTICE: num elem: 70 qsort: 27.0 radix: 32.9
NOTICE: num elem: 80 qsort: 30.0 radix: 30.5 ***
NOTICE: num elem: 90 qsort: 29.7 radix: 29.9
select i % 4 as res from generate_series(1,100,1) i order by res offset 1000;
NOTICE: num elem: 30 qsort: 38.1 radix: 54.4
NOTICE: num elem: 40 qsort: 36.5 radix: 46.3
NOTICE: num elem: 50 qsort: 37.0 radix: 40.4
NOTICE: num elem: 60 qsort: 35.6 radix: 37.9
NOTICE: num elem: 70 qsort: 35.4 radix: 34.8 ***
NOTICE: num elem: 80 qsort: 36.8 radix: 32.4
NOTICE: num elem: 90 qsort: 38.3 radix: 30.4
select i % 6 as res from generate_series(1,100,1) i order by res offset 1000;
SET
NOTICE: num elem: 30 qsort: 48.6 radix: 54.6
NOTICE: num elem: 40 qsort: 50.6 radix: 46.8 ***
NOTICE: num elem: 50 qsort: 50.2 radix: 41.9
NOTICE: num elem: 60 qsort: 43.6 radix: 37.2
NOTICE: num elem: 70 qsort: 48.6 radix: 36.4
NOTICE: num elem: 80 qsort: 43.2 radix: 34.3
NOTICE: num elem: 90 qsort: 45.4 radix: 32.2
select i % 10 as res from generate_series(1,100,1) i order by res offset 1000;
NOTICE: num elem: 30 qsort: 66.6 radix: 60.6 ***
NOTICE: num elem: 40 qsort: 66.9 radix: 52.7
NOTICE: num elem: 50 qsort: 60.4 radix: 45.9
NOTICE: num elem: 60 qsort: 58.4 radix: 41.8
NOTICE: num elem: 70 qsort: 63.9 radix: 37.8
NOTICE: num elem: 80 qsort: 56.8 radix: 37.1
NOTICE: num elem: 90 qsort: 58.7 radix: 33.5
select (250*random())::int as res from generate_series(1,100,1) i order by res
offset 1000;
SET
NOTICE: num elem: 30 qsort: 77.9 radix: 79.7
NOTICE: num elem: 40 qsort: 74.2 radix: 72.2 ***
NOTICE: num elem: 50 qsort: 88.0 radix: 64.6
NOTICE: num elem: 60 qsort: 90.7 radix: 64.6
NOTICE: num elem: 70 qsort: 97.2 radix: 61.2
NOTICE: num elem: 80 qsort: 96.8 radix: 60.3
NOTICE: num elem: 90 qsort: 94.6 radix: 63.6
select (64000*random())::int as res from generate_series(1,100,1) i order by
res offset 1000;
NOTICE: num elem: 30 qsort: 82.6 radix: 83.9
NOTICE: num elem: 40 qsort: 91.2 radix: 76.9 ***
NOTICE: num elem: 50 qsort: 86.7 radix: 70.9
NOTICE: num elem: 60 qsort: 91.4 radix: 75.0
NOTICE: num elem: 70 qsort: 91.1 radix: 74.5
NOTICE: num elem: 80 qsort: 96.8 radix: 63.6
NOTICE: num elem: 90 qsort: 107.9 radix: 61.3
select (1_000_000_000*random())::int as res from generate_series(1,100,1) i
order by res offset 1000;
SET
NOTICE: num elem: 30 qsort: 76.0 radix: 84.3
NOTICE: num elem: 40 qsort: 78.7 radix: 74.8 ***
NOTICE: num elem: 50 qsort: 91.7 radix: 74.6
NOTICE: num elem: 60 qsort: 92.7 radix: 70.3
NOTICE: num elem: 70 qsort: 98.2 radix: 68.1
NOTICE: num elem: 80 qsort: 104.8 radix: 70.5
NOTICE: num elem: 90 qsort: 111.0 radix: 70.6
From 414c3323b8f0fbe845a5f0a43d761bc272eb71a6 Mon Sep 17 00:00:00 2001
From: John Naylor <[email protected]>
Date: Wed, 12 Nov 2025 14:31:24 +0700
Subject: [PATCH v6 2/2] Detect common prefix to avoid wasted work during radix
sort
This is particularly useful for integers, since they commonly
have some zero upper bytes.
Reviewed-by: Chengpeng Yan <[email protected]>
---
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 f87235b90d7..8b573d48d1d 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"
@@ -2915,10 +2916,67 @@ sort_byvalue_datum(SortTuple *data, size_t n, Tuplesortstate *state)
{
if (not_null_count > RADIX_SORT_THRESHOLD)
{
- 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);
+ }
}
else
{
--
2.52.0
From ab05807d661fdf460b313cc74a8788551571aa0b Mon Sep 17 00:00:00 2001
From: John Naylor <[email protected]>
Date: Fri, 17 Oct 2025 09:57:43 +0700
Subject: [PATCH v6 1/2] Use radix sort when SortTuple contains a pass-by-value
datum
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
For now this only works for signed and unsigned ints
with the usual comparison semantics, the same types
for which we previously had separate qsort
specializations.
[TODO...]
Reviewed-by: Chengpeng Yan <[email protected]>
Reviewed-by: Álvaro Herrera <[email protected]>
Tested-by: Chao Li <[email protected]> (earlier version)
---
src/backend/utils/sort/tuplesort.c | 547 ++++++++++++++++++------
src/include/utils/guc.h | 1 +
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 +
6 files changed, 420 insertions(+), 237 deletions(-)
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 9e4cd816137..f87235b90d7 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
@@ -32,7 +32,7 @@
* 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
@@ -477,121 +477,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
@@ -613,6 +507,20 @@ qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
#define ST_DEFINE
#include "lib/sort_template.h"
+/* state for radix sort */
+typedef struct RadixPartitionInfo
+{
+ union
+ {
+ size_t count;
+ size_t offset;
+ };
+ size_t next_offset;
+} RadixPartitionInfo;
+
+#define RADIX_SORT_THRESHOLD 40
+
+
/*
* tuplesort_begin_xxx
*
@@ -1364,7 +1272,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;
}
@@ -2332,7 +2240,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));
@@ -2343,7 +2251,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));
@@ -2653,10 +2561,391 @@ 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;
+}
+
+/*
+ * 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)
+{
+ RadixPartitionInfo 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 to 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();
+ };
+
+ /* count sorted partitions */
+ 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 > RADIX_SORT_THRESHOLD)
+ {
+ radix_sort_tuple(partition_begin,
+ num_elements,
+ level + 1,
+ state);
+ }
+ else
+ {
+ qsort_tuple(partition_begin,
+ num_elements,
+ state->base.comparetup,
+ 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;
+ }
+}
+
+/*
+ * Partition tuples by NULL and NOT NULL first sort key.
+ * Then dispatch to either radix sort or qsort.
+ */
+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 tuple if NULLS FIRST, or first NULL element if
+ * NULLS LAST. This is 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)
+ 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/
+ */
+ if (d1 < n - 1)
+ {
+ size_t j = d1; /* forward index */
+ SortTuple save = data[d1]; /* create gap at front */
+
+ while (j < n - 1)
+ {
+ /* gap is at j, move d1's element to gap */
+ data[j] = data[d1];
+
+ /* advance j to first unknown element */
+ j += 1;
+
+ /* move j's element back to d1 */
+ data[d1] = data[j];
+
+ /* advance d1 if the element belongs in the left partition */
+ d1 += (data[d1].isnull1 == nulls_first);
+ }
+
+ /* place gap between left and right partitions */
+ data[j] = data[d1];
+
+ /* restore the saved element */
+ data[d1] = save;
+
+ /* assign it to the correct partition */
+ d1 += (data[d1].isnull1 == nulls_first);
+ }
+
+ /* d1 is now the number of elements in the left partition */
+ 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 for abbreviated keys, 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 > 1)
+ {
+ if (not_null_count > RADIX_SORT_THRESHOLD)
+ {
+ radix_sort_tuple(not_null_start,
+ not_null_count,
+ 0,
+ state);
+ }
+ else
+ {
+ qsort_tuple(not_null_start,
+ not_null_count,
+ state->base.comparetup,
+ 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 qsort() routines.
+ * 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)
@@ -2666,30 +2955,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 > RADIX_SORT_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/guc.h b/src/include/utils/guc.h
index bf39878c43e..dae35dd3fc0 100644
--- a/src/include/utils/guc.h
+++ b/src/include/utils/guc.h
@@ -324,6 +324,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 wip_radix_sort;
#ifdef DEBUG_BOUNDED_SORT
extern PGDLLIMPORT bool optimize_bounded_sort;
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 14dec2d49c1..0c4e9511151 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -4048,6 +4048,7 @@ qsort_comparator
query_pathkeys_callback
radius_attribute
radius_packet
+RadixPartitionInfo
rangeTableEntry_used_context
rank_context
rbt_allocfunc
--
2.52.0
