Re: Reduce build times of pg_trgm GIN indexes

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:
> 1. radix_sort_trigrams_signed has an `int count` argument, but the
> caller trigram_qsort uses size_t.

Changed count argument to size_t.

> 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(), ...).

> 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.
> 0003:
>
> 1. ginInsertBAEntry leaks the copied key Datum if the type is by-ref
> and already present in the accumulator.

Good catch!

They weren't leaked for good but would have gotten cleaned up with the
next batch. But they would have unnecessarily increased the memory
footprint. Especially, as the number of unique trigrams is typically low
and hence we often hit the "already present in the accumulator" path.

> I think specifying HASH_KEYCOPY to only copying the Datum key if an
> entry is already present is more appropriate.

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.

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

Would you like to see anything specific in the comment?

Attached is the updated patch, rebased on latest master. With 0003,
rbtree.h/.c are completely unused and could be removed as well,
including the test code.

--
David Geier