Re: hashjoins vs. Bloom filters (yet again)

On 8/21/26 21:52, Matheus Alcantara wrote:
> On Fri Aug 21, 2026 at 12:20 PM -03, Tomas Vondra wrote:
>>> - the bloom_filter_pushdown_max_build_relids off-by-one: =1 was
>>> disabling pushdown entirely, because the {owner}+build_relids lookup
>>> needs the enumeration to reach one level higher than the build side;
>>
>> Yeah, I forgot about this consequence of changing the filter selectivity
>> calculation. I'm not entirely sure that approach is quite correct (based
>> on Denis Rodionov's review), but we can improve it later.
>>
>
> Yeah, not sure either. I'm still studying the Denis Rodionov's review to
> think more about this.

Attached is a proof-of-concept patch (on top of v9-0001..v9-0021) that
implements the semijoin + false-positive model from my review, to make
the discussion concrete. It's not meant as a finished patch; it's more
of "here's what the formula looks like as code, and here's what testing
it turned up".

Summary of the change
======================
bloom_build_side_join_ratio() now estimates

bloom_sel = s + (1 - s) * p

where s is the JOIN_SEMI selectivity of the clauses linking the owner to
build_relids (FK-aware, via get_foreign_key_join_selectivity(), the same
way ordinary join size estimation already is), and p is the Bloom
filter's false-positive probability, sized with exactly the same
bitset/hash-count policy the executor uses to build the real runtime
filter (bloom_create_probe() / bloom_probe_work_mem(), factored out into
lib/bloomfilter.c so planner and executor can't drift apart).

n for the false-positive estimate is approximated by the build side's
own row count (an upper bound on distinct build keys, the same
simplification Zeyl et al. use in the SIGMOD-Companion'25 paper). A
tighter NDV estimate for a joined build side is future work.

Two things turned up while testing this that seem worth discussing on
their own, separately from the formula
========================================================================
1. enumerate_bloom_filter_build_relids() enumerates build-side relid
combinations purely combinatorially, with no check that the
combination could ever be a legal join given the query's outer/
anti-join ordering constraints. The old ratio-based selectivity never
noticed this (it never touches real join infrastructure), but a real
JOIN_SEMI clause-selectivity estimate does, and crashes:

ERROR: could not find RelOptInfo for given relids

I added bloom_relids_are_joinable() (mirrors the ordering check
join_is_legal() applies to a real join attempt) to filter these out
before they reach selectivity estimation.

2. Separately (and this one surprised me more), even a build_relids
combination that's a perfectly ordinary, legal join can't be fed to
clauselist_selectivity() with JOIN_SEMI at this point in planning:
eqjoinsel()'s semi/anti-join handling calls find_join_input_rel() on
the RHS relids to check uniqueness, and for anything spanning more
than one relation that requires an already-built joinrel. No such
joinrel exists yet when find_interesting_bloom_filters() runs: scan-
path generation happens before the bottom-up join search builds any
joinrels at all. So *any* multi-relation build_relids hits this,
regardless of (1).

The workaround, for multi-relation build sides only, is the product
of the per-relation semijoin selectivities instead of one estimate
against the combined set (each per-relation term is safe on its own,
since a single relid always has a real base-rel RelOptInfo). Here's
why that's not just a less accurate version of the real estimate:
in some cases it's blind to a restriction entirely, not just less
precise about it. Take a plain chain: t1 joins t2, t2 joins
t3, and a restrictive filter sits on t3, with no direct t1/t3 clause
anywhere. A Bloom filter candidate on t1 built from {t2,t3} gets
estimated as

estimate({t2,t3}) = estimate({t2}) * estimate({t3})

estimate({t3}) is supposed to be the semijoin selectivity of the
clauses linking t1 directly to t3. There are none, so
clauselist_selectivity() on an empty clause list returns 1.0 (no
restriction), and the product collapses to estimate({t2}) alone, no
matter how selective t3's filter is. The t3 restriction isn't
underweighted, it's invisible to this formula.

Minimal repro (t3.x < 10 selects about 0.01% of rows):

set bloom_filter_pushdown_max_build_relids = 4;
set bloom_filter_pushdown_threshold = 0.1;
explain (costs off)
select * from t1 join t2 on t1.a = t2.a
join t3 on t2.b = t3.b
where t3.x < 10;

never proposes a filter on t1 built from {t2,t3}, however selective
t3.x is. (Also checked, by hand, that this doesn't interact with
join_collapse_limit: root->simple_rel_array has RelOptInfos for every
base relation up front regardless of how collapse-limit restructures
the join order search. Same plan with join_collapse_limit=1 and the
default, using the same t1/t2/t3 setup above with join_collapse_limit
set before the EXPLAIN.)

Same effect shows up in the hashjoin_bloom_snowflake regression test
(included in the patch, in the updated expected output). Before, with
a fact table joined through one dimension to a filtered second
dimension:

Seq Scan on bloom_snowflake_multi_fact f (rows=24628) (actual
rows=23531)
Bloom Filter: keys=(id1a, id1b) expected=24.6% ...
rejected=76469 (76.5%)

after (build side now spans two relations, filter no longer proposed
at all):

Seq Scan on bloom_snowflake_multi_fact f (rows=100000) (actual
rows=100000)

I don't have a fix for this beyond "decompose into single relations":
a real fix would need either a way to estimate JOIN_SEMI
selectivity/uniqueness without an existing joinrel, or restructuring
so this estimate happens after the relevant joinrel exists. Flagging
it rather than attempting it here, since it's exactly the predicate-
transfer mechanism the snowflake/star cases in the original paper are
built around, so it seemed worth a wider opinion before I guess at a
fix.

On the positive side, the more accurate estimate does the right thing at
least once: stats_ext.out's ndistinct-extended-statistics test now
correctly stops proposing a Bloom filter for a join where the extended
stats show it's nearly a 1:1 match (a filter wouldn't reject enough to
be worth it); previously it proposed one anyway.

Testing
=======
Applied on top of v9-0001..v9-0021, built with meson (-Dcassert=true),
ran the full regress suite (meson test --suite regress --suite setup)
plus hashjoin_bloom/hashjoin_bloom_star/hashjoin_bloom_snowflake. 13
tests initially diverged from expected output; all traced back to either
(a) a Bloom filter now being pushed down where the old formula never
proposed one (plan-only diff), or (b) row reordering in output with no
ORDER BY (never a change in which rows were returned; checked several of
these row-for-row by hand). Expected files updated accordingly; full
suite is green (248/248) with the patch applied.

I haven't run performance benchmarks or written new targeted tests (e.g.
the semijoin-vs-fanout numeric example from my first message in this
thread, or something exercising the snowflake predicate-transfer loss
more thoroughly than the regression test does); happy to put those
together if it would help move the discussion along, it's a
straightforward follow-up on top of what's already here.

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