Re: hashjoins vs. Bloom filters (yet again)

On 8/21/26 20:52, Matheus Alcantara wrote:
> 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.
>

I think this is a bit weird. I think the join of "f" to "d1" is expected
to discard ~50% of the tuples, right?

The way I imagine the join planning to work is that it builds different
join orders, including e.g. a left-deep:

HJ
/ \
D12 HJ
/ \
D11 HJ
/ \
D1 F

and the bushy plan (which is the plan you showed)

HJ
/ \
HJ F
/ \
D12 HJ
/ \
D11 D1

I was assuming the left deep would win (thanks to the filter), but now I
realize that may not be true, for two reasons.

First, pushing down a filter usually means the tuples get discarded
early, but the actual join gets postponed after other joins. But that
can't happen here - we can't join D1 last, because D11 and D12 are
joined "through" D1. Which likely eliminates a lot of the benefit.

Second, it may even make the join more expensive, because it increases
the number of probes. In the bushy plan (the second one), each of the
D11 and D12 hash tables gets probed once for each D1 row. But with the
left-deep plan, those hashes get probed once per F row. And F >> D1.

> 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?
>

I think you may very well be right, and we may need to rethink the
heuristic. We may need to prefer larger build sides, say by accepting
larger relids if it does not make the filter worse (instead of requiring
an improvement). Or something like that, not sure.

I'd consider the above plan to be a regression compared to v9.

regards

--
Tomas Vondra