Re: hashjoins vs. Bloom filters (yet again)

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

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.

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

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