v6-0001-Use-radix-sort-when-SortTuple-contains-a-pass-by-.patch

From ab05807d661fdf460b313cc74a8788551571aa0b Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
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 <chengpeng_yan@outlook.com>
Reviewed-by: Álvaro Herrera <alvherre@kurilemu.de>
Tested-by: Chao Li <li.evan.chao@gmail.com> (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