Re: Reduce build times of pg_trgm GIN indexes

> Another 0001 regression is for long text keys:
>
> SET maintenance_work_mem = '256MB';
> SET max_parallel_maintenance_workers = 0;
> CREATE TABLE long_key AS
> SELECT i, ARRAY[repeat('a',6000)] a FROM generate_series(1,1000000) i;
> VACUUM (FREEZE,ANALYZE) long_key;
> CREATE INDEX long_key_gin ON long_key USING gin(a);
>
> in my run, slowdown is 1605.768 -> 705.046 ms
>
> CPU profiles show datum_image_hash() -> hash_bytes() on top. The RB
> tree use the fast memcmp, but hashing bytes is much more expensive:
> each 12 bytes from input we perform mix marco, which is 6 calls of
> `pg_rotate_left32`
datum_image_hash() uses hash_bytes() which is incredibly slow. I tried
some other hash functions with your example. Results:

hash_bytes(): 1956 ms
fasthash32(): 1200 ms
xxhash3(): 817 ms
master: 651 ms

xxhash3() heavily uses AVX instructions to get to that level of
throughput. Using fasthash32() would be an easy win and should be
correct, given that datum_image_hash() is currently only called from
nodeMemoize.c and nowhere leaks to on-disk representations. Building and
integrating a faster hash function is a lot more effort and preferably
something we do as a separate effort. On that note: datum_image_hash()
can also be optimized considerably for fixed length data types which
should help the trigram case where trigrams are compared via int4cmp().

To me the test case also seems somewhat degenerate. I think the gains
for the average case by far outweigh the losses here. Interestingly,
having the strings mismatch towards the end makes it completely blow up
in both cases.

CREATE TABLE long_key AS
SELECT
i,
ARRAY[repeat('a', 6000 - length(i::text)) || i::text] AS a
FROM
generate_series(1, 1000000) i;

CREATE INDEX suddenly runs for minutes (hours?) because when the strings
are of different lengths, varstr_cmp() can no longer try first with
memcmp() but always has to call pg_strncoll().

In that case the hash-based implementation wins again. I measured 8,538
ms on master vs 6,749 ms with the patch.

--
David Geier