Re: Reduce build times of pg_trgm GIN indexes

On Wed, 9 Sept 2026 at 10:49, David Geier <geidav(dot)pg(at)gmail(dot)com> wrote:
>
> Hi Matthias!
>
> Thanks a lot for your review.
>
> > Please add commit descriptions; the current patches don't have much
> > other than their subjects which don't describe any rationale for the
> > changes applied.
>
> Done.

0001: LGTM

0002:

> > 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.

> > 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?

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.

0003:

> > 1. ginInsertBAEntry leaks the copied key Datum if the type is by-ref
> > and already present in the accumulator.
>
> Good catch!
>
> I cannot use HASH_KEYCOPY because I'm using simplehash.h. I changed it
> to use the original key for doing the lookup and only create the copy in
> the !found path. This is also how the old code did it. Changing the key
> of an already inserted hashmap entry is save because we overwrite it
> with a copy. So the hash function will keep returning the same position
> for it.

Ah, indeed. Thanks for fixing it.

> > 2. The comment for ginInsertBAEntries was completely removed, rather
> > than updated to the new workings.
>
> Yes, because the comment no longer applies. All of it was specific to
> using a red-black tree. ginInsertBAEntries() is now merely syntactic
> sugar. I thought about removing the function completely but it's used in
> a couple of places and without it, the call sites would get slightly
> more ugly.

I see, that seems reasonable.

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.

Kind regards,

Matthias van de Meent
Databricks (https://www.databricks.com)