Reduce build times of pg_trgm GIN indexes

From 00c75bd58b7982c8bfe62d1260e9366766bc7f34 Mon Sep 17 00:00:00 2001
From: David Geier <geidav.pg@gmail.com>
Date: Fri, 14 Nov 2025 11:37:40 +0100
Subject: [PATCH v2 8/8] Add ASCII fastpath to generate_trgm_only()

---
 contrib/pg_trgm/trgm_op.c | 124 ++++++++++++++++++++------------------
 1 file changed, 65 insertions(+), 59 deletions(-)

diff --git a/contrib/pg_trgm/trgm_op.c b/contrib/pg_trgm/trgm_op.c
index 39b586f5b9a..d2087b3a45e 100644
--- a/contrib/pg_trgm/trgm_op.c
+++ b/contrib/pg_trgm/trgm_op.c
@@ -226,32 +226,6 @@ show_limit(PG_FUNCTION_ARGS)
 	PG_RETURN_FLOAT4(similarity_threshold);
 }
 
-/*
- * Finds first word in string, returns pointer to the word,
- * endword points to the character after word
- */
-static char *
-find_word(char *str, int lenstr, char **endword, int *charlen)
-{
-	char	   *beginword = str;
-
-	while (beginword - str < lenstr && !ISWORDCHR(beginword))
-		beginword += pg_mblen(beginword);
-
-	if (beginword - str >= lenstr)
-		return NULL;
-
-	*endword = beginword;
-	*charlen = 0;
-	while (*endword - str < lenstr && ISWORDCHR(*endword))
-	{
-		*endword += pg_mblen(*endword);
-		(*charlen)++;
-	}
-
-	return beginword;
-}
-
 /*
  * Reduce a trigram (three possibly multi-byte characters) to a trgm,
  * which is always exactly three bytes.  If we have three single-byte
@@ -337,58 +311,90 @@ make_trigrams(trgm *tptr, char *str, int bytelen, int charlen)
 static int
 generate_trgm_only(trgm *trg, char *str, int slen, TrgmBound *bounds)
 {
-	trgm	   *tptr;
-	char	   *buf;
-	int			charlen,
-				bytelen;
-	char	   *bword,
-			   *eword;
+	trgm *tptr = trg;
+	char *buf;
 
 	if (slen + LPADDING + RPADDING < 3 || slen == 0)
 		return 0;
 
-	tptr = trg;
-
-	/* Allocate a buffer for case-folded, blank-padded words */
-	buf = (char *) palloc(slen * pg_database_encoding_max_length() + 4);
+	buf = palloc_array(char, slen * pg_database_encoding_max_length() + 4 + 1);
+	memset(buf, ' ', LPADDING);
 
-	if (LPADDING > 0)
+	for (int i = 0; i < slen; )
 	{
-		*buf = ' ';
-		if (LPADDING > 1)
-			*(buf + 1) = ' ';
-	}
+		int num_bytes = LPADDING;
+		int num_chars = LPADDING;
+		char *word;
 
-	eword = str;
-	while ((bword = find_word(eword, slen - (eword - str), &eword, &charlen)) != NULL)
-	{
+		/* Extract next word */
+		while (i < slen)
+		{
+			if ((str[i] & 0x80) == 0) /* Fast path for ASCII-only */
+			{
+				if (isalnum(str[i]))
+				{
 #ifdef IGNORECASE
-		bword = str_tolower(bword, eword - bword, DEFAULT_COLLATION_OID);
-		bytelen = strlen(bword);
+					buf[num_bytes++] = pg_ascii_tolower(str[i++]);
 #else
-		bytelen = eword - bword;
+					buf[num_bytes++] = str[i++];
 #endif
+				}
+				else
+				{
+					i++;
+					break;
+				}
+			}
+			else
+			{
+				const int mblen = pg_mblen(str + i);
+				Assert(mblen >= 2); /* Otherwise, it would be ASCII */
+
+				if (ISWORDCHR(str + i))
+				{
+					memcpy(buf + num_bytes, str + i, mblen);
+					num_bytes += mblen;
+					i += mblen;
+				}
+				else
+				{
+					i += mblen;
+					break;
+				}
+			}
+
+			num_chars++;
+		}
 
-		memcpy(buf + LPADDING, bword, bytelen);
+		if (num_chars > LPADDING)
+		{
+			memset(buf + num_bytes, ' ', RPADDING);
+			num_bytes += RPADDING;
+			num_chars += RPADDING;
+			word = buf;
 
 #ifdef IGNORECASE
-		pfree(bword);
+			if (num_chars != num_bytes)
+			{
+				word = str_tolower(buf, num_bytes, DEFAULT_COLLATION_OID);
+				num_bytes = strlen(word); /* String can get shorter from lower-casing */
+			}
 #endif
 
-		buf[LPADDING + bytelen] = ' ';
-		buf[LPADDING + bytelen + 1] = ' ';
+			if (bounds)
+				bounds[tptr - trg] |= TRGM_BOUND_LEFT;
+
+			tptr = make_trigrams(tptr, word, num_bytes, num_chars);
+
+			if (bounds)
+				bounds[tptr - trg - 1] |= TRGM_BOUND_RIGHT;
 
-		/* Calculate trigrams marking their bounds if needed */
-		if (bounds)
-			bounds[tptr - trg] |= TRGM_BOUND_LEFT;
-		tptr = make_trigrams(tptr, buf, bytelen + LPADDING + RPADDING,
-							 charlen + LPADDING + RPADDING);
-		if (bounds)
-			bounds[tptr - trg - 1] |= TRGM_BOUND_RIGHT;
+			if (word != buf)
+				pfree(word);
+		}
 	}
 
 	pfree(buf);
