Re: hashjoins vs. Bloom filters (yet again) - Mailing list pgsql-hackers

On 31/07/26 09:52, Tomas Vondra wrote:
> Understood, makes sense. Let's take some time to review each others
> patches, and then we can agree which open questions to work on next.
> 

v9-0001-PoC-hashjoin-bloom-filter-pushdown:

1. In create_hashjoin_plan, try_push_bloom_filter calls
find_bloom_filter_recipient() to locate the scan in the outer subtree, 
and if
it returns NULL it just return without building anything, even though 
the path
row estimate was already reduced by the filter selectivity during 
costing, so
if the recipient isn't reachable we've choose a plan because of a filter
benefit that then never materializes.

find_bloom_filter_recipient() does return NULL for parallel-aware 
recipients
but I'm wondering if it can also return NULL for non parallel cases, even
though I couldn't construct a serial plan that reaches a NULL 
recipient. Not
sure if we need a guard for such case (e.g assert).

2. I think that the filter selectivity can diverge from the filter that's
actually built. IIUC the row-estimate reduction for a realized filter 
comes
from f->selectivity, computed in find_interesting_bloom_filters from only
f->clauses. But try_push_bloom_filter builds the physical filter from 
all of
hj->hashkeys. When the inner side carries more keys/relations than
f->build_relids, the filter that runs and the selectivity that was 
costed are
computed from different key sets. Results stay correct, but the
cardinality/cost on the path, and the expected= value in EXPLAIN, 
won't match
what the filter actually does.

Consider f JOIN d1 ON f.k1=d1.k1 JOIN d2 ON f.k2=d2.k2 AND d1.a=d2.a 
where only
d1 is a selective filter source. If the planner forms d1 JOIN d2 as the
hash-join inner and realizes the single-relation candidate f={d1} (whose
selectivity was estimated from f.k1=d1.k1 alone, since
compute_join_expected_filters realizes on bms_is_subset(f->build_relids,
other_relids)), try_push_bloom_filter still copies all of 
hj->hashkeys, so the
physical filter is keys=(f.k1, f.k2). The row estimate was credited for a
one-key filter while a two-key filter runs.

3. Adaptive state and counters seems that don't seem to be reset across
rescans. ExecReScanHashJoin clears the producer's bloom_filter 
pointer, but the
consumer's BloomFilterState persists. After a rescan the producer 
rebuilds a
fresh filter while the consumer may still be in "sampling"/disabled 
mode from
the previous iteration, so it under-probes the new filter initially.

Minor / cosmetic:
- ExecBloomFilterHash returns 0 from a bool function (and its "XXX 
correct?"
   NULL-key pass-through I think that is in fact correct since a NULL 
key can't
   be in the filter, and letting it through is safe).

- BloomFilterState->nkeys is unused.

- A few typos in the commit message / comments: "futehr", "gest",
   "downn", "fproducer", "The effectivity of a filter is depends".

----

v9-0004-Make-sure-Gather-nodes-don-t-have-filters:

1. I'm wondering if we also should add the guard on
generate_useful_gather_paths().

---

v9-0007-Properly-plan-filters-built-on-joins:

Most of this commit changes e.g bloom_build_side_join_ratio and the 
selectivity
estimation is reworked by later commits (the 
bloom_build_side_join_ratio rework
and the FK-aware estimation), so I think that we may consider 
squashing these
commits but I didn't look yet deeply to see if it's really makes 
sense. What do
you think?

---

v9-0010-Fix-handling-of-filters-in-add_partial_path:

This is a bug fix (add_partial_path sorting), and I think it should be 
squashed
rather than kept as a standalone commit. The fix itself seems correct 
to me: it
gates cost-domination on expected_filters_equal so paths with 
different filter
sets don't prune each other, and it orders the list by filter-count 
first so
linitial(partial_pathlist) is always filter-free.

I think that it should be squashed into 0002, which is the commit that 
first
puts filters on partial paths and therefore creates the requirement that
add_partial_path keep a filter-free path at the front.

There's also an ordering/bisect hazard that makes this more than 
cosmetic: 0004
adds Assert(cheapest_partial_path->expected_filters == NULL), whose
precondition IIUC is exactly what this fix establishes.

---

v9-0011-Fix-filters-on-joins-in-compute_join_expected_fil:

Also a bug fix (compute_join_expected_filters), and also a squash 
candidate.
The fix also seems correct to me.

I think that it should be squashed into 0007. The defect only exists 
once joins
can be build sides. The commit message itself notes the code "worked 
fine for
singleton build relids." Singleton build sides come from 0001; 
multi-relation
build sides come from 0007, so it seems to me that 0007 is the commit that
makes the defect reachable and should arrive correct.

---

This is what I have for now, I plan to review the remaining patches 
soon. I can
also work on this comments that I've made and propose a v10 if you 
agree with
them.

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