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
