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

Hi there,

Thank you Tomas, Ilia, and Corey for your feedback!

Here's v9:

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: the join mcv commit, now with bug fixes and more test coverage.
0004: improve default auto-generated statistics name

Changes since v8:
1. Added a new 0001 patch that fixes an existing memory leak bug.
2. 0002 now also combines columns and expressions into a single list
in StatExtEntry and StatisticExtInfo, per Tomas' and Corey's feedback.
These lists also preserve the columns and expressions in user declared
order.
3. 0002 adds more test coverage for the refactor, including regression
tests for the new ordering of the statistics object definition, with a
few more statistics objects left for the pg_upgrade tap tests.
4. 0002 continues to encode the ndistinct and dependency data with
plain columns ascending followed by expressions descending, because
that makes deduplication and the duplicate check easier during stats
import in pg_dump and pg_upgrade.
5. 0002: CREATE STATISTICS now expands generated columns and
const-folds each entry before the duplicate check, so an entry that
reduces to a column already listed is rejected with "duplicate column
or expression in statistics definition". For example, when a is
already listed, (a), (CASE WHEN true THEN a END), and a pass-through
virtual generated column on a all reduce to a and are rejected.
6. 0003 fixes the range-query estimate bug Tomas reported.
7. Added 0004 to improve the auto-generated statistics object name.
8. Various test additions, updates, and cosmetic fixes.

I've looked into the performance issue Ilia reported and am
experimenting with fixes, but this revision doesn't include the fix
yet.

For this round I'd most appreciate a thorough review of 0001 and 0002
to see whether they're committable. 0003 and onward are complete, and
I'd welcome feedback and discussion on those too.

-----------------

See more details in the following quote reply:

> On Mon, Jul 27, 2026 at 12:41 PM Corey Huinker <corey(dot)huinker(at)gmail(dot)com>
wrote:
>> On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
>> The main question I have is whether maybe we should get rid of the
>> columns vs. expressions in more places. Currently the patch removes that
>> from the catalog, but then it still "restores" this difference when
>> reading the statistics information, so that both StatExtEntry and
>> StatisticExtInfo still store this separately. But do we need to?
>
> I'd be in favor of this. It was a pain interleaving the expressions in
every time we found a negative attnum, and it also prevented skippping
ahead to to desired attribute because we had to know that we had consumed
all "previous" expressions. Good riddance to that.
>
>> It means we still need two loops in a lot of places, first over columns
>> and then over expressions. If we treated everything as expressions,
>> wouldn't it be simpler?
>
> That might be the best way.

I've spent a lot of time on this, and it's the bulk of the change in
v9. I've consolidated the "columns" and the "exprs" fields into a
single "exprs" list in StatExtEntry, and the "keys" and the "exprs"
fields into a single "exprs" list in StatisticExtInfo. In some places
this collapses two loops into one. In others we still have to tell
plain columns and complex expressions apart:
a. We extract the complex expressions to build per-expression
statistics, stored in pg_statistic_ext_data (the stxdexpr column) as
an array of pg_statistic tuples. Storing plain columns there would be
wasteful, since their statistics already live in pg_statistic.
b. For selectivity estimation the planner needs the varattno of plain
columns, so we still distinguish plain columns from complex
expressions.

I also kept encoding the ndistinct and dependency data with plain
columns first, then expressions, because otherwise stats dump/import
would do more work in the duplicate check. The order doesn't matter
for planning because, when applying these statistics, the planner
matches each clause to a stored column or expression by its attribute
number (or by the expression itself), not by its position in the
encoded array.

A side effect of unifying columns and expressions is that CREATE
STATISTICS now const-folds each expression and expands virtual
generated columns before storing it. An expression that reduces to a
plain column is therefore stored as that column, so a query that
references the column directly — e.g. in a GROUP BY — can now use the
statistics object, where before the same definition was stored as an
opaque expression and wouldn't match. That's a small improvement.
Conversely, a definition like CREATE STATISTICS ON a, (CASE WHEN true
THEN a ELSE b END), where the expression folds to a and duplicates the
first column, is now rejected outright since it couldn't produce
anything useful.

On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> 1) Does pg_get_statisticsobjdef_columns naming still make sense? AFAIK
> it now returns everything, both "columns" and expressions, right? Maybe
> we should get rid of the columns vs. expressions entirely, and just hve
> one function showing everything at once?

You are correct that pg_get_statisticsobjdef_columns() now returns
both "columns" and expressions. There's also
pg_get_statisticsobjdef_expressions(), which returns only the complex
expressions; it backs the expressions-only pg_stats_ext_exprs view. I
kept the names unchanged for now because I'm not sure what to rename
them to, let me know if you have a preference.