-
 	return tptr - trg;
 }
 
-- 
2.51.0

From 457a3d0d57a834a80237d628d353408f3e2f4378 Mon Sep 17 00:00:00 2001
From: David Geier <geidav.pg@gmail.com>
Date: Wed, 12 Nov 2025 14:27:13 +0100
Subject: [PATCH v2 7/8] Faster qunique() comparator

---
 contrib/pg_trgm/trgm_op.c | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

diff --git a/contrib/pg_trgm/trgm_op.c b/contrib/pg_trgm/trgm_op.c
index 039c273f6a1..39b586f5b9a 100644
--- a/contrib/pg_trgm/trgm_op.c
+++ b/contrib/pg_trgm/trgm_op.c
@@ -139,6 +139,14 @@ CMPTRGM_UNSIGNED(const void *a, const void *b)
 		   : CMPPCHAR_UNS(a, b, 2));
 }
 
+static inline int
+CMPTRGM_EQ(const void *a, const void *b)
+{
+	char *aa = (char *)a;
+	char *bb = (char *)b;
+	return aa[0] != bb[0] || aa[1] != bb[1] || aa[2] != bb[2] ? 1 : 0;
+}
+
 /*
  * This gets called on the first call. It replaces the function pointer so
  * that subsequent calls are routed directly to the chosen implementation.
@@ -482,15 +490,11 @@ generate_trgm(char *str, int slen)
 	if (len > 1)
 	{
 		if (GetDefaultCharSignedness())
-		{
 			radix_sort_trigrams_signed((trgm *)GETARR(trg), len);
-			len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_SIGNED);
-		}
 		else
-		{
 			trigram_qsort_unsigned((void *) GETARR(trg), len, sizeof(trgm));
-			len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_UNSIGNED);
-		}
+
+		len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_EQ);
 	}
 
 	SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
@@ -1038,15 +1042,11 @@ generate_wildcard_trgm(const char *str, int slen)
 	if (len > 1)
 	{
 		if (GetDefaultCharSignedness())
-		{
 			radix_sort_trigrams_signed((trgm *)GETARR(trg), len);
-			len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_SIGNED);
-		}
 		else
-		{
 			trigram_qsort_unsigned((void *) GETARR(trg), len, sizeof(trgm));
-			len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_UNSIGNED);
-		}
+
+		len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_EQ);
 	}
 
 	SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
-- 
2.51.0

From 447ce313602e768f29c43d4a5359f4c909b8db46 Mon Sep 17 00:00:00 2001
From: David Geier <geidav.pg@gmail.com>
Date: Tue, 11 Nov 2025 13:18:59 +0100
Subject: [PATCH v2 6/8] Use radix sort

---
 contrib/pg_trgm/trgm_op.c | 64 +++++++++++++++++++++++++++++++++------
 1 file changed, 54 insertions(+), 10 deletions(-)

diff --git a/contrib/pg_trgm/trgm_op.c b/contrib/pg_trgm/trgm_op.c
index 6af120fa1ad..039c273f6a1 100644
--- a/contrib/pg_trgm/trgm_op.c
+++ b/contrib/pg_trgm/trgm_op.c
@@ -155,14 +155,6 @@ CMPTRGM_CHOOSE(const void *a, const void *b)
 }
 
 /* Define our specialized sort function name */
-#define ST_SORT trigram_qsort_signed
-#define ST_ELEMENT_TYPE_VOID
-#define ST_COMPARE(a, b) CMPTRGM_SIGNED(a, b)
-#define ST_SCOPE static
-#define ST_DEFINE
-#define ST_DECLARE
-#include "lib/sort_template.h"
-
 #define ST_SORT trigram_qsort_unsigned
 #define ST_ELEMENT_TYPE_VOID
 #define ST_COMPARE(a, b) CMPTRGM_UNSIGNED(a, b)
@@ -392,6 +384,58 @@ generate_trgm_only(trgm *trg, char *str, int slen, TrgmBound *bounds)
 	return tptr - trg;
 }
 
