v5-0004-Detect-common-prefix-to-avoid-wasted-work-during-.patch

From 28e7d66295e007c0a443b99e4f14c5a803c142e1 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Wed, 12 Nov 2025 14:31:24 +0700
Subject: [PATCH v5 4/4] Detect common prefix to avoid wasted work during radix
 sort

This is particularly useful for integers, since they commonly
have some zero upper bytes.
---
 src/backend/utils/sort/tuplesort.c | 67 ++++++++++++++++++++++++++++--
 1 file changed, 63 insertions(+), 4 deletions(-)

diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 028c5b71c27..27623bbf21e 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"
@@ -3019,10 +3020,68 @@ sort_byvalue_datum(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 *tup = not_null_start;
+				 tup < not_null_start + not_null_count;
+				 tup++)
+			{
+				Datum		this_datum = tup->datum1;
+
+				if (tup == 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 datums are the same, so we can skip radix sort.
+				 * Tiebreak with qsort 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
+				 * values have the same bits. The byte position of the
+				 * leftmost one bit is the byte where radix sort should start
+				 * bucketing.
+				 */
+				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.51.1