Re: Reduce build times of pg_trgm GIN indexes

On 14/09/2026 15:31, David Geier wrote:
>>>> 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.

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.

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

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?

- Heikki