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