+/*
+ * Needed to properly handle negative numbers in case char is signed.
+ */
+static inline unsigned char FlipSign(char x)
+{
+	return x^0x80;
+}
+
+static void radix_sort_trigrams_signed(trgm *trg, int count)
+{
+	trgm *buffer = palloc_array(trgm, count);
+	trgm *starts[256];
+	trgm *from = trg;
+	trgm *to = buffer;
+	int freqs[3][256];
+
+	/*
+	 * Compute frequencies to partition the buffer.
+	 */
+	memset(freqs, 0, sizeof(freqs));
+
+	for (int i=0; i<count; i++)
+		for (int j=0; j<3; j++)
+			freqs[j][FlipSign(trg[i][j])]++;
+
+	/*
+	 * Do the sorting. Start with last character because that's the is "LSB"
+	 * in a trigram. Avoid unnecessary copies by ping-ponging between the buffers.
+	 */
+	for (int i=2; i>=0; i--)
+	{
+		trgm *old_from = from;
+		trgm *next = to;
+
+		for (int j=0; j<256; j++)
+		{
+			starts[j] = next;
+			next += freqs[i][j];
+		}
+
+		for (int j=0; j<count; j++)
+			memcpy(starts[FlipSign(from[j][i])]++, from[j], sizeof(trgm));
+
+		from = to;
+		to = old_from;
+	}
+
+	Assert(to == buffer);
+	memcpy(trg, buffer, sizeof(trgm) * count);
+	pfree(buffer);
+}
+
 /*
  * Guard against possible overflow in the palloc requests below.  (We
  * don't worry about the additive constants, since palloc can detect
@@ -439,7 +483,7 @@ generate_trgm(char *str, int slen)
 	{
 		if (GetDefaultCharSignedness())
 		{
-			trigram_qsort_signed((void *) GETARR(trg), len, sizeof(trgm));
+			radix_sort_trigrams_signed((trgm *)GETARR(trg), len);
 			len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_SIGNED);
 		}
 		else
@@ -995,7 +1039,7 @@ generate_wildcard_trgm(const char *str, int slen)
 	{
 		if (GetDefaultCharSignedness())
 		{
-			trigram_qsort_signed((void *) GETARR(trg), len, sizeof(trgm));
+			radix_sort_trigrams_signed((trgm *)GETARR(trg), len);
 			len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_SIGNED);
 		}
 		else
-- 
2.51.0

From c68aa700a245f1eb05f701a227776e24d0c0afe7 Mon Sep 17 00:00:00 2001
From: David Geier <geidav.pg@gmail.com>
Date: Mon, 10 Nov 2025 15:40:11 +0100
Subject: [PATCH v2 5/8] Make btint4cmp() branchless

---
 src/backend/access/nbtree/nbtcompare.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/src/backend/access/nbtree/nbtcompare.c b/src/backend/access/nbtree/nbtcompare.c
index bffc4b7709c..5ae27c22621 100644
--- a/src/backend/access/nbtree/nbtcompare.c
+++ b/src/backend/access/nbtree/nbtcompare.c
@@ -60,6 +60,7 @@
 #include "utils/fmgrprotos.h"
 #include "utils/skipsupport.h"
 #include "utils/sortsupport.h"
+#include "common/int.h"
 
 #ifdef STRESS_SORT_INT_MIN
 #define A_LESS_THAN_B		INT_MIN
@@ -202,12 +203,7 @@ btint4cmp(PG_FUNCTION_ARGS)
 	int32		a = PG_GETARG_INT32(0);
 	int32		b = PG_GETARG_INT32(1);
 
-	if (a > b)
-		PG_RETURN_INT32(A_GREATER_THAN_B);
-	else if (a == b)
-		PG_RETURN_INT32(0);
-	else
-		PG_RETURN_INT32(A_LESS_THAN_B);
+	PG_RETURN_INT32(pg_cmp_s32(a, b));
 }
 
 Datum
-- 
2.51.0

From 0cdc87640cf2a2d8c946aff1669706f99280c555 Mon Sep 17 00:00:00 2001
From: David Geier <geidav.pg@gmail.com>
Date: Mon, 10 Nov 2025 14:40:37 +0100
Subject: [PATCH v2 4/8] Avoid dedup and sort in ginExtractEntries

---
 contrib/pg_trgm/trgm_gin.c       |  2 ++
 doc/src/sgml/gin.sgml            |  7 ++++++-
 src/backend/access/gin/ginutil.c | 32 +++++++++++++++++++-------------
 3 files changed, 27 insertions(+), 14 deletions(-)

diff --git a/contrib/pg_trgm/trgm_gin.c b/contrib/pg_trgm/trgm_gin.c
index 66ff6adde99..862e650efec 100644
--- a/contrib/pg_trgm/trgm_gin.c
+++ b/contrib/pg_trgm/trgm_gin.c
@@ -36,10 +36,12 @@ gin_extract_value_trgm(PG_FUNCTION_ARGS)
 {
 	text	   *val = (text *) PG_GETARG_TEXT_PP(0);
 	int32	   *nentries = (int32 *) PG_GETARG_POINTER(1);
+	bool	   *uniqueAndSorted = (bool *) PG_GETARG_POINTER(3);
 	Datum	   *entries = NULL;
 	TRGM	   *trg;
 	int32		trglen;
 
+	*uniqueAndSorted = true;
 	*nentries = 0;
 
 	trg = generate_trgm(VARDATA_ANY(val), VARSIZE_ANY_EXHDR(val));
diff --git a/doc/src/sgml/gin.sgml b/doc/src/sgml/gin.sgml
index 82410b1fbdf..b96478731f8 100644
--- a/doc/src/sgml/gin.sgml
+++ b/doc/src/sgml/gin.sgml
@@ -167,7 +167,7 @@
   <variablelist>
     <varlistentry>
      <term><function>Datum *extractValue(Datum itemValue, int32 *nkeys,
-        bool **nullFlags)</function></term>
+        bool **nullFlags, bool *uniqueAndSorted)</function></term>
      <listitem>
       <para>
        Returns a palloc'd array of keys given an item to be indexed.  The
@@ -177,6 +177,11 @@
        <literal>*nullFlags</literal>, and set these null flags as needed.
        <literal>*nullFlags</literal> can be left <symbol>NULL</symbol> (its initial value)
        if all keys are non-null.
+       If the returned keys do not contain duplicates and are sorted w.r.t. the comparison
+       function of the GIN type's operator class, store <symbol>true</symbol> in
+       <literal>uniqueAndSorted</literal>. <literal>uniqueAndSorted</literal> can be left
+       <symbol>false</symbol> (its initial value) if the keys are either unsorted or contain
+       duplicates. In that case, duplicate removal and sorting is performed by the GIN index.
        The return value can be <symbol>NULL</symbol> if the item contains no keys.
       </para>
      </listitem>
diff --git a/src/backend/access/gin/ginutil.c b/src/backend/access/gin/ginutil.c
index 75a18f457bc..22b588483d0 100644
--- a/src/backend/access/gin/ginutil.c
+++ b/src/backend/access/gin/ginutil.c
@@ -464,6 +464,7 @@ ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 {
 	Datum	   *entries;
 	bool	   *nullFlags;
+	bool		uniqueAndSorted = false;
 	int32		i;
 
 	/*
@@ -483,11 +484,12 @@ ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 	/* OK, call the opclass's extractValueFn */
 	nullFlags = NULL;			/* in case extractValue doesn't set it */
 	entries = (Datum *)
