Re: hashjoins vs. Bloom filters (yet again)

On 7/7/26 23:19, Robert Haas wrote:
> ...
>
>> 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.
>
>> 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.
>

There's one important detail / issue with these join examples, which I
realized while re-reading the paper [1] over the weekend. I either
skipped that part while reading the paper before, or maybe I did not
quite understand the section.

It works fine for the examples, because the joins are "simple" as in a
starjoin query. But it starts having issues with snowflake-like queries.

The problem is that we can only calculate the filter selectivity once we
know all the tables in the part below the HASH node. The current patch
does not account for that, it estimates the filter based on the join
clause selectivity only. That can either miss possible filters, or
produce plans with "wrong" expected cardinalities.

Consider a query like this:

SELECT * FROM
fact_table
JOIN dim_1 ON (f.a = dim_1.a)
JOIN dim_2 ON (dim_1.b = dim_2.b)

where none of the joins eliminates anything.

There's two basic ways to execute this type of query, I think (other
plans are possible, but let's focus on these two):

X
/ \
dim_2 X
/ \
dim_1 fact_table

and

X
/ \
X fact_table
/ \
dim_1 dim_2

It's not hard to force these plans with join_collapse_limit=1.

The two plans have somewhat different challenges, depending on where we
add additional WHERE filters (on which of the dim_ tables).

In the first plan, we have very limited pushdown options. We really want
to push filters to the fact_table scan, but let's add a selective WHERE
condition on dim_2. That won't add any filters on fact_table, because
the patch only looks at the join clauses and fact_table joins only with
dim_1 (and that filters nothing).

We might add a filter from dim_2 to dim_1, although that does not seem
to happen with the v4 patch for some reason (seems like a bug).

So this works as expected, but it limits where we can push filters. We
really want to do the second plan, because then we can push the filter
for the whole subplan to the fact_table.

Unfortunately, this runs into the issue with cardinality. The patch only
looks at "immediate" join selectivity to dim_1, it fails to account for
other tables on the other side of the join (in this case dim_1 + dim_2).

Let's say the query actually looks like this:

SELECT * FROM
fact_table
JOIN dim_1 ON (f.a = dim_1.a)
JOIN dim_2 ON (dim_1.b = dim_2.b)
WHERE dim_2.x < 1 -- eliminated 99% tuples
AND dim_1.x < 65; -- eliminates ~35% of tuples

The patch will look at the dim_1 join, calculate that it discards ~30%
of tuples, and will create a fact_table scan path with that estimate.

But in practice the filter is built on (dim_1 join dim_2), including the
filter on dim_2, which drastically increases the fraction of tuples to
be discarded by the join.

So the plan then looks like this:

QUERY PLAN
----------------------------------------------
Hash Join
Hash Cond: (fact_table.a = dim_1.a)
-> Seq Scan on fact_table
Bloom Filter 2: keys=(a)
-> Hash
Bloom Filter 2
-> Hash Join
Hash Cond: (dim_1.b = dim_2.b)
-> Seq Scan on dim_1
Filter: (x < 70)
Bloom Filter 1: keys=(b)
-> Hash
Bloom Filter 1
-> Seq Scan on dim_2
Filter: (x < 1)

Which is what we want - predicate transfer between dim_2 -> dim_1, and
then (dim_1,dim_2) -> fact_table. But the estimate for the scan is
completely bogus:

-> Seq Scan on fact_table (cost=0.00..18334.00 rows=691000
width=37) (actual time=0.126..157.281 rows=2927.00 loops=1)

because it accounts only for the dim_1 selectivity. Of course, if you
remove the condition (dim_1.x < 70), then there's no filter pushed down
to fact_table again, because the filter is no longer considered
interesting (and that's a missed opportunity).

Attached is a reproducer script for these two examples.

Anyway, the paper [1] correctly observes that:

... So, to estimate the cardinality, and therefore cost, of a Bloom
filter sub-plan we must know the set of relations that appear on the
build side of the hash join.

This dependency poses a problem for a bottom-up optimizer, where the
set of relations appearing on the build side of a join is not
generally known a priori.

This means that to properly cost the new scan paths, we need to know
enough about the plan shape - the relations below the HASH node of the
join. That is, we need to know whether to expect the dim_1 alone, or the
join of dim_1+dim_2. Which we obviously don't, because (a) we build
these new paths before constructing any join rels, and (b) there are
different legal join orders, so how would we know which one is best?

The paper deals with this by doing the planning in two phases, as
explained in section 3. In the first phase they essentially construct
the valid join combinations, and use this to estimate the candidate
filters (with "correct" selectivities). Then they generate the paths
(similarly to our patch, once we have interesting filters), and do the
rest of the regular planning as usual.

Obviously, this is more complex and doing things twice is not free. But
I don't think we can work around this, and I don't think it really needs
to be that expensive.

The first phase certainly does not need to do "full" planning, with path
construction and all that. We only really need to enumarate legal join
combinations, and do rudimentary selectivity estimation. Luckily, we
have a great enumeration algorithm - the DPccp, I mentioned in the join
hardness thread some time ago. Of course, that's only the enumeration,
there's still the selectivity estimation.

Sure, if your query is too hard, with millions of possible join orders
etc. this is still expensive. But those queries are mostly already
doomed, really. We could just give up after some effort limit.

I also suspect we can come up with heuristics or rules to additionally
prune the search space during the DPccp enumeration, e.g. once we figure
out a filter is not interesting, etc.

regards

[1] Including Bloom Filters in Bottom-up Optimization
https://arxiv.org/html/2505.02994v1

--
Tomas Vondra