Re: hashjoins vs. Bloom filters (yet again)

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.

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

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

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?

P.S. It seems to me that using CLOBBER_FREED_MEMORY you can catch assertion with
the v10-0001 patch.

[1] "I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft
SQL Server", CIDR 2026 — https://www.vldb.org/cidrdb/papers/2026/p29-zhao.pdf
[2] "Including Bloom Filters in Bottom-up Optimization", arXiv:2505.02994 —
https://arxiv.org/abs/2505.02994
[3]
https://www.postgresql.org/message-id/a4700550-474f-42d8-b9fc-7e3dd0bfa818%40vondra.me

--
regards, Andrei Lepikhov,
pgEdge