Re: hashjoins vs. Bloom filters (yet again)

Hi,

Thanks for reworking the patches!

I reviewed v2.1 - the serial and parallel paths - and did differential
testing: 9 join shapes x {single-batch, batched} x {serial, parallel},
comparing result multisets with the filter forced on vs. off, including
the parallel shared-filter merge and a NULL-heavy anti-join. All tests
matched, with the bloom filter active. I didn't find any correctness
issue.

On Tue Oct 27, 2026 at 1:48 PM -03, Tomas Vondra wrote:
> filter sizing
> -------------
>
> The other "big" question is how to size the filter. There are two main
> challenges, I think.
>
> 1) in some cases the filter is not really faster than the hash table
>
> One thing I realized after looking at perf results is that even a very
> selective filter (discarding 90%+ rows) may not be any faster than
> checking the hash table. I believe this simply happens for hash tables
> with very few buckets, because then the buckets are pretty much the same
> as a Bloom filter.
>
> Let's say we have a hash table with 128K buckets - each bucket is a
> HashJoinTuple pointer, so this means 1MB of data (the whole hash table
> may be much larger, but that does not matter). We size the buckets for
> load factor 1.0 (NTUP_PER_BUCKET=1), so in most cases it's enough to
> check if the bucket is NULL to reject the tuple. The Bloom filter won't
> really save anything in this case, it may even be more expensive.
>
> I think the solution will be to consider the size of the buckets array,
> and not build the filter if the array is small. But what is small? It
> probably depends on some L2/L3 cache size, but we'll need to pick some
> sort of threshold. 1MB, maybe? We could also make it relative to the
> filter size - if the filter is more than 1/8 of the buckets, it may not
> help very much. Probably requires some microbenchmarks, to find what
> values might work. Maybe if we had a way to read the L2/L3 sizes from
> the system, that'd help us too.
>

I played with this idea and it seems that we need a small change: I've
added a new GUC, hashjoin_bloom_min_hashtable_size (in bytes), checked in
the single-batch adaptive build so we skip the filter when the bucket
array is below it:

@@ -1230,6 +1230,20 @@ ExecHashBloomAdaptiveBuild(HashJoinTable hashtable)
Assert(hashtable->bloomEnabled);
Assert(hashtable->bloomFilter == NULL);

+ /*
+ * The hash table of a single-batch join stays in memory, and if its bucket
+ * array is small enough to live in the CPU caches, a lookup is cheap enough
+ * that probing a Bloom filter first does not pay for itself - not even when
+ * the join is selective enough to reject most of the outer tuples. Skip the
+ * filter while the bucket array is below the configured size. Setting the
+ * size to 0 disables the check. (A batched join sizes and builds its filter
+ * up front and never reaches this path, so this does not affect it.)
+ */
+ if (hashjoin_bloom_min_hashtable_size > 0 &&
+ (Size) hashtable->nbuckets * sizeof(HashJoinTuple) <
+ (Size) hashjoin_bloom_min_hashtable_size)
+ return;
+

hashjoin_bloom_min_hashtable_size is the smallest bucket-array size
(nbuckets * sizeof(HashJoinTuple)) for which we bother building a
filter; below it the array is cache-resident enough that a lookup is as
cheap as a filter probe. It only touches the nbatch=1 path, as you noted
the batched case is different.

I kept the default at 0, i.e. the check is off and behavior is
unchanged, and I think that's the right default for now: the useful
threshold is machine-dependent (see below), so I'd rather not bake a
number in that's wrong elsewhere. The GUC lets us measure. A better
long-term answer is probably the one you suggested, detect the value
from the L2/L3 cache size at startup, so this wouldn't be a constant or
something people have to hand-tune.

The benchmark: fact of 3M rows joined to a dimension of N distinct keys,
fact keys spread over 10*N so ~90% of probes are rejected (your "very
selective filter" case), single batch, no parallelism.

inner bucket array plain hash join v2.1 today v2.1 + gate=8MB
100k 1 MB 572 ms 708 ms 562 ms
500k 4 MB 793 ms 877 ms 776 ms
1M 8 MB 1034 ms 1016 ms 1016 ms
2M 16 MB 1623 ms 1370 ms 1376 ms
4M 32 MB 2088 ms 2060 ms 2029 ms

(best-of-3 wall time, lower is faster)

So on my machine the filter is a loss up to a ~8MB bucket array (the L2
is 16MB here), even at 90% selectivity, and I think that it's not the
adaptive-disable that saves us, the disable logic keys on selectivity,
and here the filter is selective, it's just that rejecting a lookup that
was going to hit L2 isn't worth the probe. That's why I think this needs
an explicit size gate and not another probe-window heuristic. A gate of
8MB fixes the regressions and keeps the wins. EXPLAIN confirms it fires
exactly at the threshold, the filter disappears below 8MB and is built
at 8MB and above.

A 1MB threshold would be too low here, the filter is still a loss at a
4MB bucket array, so the gate needs to sit higher, nearer the cache
size. Since that's machine-dependent, it'd be really useful to have the
same sweep on your machine, if the crossover tracks L2/L3 there too,
we'd have enough to pick a sane default (or justify reading the cache
size from the system).

> 2) we don't really know the number of elements
>
> We can build the filter in two places. While building the hash table,
> and during probing. And in both cases we don't really know the number of
> filter elements, which affects the sizing.
>
> While building the hash table it's obvious - we only have an estimate of
> the row count, but it may be inaccurate. If we decide to build the
> filter half-way through the hash table build (when going from nbatch=1
> to nbatch=2), we at least know the number of tuples seen so far, but at
> this point we also know the estimate was wrong. The code size the filter
> for 2x the tuples, but that's wishful thinking.
>
> I wonder if we might do something smarter, like writing the hash values
> into a file, and then buildign the filter from that. Yes, it will cost
> something, but the hashvalues are tiny - much smaller than the tuples.
> We could probably also deduplicate them cheaply. So maybe it's worth a
> properly sized filter. Worth a try / experiment, I guess?
>
> Another detail is that sizing the filter for tuples is not quite right.
> We really care about number of distinct keys, and if the inner relation
> has duplicates, it may be a much smaller value. Maybe it'd be worth
> building a HLL counter, or something?
>
> we'd only need to do any of this in the nbatch>1 case, ofc. With a
> single batch we have all the values in the hashtable, which means we
> know the exect row count, and we could maybe calculate distincts too.
>

I also poked at the underestimate and the tuples-vs-distinct cases a
bit. They looked milder than I expected. A large underestimate still
ended up with a reasonably sized filter, and I couldn't easily get the
"sized for tuples, not distinct keys" waste to bite, because the planner
tends to put the low-ndistinct, duplicate-heavy relation on the probe
side rather than hashing it. So the hashvalue spill-file / HLL idea
still seems worth trying, but as an improvement, not a regression fix, I
think.

--
Matheus Alcantara
EDB: https://www.enterprisedb.com