-		DatumGetPointer(FunctionCall3Coll(&ginstate->extractValueFn[attnum - 1],
+		DatumGetPointer(FunctionCall4Coll(&ginstate->extractValueFn[attnum - 1],
 										  ginstate->supportCollation[attnum - 1],
 										  value,
 										  PointerGetDatum(nentries),
-										  PointerGetDatum(&nullFlags)));
+										  PointerGetDatum(&nullFlags),
+										  PointerGetDatum(&uniqueAndSorted)));
 
 	/*
 	 * Generate a placeholder if the item contained no keys.
@@ -502,13 +504,6 @@ ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 		return entries;
 	}
 
-	/*
-	 * If the extractValueFn didn't create a nullFlags array, create one,
-	 * assuming that everything's non-null.
-	 */
-	if (nullFlags == NULL)
-		nullFlags = (bool *) palloc0(*nentries * sizeof(bool));
-
 	/*
 	 * If there's more than one key, sort and unique-ify.
 	 *
@@ -516,11 +511,18 @@ ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 	 * pretty bad too.  For small numbers of keys it'd likely be better to use
 	 * a simple insertion sort.
 	 */
-	if (*nentries > 1)
+	if (*nentries > 1 && !uniqueAndSorted)
 	{
 		keyEntryData *keydata;
 		cmpEntriesArg arg;
 
+		/*
+		 * If the extractValueFn didn't create a nullFlags array, create one,
+		 * assuming that everything's non-null.
+		 */
+		if (nullFlags == NULL)
+			nullFlags = (bool *) palloc0(*nentries * sizeof(bool));
+
 		keydata = palloc_array(keyEntryData, *nentries);
 		for (i = 0; i < *nentries; i++)
 		{
@@ -568,9 +570,13 @@ ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 	/*
 	 * Create GinNullCategory representation from nullFlags.
 	 */
-	*categories = (GinNullCategory *) palloc0(*nentries * sizeof(GinNullCategory));
-	for (i = 0; i < *nentries; i++)
-		(*categories)[i] = (nullFlags[i] ? GIN_CAT_NULL_KEY : GIN_CAT_NORM_KEY);
+	StaticAssertStmt(GIN_CAT_NORM_KEY == 0, "Assuming GIN_CAT_NORM_KEY is 0");
+	*categories = palloc0_array(GinNullCategory, *nentries);
+
+	if (nullFlags != NULL)
+		for (i = 0; i < *nentries; i++)
+			if (nullFlags[i])
+				(*categories)[i] = GIN_CAT_NULL_KEY;
 
 	return entries;
 }
-- 
2.51.0

From c38f3517d05d3cefa0fc6d994f4e8f6ac14273d9 Mon Sep 17 00:00:00 2001
From: David Geier <geidav.pg@gmail.com>
Date: Mon, 10 Nov 2025 13:35:11 +0100
Subject: [PATCH v2 3/8] Use sort_template.h

---
 contrib/pg_trgm/trgm_op.c | 47 ++++++++++++++++++++++++++++++---------
 1 file changed, 37 insertions(+), 10 deletions(-)

diff --git a/contrib/pg_trgm/trgm_op.c b/contrib/pg_trgm/trgm_op.c
index 81182a15e07..6af120fa1ad 100644
--- a/contrib/pg_trgm/trgm_op.c
+++ b/contrib/pg_trgm/trgm_op.c
@@ -154,6 +154,23 @@ CMPTRGM_CHOOSE(const void *a, const void *b)
 	return CMPTRGM(a, b);
 }
 
