2. This increases the memory requirements of trigram_qsort by a huge margin.
Could you change the radixsort to operate in-place, so that the new
buffer is not needed?
Trigram radix sort is only called from generate_trgm() and
generate_wildcard_trgm() which are both used to extract the unique
trigrams from a _single_ string value.
We don't radix sort trigrams of multiple string values. Hence, the
maximum increase in memory, while building the GIN index, is in the size
of the longest string encountered, not in the number of rows.
Given that in-place radix sort is a lot more complex and slower, I think
the current tradeoff is fine.
Beyond that, other GIN index functions also allocate extra memory on a
per-value basis which shows that this should not be a problem in
practice (e.g. ginarrayextract(), gin_extract_value_trgm(), ...).
It happens, but I'd still like to avoid new O(large) allocations, if
that's possible without losing performance; allocations aren't free,
after all.
I've played around with an in-place MSD radix sort which partitions the data
and then recurses into each partition. With that code the overall
performance
regresses significantly (> 30%) which means the regression for just the sort
is even higher. I've attached my code, in case you want to take a look.
3. The implementation for trigram_qsort_unsigned has not been adjusted
nor replaced, and so keeps the same old performance that
trigram_qsort_signed had.
Please make sure to also adjust that implementation.
Done.
I laid out the code such that the compiler has the possibility to fully
inline both variants to get rid of the extra code in radix_key() for
flipping the sign bit in the unsigned case. But even if it doesn't,
radix_key() can be branchless and the performance is anyway dominated by
memory traffic.
Yes, did you check that it actually gets inlined and/or optimized for
signed/unsigned versions in your local compiler?
Yes, it does.
The compiler opted for putting upfront either 0 or 0x80 into the register it
later uses to XOR with, depending on if char_is_signed is true or false.
It always does the XOR but it's completely branchless inside the loops.
That's fine, given that the XOR is by no means the hotspot and duplicating
the function would increase code size.
Further note:
Now that trigram_radix_sort_with_signedness ends with a memcpy, and
every caller then calls trigram_qunique on that output, wouldn't it
make sense to include `trigram_qunique` in that final memcpy of
trigram_radix_sort?
Checking that the output is unique during the copy operation could
avoid another n_entries memory accesses vs post-copy uniqify
operations, and also save memmoves.
Good idea.
I've tried that but it's slower than doing it in-place. At least for my
benchmark which mostly processes trigram arrays of ~10 to a few thousand
trigrams
with a high number of duplicates (which is pretty realistic because in most
cases, the input strings are short to medium long).
What we could do instead is allocate a new TRGM varlena and use it as
temporary
radix sort buffer. The qunique() can then run on that buffer and we then
replace
the input TRGM with the temporary TRGM. This is marginally faster but
the code
is uglier as now the trigram radix sort function is concerned with
messing around
with the TRGM varlena. Hence, I'm leaning towards not using it.
A third variant I've tried is running qunique() on the final buffer from
the radix sort and then only copying over the unique trigrams back to
the input
buffer. The difference is within noise but I kept it because it doesn't
make the code harder to read, see attached patch.
Speaking about performance: apart from such small tweaks there are the
following
bigger optimizations I'm still planning to do, once this patch set went in:
1. Optimize the string processing code in generate_trgm_only() which
extracts
the non-unique trigrams from the input strings. Currently, this function
takes
up ~40% of all runtime.
2. Store trigrams as 32-bit integers inside the arrays to improve
qunique() and
sorting performance, as well as avoid the conversion to int-arrays in
some places.
Newly noticed:
The new sort template for ItemPointerData should probably be a public
and reusable function, as I see many cases of qsort(..., ...,
sizeof(ItemPointerData), someItemPtrCompareFn), where qsort itself is
backed by a generic sort_template.h implementation. Pulling the
specialized implementation into its own function would allow those
callsites to be updated to the specialized version that we're
generating here.
I had a look but only found four occurrences apart from the new sort in
my patch:
1. 1x in nodeTidScan.c
2. 1x in heap_surgery.c
3. 2x in test_tidstore.c
Have you come across any other?
Attached is the updated patch set. Only change is doing the qunique()
inside the
radix sort function and renaming a few function to better reflect that
apart from
sorting it now also deduplicates.
--
David Geier
static size_t
trigram_radix_sort_and_unique_recurse(trgm *trg, size_t count, int base,
bool char_is_signed)
{
size_t freqs[256];
size_t starts[256];
size_t cur[256];
size_t i;
int k;
if (count <= 1)
return count;
if (base >= 3)
return qunique(trg, count, sizeof(trgm), CMPTRGM_EQ);
memset(freqs, 0, sizeof(freqs));
for (i = 0; i < count; i++)
freqs[radix_key(trg[i][base], char_is_signed)]++;
starts[0] = 0;
for (k = 1; k < 256; k++)
starts[k] = starts[k - 1] + freqs[k - 1];
memcpy(cur, starts, sizeof(cur));
for (i = 0; i < count; i++)
{
for (;;)
{
unsigned char b = radix_key(trg[i][base], char_is_signed);
if (i >= starts[b] && i < cur[b])
break;
{
size_t j = cur[b]++;
trgm tmp;
memcpy(tmp, trg[i], sizeof(trgm));
memcpy(trg[i], trg[j], sizeof(trgm));
memcpy(trg[j], tmp, sizeof(trgm));
}
}
}
for (k = 0; k < 256; k++)
if (freqs[k] > 1)
trigram_radix_sort_and_unique_recurse(trg + starts[k], freqs[k], base + 1, char_is_signed);
}From 6d92f03ca284876d7198423432d65400717383a1 Mon Sep 17 00:00:00 2001
From: David Geier <[email protected]>
Date: Wed, 22 Apr 2026 14:00:40 +0200
Subject: [PATCH v11 3/3] Replace GIN build accumulator RB-tree with a hashmap
Replace the red-black tree used by ginInsertBAEntries() with a hash table
based on simplehash.h. This keeps the same basic accumulation strategy
as the previous implementation while changing key lookup and deduplication
from O(log(num_unique_keys)) tree operations to expected O(1) hash-table
operations. As a result, the overall complexity changes from
O(num_total_keys * log(num_unique_keys))
to
O(num_total_keys + num_unique_keys * log(num_unique_keys))
The latter is preferable for the usual case, where the number of unique
keys is much smaller than the number of rows. Even when most or all keys
are unique, the RB-tree rebalancing operations are sufficiently
expensive that the theoretical worst-case advantage of the tree does not
necessarily translate into better runtime.
The item pointer lists associated with each key continue to be sorted
before the accumulated entries are emitted. Use sort_template.h for this
sorting instead of qsort(). The distinct hash entries are copied into an
array and sorted using the existing GIN key comparison function so that
the output order remains unchanged.
ginInsertBAEntries() got much simpler as well. The previous implementation
inserted entries in an order intended to minimize red-black tree rebalancing
for sorted inputs. With a hash table, inserting the entries in their original
order is preferable because repeated keys are more likely to be found in the
same hash-table entry.
Use datumIsEqual() and datum_image_hash() for normal GIN keys. This is
consistent with the current GIN implementation, which does not correctly
support non-deterministic collations or types for which logically equal
values are not image-equal.
Because parallel GIN index builds also use ginInsertBAEntries(), this
change improves the accumulation phase of parallel index builds as well.
---
src/backend/access/gin/ginbulk.c | 339 +++++++++++++++----------------
src/include/access/gin_private.h | 24 +--
src/tools/pgindent/typedefs.list | 4 +-
3 files changed, 175 insertions(+), 192 deletions(-)
diff --git a/src/backend/access/gin/ginbulk.c b/src/backend/access/gin/ginbulk.c
index 85865b39105..77c12ba932b 100644
--- a/src/backend/access/gin/ginbulk.c
+++ b/src/backend/access/gin/ginbulk.c
@@ -17,107 +17,118 @@
#include <limits.h>
#include "access/gin_private.h"
+#include "common/hashfn.h"
#include "utils/datum.h"
#include "utils/memutils.h"
+#define DEF_NENTRY 2048 /* Initial hash table size */
+#define DEF_ITEMS_PER_KEY 8 /* Initial ItemPointer array size per key */
-#define DEF_NENTRY 2048 /* GinEntryAccumulator allocation quantum */
-#define DEF_NPTR 5 /* ItemPointer initial allocation quantum */
-
-
-/* Combiner function for rbtree.c */
-static void
-ginCombineData(RBTNode *existing, const RBTNode *newdata, void *arg)
+typedef struct GinHashKey
{
- GinEntryAccumulator *eo = (GinEntryAccumulator *) existing;
- const GinEntryAccumulator *en = (const GinEntryAccumulator *) newdata;
- BuildAccumulator *accum = (BuildAccumulator *) arg;
+ OffsetNumber attnum;
+ GinNullCategory category;
+ Datum key;
+} GinHashKey;
- /*
- * Note this code assumes that newdata contains only one itempointer.
- */
- if (eo->count >= eo->maxcount)
- {
- if (eo->maxcount > INT_MAX)
- ereport(ERROR,
- (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
- errmsg("posting list is too long"),
- errhint("Reduce \"maintenance_work_mem\".")));
+typedef struct GinHashEntry
+{
+ GinHashKey hashkey;
+ uint32 hash;
+ char status;
+ ItemPointerData *items;
+ uint32 numItems;
+ uint32 allocatedItems;
+} GinHashEntry;
+
+typedef struct GinSortEntry
+{
+ GinHashKey hashkey;
+ ItemPointerData *items;
+ uint32 numItems;
+} GinSortEntry;
+
+static uint32 gin_hash_key(struct ginbuild_hash *tb, GinHashKey *key);
+static bool gin_equal_key(struct ginbuild_hash *tb, GinHashKey *a, GinHashKey *b);
+
+#define SH_PREFIX ginbuild
+#define SH_ELEMENT_TYPE GinHashEntry
+#define SH_KEY_TYPE GinHashKey
+#define SH_KEY hashkey
+#define SH_HASH_KEY(tb, key) gin_hash_key(tb, &key)
+#define SH_EQUAL(tb, a, b) gin_equal_key(tb, &a, &b)
+#define SH_SCOPE static inline
+#define SH_STORE_HASH
+#define SH_GET_HASH(tb, a) (a)->hash
+#define SH_DEFINE
+#define SH_DECLARE
+#include "lib/simplehash.h"
+
+static uint32
+gin_hash_key(struct ginbuild_hash *tb, GinHashKey *key)
+{
+ BuildAccumulator *accum = (BuildAccumulator *) tb->private_data;
+ uint32 hash;
- accum->allocatedMemory -= GetMemoryChunkSpace(eo->list);
- eo->maxcount *= 2;
- eo->list = (ItemPointerData *)
- repalloc_huge(eo->list, sizeof(ItemPointerData) * eo->maxcount);
- accum->allocatedMemory += GetMemoryChunkSpace(eo->list);
- }
+ hash = hash_combine(0, murmurhash32((uint32) key->attnum));
+ hash = hash_combine(hash, murmurhash32((uint32) key->category));
- /* If item pointers are not ordered, they will need to be sorted later */
- if (eo->shouldSort == false)
+ if (key->category == GIN_CAT_NORM_KEY)
{
- int res;
-
- res = ginCompareItemPointers(eo->list + eo->count - 1, en->list);
- Assert(res != 0);
+ CompactAttribute *att;
- if (res > 0)
- eo->shouldSort = true;
+ att = TupleDescCompactAttr(accum->ginstate->origTupdesc, key->attnum - 1);
+ hash = hash_combine(hash, datum_image_hash(key->key, att->attbyval, att->attlen));
}
- eo->list[eo->count] = en->list[0];
- eo->count++;
+ return hash;
}
-/* Comparator function for rbtree.c */
-static int
-cmpEntryAccumulator(const RBTNode *a, const RBTNode *b, void *arg)
+static bool
+gin_equal_key(struct ginbuild_hash *tb, GinHashKey *a, GinHashKey *b)
{
- const GinEntryAccumulator *ea = (const GinEntryAccumulator *) a;
- const GinEntryAccumulator *eb = (const GinEntryAccumulator *) b;
- BuildAccumulator *accum = (BuildAccumulator *) arg;
-
- return ginCompareAttEntries(accum->ginstate,
- ea->attnum, ea->key, ea->category,
- eb->attnum, eb->key, eb->category);
-}
+ BuildAccumulator *accum = (BuildAccumulator *) tb->private_data;
+ CompactAttribute *att;
-/* Allocator function for rbtree.c */
-static RBTNode *
-ginAllocEntryAccumulator(void *arg)
-{
- BuildAccumulator *accum = (BuildAccumulator *) arg;
- GinEntryAccumulator *ea;
+ if (a->attnum != b->attnum)
+ return false;
+ if (a->category != b->category)
+ return false;
+ if (a->category != GIN_CAT_NORM_KEY)
+ return true;
/*
- * Allocate memory by rather big chunks to decrease overhead. We have no
- * need to reclaim RBTNodes individually, so this costs nothing.
+ * Compare the actual key values using image equality.
+ * This is correct because we don't want to deduplicate at this point.
*/
- if (accum->entryallocator == NULL || accum->eas_used >= DEF_NENTRY)
- {
- accum->entryallocator = palloc_array(GinEntryAccumulator, DEF_NENTRY);
- accum->allocatedMemory += GetMemoryChunkSpace(accum->entryallocator);
- accum->eas_used = 0;
- }
-
- /* Allocate new RBTNode from current chunk */
- ea = accum->entryallocator + accum->eas_used;
- accum->eas_used++;
-
- return (RBTNode *) ea;
+ att = TupleDescCompactAttr(accum->ginstate->origTupdesc, a->attnum - 1);
+ return datumIsEqual(a->key, b->key, att->attbyval, att->attlen);
}
+#define ST_SORT sort_itempointers
+#define ST_ELEMENT_TYPE ItemPointerData
+#define ST_COMPARE(a, b) ginCompareItemPointers(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+#define ST_SORT sort_keys
+#define ST_ELEMENT_TYPE GinSortEntry
+#define ST_COMPARE_ARG_TYPE GinState
+#define ST_COMPARE(a, b, state) ginCompareAttEntries(state, a->hashkey.attnum, a->hashkey.key, a->hashkey.category, b->hashkey.attnum, b->hashkey.key, b->hashkey.category)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
void
ginInitBA(BuildAccumulator *accum)
{
/* accum->ginstate is intentionally not set here */
- accum->allocatedMemory = 0;
- accum->entryallocator = NULL;
- accum->eas_used = 0;
- accum->tree = rbt_create(sizeof(GinEntryAccumulator),
- cmpEntryAccumulator,
- ginCombineData,
- ginAllocEntryAccumulator,
- NULL, /* no freefunc needed */
- accum);
+ accum->hash = ginbuild_create(CurrentMemoryContext, DEF_NENTRY, accum);
+ accum->allocatedMemory = accum->hash->size * sizeof(GinHashEntry);
+ accum->sorted_entries = NULL;
+ accum->num_entries = 0;
+ accum->current_pos = 0;
}
/*
@@ -142,124 +153,113 @@ getDatumCopy(BuildAccumulator *accum, OffsetNumber attnum, Datum value)
}
/*
- * Find/store one entry from indexed value.
+ * Insert one entry into the hash map.
+ * If the key already exists, append to its ItemPointer array.
+ * Otherwise, create a new hash entry with a new ItemPointer array.
*/
static void
ginInsertBAEntry(BuildAccumulator *accum,
ItemPointer heapptr, OffsetNumber attnum,
Datum key, GinNullCategory category)
{
- GinEntryAccumulator eatmp;
- GinEntryAccumulator *ea;
- bool isNew;
+ GinHashKey hashkey;
+ GinHashEntry *entry;
+ bool found;
+ uint64 oldsize;
- /*
- * For the moment, fill only the fields of eatmp that will be looked at by
- * cmpEntryAccumulator or ginCombineData.
- */
- eatmp.attnum = attnum;
- eatmp.key = key;
- eatmp.category = category;
- /* temporarily set up single-entry itempointer list */
- eatmp.list = heapptr;
+ hashkey.attnum = attnum;
+ hashkey.category = category;
+ hashkey.key = key;
- ea = (GinEntryAccumulator *) rbt_insert(accum->tree, (RBTNode *) &eatmp,
- &isNew);
+ oldsize = accum->hash->size;
+ entry = ginbuild_insert(accum->hash, hashkey, &found);
- if (isNew)
+ if (!found)
{
/*
- * Finish initializing new tree entry, including making permanent
- * copies of the datum (if it's not null) and itempointer.
+ * Finish initializing new hashmap entry including making a permanent
+ * copy of the key.
*/
if (category == GIN_CAT_NORM_KEY)
- ea->key = getDatumCopy(accum, attnum, key);
- ea->maxcount = DEF_NPTR;
- ea->count = 1;
- ea->shouldSort = false;
- ea->list = palloc_array(ItemPointerData, DEF_NPTR);
- ea->list[0] = *heapptr;
- accum->allocatedMemory += GetMemoryChunkSpace(ea->list);
+ entry->hashkey.key = getDatumCopy(accum, attnum, key);
+
+ entry->items = palloc_array(ItemPointerData, DEF_ITEMS_PER_KEY);
+ entry->numItems = 0;
+ entry->allocatedItems = DEF_ITEMS_PER_KEY;
+ accum->allocatedMemory += (accum->hash->size - oldsize) * sizeof(GinHashEntry);
+ accum->allocatedMemory += GetMemoryChunkSpace(entry->items);
}
- else
+
+ if (entry->numItems >= entry->allocatedItems)
{
- /*
- * ginCombineData did everything needed.
- */
+ uint32 new_allocated;
+
+ if (entry->allocatedItems > UINT32_MAX / 2)
+ ereport(ERROR,
+ (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
+ errmsg("too many GIN item pointers for a single key"),
+ errhint("Reduce \"maintenance_work_mem\".")));
+
+ accum->allocatedMemory -= GetMemoryChunkSpace(entry->items);
+ new_allocated = entry->allocatedItems * 2;
+ entry->items = repalloc_huge(entry->items, mul_size(sizeof(ItemPointerData), new_allocated));
+ entry->allocatedItems = new_allocated;
+ accum->allocatedMemory += GetMemoryChunkSpace(entry->items);
}
+
+ entry->items[entry->numItems++] = *heapptr;
}
-/*
- * Insert the entries for one heap pointer.
- *
- * Since the entries are being inserted into a balanced binary tree, you
- * might think that the order of insertion wouldn't be critical, but it turns
- * out that inserting the entries in sorted order results in a lot of
- * rebalancing operations and is slow. To prevent this, we attempt to insert
- * the nodes in an order that will produce a nearly-balanced tree if the input
- * is in fact sorted.
- *
- * We do this as follows. First, we imagine that we have an array whose size
- * is the smallest power of two greater than or equal to the actual array
- * size. Second, we insert the middle entry of our virtual array into the
- * tree; then, we insert the middles of each half of our virtual array, then
- * middles of quarters, etc.
- */
void
ginInsertBAEntries(BuildAccumulator *accum,
ItemPointer heapptr, OffsetNumber attnum,
Datum *entries, GinNullCategory *categories,
int32 nentries)
{
- uint32 step = nentries;
-
if (nentries <= 0)
return;
Assert(ItemPointerIsValid(heapptr) && attnum >= FirstOffsetNumber);
- /*
- * step will contain largest power of 2 and <= nentries
- */
- step |= (step >> 1);
- step |= (step >> 2);
- step |= (step >> 4);
- step |= (step >> 8);
- step |= (step >> 16);
- step >>= 1;
- step++;
-
- while (step > 0)
- {
- int i;
-
- for (i = step - 1; i < nentries && i >= 0; i += step << 1 /* *2 */ )
- ginInsertBAEntry(accum, heapptr, attnum,
- entries[i], categories[i]);
-
- step >>= 1; /* /2 */
- }
+ for (int i = 0; i < nentries; i++)
+ ginInsertBAEntry(accum, heapptr, attnum, entries[i], categories[i]);
}
-static int
-qsortCompareItemPointers(const void *a, const void *b)
-{
- int res = ginCompareItemPointers((const ItemPointerData *) a, (const ItemPointerData *) b);
-
- /* Assert that there are no equal item pointers being sorted */
- Assert(res != 0);
- return res;
-}
-
-/* Prepare to read out the rbtree contents using ginGetBAEntry */
+/* Prepare to read out the hash table contents using ginGetBAEntry */
void
ginBeginBAScan(BuildAccumulator *accum)
{
- rbt_begin_iterate(accum->tree, LeftRightWalk, &accum->tree_walk);
+ ginbuild_iterator iter;
+ GinHashEntry *entry;
+ uint32 i = 0;
+
+ accum->num_entries = accum->hash->members;
+ accum->current_pos = 0;
+
+ if (accum->num_entries == 0)
+ return;
+
+ accum->sorted_entries = palloc_array(GinSortEntry, accum->num_entries);
+ ginbuild_start_iterate(accum->hash, &iter);
+
+ while ((entry = ginbuild_iterate(accum->hash, &iter)) != NULL)
+ {
+ GinSortEntry *se = &accum->sorted_entries[i];
+ sort_itempointers(entry->items, entry->numItems);
+
+ se->hashkey = entry->hashkey;
+ se->items = entry->items;
+ se->numItems = entry->numItems;
+ i++;
+ }
+
+ Assert(i == accum->num_entries);
+ sort_keys(accum->sorted_entries, accum->num_entries, accum->ginstate);
+ accum->current_pos = 0;
}
/*
- * Get the next entry in sequence from the BuildAccumulator's rbtree.
+ * Get the next entry in sequence from the BuildAccumulator's sorted hash entries.
* This consists of a single key datum and a list (array) of one or more
* heap TIDs in which that key is found. The list is guaranteed sorted.
*/
@@ -268,25 +268,18 @@ ginGetBAEntry(BuildAccumulator *accum,
OffsetNumber *attnum, Datum *key, GinNullCategory *category,
uint32 *n)
{
- GinEntryAccumulator *entry;
- ItemPointerData *list;
-
- entry = (GinEntryAccumulator *) rbt_iterate(&accum->tree_walk);
+ GinSortEntry *entry;
- if (entry == NULL)
+ if (accum->current_pos >= accum->num_entries)
return NULL; /* no more entries */
- *attnum = entry->attnum;
- *key = entry->key;
- *category = entry->category;
- list = entry->list;
- *n = entry->count;
-
- Assert(list != NULL && entry->count > 0);
+ entry = &accum->sorted_entries[accum->current_pos];
+ accum->current_pos++;
- if (entry->shouldSort && entry->count > 1)
- qsort(list, entry->count, sizeof(ItemPointerData),
- qsortCompareItemPointers);
+ *attnum = entry->hashkey.attnum;
+ *key = entry->hashkey.key;
+ *category = entry->hashkey.category;
+ *n = entry->numItems;
- return list;
+ return entry->items;
}
diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index 3c5fd6ba817..df6b44796c6 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -18,7 +18,6 @@
#include "common/int.h"
#include "catalog/pg_am_d.h"
#include "fmgr.h"
-#include "lib/rbtree.h"
#include "nodes/tidbitmap.h"
#include "storage/bufmgr.h"
@@ -420,26 +419,15 @@ extern void ginadjustmembers(Oid opfamilyoid,
List *functions);
/* ginbulk.c */
-typedef struct GinEntryAccumulator
-{
- RBTNode rbtnode;
- Datum key;
- GinNullCategory category;
- OffsetNumber attnum;
- bool shouldSort;
- ItemPointerData *list;
- uint32 maxcount; /* allocated size of list[] */
- uint32 count; /* current number of list[] entries */
-} GinEntryAccumulator;
typedef struct
{
- GinState *ginstate;
- Size allocatedMemory;
- GinEntryAccumulator *entryallocator;
- uint32 eas_used;
- RBTree *tree;
- RBTreeIterator tree_walk;
+ GinState * ginstate;
+ Size allocatedMemory;
+ struct ginbuild_hash * hash;
+ struct GinSortEntry * sorted_entries;
+ uint32 num_entries;
+ uint32 current_pos;
} BuildAccumulator;
extern void ginInitBA(BuildAccumulator *accum);
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index de21cea65f9..e243a205b45 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1107,7 +1107,8 @@ GinBuildShared
GinBuildState
GinChkVal
GinEntries
-GinEntryAccumulator
+GinHashEntry
+GinHashKey
GinIndexStat
GinLeader
GinMetaPageData
@@ -1127,6 +1128,7 @@ GinScanKeyData
GinScanOpaque
GinScanOpaqueData
GinSegmentInfo
+GinSortEntry
GinState
GinStatsData
GinTernaryValue
--
2.53.0
From 4a6e0875ae9b71530bc8a43ce5c25ef96d08b857 Mon Sep 17 00:00:00 2001
From: David Geier <[email protected]>
Date: Tue, 11 Nov 2025 13:18:59 +0100
Subject: [PATCH v11 2/3] Use radix sort to extract trigrams
Replace the comparison-based sort used by generate_trgm() and
generate_wildcard_trgm() with a three-pass radix sort.
Trigrams consist of three bytes, so their keys have a fixed and very
small width. A radix sort can therefore order them in linear time with
respect to the number of trigrams, avoiding the repeated comparator calls
and recursive partitioning performed by qsort.
The implementation preserves the existing behavior on platforms where
char is signed by flipping the most significant bit before sorting.
The radix sort requires a temporary buffer, increasing the memory
footprint while trigrams are being extracted from an input string.
However, the sort is performed separately for each string and is never
applied across multiple strings at once. Consequently, the additional
memory is limited to the processing of the current string and should
have a negligible effect on the overall memory footprint of a GIN index
build.
The resulting order remains compatible with trigram deduplication and
does not change the generated trigram sets.
---
contrib/pg_trgm/trgm_op.c | 99 ++++++++++++++++++++++++---------------
1 file changed, 61 insertions(+), 38 deletions(-)
diff --git a/contrib/pg_trgm/trgm_op.c b/contrib/pg_trgm/trgm_op.c
index 22bcc3c3361..57eaba43f14 100644
--- a/contrib/pg_trgm/trgm_op.c
+++ b/contrib/pg_trgm/trgm_op.c
@@ -226,33 +226,6 @@ CMPTRGM_CHOOSE(const void *a, const void *b)
return CMPTRGM(a, b);
}
-#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"
-
-/* Sort an array of trigrams, handling signedness correctly */
-static void
-trigram_qsort(trgm *array, size_t n)
-{
- if (GetDefaultCharSignedness())
- trigram_qsort_signed(array, n, sizeof(trgm));
- else
- trigram_qsort_unsigned(array, n, sizeof(trgm));
-}
-
-
/*
* Compare two trigrams for equality. This has the same signature as
* comparison functions used for sorting, so that this can be used with
@@ -268,11 +241,67 @@ CMPTRGM_EQ(const void *a, const void *b)
return aa[0] != bb[0] || aa[1] != bb[1] || aa[2] != bb[2] ? 1 : 0;
}
-/* Deduplicate an array of trigrams */
+/*
+ * Needed to properly handle negative numbers in case char is signed.
+ */
+static inline unsigned char
+radix_key(char x, bool char_is_signed)
+{
+ return char_is_signed ? x ^ 0x80 : x;
+}
+
+static inline size_t
+trigram_radix_sort_and_unique(trgm *trg, size_t count, bool char_is_signed)
+{
+ trgm *buffer = palloc_array(trgm, count);
+ trgm *starts[256];
+ trgm *from = trg;
+ trgm *to = buffer;
+ size_t freqs[256];
+
+ /*
+ * Do the sorting. Start with last character because that's the "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;
+
+ /*
+ * Compute frequencies to partition the buffer.
+ */
+ memset(freqs, 0, sizeof(freqs));
+
+ for (size_t j = 0; j < count; j++)
+ freqs[radix_key(trg[j][i], char_is_signed)]++;
+
+ for (size_t j = 0; j < 256; j++)
+ {
+ starts[j] = next;
+ next += freqs[j];
+ }
+
+ for (size_t j = 0; j < count; j++)
+ memcpy(starts[radix_key(from[j][i], char_is_signed)]++, from[j], sizeof(trgm));
+
+ from = to;
+ to = old_from;
+ }
+
+ count = qunique(buffer, count, sizeof(trgm), CMPTRGM_EQ);
+ memcpy(trg, buffer, sizeof(trgm) * count);
+ pfree(buffer);
+ return count;
+}
+
static size_t
-trigram_qunique(trgm *array, size_t n)
+trigram_sort_and_unique(trgm *array, size_t n)
{
- return qunique(array, n, sizeof(trgm), CMPTRGM_EQ);
+ if (GetDefaultCharSignedness())
+ return trigram_radix_sort_and_unique(array, n, true);
+ else
+ return trigram_radix_sort_and_unique(array, n, false);
}
/*
@@ -611,10 +640,7 @@ generate_trgm(char *str, int slen)
* Make trigrams unique.
*/
if (len > 1)
- {
- trigram_qsort(GETARR(trg), len);
- len = trigram_qunique(GETARR(trg), len);
- }
+ len = trigram_sort_and_unique(GETARR(trg), len);
SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
@@ -1142,10 +1168,7 @@ generate_wildcard_trgm(const char *str, int slen)
trg = arr.datum;
len = arr.length;
if (len > 1)
- {
- trigram_qsort(GETARR(trg), len);
- len = trigram_qunique(GETARR(trg), len);
- }
+ len = trigram_sort_and_unique(GETARR(trg), len);
trg->flag = ARRKEY;
SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
--
2.53.0
From 9f77777031665d398d7ceaad7d390630d6054911 Mon Sep 17 00:00:00 2001
From: David Geier <[email protected]>
Date: Mon, 10 Nov 2025 15:40:11 +0100
Subject: [PATCH v11 1/3] Use branchless comparisons in btint4cmp and btint8cmp
Use the common pg_cmp_s32() and pg_cmp_s64() helpers to implement the
built-in B-tree comparison functions for int4 and int8.
The previous implementations used conditional branches to distinguish
less-than, equal, and greater-than values. The common comparison helpers
perform the same three-way comparison without data-dependent branches,
which can improve performance for workloads involving frequent integer
comparisons while preserving the required comparator result semantics.
btint4cmp() and btint8cmp() are PostgreSQL-callable functions invoked
through the function manager. They are not inlined at their call sites,
so replacing the original conditional implementation does not prevent a
compiler from optimizing an inline comparison in contexts where it can
see and better optimize the surrounding code. In other words, this
change affects the function-manager call path without imposing a
performance regression on callers for which the comparison could
otherwise have been inlined.
The comparison helpers also provide the appropriate handling for the
full ranges of int32 and int64 values without relying on subtraction,
which could overflow for values near the type limits.
---
src/backend/access/nbtree/nbtcompare.c | 15 +++------------
1 file changed, 3 insertions(+), 12 deletions(-)
diff --git a/src/backend/access/nbtree/nbtcompare.c b/src/backend/access/nbtree/nbtcompare.c
index 4e3a3a0f7ce..80dec200a3d 100644
--- a/src/backend/access/nbtree/nbtcompare.c
+++ b/src/backend/access/nbtree/nbtcompare.c
@@ -61,6 +61,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
@@ -194,12 +195,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
@@ -262,12 +258,7 @@ btint8cmp(PG_FUNCTION_ARGS)
int64 a = PG_GETARG_INT64(0);
int64 b = PG_GETARG_INT64(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_s64(a, b));
}
Datum
--
2.53.0
