Hi Tomas, Five planner comments on v9, and a correctness check -- I went looking for wrong answers rather than for speed, and did not find any.
1 a conditional rowcount living in pathlist, which every reader then has to
be taught to ignore -- and one still isn't; 0001 moves those paths out
2 the probe cost is charged on the wrong row count -- 0002
3 bloom_filter_pushdown_max_build_relids = 1 disables pushdown entirely
4 six arms of find_bloom_filter_recipient() are never taken
5 whether the pre-pass needs to estimate at all -- a question, not a patch
6 the correctness check: 480 runs with the filter off and on, 0 differences
Both patches are against 772c6d85e1, and every line number below is that
commit's. They are independent of each other.
1. A conditional rowcount is being kept in the list every part of the planner
reads.
apply_expected_filters() discounts a path's rows and cost for a filter that a
hash join above is expected to build and push down:
path->total_cost += probes * BLOOM_FILTER_PROBE_COST * path->rows;
path->rows = clamp_row_est(path->rows * surviving);
That rowcount is conditional. It is the number this path will produce if one
particular join above it is the one that survives into the plan, and only that
join can make it true. To every other consumer the path is simply reporting
the wrong count, and cheaper than it is.
pathlist has no way to say "wrong for you". optimizer/README:
To keep cost estimation rules relatively simple, we make an implementation
restriction that all paths for a given relation of the same parameterization
(i.e., the same set of outer relations supplying parameters) must have the
same rowcount estimate. [...] The restriction is useful in particular to
support pre-filtering of join paths in add_path_precheck. Without this rule
we could never reject a parameterized path in advance of computing its
rowcount estimate, which would greatly reduce the value of the pre-filter
mechanism.
So the exclusion cannot live in the data; it has to be restated at each reader,
and v9 restates it seven times: set_cheapest() (pathnode.c:296),
add_path() (677), add_path_precheck() (909), add_partial_path() (1054),
get_cheapest_path_for_pathkeys() (pathkeys.c:648),
get_cheapest_fractional_path_for_pathkeys() (705) and
generate_expected_filter_paths() (allpaths.c:1483).
36 functions read ->pathlist, and one of the seven is in fact missing:
get_cheapest_parallel_safe_total_inner() (pathkeys.c:729) comes right after two
helpers that do skip these paths, and does not. It returns the first
parallel-safe unparameterized path it finds, and the discount is what moves one
to the front of a cost-ordered list; over make check it hands one back six
times, always to the build side of a parallel join, where a pushed-down filter
never arrives. No expected output changes, so it is a mis-costed candidate
rather than a wrong plan today, and a guard there closes it.
PostgreSQL has met this shape before. A partial path's rowcount is per-worker,
so it is not comparable with an ordinary path's either, and the answer was not a
predicate at each reader but a second list -- partial_pathlist, with its own
add_partial_path(). 0001 does the same:
List *filtered_pathlist; /* Paths expecting pushed-down filters */
with an add_filtered_path() that prunes within one filter set using add_path()'s
own comparison, required_outer axis included: a join path carrying filters can
be parameterized, and rowcounts across parameterizations are as incomparable
here as in pathlist. All seven guards then go away rather than gaining an
eighth -- those functions are no longer handed such a path -- and pathkeys.c
stops mentioning Bloom filters. optimizer/README gets a paragraph next to the
parameterization restriction, as it has for partial paths.
This is not free of hand-maintained rules either, just of smaller ones: the new
field has to be cleared wherever the existing path lists are, and the commit
message goes through where that is and what happens when you miss one. One
consequence worth flagging outside the patch: a CustomScan provider offering a
filter-expecting path must now call add_filtered_path() rather than add_path(),
or nothing will consume it.
0001 is 360 insertions, 287 deletions across 11 files. On its own make check is
248/248 and test_bloom_customscan passes; the 480-run differential in 6 comes
out identical setting by setting against plain v9, 197 engaged and 0 mismatches.
What it does not do: a merge join still cannot use a filter-bearing path as its
inner. It can already carry one on the outer side -- try_mergejoin_path()
propagates the filters and match_unsorted_outer() supplies the path -- but
serving the inner side needs more than a list, because
get_cheapest_path_for_pathkeys() takes a required_outer the caller knows,
whereas which filter set to ask for depends on a producing hash join that may be
several levels up. As your XXX there says, admitting them turns "pick the
cheapest sorted inner" into a search over inner/outer combinations. It also
does not remove enumerate_bloom_filter_build_relids(): the selectivity still
comes from the cardinality of {owner} + build_relids, which doesn't exist while
the scan path is being costed, and moving the paths doesn't make it available
earlier. That is 5 below.
This is roughly where you and Robert had got to:
> In a plan tree with many joins, pushing down the Bloom
> filtering (or other filtering) decision to the lowest possible level
> could drastically change the row count estimates, and thus the
> costing, for a whole bunch of intermediate nodes
The row counts do change, and for the multi-join case they have to. Keeping
those paths in their own list means the change stops being something the rest of
the planner has to be defended against.
2. The probe cost is charged on the post-qual row count.
The other line of apply_expected_filters():
path->total_cost += probes * BLOOM_FILTER_PROBE_COST * path->rows;
path->rows is baserel->rows, i.e. after the scan's own quals. The filter is
probed before them, in execScan.h:
if (node->ps.bloom_filters != NIL &&
!ExecBloomFilters(node->ps.bloom_filters, econtext))
{
ResetExprContext(econtext);
continue;
}
/*
* check that the current tuple satisfies the qual-clause
...
*/
if (qual == NULL || ExecQual(qual, econtext))
so the number of probes is baserel->tuples. The charge is short by the quals'
selectivity, and goes to zero as they get more selective while the probe count
does not move.
CREATE TABLE s_d1 (id int PRIMARY KEY, x int);
INSERT INTO s_d1 SELECT i, i % 10 FROM generate_series(1, 1200) i;
CREATE TABLE s_fact (k1 int, sel int);
INSERT INTO s_fact SELECT (i % 1200) + 1, i % 10
FROM generate_series(1, 120000) i;
VACUUM ANALYZE s_d1; VACUUM ANALYZE s_fact;
SET max_parallel_workers_per_gather = 0;
EXPLAIN (ANALYZE, TIMING OFF) SELECT count(*) FROM s_fact f JOIN s_d1 d1
ON f.k1 = d1.id WHERE f.sel = 0 AND d1.x = 1;
off (hash side elided, it is identical):
Aggregate (cost=2088.05..2088.06 rows=1 width=8) (actual rows=1.00 loops=1)
-> Hash Join (cost=22.50..2085.06 rows=1198 width=0) (actual
rows=12000.00 loops=1)
Hash Cond: (f.k1 = d1.id)
-> Seq Scan on s_fact f (cost=0.00..2031.00 rows=11980
width=4) (actual rows=12000.00 loops=1)
Filter: (sel = 0)
Rows Removed by Filter: 108000
on:
Aggregate (cost=2074.63..2074.64 rows=1 width=8) (actual rows=1.00 loops=1)
-> Hash Join (cost=22.50..2071.63 rows=1198 width=0) (actual
rows=12000.00 loops=1)
Hash Cond: (f.k1 = d1.id)
-> Seq Scan on s_fact f (cost=0.00..2045.97 rows=1198
width=4) (actual rows=12000.00 loops=1)
Filter: (sel = 0)
Rows Removed by Filter: 9
Bloom Filter 1: keys=(k1) expected=10.0%
checked=119990 rejected=107991 (90.0%)
2045.97 - 2031.00 = 14.97, which is BLOOM_FILTER_PROBE_COST -- cpu_operator_cost
* 0.5, so 0.00125 -- times the scan's estimated output, 11980. The line under
it says checked=119990: the probe happens on what the scan fetches, not on what
it returns, so the charge should be 150. (Those two figures move a little with
ANALYZE's sample; the identity does not.)
That is not academic here: the discount is what makes the planner take the
filter, and the filter loses. Both scans emit 12000 rows -- everything the
filter rejects, "sel = 0" would have rejected anyway -- so it buys 107991 fewer
integer comparisons and pays 119990 four-hash probes for them. The planner
makes it some 13 cheaper overall, and it runs slower:
enable_hashjoin_bloom = off min 8.856 ms median 9.104 ms
enable_hashjoin_bloom = on min 11.427 ms median 11.552 ms
(12 runs each, interleaved.) With the probes charged on tuples the scan is
some 135 dearer against some 28 saved at the join, and it would not be chosen.
Two ways to reconcile the model with the executor: charge on what is probed, or
move the probe after ExecQual. Which order is better depends on the filter's
selectivity against the quals', the same way qual ordering does, and either is
defensible -- but the cost model should describe the one the executor performs.
0002 takes the first, in each scan cost function, on the count it already has in
hand:
cost_seqscan, cost_samplescan baserel->tuples
cost_index, cost_bitmap_heap_scan tuples_fetched
cost_tidscan, cost_tidrangescan ntuples
create_filtered_scan_path() re-costs its IndexPath clone rather than adjusting
the copied costs; cost_index() recomputes only costs, so the indexclauses and
pathkeys it copied are reused as before. apply_expected_filters() stays for
CustomScan providers, whose paths core cannot cost, and its comment says what it
therefore cannot get right.
One regression plan changes as a result, and it is worth showing that the change
is the right way round: the fkest query in join no longer picks the filter, and
0002 updates join.out for it. fkest is 1000 rows, too small to time; scaled to
1M with the same ratios (x100 = x/100000, so the qual keeps a tenth), on v9:
enable_hashjoin_bloom = off 173.868 ms
enable_hashjoin_bloom = on 195.466 ms
The filter probes every tuple to avoid an integer comparison on the rows the
qual would have dropped anyway.
3. bloom_filter_pushdown_max_build_relids = 1 turns pushdown off entirely.
1 is the minimum the GUC accepts. With a 120k-row fact joined to a 1200-row
dim1 on dim1's primary key and WHERE d1.x = 1, at 1 the plan has no filter; at 2
the same query gets "Bloom Filter 1: keys=(k1)". The build side here is one
relation.
bloom_build_side_join_ratio() looks up the build side plus the owner:
relids = bms_copy(build_relids);
relids = bms_add_member(relids, rel->relid);
foreach (lc, build_sides)
{
SimpleRelOptInfo *rel = (SimpleRelOptInfo *) lfirst(lc);
if (bms_equal(rel->relids, relids))
{
nrows = rel->rows;
break;
}
}
return Min(1.0, Max(0.0, nrows / rel->rows));
and build_sides is capped at bloom_filter_pushdown_max_build_relids relations:
for (level = 2; level <= bloom_filter_pushdown_max_build_relids; level++)
so a K-relation build side needs level K+1. At 1 the two-relation set is never
enumerated, nrows stays DBL_MAX, and the ratio is 1.0 for every candidate. At
the default of 3 the largest build side that gets a real estimate is two
relations, not three -- while guc_parameters.dat says
short_desc => 'Maximum number of base relations in an enumerated
hash join bloom filter build side.',
This came in with your 0014; before it the function did not consult the
enumeration at all, but multiplied the build relations' own row estimates out
of root->simple_rel_array[], so the GUC could not affect it. Same query, same
data:
your 0001-0013, max_build_relids = 1 -> filter present
your 0001-0021, max_build_relids = 1 -> no filter
max_build_relids = 2 -> filter present
Cosmetic, in the same function: the foreach declares SimpleRelOptInfo *rel,
shadowing the RelOptInfo *rel that the return statement then uses. It reads
correctly, but it made me look twice.
This is the same coupling as 1, in its narrowest form: a budget meant to bound
the search decides the value of an estimate. "not enumerated" and "not
selective" both come back as 1.0, and the caller cannot tell them apart.
4. Six arms of find_bloom_filter_recipient() are never taken, and the rescan
case would need an answer before they could be.
case T_Sort:
case T_IncrementalSort:
case T_Material:
case T_Memoize:
case T_Unique:
case T_Limit:
return find_bloom_filter_recipient(outerPlan(plan), target_relid);
nodeHashjoin.c:
* added to EState.es_bloom_producers, so that the rescans etc. (filter
* freed + recreated when the hash table is destroyed and rebuilt) are
* transparent to the consumer.
ExecReScanMaterial():
else
tuplestore_rescan(node->tuplestorestate);
With an elog in those six arms, on the non-NULL return only, make check, the
CustomScan module, the 480-run differential and four shapes built to aim at them
all give 0 -- and still 0 with both patches applied, which admit more
filter-bearing paths to join generation. A Sort/Limit/Unique between the join
and the scan comes with a subquery boundary, and Memoize/Material landed on the
build side instead. So the arms look dead today; if they are meant to become
live, the rescan case needs an answer first, and until then an Assert would say
what is intended.
5. Does the pre-pass need to estimate at all?
A question rather than a proposal. For most filters the pre-pass estimates a
number the planner is about to compute properly anyway.
bloom_build_side_join_ratio() says what it wants:
* We approximate the surviving fraction as the estimated cardinality of the
* join of {owner} + build_relids divided by the owner's cardinality.
Whenever the join that realizes a filter has the owner as its whole outer side,
that quantity is joinrel->rows / outer_rel->rows, and final_cost_hashjoin() has
both -- set_joinrel_size_estimates() has just run on the real joinrel, with the
real statistics. Instrumenting the realization site in
compute_join_expected_filters(), the fraction with
bms_num_members(outer_relids) == 1 is:
make check, 248 tests 20348 of 25740 realized filters (79%)
40 generated star/snowflake 2732 of 5402 (51%)
(the make check counts move a little with ANALYZE's sample; the fraction does
not.) For the rest the owner sits below at least one more join, the
intermediate joins physically see fewer rows, and the rowcount does have to
move.
I am not proposing to special-case the first group: whether a filter lands in it
depends on the join order finally chosen, so the pre-pass -- which runs before
join ordering -- cannot skip the work, and two costing routes for one feature
seems worse than the duplication it saves. What I would ask is whether the
pre-pass could defer to the real estimate where one is available, because it is
a second implementation of join planning -- simple_join_is_legal(),
simple_build_joinrel_restrictlist(), simple_set_joinrel_size_estimates() and a
dozen more shadowing their originals across joinrels.c (+674), equivclass.c
(+271) and relnode.c (+164), 1109 lines -- and shadows drift. 3 above is a bug
in exactly that machinery.
6. Results check, no differences.
40 generated star/snowflake queries over a 120k-row fact table and five
dimensions: inner/left/right/semi/anti, one to three dimensions, NULL-bearing
and text and bigint keys, GROUP BY/HAVING, DISTINCT, ORDER BY + LIMIT,
materialized CTEs, subqueries in FROM. Each run with enable_hashjoin_bloom off
and on under twelve settings: default; work_mem 64kB and 256kB;
bloom_filter_pushdown_max 1 and 10; threshold 0.0 and 1.0; max_build_relids 1
and 100; max_build_sets 1; parallel with and without a small work_mem.
480 runs, 197 with a filter in the plan, 0 differences in rows returned.
Where the 197 fall, by shape:
INNER 13 queries 156 runs 90 with a filter
SEMI 9 108 64
LEFT 11 132 43
RIGHT 5 60 0
ANTI 2 24 0
The two zeroes read as semantics rather than a gap: a Bloom filter can only
discard a probe row that has no match on the build side, and that is exactly the
row an anti join has to keep and the one a right join has to emit null-extended.
Of the 283 runs with no filter, threshold = 1.0 and max_build_relids = 1 account
for 40 each (the latter is 3 above) and the two parallel settings for 38 and 39.
Not covered, per your (3) and (4): a partitioned fact table gets none at all.
Those runs are all single-batch -- the dimensions are too small to spill. A
separate set for batching, with a 300k-row build side and probe keys spread over
10M so the filter stays selective, reaches Batches: 8 with
"rejected=486622 (97.3%)". Eight shapes on those tables
(inner/left/semi/anti/two build sides/GROUP BY/DISTINCT) at work_mem 64kB,
128kB, 256kB and 1MB: 32 runs, 23 with Batches > 1 and a filter, 0 differences.
Four cases checked separately, all four with a filter in the plan and all four
identical with it off and on: rescan (the hash side rebuilt for every outer row,
via a correlated subquery); cross-type, an int4 probe key against an int8 build
key; numeric, '<i>.00' on the build side against '<i>.0' on the probe side --
equal, different byte representations; and float8, -0.0 on the build side
against 0.0 on the probe side.
make check on the v9 branch alone is 248/248 on 7a0299a134; with 0001 it is
still 248/248, and 0002 keeps it there by updating join.out for the fkest plan
change discussed in 2.
Thanks,
Rui
0001-Keep-filter-expecting-paths-out-of-pathlist.patch
Description: Binary data
0002-Charge-the-Bloom-filter-probe-cost-on-the-rows-actua.patch
Description: Binary data
