Re: hashjoins vs. Bloom filters (yet again)

On 8/21/26 16:19, Matheus Alcantara wrote:
> On Wed Aug 12, 2026 at 4:18 PM -03, Tomas Vondra wrote:
>> I agree find_bloom_filter_recipient() returning NULL should be treated
>> as an error / Assert(false). If we have a path expecting a filter, and
>> yet we don't find a recipient, something clearly went wrong.
>>
>> I'm not aware of a query that'd cause such failures, but maybe just
>> adding the assert and running check-world would trigger some failure?
>>
>
> I did that experiment. I added Assert(recipient != NULL) in
> try_push_bloom_filter and ran make check plus a set of scale-10 parallel
> and partitioned queries and it didn't fired any assert error.
>
> But I think that a bare assert isn't safe on its own. IIUC
> try_partial_hashjoin_path may realizes filters even for a parallel-aware
> hash join, while find_bloom_filter_recipient returns early with a NULL
> on parallel_aware nodes. So if a parallel hash join with filter were
> ever chosen, try_push_bloom_filter would legitimately get a NULL
> recipient and the assert would fire on a valid query.

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.

> In practice those paths don't get chosen, but that's not enforced. So
> I added the missing !parallel_hash guard in
> try_partial_hashjoin_path, so a parallel-aware hash join no longer
> realizes a filter to pushdown (this was done on 0002).
>

OK, seems like an omission in my try_partial_hashjoin_path changes.

>> 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.)

>>> 3. Adaptive state and counters seems that don't seem to be reset across
>>> rescans. ExecReScanHashJoin clears the producer's bloom_filter pointer,
>>> but the
>>> consumer's BloomFilterState persists. After a rescan the producer
>>> rebuilds a
>>> fresh filter while the consumer may still be in "sampling"/disabled mode
>>> from
>>> the previous iteration, so it under-probes the new filter initially.
>>>
>>
>> Good point. I was assuming it makes sense to keep the adaptive state
>> across rescans, but I think you're probably right it should be reset.
>>
>
> Fixed. HashState now carries a generation counter bumped in
> ExecHashTableCreate whenever the filter is (re)built; the recipient
> resets its adaptive state when it sees a new generation. A rescan that
> reuses the hashtable doesn't rebuild the filter, so it doesn't bump the
> counter and the state is (correctly) kept.
>

OK

>>> Minor / cosmetic:
>>> - ExecBloomFilterHash returns 0 from a bool function (and its "XXX
>>> correct?"
>>> NULL-key pass-through I think that is in fact correct since a NULL key
>>> can't
>>> be in the filter, and letting it through is safe).
>>>
>>> - BloomFilterState->nkeys is unused.
>>>
>>> - A few typos in the commit message / comments: "futehr", "gest",
>>> "downn", "fproducer", "The effectivity of a filter is depends".
>>>
>>
>> Yeah, needs some cleanup.
>>
>
> Done, ExecBloomFilterHash returns false instead of 0, removed the unused
> BloomFilterState.nkeys, and fixed the code-comment typos. I also
> re-static'd get_foreign_key_join_selectivity. The FK commit exported it
> to call from find_interesting, but the later "rework generation" commit
> removed that caller, so the export was dead.
>

OK

>>> ----
>>>
>>> v9-0004-Make-sure-Gather-nodes-don-t-have-filters:
>>>
>>> 1. I'm wondering if we also should add the guard on
>>> generate_useful_gather_paths().
>>>
>>
>> Good idea.
>>
>
> Added the same expected_filters guard to generate_useful_gather_paths.
>

OK

>>> ---
>>>
>>> v9-0007-Properly-plan-filters-built-on-joins:
>>>
>>> Most of this commit changes e.g bloom_build_side_join_ratio and the
>>> selectivity estimation is reworked by later commits (the
>>> bloom_build_side_join_ratio rework and the FK-aware estimation), so I
>>> think that we may consider squashing these commits but I didn't look
>>> yet deeply to see if it's really makes sense. What do you think?
>>
>> Sure, feel free to squash. I only kept these commits separate to make
>> the changes more obvious / reviews easier.
>>
>>>
>>> [ ... ]
>>>
>>
>> Same answer to squashing - yes, it should be squashed, and I think
>> you're right 0002 is the proper target.
>>
>>> There's also an ordering/bisect hazard that makes this more than
>>> cosmetic: 0004
>>> adds Assert(cheapest_partial_path->expected_filters == NULL), whose
>>> precondition IIUC is exactly what this fix establishes.
>>>
>>
>> Not sure I follow. Are you saying the fix is not correct, or that
>> merging it into 0002 could trigger the assert in 0004?
>>
>
> 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.

>> Sure. Feel free to squash the patches as you see fit. We can always
>> reorganize it later, if needed.
>>
>
> I squashed 0010 into 0002 and 0011 into 0007. I looked at also folding
> the bloom_build_side_join_ratio rework / FK-estimation commits into
> 0007, but the estimation was reworked in a chain (FK commit -> ratio
> rework -> "rework generation of interesting filters") interleaved with
> the GUC and LATERAL commits, so a clean squash is a fairly
> conflict-heavy rebase for little gain, so I think that this is enough
> for now. Let's think about a better organization of these patches later.
>

+1

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

> - the dead find_bloom_filter_recipient arms (now asserted, with T_Limit
> returning NULL outright since pushing below a LIMIT would be wrong);
> - plus the small cleanups he noted.
>
> v10 attached.
>

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

regards

--
Tomas Vondra