Re: hashjoins vs. Bloom filters (yet again)

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.

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

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

--
regards, Andrei Lepikhov,
pgEdge