Re: hashjoins vs. Bloom filters (yet again)

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