Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem

Hi,

Thank you for the report, and I am able to reproduce it.

The loop added by a1b4f289bee is fine when the estimate holds. Buckets are
about a seventh of the budget and every batch is full, so clearing them is
noise. The trouble is that the array is sized from work_mem while the number
of non empty batches saturates at the real row count, so the waste scales
with work_mem times real rows, not with the data. Your query estimates 6.5
billion inner rows and gets 768. At 256MB that is 69GB of memset, where a
profile spends 84 percent of its time, up from 8 percent at 64kB.

ANALYZE does fix your case, worth saying. But the mechanism does not need
stale statistics. Join selectivity multiplies, so a
moderate error on one relation becomes a large one after a few joins. Your
unanalyzed table is off by 2910x and the self join squares that to 8.5
million. A thousandfold overestimate is already enough to show this, which
is ordinary for a join of several tables with correlated columns.

Before a1b4f289bee the time does not move with work_mem at all. I measured
153 ms at every setting from 64kB to 16MB.

Median of 6 runs on master, and with the attached patch:
Attached flame.zip shows the flame graph of these experiments.

work_mem master patched Buckets Batches
64kB 45 ms 262144 256
64MB 327 ms 64 ms 4194304 4096
128MB 461 ms 59 ms 8388608 2048
256MB 709 ms 54 ms 16777216 1024

The patch redoes the sizing decision once the inner side has been read,
using
the real row count. If it now fits in one batch it rebuilds the table that
way and reads the spilled tuples back. Changing nbuckets is safe there
because a single batch no longer takes the batch number from the bits above
log2_nbuckets.

It only shrink to one batch. Shrinking to fewer batches also works, since
the batch
number is the same rotated value under a narrower mask, so old batch i
merges
into new batch i & (new - 1) and nothing is rehashed. But nbuckets is
frozen then,
because moving it changes every batch number, so that path only speed up
and
not reduce any memory footprint.

Thanks,
Shihao