+/* Define our specialized sort function name */
+#define ST_SORT trigram_qsort_signed
+#define ST_ELEMENT_TYPE_VOID
+#define ST_COMPARE(a, b) CMPTRGM_SIGNED(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#define ST_DECLARE
+#include "lib/sort_template.h"
+
+#define ST_SORT trigram_qsort_unsigned
+#define ST_ELEMENT_TYPE_VOID
+#define ST_COMPARE(a, b) CMPTRGM_UNSIGNED(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#define ST_DECLARE
+#include "lib/sort_template.h"
+
 /*
  * Deprecated function.
  * Use "pg_trgm.similarity_threshold" GUC variable instead of this function.
@@ -209,12 +226,6 @@ show_limit(PG_FUNCTION_ARGS)
 	PG_RETURN_FLOAT4(similarity_threshold);
 }
 
-static int
-comp_trgm(const void *a, const void *b)
-{
-	return CMPTRGM(a, b);
-}
-
 /*
  * Finds first word in string, returns pointer to the word,
  * endword points to the character after word
@@ -426,8 +437,16 @@ generate_trgm(char *str, int slen)
 	 */
 	if (len > 1)
 	{
-		qsort(GETARR(trg), len, sizeof(trgm), comp_trgm);
-		len = qunique(GETARR(trg), len, sizeof(trgm), comp_trgm);
+		if (GetDefaultCharSignedness())
+		{
+			trigram_qsort_signed((void *) GETARR(trg), len, sizeof(trgm));
+			len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_SIGNED);
+		}
+		else
+		{
+			trigram_qsort_unsigned((void *) GETARR(trg), len, sizeof(trgm));
+			len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_UNSIGNED);
+		}
 	}
 
 	SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
@@ -974,8 +993,16 @@ generate_wildcard_trgm(const char *str, int slen)
 	 */
 	if (len > 1)
 	{
-		qsort(GETARR(trg), len, sizeof(trgm), comp_trgm);
-		len = qunique(GETARR(trg), len, sizeof(trgm), comp_trgm);
+		if (GetDefaultCharSignedness())
+		{
+			trigram_qsort_signed((void *) GETARR(trg), len, sizeof(trgm));
+			len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_SIGNED);
+		}
+		else
+		{
+			trigram_qsort_unsigned((void *) GETARR(trg), len, sizeof(trgm));
+			len = qunique(GETARR(trg), len, sizeof(trgm), CMPTRGM_UNSIGNED);
+		}
 	}
 
 	SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
-- 
2.51.0

From ae80c2dc190493f8c9811c1949c7ebced265abd5 Mon Sep 17 00:00:00 2001
From: David Geier <geidav.pg@gmail.com>
Date: Mon, 10 Nov 2025 13:35:01 +0100
Subject: [PATCH v2 2/8] Optimized comparison functions

---
 src/backend/access/gin/ginutil.c | 23 ++++++++++++++++-------
 src/include/access/gin_private.h | 19 +++++++++++++++----
 2 files changed, 31 insertions(+), 11 deletions(-)

diff --git a/src/backend/access/gin/ginutil.c b/src/backend/access/gin/ginutil.c
index d205093e21d..75a18f457bc 100644
--- a/src/backend/access/gin/ginutil.c
+++ b/src/backend/access/gin/ginutil.c
@@ -114,6 +114,7 @@ initGinState(GinState *state, Relation index)
 	for (i = 0; i < origTupdesc->natts; i++)
 	{
 		Form_pg_attribute attr = TupleDescAttr(origTupdesc, i);
+		FunctionCallInfoBaseData *fci  = &state->compareFnCallInfo[i].fcinfo;
 
 		if (state->oneCol)
 			state->tupdesc[i] = state->origTupdesc;
@@ -222,6 +223,10 @@ initGinState(GinState *state, Relation index)
 			state->supportCollation[i] = index->rd_indcollation[i];
 		else
 			state->supportCollation[i] = DEFAULT_COLLATION_OID;
+
+		InitFunctionCallInfoData(*fci, &state->compareFn[i], 2, state->supportCollation[i], NULL, NULL);
+		fci->args[0].isnull = false;
+		fci->args[1].isnull = false;
 	}
 }
 
@@ -402,8 +407,7 @@ typedef struct
 
 typedef struct
 {
-	FmgrInfo   *cmpDatumFunc;
-	Oid			collation;
+	FunctionCallInfoBaseData   *cmpFuncInfo;
 	bool		haveDups;
 } cmpEntriesArg;
 
@@ -425,9 +429,15 @@ cmpEntries(const void *a, const void *b, void *arg)
 	else if (bb->isnull)
 		res = -1;				/* not-NULL "<" NULL */
 	else
-		res = DatumGetInt32(FunctionCall2Coll(data->cmpDatumFunc,
-											  data->collation,
-											  aa->datum, bb->datum));
+	{
+		FunctionCallInfo fci = data->cmpFuncInfo;
+		fci->args[0].value = aa->datum;
+		fci->args[1].value = bb->datum;
+		res = DatumGetInt32(FunctionCallInvoke(fci));
+
+		if (fci->isnull)
+			elog(ERROR, "function %u returned NULL", fci->flinfo->fn_oid);
+	}
 
 	/*
 	 * Detect if we have any duplicates.  If there are equal keys, qsort must
@@ -518,8 +528,7 @@ ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 			keydata[i].isnull = nullFlags[i];
 		}
 
-		arg.cmpDatumFunc = &ginstate->compareFn[attnum - 1];
-		arg.collation = ginstate->supportCollation[attnum - 1];
+		arg.cmpFuncInfo = &ginstate->compareFnCallInfo[attnum - 1].fcinfo;
 		arg.haveDups = false;
 		qsort_arg(keydata, *nentries, sizeof(keyEntryData),
 				  cmpEntries, &arg);
diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index e155045ce8a..7cf19c8a5dc 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -51,6 +51,11 @@ typedef struct GinOptions
 #define GIN_SHARE	BUFFER_LOCK_SHARE
 #define GIN_EXCLUSIVE  BUFFER_LOCK_EXCLUSIVE
 
+typedef union CompareFuncCallInfoData
+{
+	FunctionCallInfoBaseData fcinfo;
+	char fcinfo_data[SizeForFunctionCallInfo(2)];
+} CompareFuncCallInfoData;
 
 /*
  * GinState: working data structure describing the index being worked on
@@ -77,6 +82,10 @@ typedef struct GinState
 	/*
 	 * Per-index-column opclass support functions
 	 */
