Re: hashjoins vs. Bloom filters (yet again)

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.

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.

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

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

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

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

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

--
regards, Andrei Lepikhov,
pgEdge