Re: hashjoins vs. Bloom filters (yet again)

Hi Matheus,

v10 applies cleanly to 31c002aa8978 (master as of Aug 21), builds
warning-free, and make check is 248/248, with pg_plan_advice,
pg_stash_advice, postgres_fdw and test_bloom_customscan green as well.
The three points you took from my last mail check out: the seqscan
surcharge is now exactly BLOOM_FILTER_PROBE_COST times the tuples
fetched, and the losing filter from that mail is no longer chosen;
max_build_relids = 1 produces filters again, and the default realizes a
three-relation build side; the five Asserts and T_Limit's unconditional
NULL are in, and nothing fired across the runs below (cassert build).

Results check, no differences -- run on v10 as posted, and again with
the attached patch applied. 40 star/snowflake queries
(inner/left/right/semi/anti, one to three dimensions, int/bigint/text
and NULL-bearing keys, aggregates, DISTINCT, ORDER BY + LIMIT, CTEs,
subqueries, UNION ALL) x 12 GUC settings (work_mem, threshold,
pushdown_max, max_build_relids, max_build_sets, parallel), each with
enable_hashjoin_bloom off and on: 480 comparisons per run, 0
differences in rows returned (a fresh query set, not comparable with
my v9 mail). Also identical off and on, both times: a batching set
(300k-row build side, Batches 4-16), a correlated
subquery that rebuilds the hashtable and filter on each of its 200
executions (the shape the new generation counter is for), the
cross-type/numeric/float8 cases from last time, and DML -- UPDATE
FROM, DELETE USING, MERGE, a conditional UPDATE, applied to two
identical 200k-row copies with the filter off vs on, EXCEPT ALL empty
in both directions.

On the snowflake trade-off you and Tomas discussed -- exact matching
fixing the estimate but the fact losing its filter -- the attached
patch is a proposal that keeps every realizable alternative alive
instead of preferring either build-side size. Your two-pass
description locates the problem exactly; the subset assumption
survives in two places, and each needs its half of the fix:

- The de-duplication in find_interesting_bloom_filters() prunes
subset-related candidates against each other on selectivity, keeping
the smaller build side unless the larger one discards strictly more.
That rule was sound under subset matching: the smaller build side
was realizable at every join the larger one was, so the more
selective of the two dominated. Under exact matching the two are
realized at different joins, and which of them ever appears as an
inner depends on the join order chosen later; a less selective
candidate can be the only one a given order can realize, and a
weaker filter still beats none. Selectivity alone cannot establish
dominance between them, so the patch drops only exact duplicates and
keeps every candidate. (Keeping just the equal-selectivity pairs
would also fix the suite, but leaves a rule that cannot say why ties
are special.)

- find_bloom_filter_combinations() emits a single combination, so even
with the candidates kept, only one of them gets a path. The patch
emits one extra combination per filter skipped on a build-side
conflict: the same greedy pass, seeded with the skipped filter,
duplicates dropped. (Filters dropped by the pushdown_max cap alone
get no alternative -- they conflict with nothing, so the primary
combination realizes fine without them. That keeps the star suite
untouched: its dimensions share no join clause or ordering
restriction, so no multi-dimension build side is enumerated, every
candidate is a disjoint singleton, and no conflicts arise. An
earlier draft that seeded cap-dropped filters too made one star plan
swap its third filter on a 0.07% cost tie.)

Each combination becomes its own scan path, and a path whose filter a
join order cannot realize is already rejected at that join by the
bms_equal check, so the join search keeps exactly the realizable
alternative. No estimate diverges: every candidate's selectivity is
still computed over its own build_relids, and the filter that runs is
the one that was costed.

I went this way rather than "prefer larger build sides" because which
candidate is realizable depends on the join order. On a fact -> d1 ->
d11 chain with d11 joined 1:1 and unrestricted, {d1} and {d1,d11} tie
exactly: left to itself the planner picks the bushy plan and realizes
{d1,d11}; under join_collapse_limit = 1 (which the star suite itself
runs under) the same query goes left-deep and realizes {d1} at the
fact-d1 join. Keeping only the larger candidate loses the left-deep
plan's filter the same way keeping only the smaller one loses the
bushy plan's today. Keeping both lets the costing make the call.

With the patch the snowflake suite regains all six filter instances it
lost in v10 (17 in v9, 11 in v10, 17 again); star and the simple suite
are unchanged. The other expected outputs that move all read as the
right direction, and show where the wider candidate set bites: in
join.out the fkest three-way join filters f3 from the pre-joined
{f1,f2}, and t6 takes a filter from {t4,t5}; in returning.out the
join-view UPDATE builds its filter on the joined {foo_1,foo_2}, and
joinme_1 takes one from {foo_1,joinme,foo_2}; in the plan/stash advice
tests the fact scan carries the two singleton filters (dim1_id) and
(dim2_id) under the plain join order, where v10's only filter-bearing
option was the cross-product {d1,d2} build side hashed behind a
nestloop; and two MERGE result listings without ORDER BY change row
order as the MERGE's own join plan does. make check with the patch is
248/248 with the regenerated outputs; the results check above covers
the rest.

The price is planning time, and it depends on the shape. Every
alternative is a scan path, and every scan path is a join input at
every level of the search, so the cost follows the number of tied
candidates: none in a pure star, one per level in a linear dimension
chain (flat in my measurements up to six levels), and most on a
dimension that hangs k unrestricted sub-dimensions. That last shape is
the bad case: the build side has to contain the dimension itself, so it
takes one of the max_build_relids slots, and every group of up to
max_build_relids - 1 sub-dimensions beside it is another candidate with
the same keys and the same selectivity. Planning time in ms on it,
cassert build, all GUCs at their defaults except the two swept, median
of nine EXPLAINs ("off" is the same code path in both versions):

bloom off v10 on patch on
k=4 max_build_relids=3 1.4 1.6 2.0
max_build_relids=5 1.4 1.6 2.3
k=6 max_build_relids=3 3.7 4.5 11.1
max_build_relids=5 3.8 4.7 14.4
k=8 max_build_relids=3 4.3 4.9 11.9
max_build_relids=5 4.1 5.0 12.0

What that buys is the filter this patch is about: at k=6 the fact's
scan carries no filter on v10 and gets one from the pre-joined
{d1,ch1,ch2} with the patch, exactly the snowflake case, so the 2.4x is
the cost of not losing it. Raising max_build_relids adds little and
stops adding anything at k=8, because
bloom_filter_pushdown_max_build_sets truncates the enumeration at 100
sets before the extra levels can produce candidates. Whether that is
an acceptable price for the fact's filter is your call; a cap on the
number of alternative combinations per relation would be a one-line
knob.

The tied candidates also point at what I think is the real answer,
though it is beyond this patch. They build the same filter -- same
keys, same selectivity, same rows rejected -- and differ only in which
inner they can be realized at. Realizing a candidate at any inner
whose join ratio equals the candidate's own (subset matching behind a
selectivity guard) would give one path per distinct filter instead of
one per realizable inner, keep the estimate honest (the guard is
exactly the divergence exact matching was introduced to stop), and
remove the lost filter and the extra paths together. It needs the
ratio for the actual inner at realization time, which the enumeration
only carries up to max_build_relids + 1 relations, so it is a bigger
change than I want to propose blind.

One last thing, unrelated to the filters themselves: the
test_bloom_customscan module has no .gitignore, so after a run of its
tests the generated log/ and results/ directories show up in git status.
All the other modules under src/test/modules except test_wait_lsn carry
one listing /log/, /results/ and /tmp_check/.

Thanks,
Rui