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
