Re: hashjoins vs. Bloom filters (yet again)

On 10/6/26 13:26, Andrei Lepikhov wrote:
> On 05/10/2026 18:24, Tomas Vondra wrote:
>> On 10/5/26 14:04, Andrei Lepikhov wrote:
>>> On 29/09/2026 19:57, Tomas Vondra wrote:
>> Sure, pushdown is more complex than applying filters inside the single
>> hashjoin (which is what v2 does), no argument there.
>
> Fair enough - complexity isn't my argument, let's keep it out of scope. My
> argument is narrower: the path-based pushdown design needs a number that today's
> statistics can't produce, and I don't see what fills that gap.
>
>> I fail to see how
>> the "opportunistic approach works better".
>
> Maybe I wasn't precise enough. By 'better' I meant broader and more stable, not
> faster.
>
> Broader: the opportunistic approach can be applied to every HashJoin in the
> plan, and it can push filter clauses down as deep as needed if there are no
> strong evidence that filter can't provide any meaningful impact. It also works
> in the cases where we have no usable statistics at all - which, in ERP-style
> schemas, is most of them.
>

AFAIK it faces the same challenge with estimating filter selectivity,
even if the Bloom filter is used only in the hashjoin that built it.

v2 did no pushdown, if I remember correctly. I can't imagine committing
a version that would do a pushdown at execution time, for reasons that I
explained before (breaking EXPLAIN).

> Stable: it doesn't change the join order. You're right that this cuts both ways
> - changing the join order is where the biggest wins are, and I'm not disputing
> that. My point is that it's a trade: path-based approach gains the best-case
> plans, and you also gain a new way to lose them.
>

The pushdown changes the join order, but does not change the order in
which the filtering happens.

>>
>> In fact, the pushdown makes the plan more resilient to poor estimates
>> (which is what you're pointing out), and picking poor join orders.
>> Because while it does change join order, it does not change the order in
>> which we apply the "join filtering". That's one of the key benefits.
>
> I may be using 'resilient' differently from you. So, let's specify.
>
> A pushed-down filter can only lower the row estimates below it - it never raises
> them, right? That pushes some segments of plan tree towards the aggressive side:
> NestLoop , Memoize, HashAgg with a smaller hash table.
> When the filter really is that selective, this is exactly what we want. When it
> isn't, we have picked a plan that fails badly rather than one that is merely slow.
>
> That asymmetry is my whole concern. Overestimation costs us a sort or a bigger
> hash table. Underestimation gives us a stack of nested loops that runs for a
> week. And Postgres multiplies selectivities, so a per-filter bias compounds it.
>
> The opportunistic version can only make that plan faster, or leave it alone.
>

I don't think it works like that. The important details is that while
the apparent join order changes, the order in which the join filtering
happens remains pretty much the same.

Consider a trivial example - a left-deep plan F-D1-D2-D3-D4-D5, joining
a fact table to dimensions, starting with the most selective dimension
joins. Now let's build Bloom filters for dimensions D1 and D2, which
also changes the join order to F-D3-D4-D5-D1-D2. But the D1/D2 filtering
still happens *before* D3 gets joined, and that join expects the same
cardinality from that input. There's no reason why this would "push" the
plan tree towards a "more aggressive" side.

Maybe this example is too simple. It'd be helpful if you could share an
example demonstrating the issue.

>>
>> We may be unable to get accurate estimate of the Bloom filter, because
>> the stats we have are not sufficient. And maybe we'll not do the
>> pushdown in some cases because or estimate is too conservative. I don't
>> think that's a huge issue, as long as we don't cause (big) regressions
>> relative to "no pushdown" plans.
>
> My point here is that if we add path-based Bloom implementation alone, we have a
> methodological blind spot.
>
> Two things make me sceptical of anything built on ndistinct here. First, the
> case I keep running into is two relations of similar size with similar ndistinct
> - the MCV lists don't overlap usefully, and the unmatched rows live in the tail
> that we model with a single number. Second, ndistinct doesn't shrink as we go up
> the tree the way rows do: as far as I can see, eqjoinsel() works from
> get_variable_numdistinct() and then clamps, so a column keeps its base-table
> distinct count until the row estimate drops below it. That is a long-standing
> source of trouble on its own, and a filter estimate built on top would inherit it.
>

Sure, no argument about ndistinct being very crude statistic, often
producing wildly inaccurate estimates. But AFAIK the filter pushdown
does not make us more exposed, because it merely relies on the join
cardinality estimates.

>>> 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.
>>>
>>
>> But we're already calculating that estimate when building the plans,
>> even without the filter pushdown. We don't change that at all. And as I
>> wrote above - increased resiliency to poor estimates (and thus poor join
>> orders) is one of the benefits of filter pushdown.
>
> Today a bad join selectivity gives us a bad row count; with the filter in the
> cost model it also gives us a different join order and different node types.
> This is more about blast radius of the feature.
>

I don't think so. It gives us a different apparent join order, but the
data is still filtered in the same order as before.

>>> 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.
>>>
>> Perhaps. I think it makes sense to do v2 (i.e. Bloom filters inside a
>> single hashjoin node) first, and use it to introduce infrastructure that
>> is also useful for the pushdown patches. Like sizing filters, the
>> adaptive behavior, etc.
>
> Agreed. I'd put the division of labour like this:
>
> - The opportunistic filter is the default: build it unless we can prove it is
> pointless. For example, a FK join where every outer row finds a match. So it
> works as a safety net.
>

Agreed.

> - The path-based version is then free to do the thing only it can do: reach
> plans we would not otherwise consider. And because the safety net is already
> there, it doesn't have to fire often to be worth having. When the selectivity
> behind a filter rests on a guess it can simply decline to push.
>

Not sure how could it "know" which plans would be unreachable, or what
kind of safety net you mean.

regards

--
Tomas Vondra