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
#!/bin/bash
N=${N:-10}
psql -X -q <<'EOF'
set client_min_messages = warning;
create table if not exists t3m as select g as id, g % 1000 as a from
generate_series(1, 3000000) g;
create table if not exists t3m_wide as select g as id, g % 1000 as a, g % 997
as b, g * 2 as c, repeat(md5(g::text), 3) as pad from generate_series(1,
3000000) g;
create table if not exists t300k as select g as id, g % 1000 as a from
generate_series(1, 300000) g;
create table if not exists t60k as select g as id, g % 1000 as a from
generate_series(1, 60000) g;
create table if not exists t3m_dup as select -(g % 10) - 1 as id, g % 1000 as a
from generate_series(1, 3000000) g;
create table if not exists t4m_outer as select g as id, g % 1000 as b, case
when g % 4000 = 0 then -1 else g % 1000 end as c from generate_series(1,
4000000) g;
create or replace function f() returns setof int rows 100000000 language sql as
'select g * 3 from generate_series(1, 1000) g';
vacuum analyze t3m, t3m_wide, t300k, t60k, t3m_dup, t4m_outer;
EOF
# run <name> <query> [parallel workers]
run() {
{
echo "set jit = off; set max_parallel_workers_per_gather = ${3:-0};"
echo "set parallel_setup_cost = 0; set parallel_tuple_cost = 0;"
echo "set enable_mergejoin = off; set enable_nestloop = off; set
work_mem = '1GB';"
echo "$2;"
echo '\timing on'
for i in $(seq $N); do echo "$2;"; done
} | psql -X -q | awk '/^Time:/ {print $2}' |
sort -n | awk -v name="$1" '{a[NR] = $1} END {printf "%-14s %8.1f
ms\n", name, a[int((NR + 1) / 2)]}'
}
run build_3m "select sum(i.a) from f() o(id) join t3m i on o.id = i.id"
run build_wide "select sum(i.a + i.b + i.c + length(i.pad)) from f() o(id) join
t3m_wide i on o.id = i.id"
run build_300k "select sum(i.a) from f() o(id) join t300k i on o.id = i.id"
run rebuild "select sum(i.a) from f() o(id) join (select * from t3m i where
(i.id % 1) = 0) i on o.id = i.id"
run build_60k "select sum(i.a) from f() o(id) join t60k i on o.id = i.id"
run dup_keys "select sum(i.a) from f() o(id) join t3m_dup i on o.id = i.id"
run parallel "select sum(i.a) from t4m_outer o join t3m i on o.id = i.id
where o.b <> o.c" 2
v1-0001-Link-tuples-into-large-private-hash-join-tables-i.patch
Description: Binary data
v1-0002-Link-tuples-into-large-Parallel-Hash-tables-in-gr.patch
Description: Binary data
