Re: Is there value in having optimizer stats for joins/foreignkeys?

From: Alexandra Wang <alexandra(dot)wang(dot)oss(at)gmail(dot)com>
To: Tomas Vondra <tomas(at)vondra(dot)me>
Cc: Corey Huinker <corey(dot)huinker(at)gmail(dot)com>, ilya(dot)evdokimov(at)tantorlabs(dot)com, jian he <jian(dot)universality(at)gmail(dot)com>, pgsql-hackers(at)lists(dot)postgresql(dot)org, Andrei Lepikhov <lepihov(at)gmail(dot)com>, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, hs(at)cybertec(dot)at, Jeff Davis <pgsql(at)j-davis(dot)com>
Subject: Re: Is there value in having optimizer stats for joins/foreignkeys?
Date: 2026-11-18 08:44:39
Message-ID: CAK98qZ247XHLC37pkhaBfrtdEbMZ=Jn3B52K38fC-P4aGCq_vw@mail.gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi there,

Sorry about the long silence since my last post. I was on maternity
leave. I'm back now, and here are the v10 patches!

Thanks to Tomas for the v9 review, to Chengpeng for the 0002 report,
and to Ilia for the ANALYZE timings. I have addressed, or partly
addressed, all of the feedback, and here is a brief summary of what
changed in v10.

The organization of the patches remains the same as in v9, except that
I swapped 0003 and 0004, following Tomas's suggestion:

0001: a minor bug fix
0002: the refactor commit that unifies columns and expressions into a
single list in the pg_statistic_ext catalog, the pg_stats_ext view,
and the in-memory StatExtEntry and StatisticExtInfo structs. The
user-written order of columns and expressions is preserved in the
catalog, the view, the \dX display, and in the MCV data.
0003: improve default auto-generated statistics names (moved before
the join stats patch, as Tomas suggested)
0004: the join MCV commit

I spent the most effort on the following parts of 0004:

- Sampling: following Tomas's suggestion, ANALYZE now groups the
anchor sample rows by join value, does one index scan per distinct
value, and picks the sample from all the matches in a single pass.
The cost no longer grows with the size of the join, which fixes the
slow ANALYZE Ilia reported.

- Definition: the FROM clause is now parsed with
transformFromClause(), as for a SELECT, so USING, NATURAL and
parenthesized joins work, with the same name resolution and error
messages as in a query.

- Selectivity: Tomas found that v9 misread the join MCV frequencies.
They are fractions of the joined rows, not of the anchor table. v10
now uses them to correct the planner's own join estimate rather than
replace it, and the cross-check he questioned is gone.

Beyond these, there are miscellaneous other bug fixes. There are also
substantial code and test refactors and cleanups, which I hope will
make the patch easier to review.

My goal is to get these four patches into a committable state,
especially 0004, and I'd be grateful for any review. In the meantime,
these are the follow-ups to 0004 I have in mind:

1. Support partitioned tables
2. Support multiple join conditions
3. Support a sequential scan as a fallback when no index is available
for join sampling
4. Support n-way joins
5. Support semi and anti joins
6. Support other statistics kinds

I have looked briefly into 2 to 4 and tried to keep the current code
open to them. I'd appreciate any thoughts on which of these matter
most, or on anything important that is missing from the list.

======================================================================
Below is a long list of quoted replies.
======================================================================

On Sat, Aug 8, 2026 at 3:08 PM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> 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.

I just noticed the XXX comment while I was working on that area of the
code for 0002. It is not related to join stats at all.

To check whether it matters in practice, I created 30,000 rows (the
default sample size) with a ~32kB incompressible text value stored
externally, and

CREATE STATISTICS s ON (md5(doc)), (id % 10) FROM big;

Peak memory of the backend during ANALYZE, from log_statement_stats
(median of 3 runs each, within 1%, and the lower of 2 runs without the
statistics):

master 1,117,600 kB
master + 0001 153,744 kB
master, without the statistics 15,376 kB

So I think it might be worth backpatching.

On Sat, Aug 8, 2026 at 3:08 PM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> 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.

Fixed.

> - 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.

I profiled planning with pgbench running EXPLAIN only, on a table with
8 statistics objects. The list walks don't show up: each one is
bounded by the entries of one object, which STATS_MAX_DIMENSIONS
limits to 8. If that limit is raised, the planner could build a
bitmapset of the plain columns once per object and use it in those
places. I'd rather not add a second representation before we need it.

The profile found a larger cost elsewhere. With 0002, every planning
parses stxexprs for every statistics object, including column-only
ones that master reads from stxkeys without parsing. On that benchmark
it's about 20% fewer transactions per second. Master already does the
same for statistics with expressions. Is that acceptable for now, or
should 0002 cache the parsed definitions in the relcache first, as
RelationGetIndexExpressions() does for index expressions?

> 0003 - Add join MCV statistics for selectivity estimation
>
> create statistics on a.x, a.y from a join b on (a.x = a.y);
>
> This leads to a crash in CreateStatistics() [...]

