Re: hashjoins vs. Bloom filters (yet again)

On 06/10/2026 16:07, Tomas Vondra wrote:
>
> On 10/6/26 13:26, Andrei Lepikhov wrote:
>> On 05/10/2026 18:24, Tomas Vondra wrote:
>> 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.

In my view, the opportunistic approach would use estimates only to reject
provably pointless cases, and would build the filter whenever the case is
uncertain. That's the asymmetry I keep pointing at: the path-based version needs
a number — how selective the filter is — and feeds it into the cost model, so a
wrong estimate gives us a different plan.

The opportunistic version needs only a one-sided test: can we prove this filter
is useless? A wrong answer there costs us some hashing, not a join order. It
also lets us handle COALESCE(), CASE and other constructs that collapse
statistics to default selectivities — the cases where the path-based version has
nothing to work with at all.

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

On the EXPLAIN point: agreed, a filter that appears at execution time only is
not committable. What I have in mind stays visible in the plan — the decision is
made at plan time, the filter just doesn't have to be load-bearing for the cost
model.

BTW, it seems to me that there is also some precedent for showing execution-time
decisions in EXPLAIN: runtime partition pruning reports "Subplans Removed". I'd
expect a filter to be presentable the same way.
>> 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.
>
> 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.

In the current v10 the INNER JOIN example works well. But even here I see one
source of uncertainty: the Bloom filter promises more than it can deliver.
Please look at the attached example. The estimates there are quite accurate, and
we still get a 3x regression in execution time.

Yes, we can find a fix for each root cause of this bad plan, but the uncertainty
remains: I can imagine a case with many NULLs in the input that pass the filter
and cause a regression as well. Also, don't forget that the typical case isn't a
multi-way join like this one, but a more complex query with limited freedom to
reorder joins — outer joins, lateral references, and so on.

This is not an argument for dropping this work, just a demonstration that the
scope should start narrow and be extended step by step as new estimation
machinery arrives.

--
regards, Andrei Lepikhov,
pgEdge