Re: hashjoins vs. Bloom filters (yet again)

On Fri Jul 31, 2026 at 9:52 AM -03, Tomas Vondra wrote:
>> 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.
>

Yeah, I think that it's a good idea. Do you mind sharing on github?

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

Good to know, thanks.

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

Great, so I think that we are on the same the page regarding this topic.
This change also surprised me, I wouldn't expect such difference. I'm
wondering if this size should be configured using a GUC instead of hard
code value. For development it may help to explore other scenarios, but
for the user perspective I'm not sure. What do you think?

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

Ok, make sense, I agree.

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

Yeah, my machine seems much slower compared with your. I'm using a
MacBook Pro M3 with debug symbols and asserts enabled. I tried to not
make the machine busy while running the tests to not effect the
execution time but it seems it didn't help to much.

> 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 just pick the most interesting ones. I didn't execute all TPC-H
queries due to long time running. My schema have a bunch of indexes, so
I think that this enable more queries to use the filters.

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

I'll try to play with your scripts and also try to create my scripts to
share my state (I'm running my tpch database for a while and I may
already manually change something that I don't remember that may cause
such differences).

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

Interesting finding.

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

Yeah, I think that it may help, or at least a script that prepare the
schema to compare the timings (with same indexes, statistics target,
etc) properly.

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

Sounds a good plan.

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