WIP: bloom filter in Hash Joins with batches

Hi,

while working on the Hash Join improvements, I've been repeatedly
running into the idea of bloom filter - various papers on hash joins
mention bloom filters as a way to optimize access to the hash table by
doing fewer lookups, etc.

Sadly, I've been unable to actually see any real benefit of using a
bloom filter, which I believe is mostly due to NTUP_PER_BUCKET=1, which
makes the lookups much more efficient (so the room for bloom filter
improvements is narrow).

The one case where bloom filter might still help, and that's when the
bloom filter fits into L3 cache (a few MBs) while the hash table (or
more accurately the buckets) do not. Then there's a chance that the
bloom filter (which needs to do multiple lookups) might help.

But I think there's another case where bloom filter might be way more
useful in Hash Join - when we do batching. What we do currently is that
we simply

     1) build the batches for the hash table (inner relation)

     2) read the outer relation (usually the larger one), and split it
        into batches just like the hash table

     3) while doing (2) we join the first batch, and write the remaining
        batches to disk (temporary files)

     4) we read the batches one by one (for both tables) and do the join

Now, imagine that only some of the rows in the outer table actually
match a row in the hash table. Currently, we do write those rows into
the temporary file, but with a bloom filter on the whole hash table (all
the batches at once) we can skip that for some types of joins.

For inner join we can immediately discard the outer row, for left join
we can immediately output the row. In both cases we can completely
eliminate the overhead with writing the tuple to the temporary file and
then reading it again.

The attached patch is a PoC of this approach - I'm pretty sure it's not
perfectly correct (e.g. I only tried it with inner join), but it's good
enough for demonstrating the benefits. It's rather incomplete (see the
end of this e-mail), and I'm mostly soliciting some early feedback at
this point.

The numbers presented here are for a test case like this:

     CREATE TABLE dim (id INT, dval TEXT);
     CREATE TABLE fact (id INT, fval TEXT);

     INSERT INTO dim SELECT i, md5(i::text)
                       FROM generate_series(1,10000000) s(i);

     -- repeat 10x
     INSERT INTO fact SELECT * FROM dim;

and a query like this

     SELECT COUNT(fval) FROM fact JOIN dim USING (id) WHERE dval < 'a';

with different values in the WHERE condition to select a fraction of the
inner 'dim' table - this directly affects what portion of the 'fact'
table has a matching row, and also the size of the hash table (and
number of batches).

Now, some numbers from a machine with 8GB of RAM (the 'fact' table has
~6.5GB of data, so there's actually quite a bit of memory pressure,
forcing the temp files to disk etc.).

With work_mem=16MB, it looks like this:

     batches   filter   select.    bloom  master    bloom/master
     -----------------------------------------------------------
       4        1     6.25%    23871   48631         49.09%
       8        2    12.50%    25752   56692         45.42%
       8        3    18.75%    31273   57455         54.43%
      16        4    25.01%    37430   62325         60.06%
      16        5    31.25%    39005   61143         63.79%
      16        6    37.50%    46157   63533         72.65%
      16        7    43.75%    53500   65483         81.70%
      32        8    49.99%    53952   65730         82.08%
      32        9    56.23%    55187   67521         81.73%
      32        a    62.49%    64454   69448         92.81%
      32        b    68.73%    66937   71692         93.37%
      32        c    74.97%    73323   72060        101.75%
      32        d    81.23%    76703   73513        104.34%
      32        e    87.48%    81970   74890        109.45%
      32        f    93.74%    86102   76257        112.91%

The 'batches' means how many batches were used for the join, 'filter' is
the value used in the WHERE condition, selectivity is the fraction of
the 'dim' table that matches the condition (and also the 'fact'). Bloom
and master are timings of the query in miliseconds, and bloom/master is
comparison of the runtimes - so for example 49% means the hash join with
bloom filter was running ~2x as fast.

Admittedly, work_mem=16MB is quite low, but that's just a way to force
batching. What really matters is the number of batches and selectivity
(how many tuples we can eliminate using the bloom filter).

For work_mem=64MB it looks like this:

     batches   filter   select.    bloom  master    bloom/master
     -----------------------------------------------------------
           1       1     6.25%     24846   23854        104.16%
           2       2    12.50%     24369   45672         53.36%
           2       3    18.75%     30432   47454         64.13%
           4       4    25.01%     36175   59741         60.55%
           4       5    31.25%     43103   62631         68.82%
           4       6    37.50%     48179   64079         75.19%

So initially it's a bit slower (it's not doing any batching in this
case, but the code is a bit silly and while not building the bloom
filter it still does some checks). But once we start batching, it gets
2x as fast again, and then slowly degrades as the selectivity increases.

Attached is a spreadsheet with results for various work_mem values, and
also with a smaller data set (just 30M rows in the fact table), which
easily fits into memory. Yet it shows similar gains, shaving off ~40% in
the best case, suggesting that this is not just thanks to reduction of
I/O when forcing the temp files to disk.

As I mentioned, the patch is incomplete in several ways:

   1) It does not count the bloom filter (which may be quite big) into
      work_mem properly.

   2) It probably does not work for outer joins at this point.

   3) Currently the bloom filter is used whenever we do batching, but it
      should really be driven by selectivity too - it'd be good to (a)
      estimate the fraction of 'fact' tuples having a match in the hash
      table, and not to do bloom if it's over ~60% or so. Also, maybe
      the could should count the matches at runtime, and disable the
      bloom filter if we reach some threshold.

But overall, this seems like a nice optimization opportunity for hash
joins on large data sets, where batching is necessary.

Ideas?

--
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services