Message-ID: <16c60936-9b6e-4649-a34a-a155f3d0bd07@vondra.me>
Date: Wed, 8 Jul 2026 00:26:41 +0200
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: hashjoins vs. Bloom filters (yet again)
To: Robert Haas <robertmhaas@gmail.com>
Cc: Oleg Bartunov <obartunov@postgrespro.ru>,
 PostgreSQL Hackers <pgsql-hackers@postgresql.org>
References: <5cd8c20c-14b5-4b0d-bedc-69bf714e87eb@vondra.me>
 <CAF4Au4z0T16jcUauUBmAzGWW6E034BRdkSL2Bg8riP9uO-5O8w@mail.gmail.com>
 <eb4c51c7-2758-447f-8e65-50f4ff0d36da@vondra.me>
 <CA+TgmobDw_0zE02GGsHY5qmFwpjAKSsNg6VBN8oqpSNT_fOwcA@mail.gmail.com>
 <838eb84c-7da6-46ec-bc27-df9ca2009c67@vondra.me>
 <CA+TgmoZFHLVoyYdQHEBs5NdY_TpDWXFvzb=nzw35BOK0TaXhhg@mail.gmail.com>
Content-Language: en-US
From: Tomas Vondra <tomas@vondra.me>
In-Reply-To: 
 <CA+TgmoZFHLVoyYdQHEBs5NdY_TpDWXFvzb=nzw35BOK0TaXhhg@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Archived-At: 
 <https://www.postgresql.org/message-id/16c60936-9b6e-4649-a34a-a155f3d0bd07%40vondra.me>
Precedence: bulk


On 7/7/26 23:19, Robert Haas wrote:
> On Tue, Jul 7, 2026 at 2:39 PM Tomas Vondra <tomas@vondra.me> wrote:
>> I don't disagree, but it's that what all the push-down patches in this
>> thread are already doing? When I said "tied to hash join" I meant the
>> filter would be built by a hash join, not that all the joins have to be
>> hash joins. It can certainly by pushed through NL/merge joins.
> 
> I haven't actually looked at the patches -- I was just responding to
> the email. Sounds like I misunderstood.
> 
>> You're definitely right the extra paths may be rather expensive, and
>> we'll need to keep that under control. If a query has 10 joins, we can't
>> realistically consider all 2^10 of filter combinations.
> 
> Yeah.
> 
>> But I think there are more options how to limit the cost. For example,
>> it's unlikely to help when the scan already returns very few tuples. So
>> maybe we could consider filters only when the row count is above 1000,
>> or something like that. And maybe we could do something similar based on
>> cost? But that would ignore savings above the scan (e.g. maybe one of
>> the later joins is very expensive).
> 
> I'm not sure which scan you mean when you say "when the scan already
> returns very few tuples." Suppose we propose to join A to B. We plan
> to use a hash join and use B as the build table and A as the probe
> table. So, if I understand correctly, we'd build the bloom filter on B
> and use it when scanning A. Do you mean that the filter is unlikely to
> help when B is small, or when A is small?

When A is small, i.e. the outer side of the join (not the side on which
we built the hash / filter).

The idea is that if the outer side has 1000 rows, even if we eliminate
90% of them it may not pay for itself (because of the cost of extra
paths during planning, building the filters etc.).

One of my ideas for keeping the number of paths under control was to
stop "adding" filters to a path once the cardinality drops below some
threshold. Let's say we start with a scan returning 1M rows, and we add
2 filters eliminating 90% tuples each. Cool, now it's expected to return
10k rows. Should we consider a version with a 3rd filter? Maybe it'll
help a little bit, but the benefit is certainly much smaller than for
the first two filters.

> Neither is obvious to me: if
> B is small, the hash table will be small, which might make it cheap to
> probe, but it also makes the Bloom filter small, so maybe that's
> *really* cheap to probe, plus a small Bloom filter is enough to have a
> really low false-positive rate.

The size of B (on which the hash table is built) is a very poor signal.
What matters is the selectivity of the join, and a tiny table can
eliminate 1% or 99% - it does not depend on the size.

