Hi Alexanda,
Thanks for the v9 patch! Here's a bunch of review comments. I think
0001, 0002 and 0004 are not far from committable. I still need to do
more review on 0002, but I don't expect major issues.
I'd move 0004 right after 0002, so that we can get it out of the way. It
seems more like a consequence of 0002 than related to join stats.
0001 - Fix memory leak in make_build_data()
- I think this is fine, ready to go. It should have been addressed, per
the XXX comment. Can it be a problem in backbranches too, or is it
somehow more serious with join stats? Or did you just notice the XXX
comment? I'm asking because of backpatching.
0002 - Unify extended statistics columns and expressions
I think there's a couple issuses.
- The psql describe code still checks (sversion >= 190000), but that's
now wrong, it needs to check 200000. A simple rebase omission, but
it can lead to failures on 19.
- This replaces simple O(1) bitmapset checks with list walks in a couple
places. I know we already tested how much more expensive this is, but
I keep wondering if it might get worse with enough statistics and/or
if we end up increasing the limit on statistics columns.
I'm not saying we should not do this, or that the patch is wrong, but
maybe there's a data structure / representation we could use to save
on the overhead. Not sure, just spitballing.
0003 - Add join MCV statistics for selectivity estimation
- I think it's not strict enough when validating the join clauses.
Consider this example:
----
create table a (x int, y int);
create table b (p int, q int);
create statistics on a.x, a.y from a join b on (a.x = a.y);
----
This leads to a crash in CreateStatistics(), in this part
indexed_var = (lvar->varno > rvar->varno) ? lvar : rvar;
Assert(indexed_var->varno > 1);
Whic is not surprising, because the "join clause" is not actually
connecting the two relations, it only references "a". I suppose this
should be rejected in transformStatsStmt(), in stxjoinconds checks.
Also, looking at the error wording:
ERROR: join statistics require a single equality join condition per
pair of tables
Won't that be a bit confusing once we start supporting larger joins?
It seems to suggest we require a join clause for each pair, but I
don't think we need that - it should be enough to have enough clauses
to have connected join graph, no?
(I don't recall if/how the sampling paper deals with cyclic graphs.)
- This seems wrong:
Oid rel_oids[STATS_MAX_DIMENSIONS + 1];
STATS_MAX_DIMENSIONS is the number of dimensions, not the number of
relations. We can have joins with no columns in the statistic, so we
could exceed this limit.
Right now it works, because we only allow 2-way joins, but we want to
relax that. Maybe we want to have a similar limit, in which case we
should have a separate constant with an appropriate name.
- I think the sampling has issues with partitioned tables. Consider
this example:
CREATE TABLE t1 (id int);
CREATE TABLE t2 (id int, val int) PARTITION BY RANGE (id);
CREATE TABLE t2_1 PARTITION OF t2 FOR VALUES FROM (0) TO (100);
CREATE TABLE t2_2 PARTITION OF t2 FOR VALUES FROM (100) TO (200);
CREATE INDEX t2_idx ON t2 (id);
INSERT INTO t1 SELECT g FROM generate_series(1, 199) g;
INSERT INTO t2 SELECT g, g % 10 FROM generate_series(1, 199) g;
CREATE STATISTICS s (mcv)
ON t2.val
FROM t1 JOIN t2 ON t1.id = t2.id;
ANALYZE t1;
which crashes in sample_index() like this:
Program received signal SIGSEGV, Segmentation fault.
table_index_fetch_begin (rel=0x758dddcb5600, flags=0)
1258 return rel->rd_tableam->index_fetch_begin(rel, flags);
because this is sampling t2, which is a RELKIND_PARTITIONED_TABLE,
and as such has rel->rd_tableam = NULL.
I suppose the sampling needs to do something smarter for partitioned
tables, but I'm not sure how much more complex, or if it's worth it.
I suppose it might need to do "manual Append" or something like that.
It could be quite complex for nested partitioning schemes.
Maybe it'd be better to just use SPI for this. That is, generate a
regular query, and let the planner/executor handle the partitioning
part. Just a random thought, I haven't tried fixing the current code
or implementing the SPI thing.
- I think pg_stats_ext and pg_stats_ext_exprs need fixes to check RLS
for all relations, not just for the anchor one. Otherwise the join
MCV could show stats the role should not be able to see.
Example:
----
CREATE ROLE test_rls_owner;
CREATE SCHEMA test_rls AUTHORIZATION test_rls_owner;
SET ROLE test_rls_owner;
CREATE TABLE test_rls.anchor (id int, filler int);
CREATE TABLE test_rls.secret (id int, secret text);
INSERT INTO test_rls.anchor SELECT g, g FROM generate_series(1, 100) g;
INSERT INTO test_rls.secret
SELECT g, CASE WHEN g <= 50 THEN 'secret-1' ELSE 'secret-2' END
FROM generate_series(1, 100) g;
CREATE INDEX test_rls_secret_id_idx ON test_rls.secret (id);
-- nobody can read any rows
ALTER TABLE test_rls.secret ENABLE ROW LEVEL SECURITY;
ALTER TABLE test_rls.secret FORCE ROW LEVEL SECURITY;
CREATE STATISTICS test_rls.test_stat (mcv)
ON anchor.filler, secret.secret
FROM test_rls.anchor JOIN test_rls.secret ON anchor.id = secret.id;
ANALYZE test_rls.anchor;
-- owner cannot read anything from secret table ...
SELECT count(*) AS visible_secret_rows FROM test_rls.secret;
-- ... but its values show up here
SELECT exprs,
count(*) FILTER (WHERE v LIKE 'secret%') AS leaked_mcv_items,
min(v) FILTER (WHERE v LIKE 'secret%') AS example_leaked_value
FROM pg_stats_ext, unnest(most_common_vals) AS v
WHERE statistics_schemaname = 'test_rls'
AND statistics_name = 'test_stat'
GROUP BY exprs;
RESET ROLE;
DROP SCHEMA test_rls CASCADE;
DROP ROLE test_rls_owner;
----
AFAIK the regular privileges don't have similar issue because the
view definition has unnest(s.stxjoinrels) with a pg_has_role check,
so I guess that should do a similar check for RLS.
- It seems a bit unfortunate that creating statistics on a join, with
tables owned by different users, this restricts what the owner of the
non-anchor tables can do. Consider a statistics on t1-t2 join, owned
by u1 and u2.
----
CREATE ROLE u1;
CREATE ROLE u2;
GRANT USAGE, CREATE ON SCHEMA public to u1;
GRANT USAGE, CREATE ON SCHEMA public to u2;
SET ROLE u2;
CREATE TABLE t2 (a int, b int);
CREATE INDEX ON t2 (a);
RESET ROLE;
GRANT SELECT ON t2 TO u1;
SET ROLE u1;
CREATE TABLE t1 (a int, b int);
CREATE STATISTICS s (mcv) ON t1.a, t1.b, t2.a, t2.b
FROM t1 JOIN t2 ON (t1.a = t2.a);
ANALYZE t1;
SET ROLE u2;
DROP INDEX t2_a_idx;
ERROR: cannot drop index t2_a_idx because other objects depend on it
----
At this point, u2 is in an unfortunate situation. Can't drop the
index, can't drop the statistics (because it's owned by u1). The DROP
INDEX fails even if there's another index usable for sampling, which
is a bit weird - I don't know if we have other cases tied to a single
index (except maybe for PK indexes).
The user can't even drop the statistic object, because that's owned
by u1, of course. OTOH, the u2 user can drop the whole table t2, and
that *will* drop the whole statistics.
Seems a bit weird. I recall there was some discussion about users,
but I don't recall the details or what behavior I argued for.
- I suspect join_mcv_clause_selectivity is not quite right, resulting
in incorrect estimates. Consider this trivial join example:
---
CREATE TABLE t1 (id int);
CREATE TABLE t2 (id int, val text);
-- 1000 rows on the anchor side, only 10 of them join, 9 of those
-- have 'hit'
INSERT INTO t1 SELECT g FROM generate_series(1, 1000) g;
INSERT INTO t2
SELECT g, CASE WHEN g <= 9 THEN 'hit' ELSE 'miss' END
FROM generate_series(1, 10) g;
CREATE INDEX t2_idx ON t2 (id);
CREATE STATISTICS test_stat (mcv)
ON t2.val
FROM t1 JOIN t2 ON t1.id = t2.id;
ANALYZE t1;
ANALYZE t2;
-- 'hit' matches 9 of the 10 joining rows, so the frequency is 0.9
SELECT statistics_name, exprs, most_common_vals, most_common_freqs
FROM pg_stats_ext
WHERE statistics_name = 'test_stat';
-- with join stats: estimated 900 rows, actual 9
EXPLAIN (ANALYZE, TIMING OFF, SUMMARY OFF)
SELECT *
FROM t1 JOIN t2 ON t1.id = t2.id
WHERE t2.val = 'hit';
DROP STATISTICS repro_sel_s;
-- without join stats: estimated 9 rows, actual 9
EXPLAIN (ANALYZE, TIMING OFF, SUMMARY OFF)
SELECT *
FROM t1 JOIN t2 ON t1.id = t2.id
WHERE t2.val = 'hit';
--
I don't have the energy and time to check join_mcv_clause_selectivity
in detail right now, but it seems to me it might be confused whether
it should calculate P(join | filters) or P(join AND filters).
I believe it should calculate the former, but it seems to calculate
the latter (at least that's what the comments say).
Two more comments: While looking at calc_joinrel_size_estimate, I
noticed the selectivity calculated for semi/anti joins is very
different. I wonder if join_mcv_clause_selectivity needs to account
for this too, so that it calculates the right thing for semi/anti?
Also, I'm a bit unsure about this bit:
/*
* Cross-check: the MCV-based estimate shouldn't be lower than
* what the standard join estimator would produce (eqjoinsel on
* per-column stats only, no extended stats). If our estimate is
* lower, skip this stat and fall back to the standard estimate.
*/
standard_sel = clause_selectivity_ext(...);
if (raw_sel < standard_sel)
continue;
It's not quite clear to me if this is really true, especially when
the statistics covers some additional filters etc. I'd like to see
some valid examples where this kicks in.
In fact, how could it be correct? Consider a perfect MCV (covering
all values in the join), with impossible filters. That is, filters
that have no matches in the join.
Made up example:
--
CREATE TABLE t1 (a int, b int);
CREATE TABLE t2 (c int, d int);
INSERT INTO t1 SELECT i, mod(i,2) FROM generate_series(1,100) S(i);
INSERT INTO t2 SELECT i, mod(i+1,2) FROM generate_series(1,100) S(i);
SELECT * FROM t1 JOIN t2 ON (t1.a = t2.c)
WHERE t1.b = 0 AND t2.d = 0;
--
This is estimated to return 25 rows, because each WHERE clause matches
50% rows, and 0.5 * 0.5 = 0.25. But if we create a join statistic on
(a,b,c,d), then we *know* there are no matches.
So why should we compare this to standard_sel, which is guaranteed to
be "> 0" and override the "better" selectivity, calcualted from the
join MCV? Seems a bit strange. The other (raw_sel <= 0) checks seem
a bit suspicious too.
Moreover, isn't raw_sel an estimate for (join AND covered filters)
while standard_sel is just for the join clause. Does it even make
sense to compare those? Aren't the values fundamentally different?
(Assuming join_mcv_clause_selectivity should really calculate this
selectivity, and not P(join|filters))
- I realized join_mcv_clause_selectivity now works for individual join
clauses, i.e. joins on multiple equality clauses are not supported.
I don't recall if this was agreed as a simplification for V1, maybe
it was? I think it's acceptable, but I wonder if we actually are
handling such cases correctly?
If it's calculating (join AND filters), won't it apply the filters
multiple times - once for each join clause? We should have some
tests for such joins, even if we don't support them now.
0004 - Improve auto-generated names for extended statistics
- Seems reasonable. I'd probably move it right after 0002, so that we
can commit it before the main join stats.
- One thing I'd consider is not repeating the table name for every
attribute - that seems excessive. Maybe only when it changes, so
that for example (t1.a, t1.b, t2.c, t2.d) would get t1_a_b_t2_c_d.
I did briefly look at the performance issue reported by Ilya's, and
I think it's not surprising it takes so long. It's a rather contrived
example, because both tables have just a single value "1" in the join
column (there is a PK column, but the join clause is not using it).
So we simply read 20k rows with "1" from the anchor table, and then for
each one "sample" the second table with 500k rows, all containing "1".
So the sampling code goes through 10,000,000,000 rows, pretty much.
Most joins won't be like that, of course. But we need to be prepared
for less severe cases (a couple values with many matches in the sampled
table, etc.). I believe we improve the sampling by doing three things:
1) Deduplicate the values in "anchor" table, and build all the samples
in one pass (IIRC we still need to build an independent sample for
each individual value - before deduplication).
2) Do a single query to sample all values at once, by executing
something like
WHERE val IN (... unique values ...) ORDER BY val
This will become even more important with index prefetching.
3) In fact, I think we could even build samples for all values in one
pass / single index scan.
4) I wonder if we could actually use something like TABLESAMPLE, to
filter values early / before our sampling code.
But those are just ideas, I have not tried implementing any of it.
regards
--
Tomas Vondra
