Re: hashjoins vs. Bloom filters (yet again)

On 7/20/26 23:31, Matheus Alcantara wrote:
> On Mon Jul 20, 2026 at 4:17 PM -03, Tomas Vondra wrote:
>>> 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)?
>>
>
> I instrumented generate_expected_filter_paths() to count, per base rel,
> the eligible base paths, the filter combinations, and the pathlist
> length before/after the add_path() calls. Running the star-schema
> queries for the fact_sales scan:
>
> N basepaths combinations new paths pathlist before -> after
> 2 3 3 9 5 -> 14
> 3 4 7 28 7 -> 35
> 4 5 13 65 9 -> 74
> 5 6 23 138 11 -> 149
> 6 7 36 252 13 -> 265
>

Do I understand correctly this is for paths on the fact_sales, and there
are no new paths on the other relations (dimensions)?

> About your question: yes, add_path() does cost-compare paths that carry
> the same filter set - they go through the normal cost/pathkeys/rows
> domination like any other pair. What it deliberately does not do is
> compare across different filter sets: add_path bails out as soon as
> expected_filters differ, on the grounds that a scan feeding filter A and
> a scan feeding filter B serve different parent joins and aren't
> comparable. I think that's the right call, pruning by cost across filter
> sets seems wrong, since a more expensive scan carrying a better filter
> can pay off at the join above.
>
> The consequence, though, is that add_path prunes essentially nothing
> here. The surviving count is basepaths * combinations exactly — 0 pruned
> in every single query. The fact_sales pathlist goes from N+1 base paths
> to (N+1)*combinations - ~20x at N=6 - and every one of those extra scan
> paths then has to be considered as a join input at every level, which I
> think that is where the superlinear planning time comes from.
>

Right, that explanation seems plausible.

I'm not sure if you tried with the v5 or v6 patches, but I assume the
join stuff in v6 would make this somewhat worse due to generating even
more candidate filters. Well, maybe not for starjoin schemas, but for
snowflake.

> So it seems to me that early elimination has to happen before add_path, in the
> candidate/combination generation.
>

Yeah. Some heuristics to prune paths more aggressively. I this is what
the "heuristic 4" in the paper is about. That says:

If multiple Bloom filters are candidates on the same relation
(originating from different join clauses), then we create Bloom
filter scan plans with all possible Bloom filter candidates applied
as opposed to testing out sub-plans with various subsets of Bloom
filter candidates applied. In other words, we apply all valid
candidate Bloom filters on a base table simultaneously, as an
additional heuristic to limit the search space (Heuristic 4).

AFAICS that says they consider all filters at once, no combinations. I'm
not sure what they do about joins, maybe they consider only the most
selective filters (for larger joins). That'd prefer "more bushy" plans.

We'll have to experiment with this a bit, I guess.

regards

--
Tomas Vondra