Re: hashjoins vs. Bloom filters (yet again)

On 7/30/26 21:00, Matheus Alcantara wrote:
> 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):
>

Cool. I'll add that to my working branch, and will make sure to include
the patches in future versions, so that you don't have to rebase/rework
it again.

We could also agree on maintaining a shared branch somewhere, and post
new patch versions to -hackers from time to time. That's what we did for
index prefetching, and I think it worked. The one risk is it can move
the discussion off-list too, so we'd need to be careful about that.

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

OK. I think these changes look reasonable.

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

This is a very interesting observation! I think it's related to my point
about "filter sizing" being one of the open questions.

I definitely agree we should not require 1MB+ filters - if 1kB is
enough, we should just use that. Because as you say, if it can fit into
L2 / do fewer random probes, that can easily make a huge difference.

FWIW I disagree with "heuristic 5" from the paper, which says:

If the expected size of the Bloom filter is beyond a threshold,
a Bloom filter is not created.

The reason is that one of the benefits is being able to discard tuples
for batching hash joins, so that we don't have to spill them to disk. In
those cases the filter is likely fairly large (because the hash table is
a multiple of work_mem), but the higher cost seems to be worth it. It's
still way cheaper than the eliminated I/O.

I think we'll need to come up with some simple cost model, so that we
can do good approximate decisions.

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

I recall I already added a similar "bloom_create" variant (with a lower
floor). It seems we lost is somewhere along the way.

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

That's great. I wouldn't have expected the impact to be so significant.

There's a couple things that puzzle me:

1) The timings I see on TPC-H 10GB are much lower. I mean, for me Q3
takes ~5s on master, while for you it seems to take ~100s. Similarly for
the other queries. What kind of hardware / build are you using?

2) The queries using filter pushdown seem to be different too. In my
runs on the last patch version (without your latest changes), I see
these queries using a filter:

2 3 4 5 7 8 9 10 11 12 14 16 20

I don't know if your table shows results for all queries with a filter
in the plan, or if you selected just some interesting ones. But even
then, I've not seen 18 or 21 to pick a plan with a filter.

I suspect this may be due to schema differences (e.g. indexes, ...).
I've pushed my ugly WIP scripts here, so that we can compare:

https://github.com/tvondra/pg-tpch-bloom

It's ugly and may not be easy to use. What matters is the create-X
scripts, which create the objects / load data, etc. The run.sh script
then runs the actual test (but it's something I often tweak, depending
on what I need at the moment).

FWIW I'm not saying we should be running the tests on the same schema.
There's a lot of value in testing a wider range of cases. But it might
be good to know where do the differences come from.

FWIW I've been looking at some "random" plan changes in the TPC-H runs
I've been doing this week, and it seems there's a couple queries where a
simple ANALYZE can "flip" the plan to a substantially different one.

I believe this happens mostly because of the LIKE conditions in a couple
queries, where the estimate depends on which values end up in the MCV.
The estimate can easily change 2x, which is enough to change the shape
of the plan. Of course, plan changes like this are expected and the cost
is not hugely different (so the timing is expected to be similar too).

But it's significant enough to invalidate the evaluation of the pushed
down filters if there's analyze in between. I've seen this to happen on
Q2, Q7, Q9, Q15, but it also depends on the scale etc. (with more flips
on larger data sets)

I think we need to be careful about comparing timings only with the same
stats, i.e. without an ANALYZE in between. I wonder if we could use the
export/import of stats introduced in PG18 to stabilize this. Increasing
the statistics target to 10000 seems to (mostly) solve this.

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

Understood, makes sense. Let's take some time to review each others
patches, and then we can agree which open questions to work on next.

regards

--
Tomas Vondra