Hi Heikki, Thanks for getting back to this patch set.
>> 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. > > I agree it's a bit unfortunate that this uses so much more memory; it > would be nice to come up with some tricks to reduce it. If there are no > easy tricks available, though, it's probably a good tradeoff to accept > the memory usage. It's bounded to MaxAllocSize, and the performance > boost seems well worth it. I took a 2nd look at the in-place radix sort and realized that I missed a few optimizations that make it a lot more competitive. Most importantly: 1. Sort residual partitions with insertion sort. That's because the overhead of radix sort for small arrays is high due to the fixed memset(), frequency counting and prefix sum overhead. 2. Optimize the shuffling loop by skipping elements that are already in place. Using insertion sort for the residual partitions made it worthwhile again to optimize the trigram comparator. Attached is 0002 which optimizes CMPTRGM_SIGNED() and CMPTRGM_UNSIGNED(). With that the sort_template.h based path got faster and a bunch of other code which uses the trigram comparators such as calc_word_similarity(), trgm_contained_by(), ... >> 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. > > You could combine these final qunique() and memcpy() steps, by > introducing a version of qunique() that takes separate "source" and > "dest" arguments, instead of deduplicating in place. Dunno if it makes > any difference in practice. > > The size of the array is limited by MaxAllocSize, so you could change > the "size_t" variables to "int32". Dunno if that'd make any difference > either. Done. Didn't make for a measurable difference but reducing stack pressure seems like a good thing to do regardless. > One problem is that radix sort is slower for small arrays. The patch > makes the extreme case of just one or two trigrams in the input much > slower. That's straightforward to fix by keeping the old qsort > implementation for small arrays, although I wonder if there's some more > elegant way? That's a good point. The out-of-place radix sort regresses the following test case considerably. On my system, the file contains 104,334 lines, each consisting of a single word. The average word length is 8.4 characters. CREATE TABLE dict_words(word TEXT NOT NULL); COPY dict_words(word) FROM '/usr/share/dict/words' WITH (FORMAT text); INSERT INTO dict_words SELECT * FROM dict_words; INSERT INTO dict_words SELECT * FROM dict_words; VACUUM ANALYZE dict_words; \timing on SET max_parallel_maintenance_workers = 0; CREATE INDEX ON dict_words USING gin(word gin_trgm_ops); I optimized the out-of-place radix sort in 0003a by falling back to the same insertion sort that the in-place radix sort in 0003b uses. With that the regression disappears. Below are the results of the following patches: - master, - 0001: deduplicate across rows via hash map instead of RB-tree - 0002: optimize trigram comparators used by sort_template.h - 0003: out-of-place radix sort with insertion sort fallback - 0004: in-place radix sort with insertion sort fallback Data set | master | 0001 | 0002 | 0003 | 0004 ---------|---------|---------|---------|---------|-------- movies | 8,772 | 7,344 | 6,812 | 3,814 | 5,514 dict | 554 | 307 | 304 | 292 | 288 lineitem | 219,540 | 146,679 | 141,465 | 124,011 | 124,745 Benchmark script is also attached. The movies data set benefits most from 0003a because it contains long movie plots where the out-of-place radix sort performs best. The shorter the strings get, the less advantage 0003a has compared to 0003b. Ironically, that's also where the in-placeness is least beneficial. On a different note: is there anything else about 0001? It gives the biggest speedup and seemed uncontroversial as well. -- David Geier
From 1cc68117d8e37ae8ed83f4c565302180cfadb749 Mon Sep 17 00:00:00 2001 From: David Geier <[email protected]> Date: Fri, 6 Nov 2026 15:01:09 +0100 Subject: [PATCH v12 4/4] Use in-place American Flag Sort to extract trigrams American Flag Sort is an in-place MSD radix sort variant that recursively partitions trigrams by character position. It's slower though than out-of-place LSD radix sort for big input arrays. Insertion sort handles small partitions where the overhead of frequency and prefix sum computations outweigh the gains. qunique() still removes duplicates afterwards. --- contrib/pg_trgm/trgm_op.c | 75 +++++++++++++++++++-------------------- 1 file changed, 36 insertions(+), 39 deletions(-) diff --git a/contrib/pg_trgm/trgm_op.c b/contrib/pg_trgm/trgm_op.c index 5c1b1c14cd4..49688bbc984 100644 --- a/contrib/pg_trgm/trgm_op.c +++ b/contrib/pg_trgm/trgm_op.c @@ -272,8 +272,8 @@ 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) +static inline void +trigram_radix_sort_recurse(trgm *trg, size_t count, int base, bool char_is_signed) { if (count < 64) { @@ -292,55 +292,50 @@ trigram_radix_sort_and_unique(trgm *trg, size_t count, bool char_is_signed) memcpy(trg[j], &tmp, sizeof(trgm)); } - - return qunique(trg, count, sizeof(trgm), CMPTRGM_EQ); } else { - trgm *buffer = palloc_array(trgm, count); - trgm *starts[256]; - trgm *from = trg; - trgm *to = buffer; - uint32_t freqs[3][256]; + uint32_t freqs[256]; + uint32_t starts[256]; + uint32_t cur[256]; - /* - * Compute frequencies to partition the buffer. - */ memset(freqs, 0, sizeof(freqs)); + for (size_t i = 0; i < count; i++) + freqs[radix_key(trg[i][base], char_is_signed)]++; - for (size_t j = 0; j < count; j++) - { - freqs[0][radix_key(trg[j][0], char_is_signed)]++; - freqs[1][radix_key(trg[j][1], char_is_signed)]++; - freqs[2][radix_key(trg[j][2], char_is_signed)]++; - } + starts[0] = 0; + for (int k = 1; k < 256; k++) + starts[k] = starts[k - 1] + freqs[k - 1]; - /* - * 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--) + memcpy(cur, starts, sizeof(cur)); + + for (size_t i = 0; i < count; i++) { - trgm *old_from = from; - trgm *next = to; + unsigned char b = radix_key(trg[i][base], char_is_signed); - for (size_t j = 0; j < 256; j++) + while (i < starts[b] || i >= starts[b] + freqs[b]) { - starts[j] = next; - next += freqs[i][j]; - } + const char c = trg[i][base]; + size_t j = cur[b]; + trgm tmp; + + while (trg[j][base] == c) + j++; + + Assert(j < starts[b] + freqs[b]); - for (size_t j = 0; j < count; j++) - memcpy(starts[radix_key(from[j][i], char_is_signed)]++, from[j], sizeof(trgm)); + memcpy(tmp, trg[i], sizeof(trgm)); + memcpy(trg[i], trg[j], sizeof(trgm)); + memcpy(trg[j], tmp, sizeof(trgm)); - from = to; - to = old_from; + cur[b] = j + 1; + b = radix_key(trg[i][base], char_is_signed); + } } - count = qunique(buffer, count, sizeof(trgm), CMPTRGM_EQ); - memcpy(trg, buffer, sizeof(trgm) * count); - pfree(buffer); - return count; + for (int k = 0; k < 256; k++) + if (freqs[k] > 1 && base < 2) + trigram_radix_sort_recurse(trg + starts[k], freqs[k], base + 1, char_is_signed); } } @@ -348,9 +343,11 @@ static size_t trigram_sort_and_unique(trgm *array, size_t n) { if (GetDefaultCharSignedness()) - return trigram_radix_sort_and_unique(array, n, true); + trigram_radix_sort_recurse(array, n, 0, true); else - return trigram_radix_sort_and_unique(array, n, false); + trigram_radix_sort_recurse(array, n, 0, false); + + return qunique(array, n, sizeof(trgm), CMPTRGM_EQ); } /* -- 2.53.0
From 6afcdd994211afa6565d9eb2f90cd9b7142a7d45 Mon Sep 17 00:00:00 2001 From: David Geier <[email protected]> Date: Tue, 11 Nov 2025 13:18:59 +0100 Subject: [PATCH v12 3/4] Use out-of-place radix sort to extract trigrams Replace the comparison-based sort used by generate_trgm() and generate_wildcard_trgm() with an out-of-place LSD 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. Insertion sort handles small partitions where the overhead of frequency and prefix sum computations outweigh the gains. 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. --- contrib/pg_trgm/trgm_op.c | 126 ++++++++++++++++++++++++++------------ 1 file changed, 88 insertions(+), 38 deletions(-) diff --git a/contrib/pg_trgm/trgm_op.c b/contrib/pg_trgm/trgm_op.c index 8f9b64649d4..5c1b1c14cd4 100644 --- a/contrib/pg_trgm/trgm_op.c +++ b/contrib/pg_trgm/trgm_op.c @@ -248,33 +248,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 @@ -290,11 +263,94 @@ 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) +{ + if (count < 64) + { + for (size_t i = 1; i < count; i++) + { + trgm tmp; + size_t j = i; + + memcpy(&tmp, trg[i], sizeof(trgm)); + + while (j > 0 && cmptrgm(trg[j - 1], tmp, char_is_signed) > 0) + { + memcpy(trg[j], trg[j - 1], sizeof(trgm)); + j--; + } + + memcpy(trg[j], &tmp, sizeof(trgm)); + } + + return qunique(trg, count, sizeof(trgm), CMPTRGM_EQ); + } + else + { + trgm *buffer = palloc_array(trgm, count); + trgm *starts[256]; + trgm *from = trg; + trgm *to = buffer; + uint32_t freqs[3][256]; + + /* + * Compute frequencies to partition the buffer. + */ + memset(freqs, 0, sizeof(freqs)); + + for (size_t j = 0; j < count; j++) + { + freqs[0][radix_key(trg[j][0], char_is_signed)]++; + freqs[1][radix_key(trg[j][1], char_is_signed)]++; + freqs[2][radix_key(trg[j][2], char_is_signed)]++; + } + + /* + * 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; + + for (size_t j = 0; j < 256; j++) + { + starts[j] = next; + next += freqs[i][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); } /* @@ -633,10 +689,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)); @@ -1164,10 +1217,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 6810e521b26da3a38183dd48ea2ebd6075ce88b4 Mon Sep 17 00:00:00 2001 From: David Geier <[email protected]> Date: Fri, 6 Nov 2026 10:51:50 +0100 Subject: [PATCH v12 2/4] Optimize trigram sort comparators CMPTRGM_SIGNED() and CMPTRGM_UNSIGNED() now assemble the trigram into a single uint32 from explicit byte loads, with trg[0] as the most significant byte, making the comparison endian-agnostic and avoiding a read past the 3-byte trgm. The signed variant flips the sign bit of each byte so that signed-char ordering maps onto unsigned ordering, in the spirit of radix sort. --- contrib/pg_trgm/trgm_op.c | 46 +++++++++++++++++++++++++++++---------- 1 file changed, 34 insertions(+), 12 deletions(-) diff --git a/contrib/pg_trgm/trgm_op.c b/contrib/pg_trgm/trgm_op.c index 22bcc3c3361..8f9b64649d4 100644 --- a/contrib/pg_trgm/trgm_op.c +++ b/contrib/pg_trgm/trgm_op.c @@ -185,30 +185,52 @@ _PG_init(void) MarkGUCPrefixReserved("pg_trgm"); } -#define CMPCHAR(a,b) ( ((a)==(b)) ? 0 : ( ((a)<(b)) ? -1 : 1 ) ) - /* * Functions for comparing two trgms while treating each char as "signed char" or * "unsigned char". + * + * Trigrams are stored in memory as trg[0], trg[1], trg[2], ordered from most + * significant trigram to least significant trigram. + * The code adheres to that by shifting trg[0] to the most significant byte, + * trg[1] to the second most significant byte anbd trg[2] to the last significant + * byte. Only loading bytes makes this code endian-agnostic. + * */ +static pg_always_inline int +cmptrgm(const trgm a, const trgm b, bool char_is_signed) +{ + const uint8 *ua = (const uint8 *)a; + const uint8 *ub = (const uint8 *)b; + uint32 ia = ((uint32)ua[0] << 16) | ((uint32)ua[1] << 8) | ua[2]; + uint32 ib = ((uint32)ub[0] << 16) | ((uint32)ub[1] << 8) | ub[2]; + + /* + * The signed comparator flips the sign bit of each of the three trigrams to + * ensure correct ordering on compilers that tread char as signed. + * + * Background: When treated as unsigned, positive numbers sort after negative + * numbers because negative numbers have the sign bit set in two's complement. + * Flipping the sign bit reverses this order. + */ + if (char_is_signed) + { + ia ^= 0x00808080; + ib ^= 0x00808080; + } + + return (ia < ib) ? -1 : ((ia > ib) ? 1 : 0); +} + static inline int CMPTRGM_SIGNED(const void *a, const void *b) { -#define CMPPCHAR_S(a,b,i) CMPCHAR( *(((const signed char*)(a))+i), *(((const signed char*)(b))+i) ) - - return CMPPCHAR_S(a, b, 0) ? CMPPCHAR_S(a, b, 0) - : (CMPPCHAR_S(a, b, 1) ? CMPPCHAR_S(a, b, 1) - : CMPPCHAR_S(a, b, 2)); + return cmptrgm(a, b, true); } static inline int CMPTRGM_UNSIGNED(const void *a, const void *b) { -#define CMPPCHAR_UNS(a,b,i) CMPCHAR( *(((const unsigned char*)(a))+i), *(((const unsigned char*)(b))+i) ) - - return CMPPCHAR_UNS(a, b, 0) ? CMPPCHAR_UNS(a, b, 0) - : (CMPPCHAR_UNS(a, b, 1) ? CMPPCHAR_UNS(a, b, 1) - : CMPPCHAR_UNS(a, b, 2)); + return cmptrgm(a, b, false); } /* -- 2.53.0
From 0f0338e311260ccbbb358f814edf0285edc60b2d Mon Sep 17 00:00:00 2001 From: David Geier <[email protected]> Date: Wed, 22 Apr 2026 14:00:40 +0200 Subject: [PATCH v12 1/4] 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 553162c0810..581fce7adea 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -1104,7 +1104,8 @@ GinBuildShared GinBuildState GinChkVal GinEntries -GinEntryAccumulator +GinHashEntry +GinHashKey GinIndexStat GinLeader GinMetaPageData @@ -1124,6 +1125,7 @@ GinScanKeyData GinScanOpaque GinScanOpaqueData GinSegmentInfo +GinSortEntry GinState GinStatsData GinTernaryValue -- 2.53.0
gin_benchmark.sql
Description: application/sql