+
+
+	CompareFuncCallInfoData compareFnCallInfo[INDEX_MAX_KEYS];
+
 	FmgrInfo	compareFn[INDEX_MAX_KEYS];
 	FmgrInfo	extractValueFn[INDEX_MAX_KEYS];
 	FmgrInfo	extractQueryFn[INDEX_MAX_KEYS];
@@ -504,6 +513,8 @@ ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
 				  Datum a, GinNullCategory categorya,
 				  Datum b, GinNullCategory categoryb)
 {
+	FunctionCallInfoBaseData *fci;
+
 	/* if not of same null category, sort by that first */
 	if (categorya != categoryb)
 		return (categorya < categoryb) ? -1 : 1;
@@ -512,10 +523,10 @@ ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
 	if (categorya != GIN_CAT_NORM_KEY)
 		return 0;
 
-	/* both not null, so safe to call the compareFn */
-	return DatumGetInt32(FunctionCall2Coll(&ginstate->compareFn[attnum - 1],
-										   ginstate->supportCollation[attnum - 1],
-										   a, b));
+	fci = &ginstate->compareFnCallInfo[attnum - 1].fcinfo;
+	fci->args[0].value = a;
+	fci->args[1].value = b;
+	return DatumGetInt32(FunctionCallInvoke(fci));
 }
 
 /*
-- 
2.51.0

From a484e7c69bec62474b041eb4e533601e4883dab3 Mon Sep 17 00:00:00 2001
From: David Geier <geidav.pg@gmail.com>
Date: Thu, 6 Nov 2025 09:42:27 +0100
Subject: [PATCH v2 1/8] Inline ginCompareAttEntries

---
 src/backend/access/gin/ginutil.c | 38 ---------------------------
 src/include/access/gin_private.h | 44 +++++++++++++++++++++++++++-----
 2 files changed, 38 insertions(+), 44 deletions(-)

diff --git a/src/backend/access/gin/ginutil.c b/src/backend/access/gin/ginutil.c
index a546cac18d3..d205093e21d 100644
--- a/src/backend/access/gin/ginutil.c
+++ b/src/backend/access/gin/ginutil.c
@@ -387,44 +387,6 @@ GinInitMetabuffer(Buffer b)
 		((char *) metadata + sizeof(GinMetaPageData)) - (char *) page;
 }
 
-/*
- * Compare two keys of the same index column
- */
-int
-ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
-				  Datum a, GinNullCategory categorya,
-				  Datum b, GinNullCategory categoryb)
-{
-	/* if not of same null category, sort by that first */
-	if (categorya != categoryb)
-		return (categorya < categoryb) ? -1 : 1;
-
-	/* all null items in same category are equal */
-	if (categorya != GIN_CAT_NORM_KEY)
-		return 0;
-
-	/* both not null, so safe to call the compareFn */
-	return DatumGetInt32(FunctionCall2Coll(&ginstate->compareFn[attnum - 1],
-										   ginstate->supportCollation[attnum - 1],
-										   a, b));
-}
-
-/*
- * Compare two keys of possibly different index columns
- */
-int
-ginCompareAttEntries(GinState *ginstate,
-					 OffsetNumber attnuma, Datum a, GinNullCategory categorya,
-					 OffsetNumber attnumb, Datum b, GinNullCategory categoryb)
-{
-	/* attribute number is the first sort key */
-	if (attnuma != attnumb)
-		return (attnuma < attnumb) ? -1 : 1;
-
-	return ginCompareEntries(ginstate, attnuma, a, categorya, b, categoryb);
-}
-
-
 /*
  * Support for sorting key datums in ginExtractEntries
  *
diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index b33f7cec5b4..e155045ce8a 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -97,12 +97,6 @@ extern Buffer GinNewBuffer(Relation index);
 extern void GinInitBuffer(Buffer b, uint32 f);
 extern void GinInitPage(Page page, uint32 f, Size pageSize);
 extern void GinInitMetabuffer(Buffer b);
-extern int	ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
-							  Datum a, GinNullCategory categorya,
-							  Datum b, GinNullCategory categoryb);
-extern int	ginCompareAttEntries(GinState *ginstate,
-								 OffsetNumber attnuma, Datum a, GinNullCategory categorya,
-								 OffsetNumber attnumb, Datum b, GinNullCategory categoryb);
 extern Datum *ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 								Datum value, bool isNull,
 								int32 *nentries, GinNullCategory **categories);
@@ -502,6 +496,44 @@ ginCompareItemPointers(ItemPointer a, ItemPointer b)
 	return pg_cmp_u64(ia, ib);
 }
 
+/*
+ * Compare two keys of the same index column
+ */
+static inline int
+ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
+				  Datum a, GinNullCategory categorya,
+				  Datum b, GinNullCategory categoryb)
+{
+	/* if not of same null category, sort by that first */
+	if (categorya != categoryb)
+		return (categorya < categoryb) ? -1 : 1;
+
+	/* all null items in same category are equal */
+	if (categorya != GIN_CAT_NORM_KEY)
+		return 0;
+
+	/* both not null, so safe to call the compareFn */
+	return DatumGetInt32(FunctionCall2Coll(&ginstate->compareFn[attnum - 1],
+										   ginstate->supportCollation[attnum - 1],
+										   a, b));
+}
+
+/*
+ * Compare two keys of possibly different index columns
+ */
+static inline int
+ginCompareAttEntries(GinState *ginstate,
+					 OffsetNumber attnuma, Datum a, GinNullCategory categorya,
+					 OffsetNumber attnumb, Datum b, GinNullCategory categoryb)
+{
+	/* attribute number is the first sort key */
+	if (attnuma != attnumb)
+		return (attnuma < attnumb) ? -1 : 1;
+
+	return ginCompareEntries(ginstate, attnuma, a, categorya, b, categoryb);
+
+}
+
 extern int	ginTraverseLock(Buffer buffer, bool searchMode);
 
 #endif							/* GIN_PRIVATE_H */
