Re: hashjoins vs. Bloom filters (yet again)

On Tue, Jul 7, 2026 at 2:39 PM Tomas Vondra <tomas(at)vondra(dot)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? 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. 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.

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

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

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

--
Robert Haas
EDB: http://www.enterprisedb.com