Fixed. A join statistics object now describes the rows of SELECT ...
FROM <its FROM clause>, and transformStatsStmt() parses that clause
with transformFromClause(), as for a SELECT. USING, NATURAL and
parenthesized joins then work as in a query. Each condition must be an
equality between columns of two tables, so your example is rejected at
the condition:

ERROR: join statistics support only equality conditions between columns
of two tables
DETAIL: This condition does not refer to two tables.

> Won't that be a bit confusing once we start supporting larger joins?
> [...] it should be enough to have enough clauses to have connected
> join graph, no?

Agreed, and that is now the rule:

ERROR: join conditions of join statistics must connect all the tables

Larger joins and several conditions between two tables are accepted.
ANALYZE skips them with a warning until they can be built.

> (I don't recall if/how the sampling paper deals with cyclic graphs.)

It doesn't mention them. A cyclic graph is still connected, so I think
it should be accepted. What do you think?

> - 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.

You are right! The limit is gone now. I've added a 60-table definition
to the tests, which crashed before.

> - I think the sampling has issues with partitioned tables. Consider
> this example:
> [...]

Thanks for raising it! For now, I'm rejecting partitioned tables and
tables with inheritance children. I'd like to add a follow-up patch to
support them, but I haven't given it much thought yet.

> - 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:
> [...]
> 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.

You are right, and it's fixed now. While there, I also found and fixed
a planner-side leak of the same kind: estimation could pass values
from the other table to a leaky operator. Join statistics are now used
for a non-leakproof filter only if the user can read the joined
columns of every table, with no RLS on any of them.

> - 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.
>
> ----
> [... omitting the example]
> ----
>
> 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).

You're right, tying the statistics to one particular index was too
strict, and it put the owner of the other table in an awkward
position. In v10 the statistics object no longer depends on an index.
CREATE STATISTICS warns when the probed table has no index ANALYZE
could use, and ANALYZE picks any suitable index each time. Without
one, it skips the object with a warning and keeps the existing data.
In your scenario, u2 can then drop the index, the object stays, and it
is rebuilt once an index exists again. I added your example to the
regression tests. Does this behavior seem reasonable to you?

>
> 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.

Agreed, it is a bit odd that u2 can drop the table but not the
statistics object itself. I left this as it is for now. The object
depends on the columns of both tables, so dropping either table, or
one of those columns, drops it, as it would for a single-table
statistics object. I think that is the expected behavior, but I'm open
to other ideas.

>
> 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.

There were two discussions. In May, on tables with different owners,
you suggested requiring the statistics owner to have SELECT on the
joined tables instead of owning them. Tom suggested ownership of the
anchor table and SELECT on the rest, noting it was unclear what to do
if that SELECT is revoked. v10 follows that. ANALYZE rechecks the
SELECT for the object's owner and, if it has been revoked, skips the
refresh with a warning and keeps the existing data.

In July, on the index requirement, you said you'd probably go with
picking a suitable index at ANALYZE time, and either failing when
there is none or sampling with a sequential scan. That is the behavior
above, with a skip when there is no index. Do you think a
sequential-scan fallback is needed in the first version, or is
skipping acceptable for now?

> - I suspect join_mcv_clause_selectivity is not quite right, resulting
> in incorrect estimates. [...] 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).

You are right, it should calculate P(join | filters), and v9 did it
the wrong way. Your example now estimates 9 rows for 9 actual.

> 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?

Good point. I haven't worked out how to support semi and anti joins
yet, so v10 doesn't use join statistics for them, and they keep the
standard estimate. One idea is to have ANALYZE also record the sampled
rows without a match, which the sampler already sees but discards
today. That would give the fraction of outer rows with a match, which
is what semi and anti joins need, but I haven't tried it yet.

> 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.
> [...]
> 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?

The check was meant for an MCV list that doesn't store all the values.
For example, with b and e equal on every joined row, values 1 to 6
occurring 80, 50, 30, 20, 12 and 8 times, and a list that stores only
(1, 1) and (2, 2):

CREATE TABLE range_t1 (a int PRIMARY KEY, b int);
CREATE TABLE range_t2 (d int PRIMARY KEY, e int);
INSERT INTO range_t1
SELECT i, CASE WHEN i <= 80 THEN 1 WHEN i <= 130 THEN 2
WHEN i <= 160 THEN 3 WHEN i <= 180 THEN 4
WHEN i <= 192 THEN 5 ELSE 6 END
FROM generate_series(1, 200) i;
INSERT INTO range_t2 SELECT * FROM range_t1;
ANALYZE range_t1, range_t2;

CREATE STATISTICS jstats_range (mcv) ON t1.b, t2.e
FROM range_t1 t1 JOIN range_t2 t2 ON (t1.a = t2.d);
ALTER STATISTICS jstats_range SET STATISTICS 2;
ANALYZE range_t1;

