Re: hashjoins vs. Bloom filters (yet again)

On Tue Jul 28, 2026 at 12:29 PM -03, Tomas Vondra wrote:
>
>
> On 7/28/26 16:27, Matheus Alcantara wrote:
>> On Tue Jul 28, 2026 at 10:32 AM -03, Tomas Vondra wrote:
>>> Hi,
>>>
>>> Here's a v8, with a bunch of changes on top of v7 from last week. The
>>> changes are related mostly to generating the build join relids, so
>>> hopefully it's not too disruptive w.r.t. your work on selecting filter
>>> combinations, building paths etc.
>>>
>>
>> I was just about to send a v8 with the building paths changes from v5
>> and the heuristic 4 from the SIGMOD paper with some benchmark results.
>> I'll work to port it to work on top on your v8 but I'll share the
>> benchmark results because I think that it's interesting to know.
>>
>
> Yeah, sorry about that.
>

No problem!

>> Benchmark results:
>>
>> [ ... ]
>
> It's also possible some of the differences are due to differences in
> schema, i.e. we may have different indexes, foreign keys, ... and that
> may lead to different plans.
>
>> 4. Q9 is too noisy on my machine to conclude (the OFF baseline alone
>> swings 180-290s between runs). While looking at it, though, I noticed a
>> possible estimation issue:
>>
>> Q9 builds a composite, multi-relation filter - (l_suppkey, l_partkey)
>> from partsupp JOIN part. Its selectivity is estimated at ~95 surviving
>> lineitem rows (of 60M) when it actually passes 3.28M - a ~35,000x
>> underestimate - which pushes the planner to a nested loop with an index
>> scan on orders (costed for 95 loops, runs 3.28M). It comes out of
>> find_interesting_bloom_filters for multi-rel build sides, and vacuum
>> analyze doesn't change it, so it looks like a formula issue rather than
>> stale stats. Restricting to single-relation build sides
>> (bloom_filter_pushdown_max_build_relids = 1) avoids it. I'm not sure how
>> much this contributes to the Q9 noise, but the estimate itself looks
>> wrong.
>>
>
> I believe this is the estimation issue I mentioned in my post, when
> explaining the changes in 0013 and 0014. Do you see the poor estimate
> even with "my" v8?
>

Good catch on the schema - I was missing FK constraints. Adding them
seems to make things look better.

With the FKs present, Q9 is now a win rather than the regression I
reported: ON vs OFF is 55.5s vs 171.5s, ~3x faster, and stable across
three runs. And the join cardinality estimates are now good - lineitem
JOIN (partsupp JOIN part) estimates ~1.79M (actual 3.27M), instead of
the ~70 I had before. So I think that 0013/0014 is doing their job on
the join-rel size once the FK exists. I'll port my changes to work on
top of this v8 and let's see if the improvement remain.

The one thing that seems it's not fixed is the filter's own scan-level
selectivity: (l_suppkey, l_partkey) still estimates rows=71 on the
lineitem scan (of 60M) while 3,281,805 rows actually survive (94.5%
rejected). That rows=71 drives a nested loop into orders (3.28M index
probes, costed for 71):

Nested Loop (rows=71) (actual rows=3281805)
-> Seq Scan on lineitem (rows=71) (actual rows=3281805)
Bloom Filter 1: keys=(l_suppkey, l_partkey) rejected 94.5%
-> Index Scan using orders_pkey on orders (loops=3281805)

It's still 3x faster than no filter because the filter discards 94.5% -
so it "happens to pick the right plan", but I think that it's on luck
rather than a correct estimate. So it looks like the FK rework fixed the
join-rel cardinality, but the filter's selectivity still comes from the
non-FK-aware path.

>> Sorry for the delay on posting this, I was trying to improve the
>> benchmark numbers but didn't managed do it properly yet, so I decided to
>> post as is anyway. I'm attaching my v8 (which is based on your v7) just
>> for the record but I'll read your new v8 patchset to try to share some
>> feedback and also port my current changes to work on top of your v8,
>> let's see if we can get better benchmark results.
>>
>
> Not sure why you're apologizing, It's a complex feature / research,
> progress takes time. I don't think we have set any deadlines or
> anything. I'm grateful I can collaborate on it with someone.
>

Yeah, not sure either, I think that I just wanted to post it earlier, but
anyway I agree that progress takes time give the complexity and I'm
happy to collaborate with this work.

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