Re: hashjoins vs. Bloom filters (yet again)

On 10/5/26 14:04, Andrei Lepikhov wrote:
> On 29/09/2026 19:57, Tomas Vondra wrote:
>> On 9/2/26 20:12, Andrei Lepikhov wrote:
>>> 1. Estimating the number of unmatched rows. This is the key input to the
>>> filter's cost model, and I don't see a way to implement it. We do have
>>> eqjoinsel_semi(), but it compares MCV lists and then assumes uniformity over
>>> n_distinct for everything else — and the unmatched rows live mostly in that
>>> tail. So it is not that the estimate is imprecise; for the part of the
>>> population that decides the answer, there is no distribution model at all, only
>>> a count of distinct values. Histogram-based join estimation, of the kind GPORCA
>>> does by aligning buckets, does not exist here. That is one more piece of basic
>>> technology we would need first.
>>> Systems that ship this feature don't really solve it either — they work around
>>> it. The CIDR 2026 paper [1] on bitmap filters in SQL Server describes an
>>> optimiser that decides on the filter from ordinary join selectivity, then defers
>>> the bitmap's shape and memory budget to run time. That is adaptation, not
>>> estimation.
>>>
>>
>> Well, maybe we need some more infrastructure, to allow calculating
>> sufficiently good filter estimates. But it's not clear to me why we
>> couldn't rely on the existing JOIN_SEMI estimates, as suggested by Denis
>> Rodionov. I didn't have time to look at his patch/results yet, though.
>>
>> FWIW I don't think the estimates can ever be perfect, especially for
>> complex joins (and that transfers to the filter estimates).
>
> Hmm, my point isn't perfection — it's scope and blind spots.
>
> Let me summarise what we can actually derive today. These three items are
> everything eqjoinsel_semi() has to work with:
>
> 1. Strip the matched MCVs and the NULL fraction, then look at what the ndistinct
> counts leave over. No difference there — no prediction of unmatched rows at all.
> 2. FK->PK joins. Here we do have an estimate, derived from the constraint and
> the estimated input sizes.
> 3. (Potentially) matching histogram boundaries. Postgres does this in
> mergejoinscansel() and nowhere else.
>
> That is a reasonable set, but it says nothing about two tables of similar size
> with similar statistics — which is the common case. And in practice, especially
> in ERP systems, users preprocess values like this:
>
> CASE WHEN day = 'sunday' THEN salary*2 ELSE salary END
>
> examine_variable() finds no statistics for that expression, so we fall back to
> DEFAULT_NUM_DISTINCT and the default selectivities. Anything we then compute for
> unmatched rows inherits that guess. This is exactly why the opportunistic
> approach works better here: it doesn't need the number at all.
>

I'm probably missing something, but I don't understand point you're
trying to make.

Sure, pushdown is more complex than applying filters inside the single
hashjoin (which is what v2 does), no argument there. I fail to see how
the "opportunistic approach works better".

In fact, the pushdown makes the plan more resilient to poor estimates
(which is what you're pointing out), and picking poor join orders.
Because while it does change join order, it does not change the order in
which we apply the "join filtering". That's one of the key benefits.

We may be unable to get accurate estimate of the Bloom filter, because
the stats we have are not sufficient. And maybe we'll not do the
pushdown in some cases because or estimate is too conservative. I don't
think that's a huge issue, as long as we don't cause (big) regressions
relative to "no pushdown" plans.

In fact, I wonder if the "join result size" is similarly important to
the filter selectivity, when picking "candidate filters."

>>
>>> 2. Path propagation. Filtered paths seem to need planning as parameterised ones.
>>> That may well be doable. However, the use case is narrow compared with the
>>> growth of the search space it brings for complex queries, and the effect is not
>>> local: once filters are in the optimiser, the best join order itself changes [2].
>>>
>>
>> True, which is why the patch (and the paper) aims to only create very
>> limited number of filtered paths, and only when there's a plausible
>> chance of that helping. I can imagine it'd be gated by some GUC in the
>> end, and people having to opt in, but I'd prefer that to not be needed.
>>
>> I don't see the join order changes as an issue. That's expected, and
>> also how the optimization can bring the most significant benefits. The
>> adaptation approach simply can't get those.
>
> That might not be a big issue. My point is what we are stacking: in a bushy join
> tree, the number of unmatched rows is one uncertainty on top of another — the
> join clause selectivity. Whatever level of conservatism we eventually pick, it
> will either admit too many overly aggressive plans (and fails more frequently as
> a result) or cut the number of Bloom filters down to almost nothing.
>

But we're already calculating that estimate when building the plans,
even without the filter pushdown. We don't change that at all. And as I
wrote above - increased resiliency to poor estimates (and thus poor join
orders) is one of the benefits of filter pushdown.

>>> Meanwhile, as the v2 patch [3] shows, the opportunistic approach can plausibly
>>> satisfy 'do better or the same'. Its open questions — how to represent the cost
>>> in EXPLAIN, how to decide adaptively whether to enable the filter, the overhead
>>> in parallel plans — are real, but none of them blocks the design the way the two
>>> above do.
>>>
>>> What it buys: simple code and zero overhead at planning time. Also, I don't read
>>> these as competing designs. The opportunistic path can go in now and collect the
>>> field experience the bottom-up one is currently missing.
>>>
>>> I ran a v2-modified instance under a real-life ORM load. Besides the positive
>>> changes in execution time, it turned up something I did not expect: the filter
>>> makes visible those cases where one more index, on one side of the join clause
>>> expression, would switch a heavy HashJoin into a fast parameterised NestLoop.
>>>
>>> I'm not against the bottom-up approach outright. Tomas already notes in [3] that
>>> an FK join needs no filter at all, since every outer tuple finds a match — and
>>> that is a plan-time decision we can make exactly. So I would call it a starting
>>> point for an incremental cost model rather than evidence that the general
>>> problem is tractable.
>>>
>>> Does anyone see a way to estimate unmatched rows that I have missed?
>>>
>>
>> I'm not against doing v2 (with a local filter for "all" hash joins), and
>> yes - it should be simpler. But IMHO it targets quite different use
>> cases than the "pushdown" patch.
>
> Good.
>
> It also looks like a reasonably safe route. Other systems did not drop planning
> either — they deferred to runtime exactly those decisions they could not
> estimate. So we can borrow both their experience and their runtime fallback
> heuristics instead of inventing our own.
>
> I have also tested the v2 patch (plus some extra code for partial paths) on a
> couple of ERP workloads. The overhead is small even when the filter does not pay
> off — and in any case, we can add a GUC to turn it off.
>
> So maybe we should pursue both? The opportunistic approach solves the problems
> we have today and has a chance to land in core much sooner. The path-based one
> extends the scope of the optimiser and improves planning in general, but it has
> to wait for the infrastructure.
>
Perhaps. I think it makes sense to do v2 (i.e. Bloom filters inside a
single hashjoin node) first, and use it to introduce infrastructure that
is also useful for the pushdown patches. Like sizing filters, the
adaptive behavior, etc.

regards

--
Tomas Vondra