Re: hashjoins vs. Bloom filters (yet again)

On 10/8/26 15:35, Andrei Lepikhov wrote:
> 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.
>

To some extent, yes. I don't think the plans are that different, for the
reasons I explained earlier (regarding the join order changing, but not
the filter order, and us already relying on these estimates anyway).

But you're right it introduces certain amount or new risk, particularly
when the filters seem more selective. Which can happen for a couple
reasons, both for a single join (but then we already have the problem in
regular plans, I think) and when combining filters from multiple joins
(and they are e.g. correlated in some way).

It'd be interesting to see actual examples where this causes (serious)
problems compared to "old" plans.

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

Showing the filter in the explain is not enough. If you push it down,
you also have to go through all the intermediate nodes and adjust the
rowcount and cost estimates to make the explain "correct".

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

AFAIK that doesn't "break" the rowcount estimate, no?

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

This is a simple example of the current patch not considering the false
positive rate of the filter. The bloom_create logic sizes the filter to
have 1-2% false positives (because that's enough for amcheck), but for a
table with 10M rows that's ~200k rows. Which almost exactly matches the
slow plan:

-> Seq Scan on f (cost=0.00..156747.74 rows=2014 width=8) (actual
rows=230415.00 loops=1)

If you increase BLOOM_PROBE_MIN_BITSET_BYTES to 32kB, that fixes that
and the plan becomes about 30% faster than the regular one.

FWIW I'm not suggesting this is the right fix in general, it's just a
proof that it's about false positive rate. The correct solution is to
consider FPR when sizing the filters and estimating the selectivity for
the paths. That's already on the TODO somewhere.

But you're right this is not a fix for all possible issues. The filter
(or a combination of filters) may be less selective for other reasons.

regards

--
Tomas Vondra