Re: hashjoins vs. Bloom filters (yet again)

On Mon Jul 20, 2026 at 7:31 PM -03, Tomas Vondra wrote:
> 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)?
>

Yes, you are correct. Only fact_sales gets new paths. The dimensions are
pure build sides, nothing above them pushes a filter onto a dimension's
own scan, so find_interesting_bloom_filters returns nothing for them and
no filtered paths are generated.

The snowflake query is the exception. dim_product also gets filtered
paths, because it sits in the middle, it receives a filter built from
dim_category while itself being a build side for the fact join.

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

I've executed on top of v5 patches, but now I've also executed on v6,
see the results:

N filters basepaths combos generated pathlist before->after
2 2 3 3 9 5 -> 14
3 3 4 7 28 7 -> 35
4 3 5 7 35 9 -> 44
5 3 6 7 42 11 -> 53
6 3 7 7 49 13 -> 62

v6 does generate more candidate filters, but IIUC
enumerate_bloom_filter_build_relids() generate multi relation build
sides (e.g. product JOIN category as the source of a filter on the fact)
that v5 never considered. But those extra candidates get de-duplicated
and then capped at bloom_filter_pushdown_max most selective. So the
surviving filter count stays <= 3 regardless of how many the join
enumeration proposes.

But I think that what you was saying is v6 with v5-0005 which generate
more candidate filters without capping at bloom_filter_pushdown_max. I
didn't look at very deep on v6 patchset yet but I've tried to implement
v5-0005 on top of v6 (by mosting copy and pasting with some required
changes) and I think that you are correct. For startjoin schemas the
result was the same from v5 but for the snowflake case the paths
generated was a bit higher for the fact_tables, 120 generated paths
compared with 72 on v5.

I'll look more deep on v6 changes and I'll share more soon.

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