Re: hashjoins vs. Bloom filters (yet again)

On 8/12/26 16:49, Matheus Alcantara wrote:
> On 31/07/26 09:52, Tomas Vondra wrote:
>> Understood, makes sense. Let's take some time to review each others
>> patches, and then we can agree which open questions to work on next.
>>
>
> v9-0001-PoC-hashjoin-bloom-filter-pushdown:
>
> 1. In create_hashjoin_plan, try_push_bloom_filter calls
> find_bloom_filter_recipient() to locate the scan in the outer subtree,
> and if
> it returns NULL it just return without building anything, even though
> the path
> row estimate was already reduced by the filter selectivity during
> costing, so
> if the recipient isn't reachable we've choose a plan because of a filter
> benefit that then never materializes.
>
> find_bloom_filter_recipient() does return NULL for parallel-aware
> recipients
> but I'm wondering if it can also return NULL for non parallel cases, even
> though I couldn't construct a serial plan that reaches a NULL recipient.
> Not
> sure if we need a guard for such case (e.g assert).
>

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?

> 2. I think that the filter selectivity can diverge from the filter that's
> actually built. IIUC the row-estimate reduction for a realized filter comes
> from f->selectivity, computed in find_interesting_bloom_filters from only
> f->clauses. But try_push_bloom_filter builds the physical filter from
> all of
> hj->hashkeys. When the inner side carries more keys/relations than
> f->build_relids, the filter that runs and the selectivity that was
> costed are
> computed from different key sets. Results stay correct, but the
> cardinality/cost on the path, and the expected= value in EXPLAIN, won't
> match
> what the filter actually does.
>
> Consider f JOIN d1 ON f.k1=d1.k1 JOIN d2 ON f.k2=d2.k2 AND d1.a=d2.a
> where only
> d1 is a selective filter source. If the planner forms d1 JOIN d2 as the
> hash-join inner and realizes the single-relation candidate f={d1} (whose
> selectivity was estimated from f.k1=d1.k1 alone, since
> compute_join_expected_filters realizes on bms_is_subset(f->build_relids,
> other_relids)), try_push_bloom_filter still copies all of hj->hashkeys,
> so the
> physical filter is keys=(f.k1, f.k2). The row estimate was credited for a
> one-key filter while a two-key filter runs.
>

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.

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

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

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

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

> ---
>
> v9-0010-Fix-handling-of-filters-in-add_partial_path:
>
> This is a bug fix (add_partial_path sorting), and I think it should be
> squashed
> rather than kept as a standalone commit. The fix itself seems correct to
> me: it
> gates cost-domination on expected_filters_equal so paths with different
> filter
> sets don't prune each other, and it orders the list by filter-count
> first so
> linitial(partial_pathlist) is always filter-free.
>
> I think that it should be squashed into 0002, which is the commit that
> first
> puts filters on partial paths and therefore creates the requirement that
> add_partial_path keep a filter-free path at the front.
>

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?

> ---
>
> v9-0011-Fix-filters-on-joins-in-compute_join_expected_fil:
>
> Also a bug fix (compute_join_expected_filters), and also a squash
> candidate.
> The fix also seems correct to me.
>
> I think that it should be squashed into 0007. The defect only exists
> once joins
> can be build sides. The commit message itself notes the code "worked
> fine for
> singleton build relids." Singleton build sides come from 0001; multi-
> relation
> build sides come from 0007, so it seems to me that 0007 is the commit that
> makes the defect reachable and should arrive correct.
>

Agreed.

> ---
>
> This is what I have for now, I plan to review the remaining patches
> soon. I can
> also work on this comments that I've made and propose a v10 if you agree
> with
> them.
>

Sure. Feel free to squash the patches as you see fit. We can always
reorganize it later, if needed.

I'm mostly afk until the end of next week, so I won't interfere with
your review etc.

regards

--
Tomas Vondra