SELECT * FROM check_estimated_rows('
SELECT * FROM range_t1 t1, range_t2 t2
WHERE t1.b <> 1 AND t2.e <> 1 AND t1.a = t2.d');

Only (2, 2) matches in the list, so on its own it estimates 50 rows,
for 120 actual. The standard estimate is 72, so in v9 the check
discarded 50 and kept 72. But you're right that the check also fired
for values the list stores, such as your impossible filters, and that
the two values it compared are different, one a fraction of the joined
rows and the other of the cross product.

v10 removes the check and the raw_sel <= 0 checks. It combines the
list with the standard estimate the way the single-table code does, in
mcv_combine_selectivities(): the matching items come from the list,
and the part of the join the list doesn't store gets the standard
estimate. The query above now estimates 110 rows for 120 actual, and
your example, with statistics on (a, b, c, d), 1 row instead of 25,
for 0 actual.

> - 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.

You're right, it did. v9 applied the correction once per join clause,
so a join on two clauses counted the filters twice. In v10 the
statistics are applied once per join step, and only when the query
joins the tables on exactly the condition they were built on. A join
of the same tables on more conditions keeps the standard estimate. I
added the tests you suggested, for two plain conditions, a foreign key
plus another condition, and two foreign keys.

Statistics are still built only for a join of two tables on a single
condition, which I understood as the v1 scope. But I do have several
conditions and joins of more tables in mind. CREATE STATISTICS already
accepts both kinds of definitions, and ANALYZE skips them with a
warning for now. On the planner side, applying the statistics once per
join step works the same way for a statistics object on more tables,
at the step where all its tables come together. I've checked that
nothing in v10 would be in the way of either extension, and I'd like
to work on them next. Does that sound reasonable?

> 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.

Done.

> 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.

Thank you so much for looking into it! I went with 1). ANALYZE now
groups the anchor sample rows by join value, scans the index once per
distinct value, and picks the sample from all the matches in a single
reservoir pass.

On Ilia's example, "ANALYZE other_tbl, anchor_tbl" after CREATE
STATISTICS now takes 29ms, against 263s with v9, on optimized builds
on the same machine. Both build the same MCV list.

On Sun, Aug 9, 2026 at 5:50 AM Chengpeng Yan <chengpeng_yan(at)outlook(dot)com>
wrote:
> Since v9 treats an expression that const-folds to a plain column as that
> column, I think this single-entry definition should be rejected, just
> like a statistics object defined on a single plain column. Instead, it
> is accepted with `stxkind = {e}`, but `ANALYZE` builds no expression
> statistics, which seems inconsistent.

Thanks for catching this! Rather than rejecting the definition, v10
removes the behavior that caused it. 0002 no longer treats an
expression that const-folds to a plain column as that column. Entries
are classified as written, as on master, so your example is an
expression again, and ANALYZE builds expression statistics for it, as
before 0002.

Looking into your report also turned up a compatibility problem. v9
rejected some definitions that master accepts, such as ON a, b, (CASE
WHEN true THEN a END), as duplicates, which could make pg_upgrade from
19 fail, and it rejected some statistics data from 19 on import. Both
work in v10.

The cost is a small planner improvement from v9, where a GROUP BY on a
column could use an expression that folds to it. v10 estimates such
queries as master does. Does this approach look right to you?

On Sun, Aug 9, 2026 at 7:05 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> I noticed another minor issue in the psql describe code, in parsing the
> statistics definition. [...]
> I think it could be fixed by adding a flag to
> pg_get_statisticsobj_worker, to simply not generate the initial part at
> all (and then the strstr is not needed at all). Or maybe it could return
> the offset where the columns begin, also makes strstr unnecessary.

Thanks for catching it! I went with the second.
pg_get_statisticsobj_worker() now returns the offset where the columns
begin, and \d gets the definition from pg_get_statisticsobjdef(oid,
false), so the strstr() is gone. Your example now shows as
"public.aaaa ON bbbb" (mcv) ON a, b, c FROM t.

On Sun, Aug 9, 2026 at 7:17 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> There seems to be an issue in CreateStatistics(), triggering an assert.
> [...]
> I suppose we joins we want to allow single-column stats, but in that
> case we should be careful about properly filling some join kinds. It
> probably should be treated as expression (STATS_EXT_EXPRESSIONS), but I
> haven't tried.

Fixed. Without a list of kinds, join statistics get an MCV list,
whatever the number of columns, so this now works. I kept the
single-column case as an MCV list rather than expression statistics,
because it describes how the column is distributed over the join,
which is the main use case.

Best,
Alex

Attachment Content-Type Size
v10-0001-Fix-memory-leak-in-make_build_data.patch application/octet-stream 1.6 KB
v10-0002-Unify-extended-statistics-columns-and-expression.patch application/octet-stream 139.9 KB
v10-0003-Improve-auto-generated-names-for-extended-statis.patch application/octet-stream 6.0 KB
v10-0004-Add-join-MCV-statistics-for-selectivity-estimati.patch application/octet-stream 406.0 KB

In response to

Browse pgsql-hackers by date

  From Date Subject
Previous Message Steven Niu 2026-11-18 08:34:53 Re: Fix exclusion of the init fork in table_block_relation_size()