Re: Reduce build times of pg_trgm GIN indexes

Hi Heikki,

Thanks for getting back to this patch set.

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

I took a 2nd look at the in-place radix sort and realized that I
missed a few optimizations that make it a lot more competitive. Most
importantly:

1. Sort residual partitions with insertion sort. That's because the
overhead of radix sort for small arrays is high due to the fixed
memset(), frequency counting and prefix sum overhead.
2. Optimize the shuffling loop by skipping elements that are already in
place.

Using insertion sort for the residual partitions made it worthwhile
again to optimize the trigram comparator. Attached is 0002 which
optimizes CMPTRGM_SIGNED() and CMPTRGM_UNSIGNED().
With that the sort_template.h based path got faster and a bunch of other
code which uses the trigram comparators such as calc_word_similarity(),
trgm_contained_by(), ...

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

Done. Didn't make for a measurable difference but reducing stack
pressure seems like a good thing to do regardless.

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

That's a good point. The out-of-place radix sort regresses the following
test case considerably. On my system, the file contains 104,334 lines,
each consisting of a single word. The average word length is 8.4 characters.

CREATE TABLE dict_words(word TEXT NOT NULL);
COPY dict_words(word) FROM '/usr/share/dict/words' WITH (FORMAT text);
INSERT INTO dict_words SELECT * FROM dict_words;
INSERT INTO dict_words SELECT * FROM dict_words;
VACUUM ANALYZE dict_words;
\timing on
SET max_parallel_maintenance_workers = 0;
CREATE INDEX ON dict_words USING gin(word gin_trgm_ops);

I optimized the out-of-place radix sort in 0003a by falling back to the
same insertion sort that the in-place radix sort in 0003b uses. With
that the regression disappears.

Below are the results of the following patches:

- master,
- 0001: deduplicate across rows via hash map instead of RB-tree
- 0002: optimize trigram comparators used by sort_template.h
- 0003: out-of-place radix sort with insertion sort fallback
- 0004: in-place radix sort with insertion sort fallback

Data set | master | 0001 | 0002 | 0003 | 0004
---------|---------|---------|---------|---------|--------
movies | 8,772 | 7,344 | 6,812 | 3,814 | 5,514
dict | 554 | 307 | 304 | 292 | 288
lineitem | 219,540 | 146,679 | 141,465 | 124,011 | 124,745

Benchmark script is also attached.

The movies data set benefits most from 0003a because it contains long
movie plots where the out-of-place radix sort performs best. The shorter
the strings get, the less advantage 0003a has compared to 0003b.
Ironically, that's also where the in-placeness is least beneficial.

On a different note: is there anything else about 0001? It gives the
biggest speedup and seemed uncontroversial as well.

--
David Geier