Re: Reduce build times of pg_trgm GIN indexes

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

Yes, it does.

The compiler opted for putting upfront either 0 or 0x80 into the register it
later uses to XOR with, depending on if char_is_signed is true or false.
It always does the XOR but it's completely branchless inside the loops.

That's fine, given that the XOR is by no means the hotspot and duplicating
the function would increase code size.

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

I've tried that but it's slower than doing it in-place. At least for my
benchmark which mostly processes trigram arrays of ~10 to a few thousand
trigrams
with a high number of duplicates (which is pretty realistic because in most
cases, the input strings are short to medium long).

What we could do instead is allocate a new TRGM varlena and use it as
temporary
radix sort buffer. The qunique() can then run on that buffer and we then
replace
the input TRGM with the temporary TRGM. This is marginally faster but
the code
is uglier as now the trigram radix sort function is concerned with
messing around
with the TRGM varlena. Hence, I'm leaning towards not using 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.

Speaking about performance: apart from such small tweaks there are the
following
bigger optimizations I'm still planning to do, once this patch set went in:

1. Optimize the string processing code in generate_trgm_only() which
extracts
the non-unique trigrams from the input strings. Currently, this function
takes
up ~40% of all runtime.

2. Store trigrams as 32-bit integers inside the arrays to improve
qunique() and
sorting performance, as well as avoid the conversion to int-arrays in
some places.

> 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.
>
I had a look but only found four occurrences apart from the new sort in
my patch:

1. 1x in nodeTidScan.c
2. 1x in heap_surgery.c
3. 2x in test_tidstore.c

Have you come across any other?

Attached is the updated patch set. Only change is doing the qunique()
inside the
radix sort function and renaming a few function to better reflect that
apart from
sorting it now also deduplicates.

--
David Geier