0001-Specialize-tuplesort-for-keys-without-tiebreaker.patch

From 3ff95aedb1065393a0ae1496cedb463bc998a329 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Wed, 6 Apr 2022 11:38:31 +1200
Subject: [PATCH] Specialize tuplesort for keys without tiebreaker.

Commit 69749243 noted a future opportunity to avoid calling the
comparator function in the case of single column non-abbreviated sort,
where datum1 alone is enough to decide the order.

David Rowley reported a performance regression in single-column integer
sorts with a lot of duplicates, where previously the qsort_ssup()
specialization was reached, due to extra calls to the comparator.  It
seems like a good idea to fix that, so let's complete that TODO item
now.

XXX WIP, is the if-then-else getting too ugly, maybe switch to a table of
functions to search?
XXX needs testing, experiments
---
 src/backend/utils/sort/tuplesort.c | 110 +++++++++++++++++++++++------
 1 file changed, 89 insertions(+), 21 deletions(-)

diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 571fb95532..dc16e6c242 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -312,6 +312,14 @@ struct Tuplesortstate
 	 */
 	bool		haveDatum1;
 
+	/*
+	 * Whether the comparator function must always be called for tuples with
+	 * equal datum1.  This should be set to true if the sorting has extra
+	 * 'invisible' sort order beyond the regular keys, to disable optimizations
+	 * that would otherwise skip the function call.
+	 */
+	bool		alwaysTiebreak;
+
 	/*
 	 * This array holds the tuples now in sort memory.  If we are in state
 	 * INITIAL, the tuples are in no particular order; if we are in state
@@ -682,11 +690,6 @@ static void tuplesort_updatemax(Tuplesortstate *state);
  *
  * XXX: For now, these fall back to comparator functions that will compare the
  * leading datum a second time.
- *
- * 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_compare */
@@ -740,10 +743,12 @@ qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
  * 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.
+ * common comparison functions on pass-by-value leading datums.  The _tiebreak
+ * variants are for when it is necessary to call the comparator function even
+ * if datum1 is equal.
  */
 
-#define ST_SORT qsort_tuple_unsigned
+#define ST_SORT qsort_tuple_unsigned_tiebreak
 #define ST_ELEMENT_TYPE SortTuple
 #define ST_COMPARE(a, b, state) qsort_tuple_unsigned_compare(a, b, state)
 #define ST_COMPARE_ARG_TYPE Tuplesortstate
@@ -752,7 +757,7 @@ qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
 #define ST_DEFINE
 #include "lib/sort_template.h"
 
-#define ST_SORT qsort_tuple_signed
+#define ST_SORT qsort_tuple_signed_tiebreak
 #define ST_ELEMENT_TYPE SortTuple
 #define ST_COMPARE(a, b, state) qsort_tuple_signed_compare(a, b, state)
 #define ST_COMPARE_ARG_TYPE Tuplesortstate
@@ -761,7 +766,7 @@ qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
 #define ST_DEFINE
 #include "lib/sort_template.h"
 
-#define ST_SORT qsort_tuple_int32
+#define ST_SORT qsort_tuple_int32_tiebreak
 #define ST_ELEMENT_TYPE SortTuple
 #define ST_COMPARE(a, b, state) qsort_tuple_int32_compare(a, b, state)
 #define ST_COMPARE_ARG_TYPE Tuplesortstate
@@ -770,6 +775,33 @@ qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
 #define ST_DEFINE
 #include "lib/sort_template.h"
 
+#define ST_SORT qsort_tuple_unsigned
+#define ST_ELEMENT_TYPE SortTuple
+#define ST_COMPARE(a, b, state) ApplyUnsignedSortComparator(a->datum1, a->isnull1, b->datum1, b->isnull1, &state->sortKeys[0])
+#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) ApplySignedSortComparator(a->datum1, a->isnull1, b->datum1, b->isnull1, &state->sortKeys[0])
+#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) ApplyInt32SortComparator(a->datum1, a->isnull1, b->datum1, b->isnull1, &state->sortKeys[0])
+#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
@@ -1215,6 +1247,12 @@ tuplesort_begin_index_btree(Relation heapRel,
 	state->abbrevNext = 10;
 	state->haveDatum1 = true;
 
+	/*
+	 * Since we sort equal keys by ItemPointer, we can't skip the comparator
+	 * call.
+	 */
+	state->alwaysTiebreak = true;
+
 	state->heapRel = heapRel;
 	state->indexRel = indexRel;
 	state->enforceUnique = enforceUnique;
@@ -3632,28 +3670,58 @@ tuplesort_sort_memtuples(Tuplesortstate *state)
 		 */
 		if (state->haveDatum1 && state->sortKeys)
 		{
+			bool		tiebreak;
+
+			/*
+			 * If there's only a single key, and the value in datum1 is not a
+			 * lossy abbreviation, then we don't need to call a tie-breaking
+			 * comparator function for equal datum1 values unless explicitly
+			 * asked to do so (eg btrees).
+			 */
+			tiebreak = state->nKeys > 1 ||
+				state->sortKeys[0].abbrev_converter ||
+				state->alwaysTiebreak;
+
 			if (state->sortKeys[0].comparator == ssup_datum_unsigned_cmp)
 			{
-				elog(DEBUG1, "qsort_tuple_unsigned");
-				qsort_tuple_unsigned(state->memtuples,
-									 state->memtupcount,
-									 state);
+				elog(DEBUG1, "qsort_tuple_unsigned%s",
+					 tiebreak ? "_tiebreak" : "");
+				if (tiebreak)
+					qsort_tuple_unsigned_tiebreak(state->memtuples,
+												  state->memtupcount,
+												  state);
+				else
+					qsort_tuple_unsigned(state->memtuples,
+										 state->memtupcount,
+										 state);
 				return;
 			}
 			else if (state->sortKeys[0].comparator == ssup_datum_signed_cmp)
 			{
-				elog(DEBUG1, "qsort_tuple_signed");
-				qsort_tuple_signed(state->memtuples,
-								   state->memtupcount,
-								   state);
+				elog(DEBUG1, "qsort_tuple_signed%s",
+					 tiebreak ? "_tiebreak" : "");
+				if (tiebreak)
+					qsort_tuple_signed_tiebreak(state->memtuples,
+												state->memtupcount,
+												state);
+				else
+					qsort_tuple_signed(state->memtuples,
+									   state->memtupcount,
+									   state);
 				return;
 			}
 			else if (state->sortKeys[0].comparator == ssup_datum_int32_cmp)
 			{
-				elog(DEBUG1, "qsort_tuple_int32");
-				qsort_tuple_int32(state->memtuples,
-								  state->memtupcount,
-								  state);
+				elog(DEBUG1, "qsort_tuple_int32%s",
+					 tiebreak ? "_tiebreak" : "");
+				if (tiebreak)
+					qsort_tuple_int32_tiebreak(state->memtuples,
+											   state->memtupcount,
+											   state);
+				else
+					qsort_tuple_int32(state->memtuples,
+									  state->memtupcount,
+									  state);
 				return;
 			}
 		}
-- 
2.30.2