Message-ID: <d43186bc-dffa-473c-84c0-0b7232ff6ef9@vondra.me>
Date: Mon, 6 Jul 2026 15:34:57 +0200
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: hashjoins vs. Bloom filters (yet again)
To: Matheus Alcantara <matheusssilv97@gmail.com>,
 Andrew Dunstan <andrew@dunslane.net>,
 PostgreSQL Hackers <pgsql-hackers@postgresql.org>
References: <5cd8c20c-14b5-4b0d-bedc-69bf714e87eb@vondra.me>
 <d08b01a9-1573-448d-a3c8-f49f6327ac02@dunslane.net>
 <baae2fc0-3e82-4ce9-9082-5ae0ca34e67e@vondra.me>
 <12d255f1-533f-414f-8caa-9867759cfce9@dunslane.net>
 <2f9a99ef-4857-4d4c-8544-30078a38dfa1@vondra.me>
 <ef511890-33f2-4ec8-be95-7438ed183541@vondra.me>
 <DJODCTHWX51C.2OICAR9ECSWTO@gmail.com>
Content-Language: en-US
From: Tomas Vondra <tomas@vondra.me>
In-Reply-To: <DJODCTHWX51C.2OICAR9ECSWTO@gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Archived-At: 
 <https://www.postgresql.org/message-id/d43186bc-dffa-473c-84c0-0b7232ff6ef9%40vondra.me>
Precedence: bulk

On 7/2/26 22:31, Matheus Alcantara wrote:
> On Wed Jul 1, 2026 at 10:25 AM -03, Tomas Vondra wrote:
>> (d) At planning / execution this works similarly to v1, except that all
>> the decisions were already done. The code in createplan.c and executor
>> is more for book-keeping and allowing lookup of filters.
>>
> 
> I'm wondering if the adaptive probing can mess the execution of the
> choose plan. Let's say that a plan was chosen with bloom filters to
> pushdown  because it would reduce e.g 50% of the rows, what if at
> runtime the bloom filter is proved to not be effective and it get
> disabled making the scan node to produce 100% of the rows to the node
> above that is not expecting? Do we end up with the same issue "expected
> x actual rows"?
> 
> I think that if we keep using the unnefective bloom filter the scan node
> will still produce more rows than expected, but perhaps this is easier
> to understand?
> 
>> I haven't incorporated the two patches posted by Andrew:
>>
>> 1) making it work with CustomScans
>>
>> 2) supporting per-key filters
>>
>> 3) allow eager creation of filters (disable delayed Hash build)
>>
>> I agree those seem like a worthwhile improvements, and the patches
>> seemed to be OK too, but I was focusing on reworking the planning. Based
>> on some off-list discussion, Andrew (or one of his colleagues) should be
>> able to adjust those for this v3 patch.
>>
> 
> I'm attaching a new v4 patchset incorporating Andrew patches with test
> cases. 0001 and 0002 are your v3 untouched, 0003 is some tests added to
> exercice the CustomScan path and 0004 is the Andrew changes with a few
> changes required from v3 version:
> 
> Unlike the v1 PoC that pushed filters down in create_hashjoin_plan
> (where it could simply walk the finished plan tree and accept any scan
> node), the filters are now decided during bottom-up path construction,
> so a scan only receives a filter if a filter-bearing path was generated
> for its base relation.  So the main change is teaching path generation
> about the custom scan.
> 

I took a quick look at the v4 patches adding the earlier patches from
Andrew,, and I think it looks sensible enough for a PoC. Thanks!

I think it'd make sense to split some of these into separate commits, as
it's not necessarily tied to just CustomScan nodes. And even if it is,
it can be a separate easier-to-review change.

I propose we move these two "features" into separate commits:

- "eager" creation of filters

- requesting per-key filters

I think it might be useful for other scans (or even non-scan nodes, if
we choose to allow filter pushdown for these). And it should be a
"generic" thing so that find_bloom_filter_recipient does not need to
check if the recipient is CustomScan. In fact, I think this should be
part of the information about expected filters "propagated" up during
planning.

FWIW It might make sense to show these things in the explain, at least
for development. AFAICS the CustomScan (used by the tests in 0003) does
not actually print the filters, right? And I'm not sure if the per-key
filters will be printed at all. But that's minor / easy to fix.

