Re: hashjoins vs. Bloom filters (yet again)

On Fri Aug 21, 2026 at 12:20 PM -03, Tomas Vondra wrote:
> I don't see how we could get into such situation, really.
>
> If we get to calling find_bloom_filter_recipient() when building a hash
> join, it means we constructed the hashjoin path with a filter on the
> hash, and an outer input that expects the filter. And at this point we
> can't change our mind - *have* to find a recipient, otherwise it'd
> invalidate the estimates calculated expecting the filter.
>
> I'm not claiming it can't happen with the current code, but that if it
> happens it's a bug. Those are not "legitimate" (correct) plans.
>

Yeah, make sense, I agree with this. I think that I overthink here.

>>> 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.
>>>
>>
>> Done, compute_join_expected_filters now requires
>> bms_equal(f->build_relids, other_relids) instead of bms_is_subset and it
>> resolves the divergence.
>>
>> But I've notice one trade-off: in a snowflake, when a dimension is
>> pre-joined with its sub-dimensions before it joins the fact, the hash
>> join's build side is {d1,d11,d12}, not {d1}. Under subset the {d1}
>> candidate (keys=(id1)) was realized there opportunistically (with a
>> selectivity computed over {d1} alone, exactly the divergence we're
>> fixing). Under exact match {d1} no longer matches, so the fact loses
>> that filter. The correctly-scoped {d1,d11,d12} candidate (still
>> keys=(id1), but selectivity over the whole build side) is in fact
>> generated, but the dedup in find_interesting_bloom_filters drops it: it
>> keeps a larger build side only if it's strictly more selective than a
>> smaller one it contains, and with d11/d12 unrestricted the two are
>> equally selective. The prefer the smaller build side rule on
>> find_interesting_bloom_filters is correct under subset (a small build
>> side matches any superset inner) but is exactly wrong under exact match
>> (the small build side may never be realizable). So exact match fixes the
>> estimate but drops fact-table filtering in snowflakes. The star case is
>> unaffected. I updated hashjoin_bloom_snowflake.out accordingly but I
>> think that keeping the fact filter with a correct estimate would mean
>> reworking that dedup to keep equally-selective supersets. What do you
>> think?
>>
>
> Hmmm, but isn't that actually correct / desirable (depending on where we
> put the WHERE restriction)? Which of the snowflake queries are you
> referring to?
>
> If we have
>
> ... WHERE d1.r < 0.5;
>
> then it seems correct to build the filter just on {d1}, join with it,
> and then maybe join with d11/d12 later. While with
>
> ... WHERE d11.r < 0.5;
>
> we'd build the filter on {d1,d11}, join with that, and then joining with
> d12 sometime later.
>
> Or have you observed a query where this causes a regression? (It's never
> gonna be perfect, it's a heuristic. But would be interesting feedback.)
>

I didn't observed any regression although I didn't execute any
performance tests with v10 but what I measured is the filter usage drop:
v10 pushes 6 fewer filter instances than v9 across the snowflake test.

The query that I was mentioning is the WHERE d1.r < 0.5 in
hashjoin_bloom_snowflake. To try to explain better I'll put my reasoning
of this problem into two passes:

Pass 1, candidate generation (per relation that could receive a filter
on find_interesting_bloom_filters(), here the fact f). We enumerate the
build sides that could filter the fact. Only d1 restricts it (f.id1 =
d1.id, and d1 has r < 0.5), so the candidates are {d1}, {d1,d11},
{d1,d11,d12}, all keyed on id1, and all equally selective, since d11/d12
don't restrict anything. The de-dup logic then collapses
equally-selective candidates to the smallest build side. So the fact's
candidate list ends up as just [{d1}]; {d1,d11,d12} is dropped here.

Pass 2, realization (compute_join_expected_filters()). We try to attach
each surviving candidate to an actual hash join, and in v10 that match
is exact, the candidate's build_relids must equal the join's inner
(build) side.

In this plan the fact's only hash join has inner = {d1,d11,d12}, because
the planner fully pre-joins the d1 subtree before touching the fact:

Hash Join
Hash Cond: (f.id2 = d2.id)
-> Hash Join
Hash Cond: (f.id1 = d1.id)
-> Seq Scan on bloom_snowflake_fact f <- no filter
-> Hash
-> Hash Join
Hash Cond: (d12.id = d1.id12)
-> Seq Scan on bloom_snowflake_dim_1_2 d12
-> Hash
-> Hash Join
Hash Cond: (d11.id = d1.id11)
-> Seq Scan on bloom_snowflake_dim_1_1 d11
Bloom Filter 1: keys=(id)
-> Hash
Bloom Filter 1
-> Seq Scan on bloom_snowflake_dim_1 d1
Filter: (r < '0.5'::double precision)

So at realization pass the one candidate we kept, {d1}, matches no inner
({d1} != {d1,d11,d12}), and the candidate that would have matched,
{d1,d11,d12}, was already discarded by the de-dup in pass 1.

v9 filtered the fact because its realization used subset matching: {d1}
is a subset from {d1,d11,d12}, so {d1} attached to the pre-joined inner.
Exact matching (the item-2 change) closes the over-crediting that subset
matching allowed, but it also removes that escape hatch, and the de-dup,
which picks the smallest equally-selective build side without knowing
which build sides will actually show up as join inners, happens to
discard the only realizable candidate.

That all being said, based on your reply I'm not sure if this is a real
issue or just an expected behavior based on v10 changes. I'm missing
something here?

>> The fix is correct, and squashing it into 0002 doesn't trigger 0004's
>> assert, it prevents it. I only meant the current ordering: 0004 adds
>> Assert(cheapest_partial_path->expected_filters == NULL), but the thing
>> that guarantees that precondition (add_partial_path keeping a
>> filter-free path first) doesn't land until the fix, which currently sits
>> several commits after 0004. So at every commit in that window the assert
>> exists without its precondition and could trip on a filter-bearing
>> partial path. Squashing the fix into 0002 closes that window. That's the
>> only reason it's more than cosmetic.
>>
>
> Ah, OK. Let's keep the asserts, though. It's a useful safety measure as
> we'll be modifying the code in various ways.
>

Ok.

>> Separately, I also folded Rui Zhao's review comments into v10, so this
>> series covers both:
>>
>> - his fix to charge the Bloom-filter probe cost on the rows actually
>> probed (it was charged on the post-qual output, so a selective scan
>> qual made the filter look almost free); his patch, folded into 0020;
>
> OK
>> - 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.

>> v10 attached.
>>
>
> Great. I'll take a closer look on v10 early next week.
>

Great, thank you!

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