Re: hashjoins vs. Bloom filters (yet again)

On 7/21/26 19:30, Matheus Alcantara wrote:
> ...>>> 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.
>

Yeah, I think you're right the bloom_filter_pushdown_max may compensate
for considering additional build sides.

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

Right, that's the point I was trying to make. I was not very clear about
combining filters from the v5 and v6 patches.

regards

--
Tomas Vondra