Re: hashjoins vs. Bloom filters (yet again)

On 9/2/26 20:12, Andrei Lepikhov wrote:
> On 22/08/2026 00:26, Tomas Vondra wrote:
>
> As I see it, the bottom-up, cost-based approach quickly becomes
> complicated, and two of the underlying problems look fundamental.
>
> 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).

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

> Hence, unblocking the bottom-up route means solving both of these in advance,
> and I don't see either one coming any closer.
>

Most patches look difficult at the beginning.

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

regards

--
Tomas Vondra