Message-ID: <838eb84c-7da6-46ec-bc27-df9ca2009c67@vondra.me>
Date: Tue, 7 Jul 2026 20:39:52 +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>
Content-Language: en-US
From: Tomas Vondra <tomas@vondra.me>
In-Reply-To: 
 <CA+TgmobDw_0zE02GGsHY5qmFwpjAKSsNg6VBN8oqpSNT_fOwcA@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Archived-At: 
 <https://www.postgresql.org/message-id/838eb84c-7da6-46ec-bc27-df9ca2009c67%40vondra.me>
Precedence: bulk


On 7/6/26 21:32, Robert Haas wrote:
> On Wed, Jun 3, 2026 at 6:07 AM Tomas Vondra <tomas@vondra.me> wrote
>> Right, there's a general concept of a "filter", and Bloom filters are
>> just one example of that. And maybe we could build other types of
>> filters more suitable for the scan. But I think it'll still be tied to a
>> hash join, because what other nodes / joins can build the filter?
> 
> Even if only hash joins build Bloom filters (or some other kind of
> filters), those filters can be pushed through other joins. For
> example, consider:
> 
> Hash Join
> Nested Loop
>   -> Seq Scan on a
>   -> Index Scan on b
> -> Hash
>   -> Seq Scan on c
> 
> If the hash join to table c builds a Bloom filter, it's perfectly
> valid to test against that filter before doing the index probe into
> table b.
> 

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.

> The hard part is the planning. I feel like doing this at path-to-plan
> time, after costing decisions have been made, is probably going to be
> a tough sell. In a plan tree with many joins, pushing down the Bloom
> filtering (or other filtering) decision to the lowest possible level
> could drastically change the row count estimates, and thus the
> costing, for a whole bunch of intermediate nodes, potentially meaning
> that the best plan is something quite different from what we
> estimated. On the other hand, if we try to do the "right" thing at
> planning time -- meaning constructing separate paths for each possible
> place where we could put the filter -- so that we can do costly
> properly, that sounds super-expensive, which will be really bad for
> queries that are supposed to have short execution times, and also not
> great for cases where the runtime is longer but our estimates are
> inaccurate, so that the extra planning effort is an expensive way of
> deciding what to do at random.
> 

I agree, but I think you're still looking at the v1 patch. The v3 posted
a week ago (and v4 posted by Matheus) are doing this doing the bottom-up
planning, when constructing scan paths.

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. The patch does
that by selecting a couple of the most promising filters, but I'm sure
we may need to do more.

With pushdown done at path-to-plan time, this was not an issue, but as
you point out it's after we already selected the plan. So we might have
missed a "better" plan, it was merely an attempt to improve the plan we
already selected. OTOH, that "limited the damage" when our estimates
turned out to be wrong.

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

The CustomScan could ignore a lot of that, of course. For example, v4
has an option to force building the filter eagerly (so that hashjoin
does not wait for the first outer tuple). But that's really a problem of
the CustomScan authors.

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.

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.

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.

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 haven't hard time to read the paper to which you linked, but I do
> sort of feel like knowing what the practical experience has been in
> other systems might be important. Theoretically there are good
> arguments for and against additional planning effort, but what happens
> in practice is not clear to me.
> 

That's a good idea, but I'm not aware of an open source database
implementing this :-(


regards

-- 
Tomas Vondra