Number of buckets in a hash join

While testing Alexander's gistchoose patch, "perf report" showed that
the test case spent a surprisingly large amount of CPU time in
ExecScanHashBucket. That function just scans a hash bucket for matches,
and it should be very quick as long as there are not many collisions.

It turns out that the planner estimated the number of rows in the hash
to be much smaller than it actually contained, and the hash table was
initialized with too few buckets as a result. The target is that each
bucket contains 10 tuples (NTUP_PER_BUCKET), but in this case, the
average was about 100.

The first question is, why do we aim at 10 tuples per bucket? My gut
feeling is that that's way too high. I would expect the target to be 1
tuple per bucket, or maybe a little more, like 2-3. Each bucket consumes
one pointer's worth of RAM, which is not much. There's also some
overhead from empty buckets when scanning the hash table, but as long as
all the buckets have at least one entry, there's no gain from having
more than one entry per bucket.

However, lowering NTUP_PER_BUCKET would not have helped in this case,
because we also have a minimum of 1024 buckets. The estimate was so bad
that even after setting NTUP_PER_BUCKET to 1, it was still pegged at
that minimum of 1024 buckets.

Ideally, the planner would always make a good guess the number of rows,
but for the situations that it doesn't, it would be good if the hash
table was enlarged if it becomes too full. It's a well-known technique
to double the size of a hash table once the load factor reaches a
certain threshold, and rehash the existing entries. Another idea is to
just collect all the entries in e.g a linked list when tuples are
inserted to the hash table, and create the buckets lazily, after all the
tuples have been inserted.

Here's an extreme example of this phenomenon. According to perf, about
95% of the CPU time is spent in ExecScanHashBucket. That would be
eliminated by sizing the hash table correctly:

create table numbers (id int4);
insert into numbers select g from generate_series(1, 10000000) g;

explain analyze select * from numbers a, generate_series(1, 100000) b
where b = a.id;
QUERY
PLAN

---------------------------------------------------------------------------------
------------------------------------------------------
Hash Join (cost=22.50..2035430.50 rows=53097600 width=8) (actual
time=32.307..2
9141.348 rows=100000 loops=1)
Hash Cond: (a.id = b.b)
-> Seq Scan on numbers a (cost=0.00..150443.20 rows=10619520
width=4) (actua
l time=0.017..716.503 rows=10000000 loops=1)
-> Hash (cost=10.00..10.00 rows=1000 width=4) (actual
time=32.268..32.268 ro
ws=100000 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 3516kB
-> Function Scan on generate_series b (cost=0.00..10.00
rows=1000 widt
h=4) (actual time=17.966..22.519 rows=100000 loops=1)
Total runtime: 29146.011 ms
(7 rows)

- Heikki