Yes, a tiny table may be cheap to probe (the Bloom filter will still be
cheaper, but it'll be closer). For large hash tables the trade offs is a
bit different, especially when the join start spilling. But even then
it's more about what fraction of tuples it eliminates.

But focusing on the relative cost of probing the hash table vs. probing
the Bloom filter is missing the point - it's about *when* you probe it.
With the pushdown the probe happens much earlier, before doing a lot of
other relatively expensive stuff.

As an extreme case, imagine we push the filter into a ForeignScan. The
foreign scan could copy the filter to the remote side, and discard all
the tuples there, saving all the network costs. (Yes, the patches don't
do this - yet, but it's not a huge change.)

Yes, maybe we could skip building the filter and just probe the hash
table directly. That only works in some cases (e.g. the FDW case would
not work), and only when the hash table is "complete" (no spilling).


> If A is small, you're not going to 
> save as much in absolute terms, but you save the same thing
> percentage-wise as on a larger table.
> 
> It seems like the most important thing -- which I'm aware you already
> mentioned -- is how likely it is that a row in A joins to a row in B.
> If the answer is "not very likely," the filter has a good chance of
> working out.
> 

Exactly. And then it's also about the cost of what happens in between
the probe and the join.

>> I think a lot of the regressions can be handled by adaptive behavior at
>> execution time. Like, we can postpone building the filter until after
>> we've already probed the hash table to know it's worth it. Or disable
>> the filter when it becomes ineffective. The v3/v4 patches already do
>> some of this, IIRC.
> 
> Yeah, adaptive behavior is great. We need to be careful not to add too
> much complexity, on the one hand, or to expect perfection, on the
> other. But it's a good way of mitigating downsides.
> 

100% agreed

>> Of course, even with the adaptive behavior we're "stuck" with the new
>> plan (which may differ from the plan we'd have picked otherwise). But
>> I'm not sure it's really that different. Because really, the impact is
>> somewhat limited.
> 
> This doesn't especially worry me: any plan can be wrong. If the
> planner goes wrong substantially more frequently with this patch than
> without, of course that would be bad. But if it just goes wrong for a
> different set of queries,  I think that's just life.
> 

OK

>> What happens is that we pick the K most selective joins, and build
>> filters for those. And then we plan with that. Those selective joins
>> would be at the very bottom of the original plan, because we prefer to
>> do selective joins first.
> 
> This is a clever idea.
> 
>> Let's say a plan has 4 joins.
>>
>>            X
>>          /   \
>>        B2     X
>>             /   \
>>            B1    X
>>                /   \
>>               A2     X
>>                    /   \
>>                   A1    T
>>
>> Most likely, A1 and A2 joins are the two most selective, so we get to
>> build filters for those, and push them to scan on T. Which means the
>> filtering is applied in the scan, and the joins themselves won't reduce
>> the cardinality at all!
>>
>> The B1 and B2 joins become "more selective", and in the new plan
>> (selected with filter pushdown) will be performed first:
>>
>>            X
>>          /   \
>>        A2     X
>>             /   \
>>            A1    X
>>                /   \
>>               B2     X
>>                    /   \
>>                   B1    T (filters from A1/A2)
>>
>> But the A1/A2 filtering still happens *before* B1/B2, thanks to the
>> filter. So B1/B2 are still planned with the same selectivity and row
>> counts as before, and so will most likely use the same join algorithm.
> 
> They could switch to a nested loop, though, which is a little tricky
> to reason about: any individual join could be better as a nested loop,
> while the set of joins taken together might be better if you use all
> hash joins so that the filters can be combined.
> 

No, I don't think they could switch to nested loops. That's the whole
point - the B1/B2 joins are planned with *exactly* the same row
estimates as before, because A1/A2 still eliminate the tuples before
B1/B2. So if they are nested loops in the new plan, it'd be the same in
the old plan too.

Of course, it can happen that B1/B2 really are nested loops, and that
it's a poor choice because A1/A2 eliminated much smaller fraction of
tuples than we thought. But that affects both plans the same way.

>> So the impact on the query plan is actually much smaller than it might
>> seem. Which likely limits the risks quite a bit.
>>
>> Of course, this is just a very simple example. Maybe it's riskier for
>> more complex joins, not sure.
> 
> I don't see that a more complex tree magnifies the risk; I think it's
> just about how sure you can be that you're actually going to filter
> something out. Your chances of winning probably actually grow with the
> number of joins for which you build the filter, because I guess you
> can bitwise-AND all of those filters and just test the result. If even
> one of the filters is highly selective, that may gain you enough to
> pay for the cost of building all of them. This is not guaranteed, of
> course, but the risks and rewards seem asymmetric: a useful filter
> seems as though it can win much harder than a useless filter can ever
> lose. I could be wrong, but my guess is that we only need to do a
> moderately good job avoiding the worst case.
> 

I admit I'm hedging a little bit - it's probably fine even for complex
plans, but I haven't done enough tests to make such a clear claim.

Maybe you're right more filters make it safer. But more filters mean we
need to consider more paths, so it's a trade off. Unless we figure out a
good way to pick "interesting" combinations.

I'm not sure about combining the filters by bitwise-AND. Maybe it could
work and help a little bit, but it'd also require all the filters to
have the same size. It's worth testing, but I think the cost of the
filter probe does not matter all that much (compared to the savings by
eliminating the tuples much earlier).


regards

-- 
Tomas Vondra