Re: hashjoins vs. Bloom filters (yet again)

On 8/12/26 22:18, Tomas Vondra wrote:
> Agreed. I was wondering about such cases too. I think the question is:
>
> Is it correct to match the filter for a "larger" build relids, or
> do the relids have to match exactly?
>
> I think we have to require an exact match, for to keep the estimates
> correct. AFAIK this would resolve the example you described, and also
> cases where the selectivity is reduced by the extra joins.
Hi,

I took another look at the Bloom filter selectivity estimate in v9, in
particular in light of the discussion above about requiring an exact
match between f->build_relids and the realized build side.

Requiring an exact match should ensure that the estimate and the
physical filter refer to the same build relation set. However, I think
there is a separate issue with how the selectivity for that relation set
is estimated: using ordinary join cardinality divided by the owner
cardinality can become too pessimistic in the presence of join fanout.

The paper discussed in this thread already models Bloom filtering as an
approximate semi-join [1]. My concern is that the
ordinary-join-cardinality approximation used in v9 can diverge
substantially from that semantics in the presence of fanout.

As I understand the current code, bloom_build_side_join_ratio()
estimates the surviving fraction roughly as

rows({owner} JOIN build_relids) / rows(owner),
clamped to [0, 1].

The problem is that an ordinary join counts every matching pair, while a
Bloom filter only cares whether at least one matching build key exists.
Ignoring false positives, the quantity we need therefore seems to be the
semi-join selectivity

s = |owner SEMI JOIN build| / |owner|
or equivalently
s = P(a probe tuple has at least one matching build key).

For example, suppose the probe side has 200000 rows and 10000 distinct
keys, with every key occurring 20 times. The build side contains only
2000 of those keys, with every build key occurring 10 times.
Only 20% of probe tuples have a matching build key, so s = 0.20.
However, the ordinary join produces 2000 * 20 * 10 = 400000 rows, and
the current ratio becomes 400000 / 200000 = 2, which is clamped to 1.0.

So the estimate says that essentially all probe tuples survive, while an
ideal Bloom filter with no false positives would reject about 80%.
Increasing the number of duplicate build rows increases the ordinary
join cardinality further, but does not change the set of keys
represented by the Bloom filter.

This suggests that ExpectedFilter.selectivity should be based on
semi-join survival rather than inner-join cardinality.

The second component is the Bloom false-positive probability.

Let m be the number of bits in the Bloom filter, k the number of Bloom
hash probes, and n the number of distinct build keys inserted into the
filter.

Under the usual uniform-hashing approximation, a single bit-setting
operation misses a particular bit with probability
1 - 1/m.

After k * n such operations, the probability that this bit is still zero is

(1 - 1/m)^(k*n),

which for sufficiently large m is approximately

exp(-k*n/m).

The probability that the bit is set is therefore approximately

1 - exp(-k*n/m),

and the usual Bloom false-positive estimate is

p ~= (1 - exp(-k*n/m))^k.

Now let s be the semi-join survival probability.

A fraction s of probe tuples has a real build-side match and therefore
always passes the Bloom filter. The remaining fraction 1 - s has no real
match, but a fraction p of those tuples still passes because of false
positives.

The expected Bloom survival is therefore
bloom_sel = s + (1 - s) * p,
and the expected rejected fraction is
r = 1 - bloom_sel = (1 - s) * (1 - p).
For example, if s = 0.20 and p = 0.10,
bloom_sel = 0.20 + 0.80 * 0.10 = 0.28,
and
r = 0.80 * 0.90 = 0.72.

So about 72% of probe tuples are expected to be rejected.

PostgreSQL's JOIN_SEMI selectivity machinery seems to model the quantity
needed for the first component. I experimented with constructing a dummy
SpecialJoinInfo using JOIN_SEMI for the hash clauses, applying
get_foreign_key_join_selectivity() to FK clauses and
clauselist_selectivity(..., JOIN_SEMI, ...) to the remaining clauses.

The harder case is a joined build side, for example
owner SEMI JOIN (R1 JOIN R2).

In this case we need to estimate which build keys survive the complete
build subtree. For example, if R1 initially contains keys {1, 2, 3, 4,
5}, but R1 JOIN R2 leaves only rows with keys {1, 2}, then the Bloom
filter built by the upper Hash Join represents only {1, 2}.

So the desired quantity is
s = P(an owner key matches at least one key produced by the complete
build subtree).

That is, the relevant estimate is owner SEMI JOIN (R1 JOIN R2), not
owner SEMI JOIN R1.

This is also how the paper describes the problem: different build-side
relation sets correspond to different Bloom-filter cardinality
estimates, because joins on the build side may remove distinct build
keys before the Bloom filter is constructed.

The false-positive estimate has a related dependency. Ideally, n should
be the number of distinct values (NDV) of the build hash key after the
complete build subtree has been evaluated, because repeated occurrences
of the same key do not add new information to the Bloom filter.

If the Bloom layout is fixed, using the build row count as an upper
bound for the number of distinct inserted keys overestimates filter
occupancy whenever duplicates are present. With an adaptive sizing
policy the effect also depends on how m and k are chosen, so estimating
the surviving build-key NDV would still be preferable.

v9 already keeps the required build relation set in ExpectedFilter, so
this seems compatible with the existing architecture. The main question
is how to obtain the semi-join estimate for the complete joined build
side without duplicating more of the normal join-planning machinery.

So I wanted to ask two questions.

Does it make sense for ExpectedFilter.selectivity to represent the
expected Bloom survival s + (1 - s) * p, with s based on semi-join
selectivity rather than ordinary join cardinality?

And for joined build sides, would it make sense to estimate the
semi-join against the complete build relation set and use the surviving
build-key NDV for the Bloom false-positive estimate, or would there be a
better way to reuse the normal joinrel/selectivity machinery?

References:

[1] Tim Zeyl, Qi Cheng, Reza Pournaghi, Jason Lam, Weicheng Wang, Calvin
Wong, Chong Chen, and Per-Ake Larson. "Including Bloom Filters in
Bottom-up Optimization." SIGMOD Companion 2025.
https://doi.org/10.1145/3722212.3724440

Best regards,
Denis Rodionov
Tantor Labs LLC
https://tantorlabs.com/