On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> 2) I think the results of queries in perform.sgml are now much harder to
> understand, because we're first showing column names and then the jsonb
> value for stxddependencies with attnums. And it's not clear how these
> two arrays map.

Good catch. Now that we've removed stxkeys, showing the attnums would
need a more complicated subquery to map column and expression names to
attnums. I dropped pg_get_statisticsobjdef_columns(oid) AS cols from
the query's SELECT list and now show only the JSON form of
stxndistinct and stxddependencies, with some explanation in prose,
which hopefully removes the confusion.

On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> 3) system-views.sgml talks about "target columns and expressions" but
> that sounds a bit weird to me. I don't think I've heard "target" used to
> describe columns an object is defined on, but maybe I'm wrong. Maybe
> "columns and expressions the statistics is defined on" would work?

Good call. I used "target" thinking of the columns and expressions as
a query's "target list", but you're right that it's confusing in the
statistics context. I've now updated system-views.sgml and friends to
describe them the way you suggested.

On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> 4) pg_get_statisticsobjdef_expressions has this:
>
> /* Skip plain column references (but not virtual generated columns) */
> if (IsA(expr, Var) && ((Var *) expr)->varattno > 0 &&
> get_attgenerated(statextrec->stxrelid, ((Var *) expr)->varattno)
> != ATTRIBUTE_GENERATED_VIRTUAL)
> continue;
>
> but it's not clear to me *why* we need to skip those. I think the
> comment should explain that.

Right. One difference in v9 is that a virtual generated column that
can be expanded into a plain column is now skipped too. I've expanded
the comment to explain why.

On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> 5) I see we're losing a FK ...
>
> DECLARE_ARRAY_FOREIGN_KEY((stxrelid, stxkeys), pg_attribute, (attrelid,
> attnum));
>
> That's unfortunate, but I guess we still have the dependencies.

Right, we still record the dependencies in pg_depend. In v9 I've also
added a new FK for stxjoinrels:
+/* each participating relation of a join statistics object exists */
+DECLARE_ARRAY_FOREIGN_KEY((stxjoinrels), pg_class, (oid));

On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> I did however do some simple experiments, and there's a behavior I don't
> quite understand. The attached script creates two correlated tables (the
> non-join columns match exactly).
>
> create table t1 (a int, b int, c int);
> create table t2 (d int, e int, f int);
>
> insert into t1
> select i, mod(i,100), mod(i,100) from generate_series(1,1000000) S(i);
>
> insert into t2
> select i, mod(i,100), mod(i,100) from generate_series(1,1000000) S(i);
>
> And then it runs queries like this:
>
> select * from t1 join t2 on t1.a = t2.d where t1.b < X and t2.e < X
>
> with X between 1 and 10, without/with extended statistics on (b,c,e,f).
> First with default_statistics_target, then with target 10000 (maximum).
>
> The results look like this:
>
> val | actual | no ext stats | target=100 | target=10000
> -----+--------+---------------+------------+-------------
> 1 | 10000 | 104 | 9700 | 10000
> 2 | 20000 | 393 | 9700 | 10000
> 3 | 30000 | 894 | 10100 | 10000
> 4 | 40000 | 1637 | 11500 | 10000
> 5 | 50000 | 2577 | 11300 | 10000
> 6 | 60000 | 3755 | 11000 | 10000
> 7 | 70000 | 5041 | 8800 | 10000
> 8 | 80000 | 6531 | 10900 | 10000
> 9 | 90000 | 8314 | 9200 | 10000
> 10 | 100000 | 10238 | 10217 | 10000
>
> The "no extended stats" results are not great, but that's expected. But
> the results with extended stats are a bit weird.
>
> First, with target=100 the estimates go up and down, which seems a bit
> surprising, as we're only increasing the fraction of rows (and of the
> MCV) matched by the conditions. Perhaps the MCV in incomplete, and this
> noise is due to which entries we end up picking for the MCV, and what
> fraction we happen to match? It does seem to oscillate around 10k.
>
> With target 10000, we use the whole join to build the MCV, so it's
> complete. And indeed, there's no noise - it always estimates 10k. But
> that's strange, isn't it? (For larger values of the query parameters the
> estimates start growing, but it matches the "no stats" estimates.)
>
> I haven't figured out why exactly this happens, but AFAICS it's due this
> block in join_mcv_clause_selectivity:
>
> if (covered_anchor_sel > 0 && other_rel->tuples > 0)
> {
> double other_denom
> = Max(other_rel->tuples * covered_other_sel, 1.0);
>
> raw_sel /= covered_anchor_sel * other_denom;
> CLAMP_PROBABILITY(raw_sel);
> }
>
> So maybe it's some thinko in how it applies the anchor?

