Re: hashjoins vs. Bloom filters (yet again)

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

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

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

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

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

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

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

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

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