Re: hashjoins vs. Bloom filters (yet again)

On Fri Jul 17, 2026 at 1:22 PM -03, Tomas Vondra wrote:
> On 7/13/26 21:26, Matheus Alcantara wrote:
>> ...
>>
>> This make sense to me as a direction. I've been sketching this idea and
>> here is my attempt to implement. This is still a PoC, it still need more
>> polishment but I've wrote some comments and commit message to try to
>> explain the idea.
>>
>
> OK, thanks. I didn't have much time to do a thorough review yet, but let
> me share at least some general feedback.
>

Thanks for the feedback.

>> For (1), the candidate selection no longer picks the "top three" most
>> selective filters. It still requires a candidate to discard at least
>> bloom_filter_pushdown_threshold (30% by default) of the rel's tuples,
>> but every candidate clearing that bar is kept, with no count-based trim.
>> > For (2), combinations are now generated breadth-first by increasing size
>> instead of enumerating every non-empty subset, and a combination stops
>> growing once its combined selectivity drops below a new
>> bloom_filter_pushdown_combination_floor GUC (0.1 by default).
>> bloom_filter_pushdown_max now caps how many filters can be combined into
>> one path rather than how many candidates survive. So, with ~50%
>> selective filters, growth stops around 3 deep regardless of how many
>> candidates exist, so 10 joins doesn't turn into 2^10 paths.
>>
>
> Makes sense. I've been working on allowing building filters on joins,
> not just on baserels (per my message from a couple days ago), and I
> think that'll also need relaxing this in some way (there are likely
> quite a few possible join rels, more than 3).
>
> I don't know if these default thresholds are reasonable - e.g. 0.1 seems
> rather high, if the relation happens to be large it may easily be a
> couple million rows etc. Maybe it'd be better to base this on number of
> rows, not as a fraction. But not sure. I wonder if we could base this
> heuristic on some approximate cost/benefit ratio instead.
>

Yeah, make sense. I'll think more about these other options.

> FWIW I think we could take inspiration from the SIGMOD paper I mentioned
> a couple times already - the authors do propose a bunch of heuristics to
> decide which filters to build etc. There's a nice overview in section
> 3.10 of the paper. Some are a bit debatable, but most seem sensible.
>

Agree. I've spent some time reading this paper this weekend, I still
need to understand some things but most of these heristics discussed on
the paper I think that is viable to implement it. I'll work on this for
the next version.

>> Each combination is passed straight into the real create_*_path
>> constructor for its scan type instead of being produced by cloning an
>> already-costed path. A new apply_expected_filters() helper is the
>> generic "cost/rows adjustment" fallback: it charges one
>> cpu_operator_cost per filter per tuple on top of shrinking the row
>> estimate, so filtering is no longer free. IndexPath is the one exception
>> still handled by cloning, since create_index_path() would just
>> redundantly re-derive indexclauses/pathkeys for no benefit, perhaps I
>> think that we can improve this.
>>
>
> Hmm, not sure what to do about indexpaths. Maybe we could have a
> "filter" variant that takes an existing IndexPath as a source, and
> reuses the indexclaused/pathkeys (without recalculating it). But then
> still does whatever other adjustments are necessary.
>

Ok, sounds reasonable.

>> For CustomPath, core can't safely clone or construct one at all. So
>> it doesn't touch CustomPath for this anymore — a provider that wants
>> filter-aware CustomPaths builds them itself, using the new exported
>> filter-combination function and either costing them for real or
>> falling back to the same generic adjustment core uses.
>>
> I think this will need some more though. I don't think we want to run
> the find_interesting_bloom_filters() from scratch multiple times, it can
> be fairly expensive. It'd be good to "cache" the filters somewhere, so
> that the CustomScan can pick the filters from there. Say, we could stash
> it in the RelOptInfo, right?
>
> This will matter much more for filters on joins, because for that we'll
> have to run a simplified version of the join enumeration, and that's
> certainly not free. That can also cache stuff more aggressively (e.g.
> the valid join relids can be calculated just once).
>

Agree that we should not run find_interesting_bloom_filters() multiple
times. I'll work on stash this on RelOptInfo for the next version.

>> Paths with differing expected filters still never dominate each other in
>> add_path, so they compete on cost exactly like paths with different
>> pathkeys do, same as in v4.
>>
>
> Yeah. The good thing is the new paths with filters still compete among
> each other, so hopefully that eliminates a fair number of them. But I
> wonder how effective that is, and whether we could introduce some more
> heuristics to discard more of them.
>
> The paper does describe a bunch of heuristics when generating candidate
> filters for joins, but I think it also describes heuristics when adding
> filters to a scan. But I don't recall the details.
>
> It might also be interesting to try constructing queries that would be
> affected by this (e.g. a fact with a bunch of dimensions with filters),
> and measuring the practical impact. Can you give that a try?
>

I gave this a try. Attached is star-schema-bloom-repro.sql, which builds
a 10M-row fact table with 6 dimension tables, FKs uniformly distributed
(no correlation between fact rows and dimension values, the worst case
for the search, since nothing prunes candidate combinations early). I
tried to reproduce the same shape as the star-schema scenario in ref
[26] that the paper's related work section mentions, plus a snowflake
variant (ref [8]).

Each query joins the fact table to N dimensions (N = 2..6), each with a
WHERE filter surviving ~30-40% of rows, individually just over our
bloom_filter_pushdown_threshold (0.3), so none of them get discarded
before the combination search runs, and the combination_floor (0.1)
isn't crossed until several are combined. I think that this stress
exactly the case you're asking about: a fact table whose scan
accumulates several non-trivial candidate filters and has to search
combinations of them. Please let me know if I miss-understood something.

Settings: defaults (bloom_filter_pushdown_max=3, threshold=0.3,
combination_floor=0.1), max_parallel_workers_per_gather=0. Each query run
with enable_hashjoin_bloom off and on, same session, same data:

N filtered dims | planning time (bloom on) | planning time (bloom off)
2 | 1.3 ms | 1.2 ms
3 | 3.9 ms | 1.8 ms
4 | 10.1 ms | 4.5 ms
5 | 21.0 ms | 6.4 ms
6 | 56.6 ms | 7.9 ms
6 (snowflake | 29.0 ms | 6.5 ms

Two things stand out:

1. Planning time grows superlinearly once N passes 4, jumping almost 10x
at N=6 relative to the OFF baseline for the same join search. That's
find_bloom_filter_combinations() actually having to walk C(n,2)/C(n,3)
subsets rather than being cut off early. Capping
bloom_filter_pushdown_max=1 (no combining at all, closest thing we have
to your Heuristic-7 idea) brought N=6 planning time down to ~20ms.

2. Execution time did not improve with the feature on for this dataset,
it's consistently ~7-11% worse (e.g. N=6: 2541ms OFF vs 2810ms ON). I
checked the plans and the join order chosen is identical in both cases,
and only one Bloom filter (on the single most selective join column)
ever gets realized, no matter how many combinations were built or how
many candidates existed. I think that most of this is because the
planning time degradation.

So I think that we need better heuristics to decide when to create such
filters. As I mention above, I'll work on to implement such heuristics
based on the paper to see if we get better values here.

> One comment - let's include the changes in expected output in each of
> the patches, so that "make check" passes after each individual patch. I
> think it makes debugging simple. V4 did it like that, but v5 seems to
> move some of the output changes to the last part.
>

Ok, I'll ensure this for the next version.

--
Matheus Alcantara
EDB: https://www.enterprisedb.com