Thanks for reporting this! It was indeed a bug. In v8,
extract_filter_info() accepted any (Var op Const) clause but treated
it as equality, ignoring the operator, so t1.b < X was evaluated as
t1.b = X and matched only one MCV group. v9 fixes it by validating the
operator in filter_op_is_supported() and counting all qualifying MCV
items.

Here are the results on v9:

val | actual | no ext stats | target=100 | target=10000
-----+--------+--------------+------------+-------------
1 | 10000 | 95 | 9800 | 10000
2 | 20000 | 393 | 18899 | 20000
3 | 30000 | 926 | 27800 | 30000
4 | 40000 | 1610 | 39000 | 40000
5 | 50000 | 2581 | 49399 | 50000
6 | 60000 | 3756 | 58500 | 60000
7 | 70000 | 5083 | 69300 | 70000
8 | 80000 | 6564 | 81301 | 80000
9 | 90000 | 8299 | 91600 | 90000
10 | 100000 | 10211 | 100500 | 100000

On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> - The automated statistics naming seems to not recognize plain columns
> anymore, so it picks t1_expr_expr_expr_expr_stat even though the
> statitstics object is on (b, c, e, f). I guess it's due to 0001.

Yeah, the naming is awful. It wasn't due to 0001 though.
ChooseExtendedStatisticNameAddition() has always emitted "expr" for
anything but a bare, unqualified column name. On master branch, even
parenthesized plain columns like "ON (b), (c)" give t_expr_expr_stat
for a single-table stat. Table qualified column names are not allowed
on master at all.

0004 resolves a simple column reference to its name
however it's written: unqualified, qualified, or parenthesized; a more
complex expression still gets "expr". Join columns are additionally
qualified with their relation:

Join: ON t1.b, t1.c, t2.e, t2.f -> t1_b_t1_c_t2_e_t2_f_stat

Single-table: ON t1.b, t1.c, (t1.e), (f) -> t1_b_c_e_f_stat

Alternatively, we could do exactly what indexes do by reusing
ChooseIndexExpressionName, so (a+b) -> a_b, though it can get noisy:
"ON (a+b), (a-b)" would give "t_a_b_a_b_stat". I'm happy to implement
that instead if you prefer.

On Mon, Jul 27, 2026 at 12:41 PM Corey Huinker <corey(dot)huinker(at)gmail(dot)com>
wrote:
> On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> > - I didn't realize we require the user to pick the "anchor" table and
> > put it first in the CREATE STATISTICS command:
> >
> > CREATE INDEX ON t1 (a);
> > CREATE STATISTICS (mcv) on t1.b, t1.c, t2.e, t2.f from t1 join t2
> > ON (t1.a = t2.d);
> > ERROR: no suitable index on "t2" column "d" for join statistics
> > HINT: Create an index on the join column to enable index-based join
> > sampling.
> >
> > In this example both t1 and t2 could have be an anchor table. So maybe
> > we could try determining the anchor table automatically? But maybe there
> > are issues, e.g. what if there are multiple candidates?
>
> It's true there could be multiple candidates, but I think we want a
clearly defined anchor table because that is the table that controls when
these stats are refreshed, as it is the one that has the real rowsample,
and all the others are joins off of that.
>
> That could mean that we have essentially the same extended stats object
on two different tables, differing only in the syntax required to specify
the different anchor table, but such situations should be rare.

Right, "needing the user to pick the 'anchor" table and put it first"
is a current limitation. In a followup I'd like to determine it
automatically from index availability and relation sizes, breaking
ties deterministically when several tables qualify. If someone would
rather pick the anchor themselves, maybe we could add explicit syntax
later.

Per Corey's point on stats refreshing: once the anchor is implicit,
the user needs to see which tables's ANALYZE refreshes the stats.
That really leads to Tomas's next point about "\d". We can show which
one is the anchor table there. Or should we refresh the join stats
object when analyzing participating table?

On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> - It's a bit inconvenient the statistics is listed in \d only for the
> anchor table. It'd be good to list it for all tables, but maybe add an
> info whether it's the anchor or not?

Agreed. I will followup on this one.

On Mon, Jul 27, 2026 at 12:41 PM Corey Huinker <corey(dot)huinker(at)gmail(dot)com>
wrote:
> On Fri, Jul 3, 2026 at 4:51 AM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
> > Not sure. I think both (a) and (c) would be OK. I'd probably go with
> > some version of (a), i.e. pick a suitable index at ANALYZE time, and
> > either "fail" when there's no index or use a seqscan sampling.
>
> I'm a big proponent of "a" here. The negative consequence of a missing
index is a slow ANALYZE, remedied by creating the index.

Thank you both. Sounds like we're agreed on (a), I'll implement (a) in
the next revision.

Best,
Alex