Re: hashjoins vs. Bloom filters (yet again)

On 7/20/26 20:17, Matheus Alcantara wrote:
>> ...
>>
>> 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.
>

Seems like a reasonable example to test. I'd have started with something
completely synthetic, but that doesn't matter.

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

Yeah, that's not great. It's probably even worse with the support for
filters on joins.

Wwe'll need to investigate a bit where does the extra time come from,
and do something about it.

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

Possibly. I think it'd be good to know how many new paths we actually
got, and see if we can eliminate at least some of them early (I don't
recall - does add_path compare costs for paths with the same filters)?

regards

--
Tomas Vondra