Re: hashjoins vs. Bloom filters (yet again)

On Tue Jul 28, 2026 at 5:58 PM -03, Tomas Vondra wrote:
> Is this with the v8 I posted? There's not the "expected" field for the
> filter, so I guess it doesn't have the filter estimate fix from my v8
> patches. And the estimates/actuals seem similar to what I saw before.
>
> For the record, this is what I see on 10GB data set for this join
>
> -> Seq Scan on lineitem (cost=0.00..1725034.76 rows=3275719 width=29)
> (actual time=0.037..2947.777 rows=3260827.00 loops=1)
> Bloom Filter 2: keys=(l_suppkey, l_partkey) expected=5.5%
> checked=59986051 rejected=56725225 (94.6%)
> Buffers: shared hit=576 read=1124567
>
> Which seems pretty spot on. It might also depend on other GUCs affecting
> the filters, I'm using
>
> set bloom_filter_pushdown_max = 10
> set bloom_filter_pushdown_max_build_relids = 10
> set bloom_filter_pushdown_max_build_sets = 10
>
> Maybe we're not matching the filters to joins correctly (relids equality
> vs. subset).
>

It didn't have the filter estimate fix from your v8. With your patch the
estimation and the plan looks very similar to what you have.

I'm attaching v9 which include the following changes (1-6 are from the
previous "my" v8):

1. Candidate selection: no count-based cap -
find_interesting_bloom_filters() now returns every candidate that clears
bloom_filter_pushdown_threshold, instead of trimming to the
bloom_filter_pushdown_max most selective. (This is the v5-0005
candidate-selection change that wasn't carried into v6/v7.)

2. Real costing for filter-aware scan paths - paths are built through the
real create_*_path constructors, and apply_expected_filters() charges one
cpu_operator_cost per filter per tuple, so filtering is no longer modeled
as free and a filter is only chosen when it's actually cheaper. (also
from v5-0005)

3. Heuristic 4 - apply all candidates at once - replaced the subset
enumeration with a single combination that applies all non-overlapping
candidates (most-selective first), so we no longer build a path per
subset. bloom_filter_pushdown_max is repurposed to cap how many filters
are applied simultaneously (per-tuple probe cost), and the
combination_floor GUC from v5 is dropped. This collapses the path
explosion and keeps planning time acceptable on the TPC-H queries.

4. IndexPath filter variant - create_filtered_scan_path() clones the
source IndexPath, reusing its indexclauses/pathkeys, and applies the same
probe-cost/row adjustment as the other scan types. I'm not sure if I
understood correctly your feedback regarding this topic on [1].

5. Cache interesting filters on the RelOptInfo - the
find_interesting_bloom_filters() result is cached and reused, so it isn't
recomputed for core path generation and again by a CustomScan provider.

6. CustomScan providers build their own filter-aware paths via the
exported find_bloom_filter_combinations() + apply_expected_filters(),
rather than core constructing CustomPaths. (also from v5-0005)

New in this patchset(v9-021): while debugging a Q8 regression I found
the filters were being built with bloom_create(), which forces a 1MB
bitset floor and lets optimal_k() go up to MAX_HASH_FUNCS (10). For a
filter that probes a large apply side that's a bad fit. In Q8 the
(l_partkey) filter probes all ~60M lineitem rows, and with a 1MB bitset
IIUC each probe is ~10 random accesses into a bitset that doesn't fit in
L2 cache, a likely cache miss per hash. So the probe stops being the
cheap "constant k" the cost model (and the paper) assume, and the filter
costs more than it saves even though it rejects >98% of the rows. This
is basically the situation that IIUC the paper warns about in section
3.5: keep the filter small enough to stay in cache and use few hash
functions.

7. Probe-oriented filter sizing - I added bloom_create_probe(), in
nodeHash.c which uses a 1KB floor and caps the hash functions at 4. So
the filter is sized to the build side and (hopefully) stays cache
resident. So, in this case the Q8 (l_partkey) filter goes from:

bits=8388608 hashes=10 memory=1024kB (rejects 98.1%)

to

bits=131072 hashes=4 memory=16kB (rejects 98.1%)

Same rejection rate, ~15x smaller and L2 cache resident.

TPC-H scale 10, warm cache, max_parallel_workers_per_gather=0,
work_mem=256MB; medians of 3 runs, enable_hashjoin_bloom off vs on:

query off (ms) on (ms) delta

Q3 107623 107418 -0.2%
Q5 20307 18433 -9.2%
Q7 21815 19933 -8.6%
Q8 18834 18824 ~0%
Q9 42602 40292 -5.4%
Q10 24180 20850 -13.8%
Q18 264641 144729 -45.3% (was a regression)
Q21 35614 37960 +6.6% (was ~+41%)

The interesting part is that the sizing change did more than fix Q8. Q18
has the same shape (a filter probing all of lineitem), so cheaper probes
flipped it from a regression into a large win, and Q21 came down from
roughly +41% to +6.6%.

Q21 is the only regression left, at +6.6% instead of ~41% on previous
version. I'm wondering if some other heuristic discussed on the paper
could help, e.g Heuristic 5 (explicitly skipping a filter whose build
side is too large to keep the bitset in cache).

I didn't look deeper on all the new patches that you worked on v8. I was
focusing on implementing these new ideas to see some improvements. I
intend to do it next.

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