-- 
2.51.0

From a0348e8dedb9a7ee53af8f88adbba0e5aeff577d Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Fri, 9 Jan 2026 19:31:19 +0200
Subject: [PATCH 1/1] Make the deduplication in ginExtractEntries() a little
 faster

The idea is to remove NULLs from the array first, and use qsort to
deduplicate only the non-NULL items. That simplifies the comparison
function a little.
---
 src/backend/access/gin/ginutil.c | 139 +++++++++++++------------------
 src/include/access/gin_private.h |   2 +-
 2 files changed, 61 insertions(+), 80 deletions(-)

diff --git a/src/backend/access/gin/ginutil.c b/src/backend/access/gin/ginutil.c
index d205093e21d..29966b9d05b 100644
--- a/src/backend/access/gin/ginutil.c
+++ b/src/backend/access/gin/ginutil.c
@@ -387,19 +387,6 @@ GinInitMetabuffer(Buffer b)
 		((char *) metadata + sizeof(GinMetaPageData)) - (char *) page;
 }
 
-/*
- * Support for sorting key datums in ginExtractEntries
- *
- * Note: we only have to worry about null and not-null keys here;
- * ginExtractEntries never generates more than one placeholder null,
- * so it doesn't have to sort those.
- */
-typedef struct
-{
-	Datum		datum;
-	bool		isnull;
-} keyEntryData;
-
 typedef struct
 {
 	FmgrInfo   *cmpDatumFunc;
@@ -410,24 +397,14 @@ typedef struct
 static int
 cmpEntries(const void *a, const void *b, void *arg)
 {
-	const keyEntryData *aa = (const keyEntryData *) a;
-	const keyEntryData *bb = (const keyEntryData *) b;
+	const Datum *aa = (const Datum *) a;
+	const Datum *bb = (const Datum *) b;
 	cmpEntriesArg *data = (cmpEntriesArg *) arg;
 	int			res;
 
-	if (aa->isnull)
-	{
-		if (bb->isnull)
-			res = 0;			/* NULL "=" NULL */
-		else
-			res = 1;			/* NULL ">" not-NULL */
-	}
-	else if (bb->isnull)
-		res = -1;				/* not-NULL "<" NULL */
-	else
-		res = DatumGetInt32(FunctionCall2Coll(data->cmpDatumFunc,
-											  data->collation,
-											  aa->datum, bb->datum));
+	res = DatumGetInt32(FunctionCall2Coll(data->cmpDatumFunc,
+										  data->collation,
+										  *aa, *bb));
 
 	/*
 	 * Detect if we have any duplicates.  If there are equal keys, qsort must
@@ -450,11 +427,13 @@ cmpEntries(const void *a, const void *b, void *arg)
 Datum *
 ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 				  Datum value, bool isNull,
-				  int32 *nentries, GinNullCategory **categories)
+				  int32 *nentries_p, GinNullCategory **categories_p)
 {
 	Datum	   *entries;
 	bool	   *nullFlags;
-	int32		i;
+	GinNullCategory *categories;
+	bool		hasNull;
+	int32		nentries;
 
 	/*
 	 * We don't call the extractValueFn on a null item.  Instead generate a
@@ -462,42 +441,60 @@ ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 	 */
 	if (isNull)
 	{
-		*nentries = 1;
+		*nentries_p = 1;
 		entries = palloc_object(Datum);
 		entries[0] = (Datum) 0;
-		*categories = palloc_object(GinNullCategory);
-		(*categories)[0] = GIN_CAT_NULL_ITEM;
+		*categories_p = palloc_object(GinNullCategory);
+		(*categories_p)[0] = GIN_CAT_NULL_ITEM;
 		return entries;
 	}
 
 	/* OK, call the opclass's extractValueFn */
 	nullFlags = NULL;			/* in case extractValue doesn't set it */
+	nentries = 0;
 	entries = (Datum *)
 		DatumGetPointer(FunctionCall3Coll(&ginstate->extractValueFn[attnum - 1],
 										  ginstate->supportCollation[attnum - 1],
 										  value,
-										  PointerGetDatum(nentries),
+										  PointerGetDatum(&nentries),
 										  PointerGetDatum(&nullFlags)));
 
 	/*
 	 * Generate a placeholder if the item contained no keys.
 	 */
-	if (entries == NULL || *nentries <= 0)
+	if (entries == NULL || nentries <= 0)
 	{
-		*nentries = 1;
+		*nentries_p = 1;
 		entries = palloc_object(Datum);
 		entries[0] = (Datum) 0;
-		*categories = palloc_object(GinNullCategory);
-		(*categories)[0] = GIN_CAT_EMPTY_ITEM;
+		*categories_p = palloc_object(GinNullCategory);
+		(*categories_p)[0] = GIN_CAT_EMPTY_ITEM;
 		return entries;
 	}
 
 	/*
-	 * If the extractValueFn didn't create a nullFlags array, create one,
-	 * assuming that everything's non-null.
+	 * Scan the items for any NULLs.  All NULLs are considered equal, so we
+	 * just need to check and remember if there are any.  We remove them from
+	 * the array here, and if necessary, put back one NULL entry to represent
+	 * them all after deduplication.
 	 */
-	if (nullFlags == NULL)
-		nullFlags = (bool *) palloc0(*nentries * sizeof(bool));
+	hasNull = false;
+	if (nullFlags)
+	{
+		int32		numNonNulls = 0;
+
+		for (int32 i = 0; i < nentries; i++)
+		{
+			if (nullFlags[i])
+				hasNull = true;
+			else
+			{
+				entries[numNonNulls] = entries[i];
+				numNonNulls++;
+			}
+		}
+		nentries = numNonNulls;
+	}
 
 	/*
 	 * If there's more than one key, sort and unique-ify.
@@ -506,63 +503,47 @@ ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 	 * pretty bad too.  For small numbers of keys it'd likely be better to use
 	 * a simple insertion sort.
 	 */
-	if (*nentries > 1)
+	if (nentries > 1)
 	{
-		keyEntryData *keydata;
 		cmpEntriesArg arg;
 
-		keydata = palloc_array(keyEntryData, *nentries);
-		for (i = 0; i < *nentries; i++)
-		{
-			keydata[i].datum = entries[i];
-			keydata[i].isnull = nullFlags[i];
-		}
-
 		arg.cmpDatumFunc = &ginstate->compareFn[attnum - 1];
 		arg.collation = ginstate->supportCollation[attnum - 1];
 		arg.haveDups = false;
-		qsort_arg(keydata, *nentries, sizeof(keyEntryData),
+		qsort_arg(entries, nentries, sizeof(Datum),
 				  cmpEntries, &arg);
 
 		if (arg.haveDups)
 		{
 			/* there are duplicates, must get rid of 'em */
-			int32		j;
+			int32		j = 1;
 
-			entries[0] = keydata[0].datum;
-			nullFlags[0] = keydata[0].isnull;
-			j = 1;
-			for (i = 1; i < *nentries; i++)
+			for (int32 i = 1; i < nentries; i++)
 			{
-				if (cmpEntries(&keydata[i - 1], &keydata[i], &arg) != 0)
-				{
-					entries[j] = keydata[i].datum;
-					nullFlags[j] = keydata[i].isnull;
-					j++;
-				}
+				if (cmpEntries(&entries[i - 1], &entries[i], &arg) != 0)
+					entries[j++] = entries[i];
 			}
-			*nentries = j;
+			nentries = j;
 		}
-		else
-		{
-			/* easy, no duplicates */
-			for (i = 0; i < *nentries; i++)
-			{
-				entries[i] = keydata[i].datum;
-				nullFlags[i] = keydata[i].isnull;
-			}
-		}
-
-		pfree(keydata);
 	}
 
 	/*
-	 * Create GinNullCategory representation from nullFlags.
+	 * Create GinNullCategory representation.
 	 */
-	*categories = (GinNullCategory *) palloc0(*nentries * sizeof(GinNullCategory));
-	for (i = 0; i < *nentries; i++)
-		(*categories)[i] = (nullFlags[i] ? GIN_CAT_NULL_KEY : GIN_CAT_NORM_KEY);
+	categories = (GinNullCategory *) palloc((nentries + (hasNull ? 1 : 0)) * sizeof(GinNullCategory));
+	for (int32 i = 0; i < nentries; i++)
+		categories[i] = GIN_CAT_NORM_KEY;
+
+	/* Put back a NULL entry, if there were any */
+	if (hasNull)
+	{
+		entries[nentries] = (Datum) 0;
+		categories[nentries] = GIN_CAT_NULL_KEY;
+		nentries++;
+	}
 
+	*nentries_p = nentries;
+	*categories_p = categories;
 	return entries;
 }
 
diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index e155045ce8a..1e97e6cb3c9 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -99,7 +99,7 @@ extern void GinInitPage(Page page, uint32 f, Size pageSize);
 extern void GinInitMetabuffer(Buffer b);
 extern Datum *ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 								Datum value, bool isNull,
-								int32 *nentries, GinNullCategory **categories);
+								int32 *nentries_p, GinNullCategory **categories_p);
 
 extern OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple);
 extern Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple,
-- 
2.47.3