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
