Speed up hash join builds by linking tuples into buckets in groups

Hi,

These patches reduce the cache misses that happen each time a tuple is
linked into its bucket while building a hash join table. They pick up
Thomas's experiment from [1], reworked into the "link them in
groups" form that Andres suggested at the time [2]. Building a hash
table of 3M rows takes about 35% less time.

"In groups" does not mean fetching several tuples at once from the child
node. Tuples are still fetched one at a time and copied into the chunks
as before; only the linking into buckets is done in groups. Fetching
tuples from child nodes in batches seems closer to what is being
discussed in [3], but this part gives a speedup without waiting for that.

=== The patches

After a tuple is copied into the chunk, its bucket header is prefetched
and the tuple is queued. Once 32 tuples have accumulated, they are
linked in a short loop. This is only used when the bucket array has at
least 65536 entries (512kB). (Below it, the queue makes no measurable
difference, so small tables are left unchanged.)

0001 is for private hash tables, 0002 is for parallel Hash. 0001 can be
committed on its own.

=== The question from [1]

[2] asked how much of the gain of [1] comes from the prefetch and how
much from out-of-order execution, and suggested that a loop linking
tuples in groups should help even without a prefetch instruction.

as in [1] (link 8 tuples later + prefetch) -38%
as in [1], without the prefetch +1% (no effect)
link in groups of 32, no prefetch -40%

So the gain of [1] comes from the prefetch, and linking in groups is
just as effective even without it. I kept the prefetch anyway because
it makes things 5-10% faster when the bucket array fits in L3 and when
the table is rebuilt.

=== Results

On an AMD Zen3 laptop (WSL2, gcc 11.4, no cassert,
-falign-functions=64), I ran the attached bench.sh.txt alternately
against master and the patched build for 10 rounds (median times):

build side master patched
3M rows (bucket array 32MB) 743.2 ms 479.4 ms (-36.0%)
3M wide rows 1369.5 ms 1093.8 ms (-23.9%)
Parallel Hash, 3M rows (2 workers) 1039.1 ms 742.9 ms (-30.3%)
300K rows (4MB) 40.1 ms 38.0 ms ( -6.5%)
underestimated, table rebuilt 579.1 ms 551.4 ms ( -6.4%)
60K rows (at the threshold) 7.4 ms 7.7 ms ( +0.7%)
duplicate keys 404.6 ms 409.9 ms ( +0.7%)

Comparing master against itself also varied by about +-4% (median), so
the +0.7% and -6% results are most likely within noise.

I only have a WSL2 machine with 2 physical cores, so I could only
measure Parallel Hash with up to 2 workers, and I haven't tried Intel,
ARM or machines with more cores. The group size (32) and the
threshold (65536) were chosen from measurements on this one machine.

Comments welcome.

Regards,
Tatsuya Kawata

[1]
https://www.postgresql.org/message-id/flat/CAEepm%3D2y9HM9QP%2BHhRZdQ3pU6FShSMyu%3DV1uHXhQ5gG-dketHg%40mail.gmail.com
[2]
https://www.postgresql.org/message-id/20200204013127.llyrwlf7e636wm5w%40alap3.anarazel.de
[3]
https://www.postgresql.org/message-id/flat/CA%2BHiwqFfAY_ZFqN8wcAEMw71T9hM_kA8UtyHaZZEZtuT3UyogA%40mail.gmail.com