To move this whole thing forward, we'll need to figure out what to do
about the *big* questions. The four main ones I can think of (based on
memory and skimming the XXX comments in the patches) are:


1) selection of 'interesting' filters

Currently, we pick 'candidate' filters based solely on the selectivity,
but that only works if the scans don't use the filter in some smart way
(i.e. when it's evaluated at the very end). But if the custom scan can
do something very smart with some filters, the selectivity alone may not
be enough. The per-key filters make it even harder, I think.


2) construction of paths with filters (adjusting cost)

Right now the paths are constructed by "cloning" existing scan paths,
which is what create_filtered_scan_path does. But as already mentioned
in some XXX comments, I don't think it can work like this.

First, there's the question of costing. Do we need to adjust the cost in
some path-specific way? Maybe we don't, at least for built-in core
paths? In that case the filters are evaluated on the tuples the path
would produce, so maybe we can just add a bit of CPU cost per tuple, to
account for the evaluation of the filter (and reduce the row estimate).
Ff the filter is selective it'd still win, as expected.

But it's a bit dubious even for built-in core paths, because we'd
operate only on paths that already went through add_path and survived
the selection. Maybe we already eliminated some interesting path?

With "smart" CustomScan it's a bigger problem, though. If the scan is
doing something smart with the filters, it likely needs to adjust the
cost in a much more complex way. But the cloning does not allow that.

But more importantly, we can't copy CustomPath like this, because the
comment in pathnodes.h says:

    * Core code must avoid assuming that the CustomPath is only as
    * large as the structure declared here; providers are allowed to
    * make it the first element in a larger structure. (Since the
    * planner never copies Paths, ...

And we'd violate that. (Maybe this is a problem for the in-core scan
paths too?)

Some particular CustomPaths might be OK, but we can't know which ones
are. Maybe we could require scans wih CUSTOMPATH_SUPPORT_BLOOM_FILTERS
to allow such cloning, but it seems pretty fragile.


3) pushdown to multiple consumers (scans of partitioned tables)

Right now, we only allow pushdown to a single consumer. But with
partitioned tables that won't work - each partition scan is a consumer
of the same join (unless it's a partition-wise join, probably). We need
to make that work. It probably can't happen right now, because we don't
push through Append nodes (per find_bloom_filter_recipient), but that
seems like something we should allow.

Does not seem extremely particularly hard to address, though. The
find_bloom_filter_recipient simply needs to collect a list of recipient
nodes, not just the one.


4) parallel hash joins

There's some complexity due to having to put the filter into shmem, but
the v2 patch solved that I think, and we can mostly just copy that. I
don't think we need to solve that now.


I think (3) and (4) are somewhat mechanical. I know, it can easily be
much harder I envision. We won't know until we try.

For (1) and (2), I think we need to make this work more like how we
build paths for pathkeys. Do some sort of initial selection of
interesting filters, without trying to be very smart. So we'd maybe
check the filter discards > 30% of tuples, but without trying to keep
only the "top three" filters.

Then we'd generate the paths for all the possible combinations of
filters, not by cloning but by passing the expected filters to the
create_ function, and constructing a new path. If the scan can do
something smart - cool, it'd calculate the cost. In the worst case it'd
apply the filter at the end, with the generic cost / rows adjustment.

The paths with matching expected filters would still compete (just like
for matching pathkeys), of course.

There's still need to be some limits, though. If the table has 10 joins,
we can't generate paths for each possible combination of filters, that'd
be 2^10 combinations. But there are some inherent limits too, I think.
For example, once we discard ~90% tuples it probably does not make much
sense to keep applying additional filters. If each filter discards ~50%
tuples, that's 3 filters. So even with 10 joins we'd be limited to ~120
paths (which is still a lot, but way lower than 2^10).

We could still have some "heuristics" limits too, e.g. don't keep all
these paths, but prune them very aggressively and pick only the best
ones - just like we do now by only picking 3 most selective filters,
except that we'd do that based on proper costing (and not selectivity).


I plan to experiment with (1) and (2) soon, but it'd be great if you
could experiment with that too, and/or think about alternative ideas.


regards

-- 
Tomas Vondra