Re: Reduce build times of pg_trgm GIN indexes

Hi Kirill,

Thanks for taking a look at the patch set.

> Hi! I think there is a regression with numeric[]. Equal numeric values
> can have different scales, so e.g. 1, 1.0 have different byte images.
> The RB-tree accumulator combines them by comparator equality while the
> hash keeps a separate entry for each image.
>
> example (no pg_trgm extension required):
>
> SET max_parallel_maintenance_workers = 0;
> SET maintenance_work_mem = '256MB';
> CREATE TABLE numeric_many AS
> SELECT i, ARRAY[round((i%100)::numeric, ((i/100)%256)::int)] AS a
> FROM generate_series(1,1000000) AS i;
> VACUUM (FREEZE, ANALYZE) numeric_many;
> SELECT count(*), count(DISTINCT a[1]),
> count(DISTINCT encode(numeric_send(a[1]),'hex')) FROM numeric_many;
>
>
> in my run size of patch index is 7.3532338308457711x bigger and build
> time is 4.0799353308331456x longer

I had considered the general case of two values being equal w.r.t.
image_datum_hash() but different w.r.t. semantic quality, but assumed
that this is a corner case that happens very infrequently and when it
happens the number of colliding values would be very low (e.g. -0, 0, +0).

The reason for why the index remains correct and won't end up with
duplicate keys is the following: ginEntryInsert() looks up the key in
the entry tree using the opclass' comparator via ginFindLeafPage() and
then findItem(). So when we flush e.g. 1.0 after 1, the lookup finds the
existing 1 tuple. The new TIDs are then merged into it: in-tuple via
addItemPointersToLeafTuple(), or into the posting tree via
ginInsertItemPointers().

The reason for the increased size and the slowdown is the cost of how
those entries get merged, and where in the index they get merged. The RB
tree didn't just remove duplicates. It merged all TIDs for a semantic
key into one sorted list in memory before touching the index. With the
hash, that merge happens later, inside the index, one image at a time.

I can see the following options to go about it:

1. Leave as is because the case is degenerate and doesn't happen in
practice.
2. Merge semantically identical hash map entries before inserting them
into the index. sort_keys() in ginBeginBAScan() already puts
semantically equal entries next to each other in
accum->sorted_entries. So we can do one pass over accum->sorted_keys
to remove duplicates while combining their TID lists.
3. We use the type's hash function instead of image_datum_hash(). That
would map semantically equal keys to the same hash entry. I didn't do
that because it means GIN indexable types would have to be hashable.
That seems like a non-starter.
4. Combination of (2) and (3). We do (3) if the type is hashable and (2)
if it's not. That adds a bunch of extra complexity.

I'm between (1) and (2). I have a hard time seeing how something like
that would happen in practice at a scale that it matters but who knows.
(2) is fairly simple and only costs one extra compare per hash map entry
in the normal case where there are no duplicates.

What do you think?

--
David Geier