Thread

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

Corey Huinker <corey.huinker@gmail.com> — 2025-12-01T20:10:25Z

Threads like [1] and [2] have gotten me thinking that there may be some
value in storing statistics about joins.

For the sake of argument, assume a table t1 with a column t2id which
references the pk of table t2 that has columns t2.t2id, t2c1, t2c2, t2c3.
In such a situation I can envision the following statistics being collected:

* The % of values rows in t2 are referenced at least once in t1
* The attribute stats (i.e. pg_statistic stats) for t2c1, t2c2, t2c3, but
associated with t1 and weighted according to the frequency of that row
being referenced, which means that values of unreferenced rows are filtered
out entirely.
* That's about it for direct statistics, but I could see creating extended
statistics for correlations between a local column value and a remote
column, or expressions on the remote columns, etc.

The storage feels like it would be identical to pg_statistic but with a
"starefrelid" field that identifies the referencing table.

That much seems straightforward. A bigger problem is how we'd manage to
collect these statistics. We could (as Jeff Davis has suggested) keep our
tablesamples, but that wouldn't necessarily help in this case because the
rows referenced, and their relative weightings would change since the last
sampling. In a worst-case scenario, We would have to sample the joined-to
tables as well,and that's an additional burden on an already IO intensive
operation.

In theory, we could do some of this without any additional stats
collection. If the ndistinct of t1.t2id is, say, at least 75+% of the
ndistinct of t2.t2id, we could just peek at the attribute stats on t2 and
use them for estimates. However, that makes some assumptions that the stats
on t2 are approximately as fresh as the stats on t1, and I don't think that
will be the case most of the time.

CCing people who have wondered out loud about this topic within earshot of
me.

Thoughts?

[1]
https://www.postgresql.org/message-id/flat/6fdc4dc5-8881-4987-9858-a9b484953185%40joeconway.com#5a93cd7a730691843a7700c770397baf
[2]
https://www.postgresql.org/message-id/flat/tencent_3018762E7D4C9BC470C821C829C1BF2F650A%40qq.com

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

Tomas Vondra <tomas@vondra.me> — 2025-12-01T21:01:58Z

On 12/1/25 21:10, Corey Huinker wrote:
> Threads like [1] and [2] have gotten me thinking that there may be some
> value in storing statistics about joins.
> 
> For the sake of argument, assume a table t1 with a column t2id which
> references the pk of table t2 that has columns t2.t2id, t2c1, t2c2,
> t2c3. In such a situation I can envision the following statistics being
> collected:
> 
> * The % of values rows in t2 are referenced at least once in t1
> * The attribute stats (i.e. pg_statistic stats) for t2c1, t2c2, t2c3,
> but associated with t1 and weighted according to the frequency of that
> row being referenced, which means that values of unreferenced rows are
> filtered out entirely.
> * That's about it for direct statistics, but I could see creating
> extended statistics for correlations between a local column value and a
> remote column, or expressions on the remote columns, etc.
> 

Do I understand correctly you propose to collect such stats for every
foreign key? I recall something like that was proposed in the past, and
the argument against was that for many joins it'd be a waste because the
estimates are good enough. And for OLTP systems that's probably true.

Of course, it also depends on how expensive this would be. Maybe it's
cheap enough? No idea.

But I always assumed we'd have a way to explicitly enable such stats for
certain joins only, and the extended stats were designed to make that
possible.

FWIW I'm not entirely sure what stats you propose to collect exactly. I
mean, what does

   ... associated with t1 and weighted according to the frequency of
   that row being referenced, which means that values of unreferenced
   rows are filtered out entirely.

mean? Are you suggesting to "do the join" and build the regular stats as
if that was a regular table? I think that'd work, and it's mostly how I
envisioned to handle joins in extended stats, restricted to joins of two
relations.

> The storage feels like it would be identical to pg_statistic but with a
> "starefrelid" field that identifies the referencing table.
> 
> That much seems straightforward. A bigger problem is how we'd manage to
> collect these statistics. We could (as Jeff Davis has suggested) keep
> our tablesamples, but that wouldn't necessarily help in this case
> because the rows referenced, and their relative weightings would change
> since the last sampling. In a worst-case scenario, We would have to
> sample the joined-to tables as well,and that's an additional burden on
> an already IO intensive operation.
> 

Combining independent per-table samples does not work, unless the
samples are huge. There's a nice paper [1] on how to do index-based join
sampling efficiently.

> In theory, we could do some of this without any additional stats
> collection. If the ndistinct of t1.t2id is, say, at least 75+% of the
> ndistinct of t2.t2id, we could just peek at the attribute stats on t2
> and use them for estimates. However, that makes some assumptions that
> the stats on t2 are approximately as fresh as the stats on t1, and I
> don't think that will be the case most of the time.
> 
> CCing people who have wondered out loud about this topic within earshot
> of me.
> 
> Thoughts?

I think adding joins to extended stats would not be all that hard
(famous last words, I know). For me the main challenge was figuring out
how to store the join definition in the catalog, I always procrastinated
and never gave that a serious try.

FWIW I think we might start by actually using per-table extended stats
on the joined tables. Just like we combine the scalar MCVs on joined
columns, we could combine multicolumn MVCs.

regards

[1] https://www.cidrdb.org/cidr2017/papers/p9-leis-cidr17.pdf

-- 
Tomas Vondra

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

Tom Lane <tgl@sss.pgh.pa.us> — 2025-12-01T22:11:55Z

Tomas Vondra <tomas@vondra.me> writes:
> On 12/1/25 21:10, Corey Huinker wrote:
>> Threads like [1] and [2] have gotten me thinking that there may be some
>> value in storing statistics about joins.

> Do I understand correctly you propose to collect such stats for every
> foreign key? I recall something like that was proposed in the past, and
> the argument against was that for many joins it'd be a waste because the
> estimates are good enough. And for OLTP systems that's probably true.

Yeah, I think that automated choices about this are unlikely to work
well.  We chose the syntax for CREATE STATISTICS with an eye to
allowing users to declaratively tell us to collect stats about
specific joins, and I still think that's a more promising approach.
But nobody's yet worked out any details.

			regards, tom lane

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

Corey Huinker <corey.huinker@gmail.com> — 2025-12-02T03:16:25Z

> Do I understand correctly you propose to collect such stats for every
> foreign key? I recall something like that was proposed in the past, and
> the argument against was that for many joins it'd be a waste because the
> estimates are good enough. And for OLTP systems that's probably true.
>

Not every foreign key, they'd be declared like CREATE STATISTICS, but would
be anchored to the constraint, not to the table.


> But I always assumed we'd have a way to explicitly enable such stats for
> certain joins only, and the extended stats were designed to make that
> possible.
>

That's the intention, but the stats stored don't quite "fit" in the buckets
that extended stats create. The attribute statistics seem much better
suited, as this isn't about combinations, there's only ever the one
combination, but rather about what can be known about the attributes in the
far table before doing the actual join.


> FWIW I'm not entirely sure what stats you propose to collect exactly. I
> mean, what does
>
>    ... associated with t1 and weighted according to the frequency of
>    that row being referenced, which means that values of unreferenced
>    rows are filtered out entirely.
>
> mean? Are you suggesting to "do the join" and build the regular stats as
> if that was a regular table? I think that'd work, and it's mostly how I
> envisioned to handle joins in extended stats, restricted to joins of two
> relations.
>

Right. We'd do the join from t1 to t2 as described earlier, and then we'd
judge the null_frac, mcv, etc for each column of t2 (as defined by the
scope of the stats declaration) according to the join. More commonly
referenced values would show up as more frequent, hence "weighted".

Just so I have an example to refer to later, say we have a table of colors:

CREATE TABLE color(id bigint primary key, color_name text unique,
color_family text null)

and there's hundreds of colors in the table that are color_family='red'
('fire engine red', 'candy apple red', 'popular muppet red', etc). Some
colors don't belong to any color_family.

And we have a table of toys:

CREATE TABLE toy(id bigint primary key, min_child_age integer, name text,
color_id bigint REFERENCES color)

And we declare a join stat on toy->color for the color_family attribute.
We'd sample rows from the toy table, left join those to color, and then
calculate the attribute stats of color_family as if it were a column in
toys. Some toys might not have a color_id, and some color_ids might not
belong to a color_family, so we'd want the null_frac to reflect those
combined conditions. For the values that do join, and the colors that do
belong to a family, we'd want to see regular MCV stats showing "red" as the
most common color_family.

But those stats aren't really a correlation or a dependency, they're just
plain old attribute stats.

I understand wanting to know the correlation between toys.min_child_age and
colors.color_family, so that makes perfect sense for extended statistics,
but color_family on its own just doesn't fit. Am I missing something?


> Combining independent per-table samples does not work, unless the
> samples are huge. There's a nice paper [1] on how to do index-based join
> sampling efficiently.
>

Thanks, now I've got some light reading for the flight home.


> I think adding joins to extended stats would not be all that hard
> (famous last words, I know). For me the main challenge was figuring out
> how to store the join definition in the catalog, I always procrastinated
> and never gave that a serious try.
>

I envisioned keying the stats off the foreign key constraint id, or adding
"starefrelid" (relation oid of the referencing table) to pg_statistic or a
table roughly the same shape as pg_statistic.


>
> FWIW I think we might start by actually using per-table extended stats
> on the joined tables. Just like we combine the scalar MCVs on joined
> columns, we could combine multicolumn MVCs.
>

That's the other half of this - if the stats existed, do we have an obvious
way to put them to use?

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

Corey Huinker <corey.huinker@gmail.com> — 2025-12-02T03:18:24Z

>
>
> Yeah, I think that automated choices about this are unlikely to work
> well.  We chose the syntax for CREATE STATISTICS with an eye to
> allowing users to declaratively tell us to collect stats about
> specific joins, and I still think that's a more promising approach.
> But nobody's yet worked out any details.
>
>
Per other response, no, I didn't envision stats on all possible joins or
even all possible foreign keys, just the ones we declare as interesting,
and even then only for the attributes that we say are interesting on the
far side of the join.

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2025-12-03T19:01:13Z

Hi there,

Thanks for raising this topic! I am currently working on a POC patch that
adds extended statistics for joins. I am polishing the patch now and will
post it soon with performance numbers, since there are interests!

On Mon, Dec 1, 2025 at 7:16 PM Corey Huinker <corey.huinker@gmail.com>
wrote:

> On Mon, Dec 1, 2025 at 1:02 PM Tomas Vondra <tomas@vondra.me> wrote:
>
I think adding joins to extended stats would not be all that hard
>> (famous last words, I know). For me the main challenge was figuring out
>> how to store the join definition in the catalog, I always procrastinated
>> and never gave that a serious try.
>>
>
> I envisioned keying the stats off the foreign key constraint id, or adding
> "starefrelid" (relation oid of the referencing table) to pg_statistic or a
> table roughly the same shape as pg_statistic.
>

 On Mon, Dec 1, 2025 at 1:02 PM Tomas Vondra <tomas@vondra.me> wrote:
>
>>
>> FWIW I think we might start by actually using per-table extended stats
>> on the joined tables. Just like we combine the scalar MCVs on joined
>> columns, we could combine multicolumn MVCs.
>>
>
> That's the other half of this - if the stats existed, do we have an
> obvious way to put them to use?
>

I have indeed started by implementing MCV statistics for joins,
because I have not found a case for joins that would benefit only from
ndistinct or functional dependency stats that MCV stats wouldn't help.

In my POC patch, I've made the following catalog changes:
- Add *stxotherrel (oid) *and *stxjoinkeys (int2vector)* fields to
*pg_statistic_ext*
- Use the existing *stxkeys (int2vector)* to store the stats object
attributes of *stxotherrel*
- Create *pg_statistic_ext_otherrel_index* on *(stxrelid, stxotherrel)*
- Add stxdjoinmcv* (pg_join_mcv_list)* to *pg_statistic_ext_data*

To use them, we can let the planner detect patterns like this:

/*
 * JoinStatsMatch - Information about a detected join pattern
 * Used internally to track what was matched in a join+filter pattern
 */
typedef struct JoinStatsMatch
{
    Oid          target_rel;       /* table OID of the estimation target */
    AttrNumber targetrel_joinkey;    /* target_rel's join column */
    Oid          other_rel;       /* table OID of the filter source */
    AttrNumber otherrel_joinkey;        /* other_rel's join column */
    List      *filter_attnums;       /* list of AttrNumbers for filter
columns in other_rel */
    List      *filter_values;    /* list of Datum constant values
being filtered */
    Oid          collation;       /* collation for comparisons */

    /* Additional info to avoid duplicate work */
    List      *join_rinfos;      /* list of join clause RestrictInfos */
    RestrictInfo *filter_rinfo;       /* the filter clause RestrictInfo */
} JoinStatsMatch;

and add the detection logic in clauselist_selectivity_ext() and
get_foreign_key_join_selectivity().

Statistics collection indeed needs the most thinking. For the
purpose of a POC, I added MCV join stats collection as part of ANALYZE
of one table (stxrel in pg_statistic_ext). I can do this because MCV
join stats are somewhat asymmetric. It allows me to have a target
table (referencing table for foreign key join) to ANALYZE, and we can
use the already collected MCVs of the joinkey column on the target
table to query the rows in the other table. This greatly mitigates
performance impact compared to actually joining two tables. However,
if we are to support more complex joins or other types of join stats
such as ndistinct or functional dependency, I found it hard to define
who's the target table (referencing table) and who's the other table
(referenced table) outside of the foreign key join scenario. So I
think for those more complex cases eventually we may as well
perform the joins and collect the join stats separately. Alvaro
Herrera suggested offline that we could have a dedicated autovacuum
command option for collecting the join statistics.

I have experimented with two ways to define the join statistics:

1. Use CREATE STATISTICS:

CREATE STATISTICS [ [ IF NOT EXISTS ] statistics_name ] [ ( mcv ) ] ON {
table_name1.column_name1 }, { table_name1.column_name2 } [, ...] FROM
table_name1 JOIN table_name2 ON table_name1.column_name3 =
table_name2.column_name4

Examples:
-- Create join MCV statistics on a single filter column (keyword)
CREATE STATISTICS movie_keyword_keyword_join_stats (mcv)
ON k.keyword
FROM movie_keyword mk JOIN keyword k ON (mk.keyword_id = k.id);
ANALYZE movie_keyword;

-- Create join MCV statistics on multiple filter columns (keyword +
phonetic_code):
CREATE STATISTICS movie_keyword_keyword_multicols_join_stats (mcv)
ON k.keyword, k.phonetic_code
FROM movie_keyword mk JOIN keyword k ON (mk.keyword_id = k.id);
ANALYZE movie_keyword;

2. Auto join stats creation for Foreign Key + Functional Dependency stats

Initially, I did not implement the CREATE TABLE STATISTICS command to
create the join stats. Instead, I’ve implemented logic in ANALYZE to
detect functional dependency stats on the referenced table through FKs
and create join statistics implicitly for those cases.

I've been using the Join Order Benchmark (JOB) [1] to measure
performance gain. I will post the POC patch and performance numbers in
a followup email.

[1] https://www.vldb.org/pvldb/vol9/p204-leis.pdf

Best,
Alex

-- 
Alexandra Wang
EDB: https://www.enterprisedb.com

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-01-29T05:04:19Z

Hi hackers,

As promised in my previous email, I'm sharing a proof-of-concept patch
exploring join statistics for correlated columns across relations.
This is a POC at this point, but I hope the performance numbers below
give a better idea of both the potential usefulness of join statistics
and the complexity of implementing them.

Join Order Benchmark (JOB)
---------------------------------------

I got interested in this work after reading a 2015 VLDB paper [1] that
introduced the Join Order Benchmark (JOB) [2].  JOB uses the IMDB
dataset, with queries having 3-16 joins (average 8). Unlike standard
benchmarks such as TPC-H which use randomly generated uniform and
independent data, JOB uses real-world data with correlations and
skewed distributions, which make cardinality estimation much harder.

The paper tested PostgreSQL among other databases. I reran the
benchmark on current PG 19devel to see where we stand today. (The
original data source is gone, but CedarDB hosts a mirror [3]; I
created a fork [4] and added some scripts. The schema DDLs and queries
are unchanged.)

Test setup:
MacBook, Apple M3 Pro
Postgres master branch (19devel), built with -O3
cold and warm runs, 3 runs each

Results (average of 3 runs):

Postgres 19devel branch:
Total execution time cold run: 140.75 s (±2.12 s)
Total execution time warm run: 117.72 s (±0.76 s)

Postgres 19devel branch, SET enable_nestloop = off:
Total execution time cold run: 87.16 s (±0.17 s)
Total execution time warm run: 86.68 s (±0.42 s)

These results suggest that the planner is frequently choosing nested
loop joins where hash or merge joins would be better.

(As a side note: with nestloops disabled, plans are dominated by hash
joins, so cold vs warm runs are very similar due to limited cache
reuse.)

Problem
--------

The slowest query in this workload is 16b.sql (attached). Its plan
contains 7 nested loop joins.

The innermost join is estimated as 34 rows but actually produces
41,840 rows — a ~1230x underestimation:

Nested Loop  (cost=6.80..3813.14 rows=34 width=4) (actual
time=2.336..304.160 rows=41840 loops=1)
  -> Seq Scan on keyword k (cost=0.00..2685.11 rows=1 width=4) (actual
time=0.402..6.161 rows=1.00 loops=1)
     Filter: (keyword = 'character-name-in-title')
  -> Bitmap Heap Scan on movie_keyword mk (cost=6.80..1124.98 rows=305
width=8) (actual time=1.933..295.493 rows=41840.00 loops=1)
     Recheck Cond: (k.id = keyword_id)

This underestimation cascades to the outermost join: ~3K estimated vs
~3.7M actual rows.

The problem can be reduced to the following query:

SELECT * FROM movie_keyword mk, keyword k
WHERE k.keyword = 'character-name-in-title'
AND k.id = mk.keyword_id;

The tables:

keyword(id PK, keyword, phonetic_code)
movie_keyword(id PK, movie_id, keyword_id)

These tables are strongly correlated via keyword_id -> keyword.id. We
can even add:

ALTER TABLE movie_keyword
  ADD CONSTRAINT movie_keyword_keyword_id_fkey
  FOREIGN KEY (keyword_id) REFERENCES keyword(id);
CREATE STATISTICS keyword_stats (dependencies)
  ON id, keyword FROM keyword;
ANALYZE keyword, movie_keyword;

However, even with the FK constraint and extended statistics on the
keyword table, the estimate remains unchanged:

SELECT * FROM check_estimated_rows(
  'SELECT * FROM movie_keyword mk, keyword k
   WHERE k.keyword = ''character-name-in-title''
     AND k.id = mk.keyword_id');
 estimated | actual
-----------+--------
        34 |  41840

This indicates that the planner cannot connect the skewed distribution
of the join key on the referencing table with the filter selectivity
on the referenced table as it applies to the join result. This is the
gap that join statistics aim to fill.

Proposed Solution
------------------

I've attached two patches:

0001: Extend CREATE STATISTICS for join MCV statistics
0002: Automatically create join MCV statistics from FK constraints

0001 is the core patch. 0002 is an optional convenience feature
that detects FK relationships during ANALYZE and auto-creates
join stats.

Syntax:

CREATE STATISTICS <name> (mcv)
  ON <other_table>.<filter_col> [, ...]
  FROM <primary_table> alias
  JOIN <other_table> alias ON (<join_condition>);

Example -- single filter column:

CREATE STATISTICS mk_keyword_stats (mcv)
  ON k.keyword
  FROM movie_keyword mk
  JOIN keyword k ON (mk.keyword_id = k.id);
ANALYZE movie_keyword;

Example -- multiple filter columns:

CREATE STATISTICS mk_multi_stats (mcv)
  ON k.keyword, k.phonetic_code
  FROM movie_keyword mk
  JOIN keyword k ON (mk.keyword_id = k.id);
ANALYZE movie_keyword;

Catalog changes:

pg_statistic_ext:
- New stats kind 'c' (join MCV) in stxkind
- New field stxotherrel (Oid): the other table in the join
- New field stxjoinkeys (int2vector): join column pair [primary_joinkey,
  other_joinkey]
- Existing stxkeys stores the filter column(s) on stxotherrel
- New index pg_statistic_ext_otherrel_index on (stxrelid, stxotherrel)

pg_statistic_ext_data:
- New field stxdjoinmcv (pg_join_mcv_list): serialized join MCV data

How stats are collected:

Join statistics are collected during ANALYZE of the primary table
(stxrelid). The current approach assumes a dependency relationship
between the join key column and the filter column(s) on the other
table. Specifically, during ANALYZE, we reuse the already-computed
single-column MCV stats for the primary table's join key column. For
each MCV value, we look up the matching row in the other table via the
join key and extract the filter column values, carrying over the
primary-side MCV frequency. This is not accurate in all cases, but
works reasonably well for the POC, especially for foreign-key-like
joins where the primary table's join key distribution is
representative of the join result.

For example, the catalog contents look like:

stxrelid      | stxotherrel | stxjoinkeys | stxkeys | stxkind
--------------+-------------+-------------+---------+--------
movie_keyword | keyword     | 2 1         | 2       | {c}

index | values       | nulls | frequency
------+--------------+-------+----------
    0 | {keyword_1}  | {f}   |      0.06
    1 | {keyword_2}  | {f}   |      0.06
    2 | {keyword_3}  | {f}   |      0.06
  ... | ...          | ...   |       ...

How the planner uses join stats:

I added the join pattern detection logic in
clauselist_selectivity_ext() and get_foreign_key_join_selectivity().
The planner looks for a pattern of:

- An equijoin clause between two relations (the join key pair), and
- Equality or IN filter clauses on columns of one relation (the filter
  columns)

When this pattern is found and matching join MCV stats exist, the
planner compares the filter values against the stored MCV items to
compute the join selectivity, replacing the default estimate.

JOB Benchmark Results
---------------------

I created a single join statistics object for the (movie_keyword,
keyword) pair and reran the JOB benchmark:

CREATE STATISTICS movie_keyword_keyword_stats (mcv)
  ON k.keyword
  FROM movie_keyword mk
  JOIN keyword k ON (mk.keyword_id = k.id);

Total execution times (average of 3 runs):

                      Cold run          Warm run
Default (baseline)  140.75s (+/-2.1)  117.72s (+/-0.8)
enable_nestloop=off   87.16s (+/-0.2)   86.68s (+/-0.4)
With join stats       85.81s (+/-3.4)   65.24s (+/-0.5)

With a single join statistics object:
- Cold run: -39% vs baseline (140.75s -> 85.81s),
  comparable to enable_nestloop=off
- Warm run: -45% vs baseline (117.72s -> 65.24s),
  -25% vs enable_nestloop=off (86.68s -> 65.24s)

Per-query times for the 10 slowest (out of 113) queries on baseline
(master branch, enable_nestloop = on):

  Query | Baseline  | No Nestloop | Join Stats | Best
  ------+-----------+-------------+------------+----------
  16b   | 10,673 ms |   2,789 ms  |  2,775 ms  | 3.8x JS
  17e   |  7,709 ms |   2,260 ms  |  2,149 ms  | 3.6x JS
  17f   |  7,506 ms |   2,304 ms  |  2,460 ms  | 3.3x NL
  17a   |  7,288 ms |   1,453 ms  |  2,388 ms  | 5.0x NL
  17b   |  6,490 ms |   1,580 ms  |  5,413 ms  | 4.1x NL
  17c   |  6,240 ms |   1,095 ms  |  5,268 ms  | 5.7x NL
  17d   |  6,261 ms |   1,263 ms  |  5,291 ms  | 5.0x NL
  6d    |  6,234 ms |     988 ms  |  1,565 ms  | 6.3x NL
  25c   |  6,133 ms |   1,848 ms  |  1,738 ms  | 3.5x JS
  6f    |  5,728 ms |   1,785 ms  |  1,556 ms  | 3.7x JS

  (JS = join stats fastest, NL = no-nestloop fastest)

All 10 queries improved over baseline. For 16b, 3 nested loop joins
were replaced with 2 hash joins and 1 merge join. Some queries (e.g.
17b) kept the same plan shape and joins but gained a Memoize node from
better cardinality estimates.

Current Limitations
-------------------

This is a proof of concept. Known limitations include:

1. The current catalog design is not ideal. It is asymmetric (a
"primary" and an "other" table), which is natural for FK-like joins,
but less intuitive for other joins.

2. Stats collection piggybacks on ANALYZE of the primary table and
uses its single-column MCV for the join key.  This can be inaccurate
when the MCV values on the "primary" side don't cover the important
values on the other side, or when the filter column isn't fully
dependent on the join key. A more accurate approach would execute the
actual join during collection, which could also decouple join stats
collection from single-table ANALYZE.

3. Currently limited to: equality join clauses, equality and IN filter
clauses, simple Var stats objects (no expressions), inner joins only,
and two-way joins only. Some of these are easier to extend; others may
be harder or unnecessary (like n-way joins).

4. Patch 0002 (auto-creation from FK constraints) should probably be
gated behind a GUC. I'm not strongly attached to this patch, but kept
it because FK joins seem like a natural and common use case.

Conclusion
----------

Even with all the current limitations, I think this experiment
suggests that join-level statistics can significantly improve plans,
as a single join stats object can materially improve workload
performance.

If there's interest, I'm happy to continue iterating on the design.

In particular, I'd welcome feedback on:
- whether this is a direction worth pursuing,
- the catalog design,
- the stats collection approach,
- the planner integration strategy,
- and scope (what kinds of joins / predicates are worth supporting).

Best,
Alex

[1] https://www.vldb.org/pvldb/vol9/p204-leis.pdf
[2] https://github.com/gregrahn/join-order-benchmark
[3] https://cedardb.com/docs/example_datasets/job/
[4] https://github.com/l-wang/join-order-benchmark



-- 
Alexandra Wang
EDB: https://www.enterprisedb.com

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

Corey Huinker <corey.huinker@gmail.com> — 2026-01-30T06:26:22Z

>
> I have indeed started by implementing MCV statistics for joins,
> because I have not found a case for joins that would benefit only from
> ndistinct or functional dependency stats that MCV stats wouldn't help.
>

That was a big question I had, and I agree that we should only add
statistics as uses for them become apparent.


>
> In my POC patch, I've made the following catalog changes:
> - Add *stxotherrel (oid) *and *stxjoinkeys (int2vector)* fields to
> *pg_statistic_ext*
> - Use the existing *stxkeys (int2vector)* to store the stats object
> attributes of *stxotherrel*
> - Create *pg_statistic_ext_otherrel_index* on *(stxrelid, stxotherrel)*
> - Add stxdjoinmcv* (pg_join_mcv_list)* to *pg_statistic_ext_data*
>

I like all these changes. Maybe "outer" rel rather than "other" rel, but it
really doesn't matter this early on.


>
> To use them, we can let the planner detect patterns like this:
>
> /*
>  * JoinStatsMatch - Information about a detected join pattern
>  * Used internally to track what was matched in a join+filter pattern
>  */
> typedef struct JoinStatsMatch
> {
>     Oid          target_rel;       /* table OID of the estimation target */
>     AttrNumber targetrel_joinkey;    /* target_rel's join column */
>     Oid          other_rel;       /* table OID of the filter source */
>     AttrNumber otherrel_joinkey;        /* other_rel's join column */
>     List      *filter_attnums;       /* list of AttrNumbers for filter columns in other_rel */
>     List      *filter_values;    /* list of Datum constant values being filtered */
>     Oid          collation;       /* collation for comparisons */
>
>     /* Additional info to avoid duplicate work */
>     List      *join_rinfos;      /* list of join clause RestrictInfos */
>     RestrictInfo *filter_rinfo;       /* the filter clause RestrictInfo */
> } JoinStatsMatch;
>
> and add the detection logic in clauselist_selectivity_ext() and
> get_foreign_key_join_selectivity().
>
> Statistics collection indeed needs the most thinking. For the
> purpose of a POC, I added MCV join stats collection as part of ANALYZE
> of one table (stxrel in pg_statistic_ext). I can do this because MCV
> join stats are somewhat asymmetric. It allows me to have a target
> table (referencing table for foreign key join) to ANALYZE, and we can
> use the already collected MCVs of the joinkey column on the target
> table to query the rows in the other table. This greatly mitigates
> performance impact compared to actually joining two tables. However,
> if we are to support more complex joins or other types of join stats
> such as ndistinct or functional dependency, I found it hard to define
> who's the target table (referencing table) and who's the other table
> (referenced table) outside of the foreign key join scenario. So I
> think for those more complex cases eventually we may as well
> perform the joins and collect the join stats separately. Alvaro
> Herrera suggested offline that we could have a dedicated autovacuum
> command option for collecting the join statistics.
>

I agree, we have to perform the joins, as the rows collected are inherently
dependent and skewed, and yes, it's going to be a maintenance overhead hit.

Initially I thought this could be mitigated somewhat by retaining
rowsamples for each table, but those row samples would be independent of
the joins, and the values we need are inherently dependent.


> I have experimented with two ways to define the join statistics:
>
> 1. Use CREATE STATISTICS:
>
> CREATE STATISTICS [ [ IF NOT EXISTS ] statistics_name ] [ ( mcv ) ] ON {
> table_name1.column_name1 }, { table_name1.column_name2 } [, ...] FROM
> table_name1 JOIN table_name2 ON table_name1.column_name3 =
> table_name2.column_name4
>

We'll need to support aliases because there could be a self-join :(


>
> Examples:
> -- Create join MCV statistics on a single filter column (keyword)
> CREATE STATISTICS movie_keyword_keyword_join_stats (mcv)
> ON k.keyword
> FROM movie_keyword mk JOIN keyword k ON (mk.keyword_id = k.id);
> ANALYZE movie_keyword;
>
> -- Create join MCV statistics on multiple filter columns (keyword +
> phonetic_code):
> CREATE STATISTICS movie_keyword_keyword_multicols_join_stats (mcv)
> ON k.keyword, k.phonetic_code
> FROM movie_keyword mk JOIN keyword k ON (mk.keyword_id = k.id);
> ANALYZE movie_keyword;
>

This is where the existing CREATE STATISTICS syntax does not serve our
purposes well. We definitely want MCV stats for both of those k.* columns
with the skew of values that join to move_keyword on that defined foreign
key, but we'd end up getting the _combinations_ of keyword, phonetic_code,
which we don't necessarily care about.

We might want an alternate syntax

CREATE STATISTICS movie_keyword_keyword_multicols_join_stats (mcv)
ON keyword, phonetic_code
[FROM movie_keyword]
USING movie_keyword_fk;

In this case, the FROM clause is redundant and therefore optional, the
columns listed must exist on the confrelid and the object is keyed to the
conrelid. Having said that, I think people don't really use constraint
names and so the join syntax will likely be used more often.

2. Auto join stats creation for Foreign Key + Functional Dependency stats
>
> Initially, I did not implement the CREATE TABLE STATISTICS command to
> create the join stats. Instead, I’ve implemented logic in ANALYZE to
> detect functional dependency stats on the referenced table through FKs
> and create join statistics implicitly for those cases.
>

I'm not excited about this, and others have expressed concern that it would
lead to an explosion of mediocre statistics objects.

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

Corey Huinker <corey.huinker@gmail.com> — 2026-01-30T07:29:56Z

>
>
> Current Limitations
> -------------------
>
> This is a proof of concept. Known limitations include:
>

I really like this proof of concept.



> 1. The current catalog design is not ideal. It is asymmetric (a
> "primary" and an "other" table), which is natural for FK-like joins,
> but less intuitive for other joins
>

I think the asymmetry comes with the territory, and we will be creating the
join statistics that prove useful. If that means that we create one object
ON b.c1, b.c2 FROM a JOIN b... and another ON a.c3, a.c4 FROM b JOIN a...
then so be it.


> .
>
> 2. Stats collection piggybacks on ANALYZE of the primary table and
> uses its single-column MCV for the join key.  This can be inaccurate
> when the MCV values on the "primary" side don't cover the important
> values on the other side, or when the filter column isn't fully
> dependent on the join key. A more accurate approach would execute the
> actual join during collection, which could also decouple join stats
> collection from single-table ANALYZE.
>

Unfortunately, I think we will have to join the remote table_b to the row
sample on table_a to get accurate join statistics, and the best time to do
that when we already have the row sample from table_a. We can further batch
up statistics objects that happen to join table_a to table_b by the same
join criteria to avoid rescans.

Will what you have work when we want to do an MCV on a mix of local and
remote columns, or will that require more work?


> 3. Currently limited to: equality join clauses, equality and IN filter
> clauses, simple Var stats objects (no expressions), inner joins only,
> and two-way joins only. Some of these are easier to extend; others may
> be harder or unnecessary (like n-way joins).
>

I suspect that n-way joins would have very limited utility and could be
adequately covered with multiple join-stats objects.


>
> 4. Patch 0002 (auto-creation from FK constraints) should probably be
> gated behind a GUC. I'm not strongly attached to this patch, but kept
> it because FK joins seem like a natural and common use case.
>

I think this is like indexing, just because you can make all possible
columns indexed doesn't mean you should. Tooling will emerge to determine
what join stats objects are worth their weight, and create only those
objects.

If there's interest, I'm happy to continue iterating on the design.
>
> In particular, I'd welcome feedback on:
> - whether this is a direction worth pursuing,
>

Yes. Very much so.


> - the catalog design,
>

I had somehow gotten the impression that you were going to take the
extended statistics format, but store individual columns in a modified
pg_statistic. That's working for now, but I wonder if that will still be
the case when we start to try this for columns that are arrays, ranges,
multiranges, tsvectors, etc. pg_statistic has the infrastructure to handle
those, but there may be good reason to keep pg_statistic focused on local
attributes and instead just keep adding new kinds to extended statistic and
let it be the grab-bag it was perhaps always meant to be.

In my own musings on how to implement this (which you have far exceeded
with this proof-of-concept), I had wondered how to stats for k.keyword and
k.phonetic_code individually from the definition
of movie_keywords2_multi_stats, but looking at what you've done I think
we're better of with defining each statistic object very narrowly, and that
means we define one object per remote column and one object per interesting
combination of columns, then so be it. So long as we can calculate them all
from the same join of the two tables, we'll avoid the nasty overhead.


> - and scope (what kinds of joins / predicates are worth supporting).
>

between-ish clauses ( x>= y AND x < z), etc is what immediately comes to
mind.

element_mcv for array types might be next, but that's well down the road.

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

Andrei Lepikhov <lepihov@gmail.com> — 2026-01-31T11:18:43Z

On 29/1/26 06:04, Alexandra Wang wrote:
> Hi hackers,
> 
> As promised in my previous email, I'm sharing a proof-of-concept patch
> exploring join statistics for correlated columns across relations.
> This is a POC at this point, but I hope the performance numbers below
> give a better idea of both the potential usefulness of join statistics
> and the complexity of implementing them.
I wonder why you chose the JOIN operator only?

It seems to me that any relational operator produces relational output 
that can be treated as a table. The extended statistics code may be 
adopted to such relations.
I think it may be a VIEW that you can declare (manually or 
automatically) and allow Postgres to build statistics on this 'virtual' 
table. So, the main focus may shift to the question: how to provably 
match a query subtree to a specific statistic.

-- 
regards, Andrei Lepikhov,
pgEdge

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

Tomas Vondra <tomas@vondra.me> — 2026-02-01T16:19:04Z

Hi Alexandra!

On 1/29/26 06:04, Alexandra Wang wrote:
> Hi hackers,
> 
> As promised in my previous email, I'm sharing a proof-of-concept patch
> exploring join statistics for correlated columns across relations.
> This is a POC at this point, but I hope the performance numbers below
> give a better idea of both the potential usefulness of join statistics
> and the complexity of implementing them.
> 

Great! Thanks for doing this, I think it's very worthy improvement and
I'm grateful you're interested in working on this.


> Join Order Benchmark (JOB)
> ---------------------------------------
> 
> I got interested in this work after reading a 2015 VLDB paper [1] that
> introduced the Join Order Benchmark (JOB) [2].  JOB uses the IMDB
> dataset, with queries having 3-16 joins (average 8). Unlike standard
> benchmarks such as TPC-H which use randomly generated uniform and
> independent data, JOB uses real-world data with correlations and
> skewed distributions, which make cardinality estimation much harder.
> 
> The paper tested PostgreSQL among other databases. I reran the
> benchmark on current PG 19devel to see where we stand today. (The
> original data source is gone, but CedarDB hosts a mirror [3]; I
> created a fork [4] and added some scripts. The schema DDLs and queries
> are unchanged.)
> 
> Test setup:
> MacBook, Apple M3 Pro
> Postgres master branch (19devel), built with -O3
> cold and warm runs, 3 runs each
> 
> Results (average of 3 runs):
> 
> Postgres 19devel branch:
> Total execution time cold run: 140.75 s (±2.12 s)
> Total execution time warm run: 117.72 s (±0.76 s)
> 
> Postgres 19devel branch, SET enable_nestloop = off:
> Total execution time cold run: 87.16 s (±0.17 s)
> Total execution time warm run: 86.68 s (±0.42 s)
> 
> These results suggest that the planner is frequently choosing nested
> loop joins where hash or merge joins would be better.
> 
> (As a side note: with nestloops disabled, plans are dominated by hash
> joins, so cold vs warm runs are very similar due to limited cache
> reuse.)
> 

Right. I have not investigated plans for the JOB queries, but a common
issue is that we pick a nested loop very early in the plan due to a poor
estimate, and that leads to a sequence of nested loops. Which just
amplifies the problem.

Is it possible to measure the accuracy of the estimates, not just the
execution time? I think it would be useful to know how much "closer" we
get to the actual cardinality. There may well be queries where the
execution time did not change much, but in a slightly different setting
it could easily be an issue.

> Problem
> --------
> 
> The slowest query in this workload is 16b.sql (attached). Its plan
> contains 7 nested loop joins.
> 
> The innermost join is estimated as 34 rows but actually produces
> 41,840 rows — a ~1230x underestimation:
> 
> Nested Loop  (cost=6.80..3813.14 rows=34 width=4) (actual
> time=2.336..304.160 rows=41840 loops=1)
>   -> Seq Scan on keyword k (cost=0.00..2685.11 rows=1 width=4) (actual
> time=0.402..6.161 rows=1.00 loops=1)
>      Filter: (keyword = 'character-name-in-title')
>   -> Bitmap Heap Scan on movie_keyword mk (cost=6.80..1124.98 rows=305
> width=8) (actual time=1.933..295.493 rows=41840.00 loops=1)
>      Recheck Cond: (k.id <http://k.id> = keyword_id)
> 
> This underestimation cascades to the outermost join: ~3K estimated vs
> ~3.7M actual rows.
> 
> The problem can be reduced to the following query:
> 
> SELECT * FROM movie_keyword mk, keyword k
> WHERE k.keyword = 'character-name-in-title'
> AND k.id <http://k.id> = mk.keyword_id;
> 
> The tables:
> 
> keyword(id PK, keyword, phonetic_code)
> movie_keyword(id PK, movie_id, keyword_id)
> 
> These tables are strongly correlated via keyword_id -> keyword.id
> <http://keyword.id>. We
> can even add:
> 
> ALTER TABLE movie_keyword
>   ADD CONSTRAINT movie_keyword_keyword_id_fkey
>   FOREIGN KEY (keyword_id) REFERENCES keyword(id);
> CREATE STATISTICS keyword_stats (dependencies)
>   ON id, keyword FROM keyword;
> ANALYZE keyword, movie_keyword;
> 
> However, even with the FK constraint and extended statistics on the
> keyword table, the estimate remains unchanged:
> 
> SELECT * FROM check_estimated_rows(
>   'SELECT * FROM movie_keyword mk, keyword k
>    WHERE k.keyword = ''character-name-in-title''
>      AND k.id <http://k.id> = mk.keyword_id');
>  estimated | actual
> -----------+--------
>         34 |  41840
> 
> This indicates that the planner cannot connect the skewed distribution
> of the join key on the referencing table with the filter selectivity
> on the referenced table as it applies to the join result. This is the
> gap that join statistics aim to fill.
> 

Agreed, I've seen various cases like this too.

> Proposed Solution
> ------------------
> 
> I've attached two patches:
> 
> 0001: Extend CREATE STATISTICS for join MCV statistics

+1 to do this (I'm not sure about restricting it to MCV, but that's a
detail we can discuss later)

> 0002: Automatically create join MCV statistics from FK constraints
> 

I think this is very unlikely, for reasons I already explained earlier
in this thread. Essentially, building and processing the stats is a
cost, and most FKs probably don't actually need it. We don't build
indexes on FKs for similar reasons. And it's not clear to me how we
would know which columns to define the statistics on.

Of course, it's up to you to keep working on this, and try to convince
us it's a good idea. I personally think it's unlikely to get accepted,
but perhaps I'm wrong.

> 0001 is the core patch. 0002 is an optional convenience feature
> that detects FK relationships during ANALYZE and auto-creates
> join stats.
> 
> Syntax:
> 
> CREATE STATISTICS <name> (mcv)
>   ON <other_table>.<filter_col> [, ...]
>   FROM <primary_table> alias
>   JOIN <other_table> alias ON (<join_condition>);
> 
> Example -- single filter column:
> 
> CREATE STATISTICS mk_keyword_stats (mcv)
>   ON k.keyword
>   FROM movie_keyword mk
>   JOIN keyword k ON (mk.keyword_id = k.id <http://k.id>);
> ANALYZE movie_keyword;
> 
> Example -- multiple filter columns:
> 
> CREATE STATISTICS mk_multi_stats (mcv)
>   ON k.keyword, k.phonetic_code
>   FROM movie_keyword mk
>   JOIN keyword k ON (mk.keyword_id = k.id <http://k.id>);
> ANALYZE movie_keyword;
> 
> Catalog changes:
> 
> pg_statistic_ext:
> - New stats kind 'c' (join MCV) in stxkind
> - New field stxotherrel (Oid): the other table in the join
> - New field stxjoinkeys (int2vector): join column pair [primary_joinkey,
>   other_joinkey]
> - Existing stxkeys stores the filter column(s) on stxotherrel
> - New index pg_statistic_ext_otherrel_index on (stxrelid, stxotherrel)
> 

- Why do we need a new stats kind? I'd have expected we'd use the same
'm' value as for a single-relation stats, simply because a join result
is just a relation too.

- For a PoC it's OK to have stxotherrel, but the final patch should not
be restricted to two relations. I think there needs to be an array of
the joined rel OIDs, or something like that.

FWIW I recognize figuring out the catalog changes is not easy - in fact
I always found it so intimidation I ended up procrastinating and not
making any progress on join statistics. So I really appreciate you
taking a stab at this.

> pg_statistic_ext_data:
> - New field stxdjoinmcv (pg_join_mcv_list): serialized join MCV data
> 

I don't understand why we need this. AFAICS we should just treat the
join result as a relation, and use the current pg_statistic_ext_data fields.

> How stats are collected:
> 
> Join statistics are collected during ANALYZE of the primary table
> (stxrelid). The current approach assumes a dependency relationship
> between the join key column and the filter column(s) on the other
> table. Specifically, during ANALYZE, we reuse the already-computed
> single-column MCV stats for the primary table's join key column. For
> each MCV value, we look up the matching row in the other table via the
> join key and extract the filter column values, carrying over the
> primary-side MCV frequency. This is not accurate in all cases, but
> works reasonably well for the POC, especially for foreign-key-like
> joins where the primary table's join key distribution is
> representative of the join result.
> 

For the PoC it's good enough, but I don't think we can rely on the
per-column MCV lists like this.

> For example, the catalog contents look like:
> 
> stxrelid      | stxotherrel | stxjoinkeys | stxkeys | stxkind
> --------------+-------------+-------------+---------+--------
> movie_keyword | keyword     | 2 1         | 2       | {c}
> 
> index | values       | nulls | frequency
> ------+--------------+-------+----------
>     0 | {keyword_1}  | {f}   |      0.06
>     1 | {keyword_2}  | {f}   |      0.06
>     2 | {keyword_3}  | {f}   |      0.06
>   ... | ...          | ...   |       ...
> 
> How the planner uses join stats:
> 
> I added the join pattern detection logic in
> clauselist_selectivity_ext() and get_foreign_key_join_selectivity().
> The planner looks for a pattern of:
> 
> - An equijoin clause between two relations (the join key pair), and
> - Equality or IN filter clauses on columns of one relation (the filter
>   columns)
> 
> When this pattern is found and matching join MCV stats exist, the
> planner compares the filter values against the stored MCV items to
> compute the join selectivity, replacing the default estimate.
> 
> JOB Benchmark Results
> ---------------------
> 
> I created a single join statistics object for the (movie_keyword,
> keyword) pair and reran the JOB benchmark:
> 
> CREATE STATISTICS movie_keyword_keyword_stats (mcv)
>   ON k.keyword
>   FROM movie_keyword mk
>   JOIN keyword k ON (mk.keyword_id = k.id <http://k.id>);
> 
> Total execution times (average of 3 runs):
> 
>                       Cold run          Warm run
> Default (baseline)  140.75s (+/-2.1)  117.72s (+/-0.8)
> enable_nestloop=off   87.16s (+/-0.2)   86.68s (+/-0.4)
> With join stats       85.81s (+/-3.4)   65.24s (+/-0.5)
> 
> With a single join statistics object:
> - Cold run: -39% vs baseline (140.75s -> 85.81s),
>   comparable to enable_nestloop=off
> - Warm run: -45% vs baseline (117.72s -> 65.24s),
>   -25% vs enable_nestloop=off (86.68s -> 65.24s)
> 
> Per-query times for the 10 slowest (out of 113) queries on baseline
> (master branch, enable_nestloop = on):
> 
>   Query | Baseline  | No Nestloop | Join Stats | Best
>   ------+-----------+-------------+------------+----------
>   16b   | 10,673 ms |   2,789 ms  |  2,775 ms  | 3.8x JS
>   17e   |  7,709 ms |   2,260 ms  |  2,149 ms  | 3.6x JS
>   17f   |  7,506 ms |   2,304 ms  |  2,460 ms  | 3.3x NL
>   17a   |  7,288 ms |   1,453 ms  |  2,388 ms  | 5.0x NL
>   17b   |  6,490 ms |   1,580 ms  |  5,413 ms  | 4.1x NL
>   17c   |  6,240 ms |   1,095 ms  |  5,268 ms  | 5.7x NL
>   17d   |  6,261 ms |   1,263 ms  |  5,291 ms  | 5.0x NL
>   6d    |  6,234 ms |     988 ms  |  1,565 ms  | 6.3x NL
>   25c   |  6,133 ms |   1,848 ms  |  1,738 ms  | 3.5x JS
>   6f    |  5,728 ms |   1,785 ms  |  1,556 ms  | 3.7x JS
> 
>   (JS = join stats fastest, NL = no-nestloop fastest)
> 
> All 10 queries improved over baseline. For 16b, 3 nested loop joins
> were replaced with 2 hash joins and 1 merge join. Some queries (e.g.
> 17b) kept the same plan shape and joins but gained a Memoize node from
> better cardinality estimates.
> 

Encouraging results, considering the limitations of the PoC patch. As
mentioned earlier, I'm curious how much the estimates improved, not just
the execution time.


> Current Limitations
> -------------------
> 
> This is a proof of concept. Known limitations include:
> 
> 1. The current catalog design is not ideal. It is asymmetric (a
> "primary" and an "other" table), which is natural for FK-like joins,
> but less intuitive for other joins.
> 

Yeah, that's not ideal. I think we'd like a catalog struct that works
for joins of more than 2 tables too.

> 2. Stats collection piggybacks on ANALYZE of the primary table and
> uses its single-column MCV for the join key.  This can be inaccurate
> when the MCV values on the "primary" side don't cover the important
> values on the other side, or when the filter column isn't fully
> dependent on the join key. A more accurate approach would execute the
> actual join during collection, which could also decouple join stats
> collection from single-table ANALYZE.
> 

Agreed. I don't think we can piggyback on the single-column MCV lists
for the reasons you mention.

> 3. Currently limited to: equality join clauses, equality and IN filter
> clauses, simple Var stats objects (no expressions), inner joins only,
> and two-way joins only. Some of these are easier to extend; others may
> be harder or unnecessary (like n-way joins).
> 
> 4. Patch 0002 (auto-creation from FK constraints) should probably be
> gated behind a GUC. I'm not strongly attached to this patch, but kept
> it because FK joins seem like a natural and common use case.
> 
> Conclusion
> ----------
> 
> Even with all the current limitations, I think this experiment
> suggests that join-level statistics can significantly improve plans,
> as a single join stats object can materially improve workload
> performance.
> 
> If there's interest, I'm happy to continue iterating on the design.
> 
> In particular, I'd welcome feedback on:
> - whether this is a direction worth pursuing,

Yes, please!

> - the catalog design,

I think we want a catalog that works for joins of more than 2 rels, etc.

> - the stats collection approach,

The best approach I'm aware of is the "Index-Based Join Sampling" paper
I mentioned earlier in this thread. I think it's OK to allow building
statistics only for joins compatible with that sampling approach.

It's not clear to me what should trigger building the stats. I assume
it'd be done by ANALYZE, but that's per-table. So would it be triggered
by ANALYZE on any of the joined tables, or just the "main" one? Would it
require a new ANALYZE option, or something else? Not sure.

> - the planner integration strategy,

I don't have a clear opinion on this yet. clauselist_selectivity_ext
seems like the right place, probably. I vaguely recall the challenge was
we either saw the per-relation restriction clauses or join clauses, but
not both at the same time?

> - and scope (what kinds of joins / predicates are worth supporting).
> 

IMHO it's fine to keep the scope rather narrow, at least for v1. As long
as we can later expand it to other cases, it's fine. The extended stats
initially did not support expressions, for example.

It's a bit orthogonal, but do you have an opinion on improving estimates
for some joins by considering per-table extended statistics in the
existing selectivity estimators (e.g. in eqjoinsel_inner)? I think it
might help cases with multi-clause join clauses, or cases where we have
a multi-column MCV list on the join key + WHERE conditions.

It's separate from what this patch aims to do, but I have imagined we'd
do that as the first step, before doing the proper join stats. I'm not
suggesting you have to do that too (or before this patch).


regards

-- 
Tomas Vondra

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

Tomas Vondra <tomas@vondra.me> — 2026-02-01T16:32:20Z

On 1/30/26 08:29, Corey Huinker wrote:
> 
>     Current Limitations
>     -------------------
> 
>     This is a proof of concept. Known limitations include:
> 
> 
> I really like this proof of concept.
> 
>  
> 
>     1. The current catalog design is not ideal. It is asymmetric (a
>     "primary" and an "other" table), which is natural for FK-like joins,
>     but less intuitive for other joins
> 
> 
> I think the asymmetry comes with the territory, and we will be creating
> the join statistics that prove useful. If that means that we create one
> object ON b.c1, b.c2 FROM a JOIN b... and another ON a.c3, a.c4 FROM b
> JOIN a...  then so be it.
>  
> 
>     .
> 
>     2. Stats collection piggybacks on ANALYZE of the primary table and
>     uses its single-column MCV for the join key.  This can be inaccurate
>     when the MCV values on the "primary" side don't cover the important
>     values on the other side, or when the filter column isn't fully
>     dependent on the join key. A more accurate approach would execute the
>     actual join during collection, which could also decouple join stats
>     collection from single-table ANALYZE.
> 
> 
> Unfortunately, I think we will have to join the remote table_b to the
> row sample on table_a to get accurate join statistics, and the best time
> to do that when we already have the row sample from table_a. We can
> further batch up statistics objects that happen to join table_a to
> table_b by the same join criteria to avoid rescans.
> 

IIRC the index-based sampling (described in the paper I mentioned) works
something like this - sample leading table, then use indexes to lookup
data from the other tables to build a statistically correct sample of
the whole join.

> Will what you have work when we want to do an MCV on a mix of local and
> remote columns, or will that require more work?
>  
> 
>     3. Currently limited to: equality join clauses, equality and IN filter
>     clauses, simple Var stats objects (no expressions), inner joins only,
>     and two-way joins only. Some of these are easier to extend; others may
>     be harder or unnecessary (like n-way joins).
> 
> 
> I suspect that n-way joins would have very limited utility and could be
> adequately covered with multiple join-stats objects.
>  

I see no clear reason why that would be the case, and it's not that hard
to construct joins on 3+ tables where stats on 2-way joins won't be good
enough. Whether those cases are sufficiently common I don't know, but I
also don't see a good reason to not address them - it should not be much
more complex than 2-way joins (famous last words, I know).

> 
> 
>     4. Patch 0002 (auto-creation from FK constraints) should probably be
>     gated behind a GUC. I'm not strongly attached to this patch, but kept
>     it because FK joins seem like a natural and common use case.
> 
> 
> I think this is like indexing, just because you can make all possible
> columns indexed doesn't mean you should. Tooling will emerge to
> determine what join stats objects are worth their weight, and create
> only those objects.
> 

Agreed.

>     If there's interest, I'm happy to continue iterating on the design.
> 
>     In particular, I'd welcome feedback on:
>     - whether this is a direction worth pursuing,
> 
> 
> Yes. Very much so.
>  
> 
>     - the catalog design,
> 
> 
> I had somehow gotten the impression that you were going to take the
> extended statistics format, but store individual columns in a modified
> pg_statistic. That's working for now, but I wonder if that will still be
> the case when we start to try this for columns that are arrays, ranges,
> multiranges, tsvectors, etc. pg_statistic has the infrastructure to
> handle those, but there may be good reason to keep pg_statistic focused
> on local attributes and instead just keep adding new kinds to extended
> statistic and let it be the grab-bag it was perhaps always meant to be.
> 
> In my own musings on how to implement this (which you have far exceeded
> with this proof-of-concept), I had wondered how to stats for k.keyword
> and k.phonetic_code individually from the definition
> of movie_keywords2_multi_stats, but looking at what you've done I think
> we're better of with defining each statistic object very narrowly, and
> that means we define one object per remote column and one object per
> interesting combination of columns, then so be it. So long as we can
> calculate them all from the same join of the two tables, we'll avoid the
> nasty overhead.
>  

Not sure I understand this. Why would this use pg_statistic at all? I
imagined we'd just treat the join as a relation, and store the stats in
pg_statistic_data_ext. The only difference is we need to store info
about the join itself (which rels / conditions), which would go into
pg_statistic_ext.

> 
>     - and scope (what kinds of joins / predicates are worth supporting).
> 
> 
> between-ish clauses ( x>= y AND x < z), etc is what immediately comes to
> mind.
> 
> element_mcv for array types might be next, but that's well down the road.

Maybe. In v1 we should focus on mimicking what we have for per-relation
stats, and only then try doing something more.

regards

-- 
Tomas Vondra

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

Tomas Vondra <tomas@vondra.me> — 2026-02-01T16:39:38Z

On 1/31/26 12:18, Andrei Lepikhov wrote:
> On 29/1/26 06:04, Alexandra Wang wrote:
>> Hi hackers,
>>
>> As promised in my previous email, I'm sharing a proof-of-concept patch
>> exploring join statistics for correlated columns across relations.
>> This is a POC at this point, but I hope the performance numbers below
>> give a better idea of both the potential usefulness of join statistics
>> and the complexity of implementing them.
> I wonder why you chose the JOIN operator only?
> 
> It seems to me that any relational operator produces relational output
> that can be treated as a table. The extended statistics code may be
> adopted to such relations.
> I think it may be a VIEW that you can declare (manually or
> automatically) and allow Postgres to build statistics on this 'virtual'
> table. So, the main focus may shift to the question: how to provably
> match a query subtree to a specific statistic.
> 

Because for each "supported" operator we need to know two things:

(1) how to sample it efficiently

(2) how to apply it in selectivity estimation

We can't add support for everything at once, and for some cases we may
not even know answers to (1) and/or (2).

We can't simply store an opaque VIEW, and build the stats by simply
executing it (and sampling the results). The whole premise of extended
stats is that people define them to fix incorrect estimates. And with
incorrect estimates the plan may be terrible, and the VIEW may not even
complete.

regards

-- 
Tomas Vondra

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

Tomas Vondra <tomas@vondra.me> — 2026-02-01T16:48:17Z

On 1/30/26 07:26, Corey Huinker wrote:
>     I have indeed started by implementing MCV statistics for joins,
>     because I have not found a case for joins that would benefit only from
>     ndistinct or functional dependency stats that MCV stats wouldn't help.
> 
> That was a big question I had, and I agree that we should only add
> statistics as uses for them become apparent.
>  

I don't have a clear opinion on this, and maybe we don't need to build
some of the stats. But I think there's a subtle point here - these stats
may not be useful for estimation of the join itself, but could be useful
for estimating the upper part of the query.

For example, imagine you have a join, with an aggregation on top.

  SELECT t1.a, t2.b, COUNT(*) FROM t1 JOIN t2 ON (...) GROUP BY 1, 2;

How would you estimate the number of groups for the aggregate without
having the ndistinct estimate on the join result?

> 
>     In my POC patch, I've made the following catalog changes:
>     - Add *stxotherrel (oid) *and *stxjoinkeys (int2vector)* fields to /
>     pg_statistic_ext/
>     - Use the existing *stxkeys (int2vector)* to store the stats object
>     attributes of /stxotherrel/
>     - Create *pg_statistic_ext_otherrel_index* on /(stxrelid, stxotherrel)/
>     - Add stxdjoinmcv*(pg_join_mcv_list)* to /pg_statistic_ext_data/
> 
> 
> I like all these changes. Maybe "outer" rel rather than "other" rel, but
> it really doesn't matter this early on.
> 

Already commented on this earlier - I don't think we want to restrict
the joins to 2-way joins. So this "outerrel" thing won't work.

> 
>     To use them, we can let the planner detect patterns like this:
> 
>     /*
>     * JoinStatsMatch - Information about a detected join pattern
>     * Used internally to track what was matched in a join+filter pattern
>     */
>     typedef struct JoinStatsMatch
>     {
>     Oid target_rel; /* table OID of the estimation target */
>     AttrNumber targetrel_joinkey; /* target_rel's join column */
>     Oid other_rel; /* table OID of the filter source */
>     AttrNumber otherrel_joinkey; /* other_rel's join column */
>     List *filter_attnums; /* list of AttrNumbers for filter columns in
>     other_rel */
>     List *filter_values; /* list of Datum constant values being filtered */
>     Oid collation; /* collation for comparisons */
> 
>     /* Additional info to avoid duplicate work */
>     List *join_rinfos; /* list of join clause RestrictInfos */
>     RestrictInfo *filter_rinfo; /* the filter clause RestrictInfo */
>     } JoinStatsMatch;
> 
>     and add the detection logic in clauselist_selectivity_ext() and
>     get_foreign_key_join_selectivity(). 
> 
>     Statistics collection indeed needs the most thinking. For the
>     purpose of a POC, I added MCV join stats collection as part of ANALYZE
>     of one table (stxrel in pg_statistic_ext). I can do this because MCV
>     join stats are somewhat asymmetric. It allows me to have a target
>     table (referencing table for foreign key join) to ANALYZE, and we can
>     use the already collected MCVs of the joinkey column on the target
>     table to query the rows in the other table. This greatly mitigates
>     performance impact compared to actually joining two tables. However,
>     if we are to support more complex joins or other types of join stats
>     such as ndistinct or functional dependency, I found it hard to define
>     who's the target table (referencing table) and who's the other table
>     (referenced table) outside of the foreign key join scenario. So I
>     think for those more complex cases eventually we may as well 
>     perform the joins and collect the join stats separately. Alvaro
>     Herrera suggested offline that we could have a dedicated autovacuum
>     command option for collecting the join statistics.
> 
> 
> I agree, we have to perform the joins, as the rows collected are
> inherently dependent and skewed, and yes, it's going to be a maintenance
> overhead hit.
> 
> Initially I thought this could be mitigated somewhat by retaining
> rowsamples for each table, but those row samples would be independent of
> the joins, and the values we need are inherently dependent.
>  

Joining per-table samples don't work (which doesn't mean having samples
would not be useful, but not for joins). But I already mentioned the
paper I think describes how to build a sample for a join. Now that I
think of it I might have even posted a PoC patch implementing it using
SPI or something like that - but that'd be years ago, at this point.


regards

-- 
Tomas Vondra

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

Corey Huinker <corey.huinker@gmail.com> — 2026-02-02T01:41:28Z

>
> Right. I have not investigated plans for the JOB queries, but a common
> issue is that we pick a nested loop very early in the plan due to a poor
> estimate, and that leads to a sequence of nested loops. Which just
> amplifies the problem.
>

Even if the plan still uses nested loops, there are other things that
benefit from better row estimates. For instance, I've seen a case where the
planner decided to apply jit to the query because it expected 40 million
rows of results...and it got 4.


> > Catalog changes:
> >
> > pg_statistic_ext:
> > - New stats kind 'c' (join MCV) in stxkind
> > - New field stxotherrel (Oid): the other table in the join
> > - New field stxjoinkeys (int2vector): join column pair [primary_joinkey,
> >   other_joinkey]
> > - Existing stxkeys stores the filter column(s) on stxotherrel
> > - New index pg_statistic_ext_otherrel_index on (stxrelid, stxotherrel)
> >
>
> - Why do we need a new stats kind? I'd have expected we'd use the same
> 'm' value as for a single-relation stats, simply because a join result
> is just a relation too.
>
> - For a PoC it's OK to have stxotherrel, but the final patch should not
> be restricted to two relations. I think there needs to be an array of
> the joined rel OIDs, or something like that.
>

A parallel array of joined rel oids could lead to some refetching of
relation tuples unless we insisted that the keys be sorted the way we
currently sort stxkeys.

However, a multi-relation extended statistic object runs into a practical
issue when we fetch the remote rows that join to the local rowsample. We
could do that with an EphemeralNamedRelation and SPI (yuck), or more likely
we would leverage the index defined for the foreign key that we're
requiring (we already do this for referential integrity lookups on
inserts), and fishing out those foreign keys from a multi-table select,
which while do-able doesn't sound like fun. If we go that route then the
inability to find a supporting foreign key (and the index that goes with
it) should fail the statistic object creation.

So an array of RI constraint Oids (InvalidOid means "The attnum in the same
array position represents a local column/expression" would give us the
ability to do MCV combinations of columns from N tables along with the
local table, provided that there are fk constraints for each of the joins.


> FWIW I recognize figuring out the catalog changes is not easy - in fact
> I always found it so intimidation I ended up procrastinating and not
> making any progress on join statistics. So I really appreciate you
> taking a stab at this.
>

+1


>
> > pg_statistic_ext_data:
> > - New field stxdjoinmcv (pg_join_mcv_list): serialized join MCV data
> >
>
> I don't understand why we need this. AFAICS we should just treat the
> join result as a relation, and use the current pg_statistic_ext_data
> fields.
>

As I said above, we'd need a parallel array of constraint keys, rel ids, or
both to make that work.


>
> > How stats are collected:
> >
> > Join statistics are collected during ANALYZE of the primary table
> > (stxrelid). The current approach assumes a dependency relationship
> > between the join key column and the filter column(s) on the other
> > table. Specifically, during ANALYZE, we reuse the already-computed
> > single-column MCV stats for the primary table's join key column. For
> > each MCV value, we look up the matching row in the other table via the
> > join key and extract the filter column values, carrying over the
> > primary-side MCV frequency. This is not accurate in all cases, but
> > works reasonably well for the POC, especially for foreign-key-like
> > joins where the primary table's join key distribution is
> > representative of the join result.
> >
>
> For the PoC it's good enough, but I don't think we can rely on the
> per-column MCV lists like this.
>

Agreed. We must go to the source.



> The best approach I'm aware of is the "Index-Based Join Sampling" paper
> I mentioned earlier in this thread. I think it's OK to allow building
> statistics only for joins compatible with that sampling approach.
>
> It's not clear to me what should trigger building the stats. I assume
> it'd be done by ANALYZE, but that's per-table. So would it be triggered
> by ANALYZE on any of the joined tables, or just the "main" one? Would it
> require a new ANALYZE option, or something else? Not sure.
>

Just the main one. Madness lies in the alternative

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

Andrei Lepikhov <lepihov@gmail.com> — 2026-02-02T09:53:16Z

On 1/2/26 17:39, Tomas Vondra wrote:
> We can't simply store an opaque VIEW, and build the stats by simply
> executing it (and sampling the results). The whole premise of extended
> stats is that people define them to fix incorrect estimates. And with
> incorrect estimates the plan may be terrible, and the VIEW may not even
> complete.

Ok, I got the point.
I think linking to a join or foreign key seems restrictive. In my mind, 
extended statistics may go the following way:

CREATE STATISTICS abc_stat ON (t1.x,t2.y,t3.z) FROM t1,t2,t3;

Suppose t1.x,t2.y, and t3.z have a common equality operator.

Here we can build statistics on (t1.x = t2.y), (t1.x = t3.z), (t2.y = 
t3.z), and potentially (t1.x = t2.y = t3.z).

But I don't frequently detect problems with JOIN estimation using a 
single join clause. Usually, we have problems with (I) join trees 
(clauses spread across joins) and (II) a single multi-clause join.
We can't solve (I) here (kinda statistics on a VIEW might help, I 
think), but may ease (II) using:

CREATE STATISTICS abc_stat ON ((t1.x=t2.x),(t1.y=t2.y)) FROM t1,t2;

or even more bravely:

CREATE STATISTICS abc_stat ON ((t1.x=t2.x),(t1.y=t2.y)) FROM t1,t2
WHERE (t1.z <> t2.z);

-- 
regards, Andrei Lepikhov,
pgEdge

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

Tomas Vondra <tomas@vondra.me> — 2026-02-02T15:57:26Z

On 2/2/26 10:53, Andrei Lepikhov wrote:
> On 1/2/26 17:39, Tomas Vondra wrote:
>> We can't simply store an opaque VIEW, and build the stats by simply
>> executing it (and sampling the results). The whole premise of extended
>> stats is that people define them to fix incorrect estimates. And with
>> incorrect estimates the plan may be terrible, and the VIEW may not even
>> complete.
> 
> Ok, I got the point.
> I think linking to a join or foreign key seems restrictive. In my mind,
> extended statistics may go the following way:
> 

I agree we don't need to restrict to joins on foreign keys. I assume the
PoC patch requires f-keys because it makes building the join sample much
simpler / easier to think about.

The paper "sampling done right" paper I mentioned explains how to sample
general joins, as long as there are appropriate indexes. Foreign keys
always have those, but the constraint itself is not needed.

FWIW I think it's perfectly acceptable to allow extended stats only on
joins with appropriate indexes. Because without that we can't do the
sampling efficiently (or possibly at all).

But I'd leave this for later. For now it's perfectly fine to limit the
scope to FK joins, and then maybe expand the scope once we figure out
the other pieces.

> CREATE STATISTICS abc_stat ON (t1.x,t2.y,t3.z) FROM t1,t2,t3;
> 
> Suppose t1.x,t2.y, and t3.z have a common equality operator.
> 
> Here we can build statistics on (t1.x = t2.y), (t1.x = t3.z), (t2.y =
> t3.z), and potentially (t1.x = t2.y = t3.z).
> 

If I understand correctly you suggest we generate all "possible" joins
joining on the columns specified in the ON clause.

I think we shouldn't do that, as it's confused about the purpose of the
ON clause. That's meant to specify the list of columns on which to build
the extended statistic, but now it would be generating join clauses.

It has to be possible to have non-join attributes in the ON clause,
because that's how we can track correlation between the tables. Which is
the whole point, I think. It's not about the join clause selectivity, or
at least not just about it.

Moreover, wouldn't it be rather inefficient? Imagine you have a join
with two tables and two join clauses. (t1.a = t2.a) AND (t1.b = t2.b).
But with your syntax it'd be just

  CREATE STATISTICS s ON (t1.a, t1.b, t2.a, t2.b) FROM t1, t2;

And we'd have to build stats for (at least) 2 joins, because we have no
idea if t1.a joins to t2.a or t2.b.

So -1 to this, IMHO we need the "full" syntax with

 CREATE STATISTICS s ON (t1.c, t2.d)
                   FROM t1 JOIN t2 ON (t1.a = t2.a AND t1.b = t2.b);

We may need some additional statistics to track the selectivity of the
join clauses, in addition to the existing MCV stats built on the join
result.

> But I don't frequently detect problems with JOIN estimation using a
> single join clause. Usually, we have problems with (I) join trees
> (clauses spread across joins) and (II) a single multi-clause join.
> We can't solve (I) here (kinda statistics on a VIEW might help, I
> think), but may ease (II) using:
> 
> CREATE STATISTICS abc_stat ON ((t1.x=t2.x),(t1.y=t2.y)) FROM t1,t2;
> 
> or even more bravely:
> 
> CREATE STATISTICS abc_stat ON ((t1.x=t2.x),(t1.y=t2.y)) FROM t1,t2
> WHERE (t1.z <> t2.z);
> 

I honestly don't see why this would be better / simpler than the CREATE
STATISTICS grammar that simply allows joins in the FROM part.

regards

-- 
Tomas Vondra

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-04-29T05:59:28Z

Hi hackers,

I posted a proof-of-concept for join statistics in the end of January [1].
Thank you to Tomas, Corey, Tom, and Andrei for the detailed feedback!
They were very helpful in shaping the v1 design.

Rather than reply to each point inline (I plan to follow up on
specific items separately), I'd like to post the v1 patch and
summarize what changed since the PoC, along with benchmark results
that include the cardinality accuracy measurements Tomas asked for.

I've attached the v1 patch and am looking for reviews.

## What changed since the PoC

The major changes, largely driven by Tomas's feedback:

1. Index-based join sampling (Algorithm 1 from Leis et al., CIDR 2017 [3]).
The PoC relied on per-column MCV lists; v1 samples tuples from one
side of the join during ANALYZE and probes the other table via index
lookup to build a sample of the join result.

2. Catalog redesign. The PoC used a new stats kind 'c' and new catalog
columns. v1 reuses the existing MCV kind ('m') and stxdmcv field,
and stores join metadata in three new nullable columns on
pg_statistic_ext: stxjoinrels, stxkeyrefs, and stxjoinconds. These
are NULL for single-table statistics.

3. N-way catalog support. The catalog design now supports N-way joins
(stxjoinrels stores the OIDs of participating relations beyond
stxrelid, stxkeyrefs maps each stats key to its source relation,
stxjoinconds stores the join conditions). v1
collection is still limited to 2-way joins, but the schema is ready
for future extension.

4. Full JOIN syntax.

CREATE STATISTICS s (mcv) ON d.name
FROM fact f JOIN dim d ON (f.dim_id = d.id);

5. Dropped the auto-creation-from-FK patch (0002 from the PoC). As
Tom and Corey noted, this should remain explicit via CREATE
STATISTICS.

6. A lot more test coverage and code for edge cases.

Scope for v1 is deliberately narrow: equality joins, equality/IN
filters, simple Var references, inner joins, 2-way only, MCV only.

## Benchmark results

I measured using the Join Order Benchmark (JOB) [2] with a single
join statistics object on the keyword/movie_keyword join:

CREATE STATISTICS movie_keyword_keyword_stats (mcv)
ON k.keyword
FROM movie_keyword mk
JOIN keyword k ON (mk.keyword_id = k.id);

Benchmark methodology:

- 4 database instances, 3 cold + 3 warm runs each configuration.
- To eliminate ANALYZE sampling noise from the main comparison, I used
a single database for the "with stats" vs "without stats" runs:
CREATE STATISTICS + ANALYZE once, benchmark with stats, then DROP
STATISTICS and benchmark without. DROP STATISTICS only removes
pg_statistic_ext/pg_statistic_ext_data, leaving pg_statistic
untouched, so single-table estimates are identical in both runs.
- Separate noise calibration (master-vs-master on different DBs) and
regression check (master vs patched-no-stats) confirmed that (a)
cross-DB ANALYZE noise is ~30% of queries, up to 19x, and (b) the
patch causes zero estimate changes when no join stats are created.

Cardinality accuracy at the keyword/movie_keyword join node (32
queries where this join appears in both plans with the same actual
row count, allowing direct comparison of the estimated rows at
that join),
measured using q-error = max(estimated/actual, actual/estimated).
A q-error of 1.0 means the estimate exactly matches reality; higher
is worse.

Without stats With stats
geometric mean 103.4x 4.2x
median 131.7x 2.4x
90th percentile 1,230.6x 29.6x

16 improved, 0 regressed, 16 unchanged.

The 16 unchanged queries have filters that the MCV join stat doesn't
cover: LIKE patterns (e.g., 3a: k.keyword LIKE '%sequel%'), no
filter on keyword at all (e.g., 15c), or equality values that
aren't frequent enough to appear in the MCV list (e.g., 32a:
k.keyword = '10,000-mile-club').

Execution time (all 113 JOB queries):

Without stats With stats Speedup
warm (median) 114.1s 74.0s 1.54x
cold (median) 141.7s 103.7s 1.37x

All 38 unrelated queries (not involving keyword/movie_keyword) show
identical estimates, confirming no side effects.

## On using single-table extended stats for join estimation

Tomas suggested that using per-table extended statistics (functional
dependencies, MCV) in join estimation could be an orthogonal
improvement. I experimented with two approaches: (1) using functional
dependency stats to adjust ndistinct in eqjoinsel when a filter
column determines the join key, and (2) using single-table extended
MCV stats covering both the join key and filter columns to compute a
correlated post-filter MCV for join estimation. Both are sound in
theory, but neither showed measurable improvement on JOB. I'll
follow up with more detail on those experiments in a separate reply.

## Feedback welcome

I'd appreciate feedback on:
- The catalog design (stxjoinrels, stxkeyrefs, stxjoinconds)
- The index-based sampling implementation
- The planner integration (clausesel.c, costsize.c)
- What should be in scope for v1 vs deferred

Best,
Alex

[1]
https://www.postgresql.org/message-id/CAK98qZ0LwJbUoiZjjFXitojHy4UskkjYDiSd_JZfGE9LbfZm9w%40mail.gmail.com
[2] https://github.com/l-wang/join-order-benchmark
[3] https://www.cidrdb.org/cidr2017/papers/p9-leis-cidr17.pdf

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-04-29T13:08:58Z

On Tue, Apr 28, 2026 at 10:59 PM Alexandra Wang <
alexandra.wang.oss@gmail.com> wrote:
> I've attached the v1 patch and am looking for reviews.

Sorry for the CI breakage!

The Assert(ndims >= 2) in multi_sort_init() failed for join stats that
have a single filter column. Attached v2 that fixed it (relaxed to
ndims >= 1, plus a shadowed variable warning from GCC).

The pg_upgrade failure is expected due to the new catalog columns.
I will post a fix soon.

Best,
Alex

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-04-29T18:46:30Z

Attached v3 that fixes another shadowed variable warning that failed
the CompilerWarnings task. CI should be green now. Sorry about the
noise!

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-05-06T12:19:05Z
```
Here's the rebased patch, it only needed a catalog version bump.

Best,
Alex

-- 
Alexandra Wang
EDB: https://www.enterprisedb.com
```

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

jian he <jian.universality@gmail.com> — 2026-05-13T15:15:31Z

On Wed, May 6, 2026 at 8:19 PM Alexandra Wang
<alexandra.wang.oss@gmail.com> wrote:
>
> Here's the rebased patch, it only needed a catalog version bump.
>

No need to update src/include/catalog/catversion.h during dev cycle.

+ if (!IsA(lfirst(l), OpExpr))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("join statistics require a single equijoin condition per pair
of tables")));

In the error message, should we replace "equijoin" with "equality join"?
IMHO,  "equijoin" is kind of informal wording.

-- Unintended error case1
DROP TABLE IF EXISTS t1;
CREATE TABLE t1 (id INTEGER PRIMARY KEY, val TEXT NOT NULL);
CREATE STATISTICS x (mcv) ON t1.val FROM t1 JOIN t1 as t1s ON (t1.id = t1s.id);
alter table t1 alter column id set data type int8;
ERROR:  could not open relation with OID 0

-- Unintended error case2
DROP TABLE IF EXISTS t1, t2;
CREATE TABLE t1 (id INTEGER PRIMARY KEY, val TEXT NOT NULL);
CREATE TABLE t2 (id INTEGER PRIMARY KEY, t1_id INTEGER NOT NULL);
CREATE STATISTICS xx (mcv) ON t1.val FROM t2 JOIN t1 ON (t2.t1_id = t1.id);
alter table t1 alter column id set data type int8;
ERROR:  missing FROM-clause entry for table "t1"
LINE 1: alter table t1 alter column id set data type int8;
                                             ^

-- Unintended error case3
DROP TABLE IF EXISTS t1, t2;
CREATE TABLE t1 (id INTEGER PRIMARY KEY, val TEXT NOT NULL);
CREATE TABLE t2 (id INTEGER PRIMARY KEY, t1_id INTEGER generated always as (1));
CREATE STATISTICS xx (mcv) ON t1.val FROM t2 JOIN t1 ON (t2.t1_id = t1.id);
alter table t2 alter column t1_id set expression as (2);
ERROR:  missing FROM-clause entry for table "t1"
LINE 1: alter table t2 alter column t1_id set expression as (2);
                                             ^

-- Unintended error case4
DROP TABLE IF EXISTS t1, t2;
CREATE TABLE t1 (id INTEGER PRIMARY KEY, val TEXT NOT NULL);
CREATE TABLE t2 (id INTEGER PRIMARY KEY, t1_id INTEGER generated always as (1));
CREATE STATISTICS xx (mcv) ON t1.val FROM t2 JOIN t1 ON (t2 = t1);
ERROR:  cache lookup failed for attribute 0 of relation 18388

In src/test/regress/sql/stats_ext_crossrel.sql, we need to add test cases for
ALTER COLUMN SET DATA TYPE and ALTER COLUMN SET EXPRESSION on columns
involved in join statistics.
These ALTER TABLE operations will internally recreate the affected join stats.

src/test/regress/sql/stats_ext_crossrel.sql currently lacks tests for equality
joins where the join qual contains whole-row variable references.This is
important because whole-row variables raise the question of whether join
statistics should be recreated when any column in the relation is modified via
ALTER COLUMN SET DATA TYPE or ALTER COLUMN SET EXPRESSION.



--
jian
https://www.enterprisedb.com/

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-05-13T17:30:56Z

Hi Jian,

Thanks for reviewing! At the current stage, I'm more interested in
reviews around the overall design and the feasibility of the current
approach, as I mentioned earlier:

On Tue, Apr 28, 2026 at 10:59 PM Alexandra Wang <
alexandra.wang.oss@gmail.com> wrote:
> I'd appreciate feedback on:
> - The catalog design (stxjoinrels, stxkeyrefs, stxjoinconds)
> - The index-based sampling implementation
> - The planner integration (clausesel.c, costsize.c)
> - What should be in scope for v1 vs deferred

I will incorporate your review feedback in the next revision, but for
now, I'd like to focus the discussion on the above areas before
polishing the existing patch.

On Wed, May 13, 2026 at 8:16 AM jian he <jian.universality@gmail.com> wrote:
> On Wed, May 6, 2026 at 8:19 PM Alexandra Wang
> <alexandra.wang.oss@gmail.com> wrote:
> >
> > Here's the rebased patch, it only needed a catalog version bump.
> >
>
> No need to update src/include/catalog/catversion.h during dev cycle.

I needed to bump the catalog version because CI broke without that
change.

> + if (!IsA(lfirst(l), OpExpr))
> + ereport(ERROR,
> + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
> + errmsg("join statistics require a single equijoin condition per pair
> of tables")));

> In the error message, should we replace "equijoin" with "equality join"?
> IMHO,  "equijoin" is kind of informal wording.

OK. I'll update the error message in the next revision.

> -- Unintended error case1
> DROP TABLE IF EXISTS t1;
> CREATE TABLE t1 (id INTEGER PRIMARY KEY, val TEXT NOT NULL);
> CREATE STATISTICS x (mcv) ON t1.val FROM t1 JOIN t1 as t1s ON (t1.id =
t1s.id);
> alter table t1 alter column id set data type int8;
> ERROR:  could not open relation with OID 0
>
> -- Unintended error case2
> DROP TABLE IF EXISTS t1, t2;
> CREATE TABLE t1 (id INTEGER PRIMARY KEY, val TEXT NOT NULL);
> CREATE TABLE t2 (id INTEGER PRIMARY KEY, t1_id INTEGER NOT NULL);
> CREATE STATISTICS xx (mcv) ON t1.val FROM t2 JOIN t1 ON (t2.t1_id = t1.id
);
> alter table t1 alter column id set data type int8;
> ERROR:  missing FROM-clause entry for table "t1"
> LINE 1: alter table t1 alter column id set data type int8;
>                                              ^
>
> -- Unintended error case3
> DROP TABLE IF EXISTS t1, t2;
> CREATE TABLE t1 (id INTEGER PRIMARY KEY, val TEXT NOT NULL);
> CREATE TABLE t2 (id INTEGER PRIMARY KEY, t1_id INTEGER generated always
as (1));
> CREATE STATISTICS xx (mcv) ON t1.val FROM t2 JOIN t1 ON (t2.t1_id = t1.id
);
> alter table t2 alter column t1_id set expression as (2);
> ERROR:  missing FROM-clause entry for table "t1"
> LINE 1: alter table t2 alter column t1_id set expression as (2);
>                                              ^
>
> -- Unintended error case4
> DROP TABLE IF EXISTS t1, t2;
> CREATE TABLE t1 (id INTEGER PRIMARY KEY, val TEXT NOT NULL);
> CREATE TABLE t2 (id INTEGER PRIMARY KEY, t1_id INTEGER generated always
as (1));
> CREATE STATISTICS xx (mcv) ON t1.val FROM t2 JOIN t1 ON (t2 = t1);
> ERROR:  cache lookup failed for attribute 0 of relation 18388
>
> In src/test/regress/sql/stats_ext_crossrel.sql, we need to add test cases
for
> ALTER COLUMN SET DATA TYPE and ALTER COLUMN SET EXPRESSION on columns
> involved in join statistics.
> These ALTER TABLE operations will internally recreate the affected join
stats.
>
> src/test/regress/sql/stats_ext_crossrel.sql currently lacks tests for
equality
> joins where the join qual contains whole-row variable references.This is
> important because whole-row variables raise the question of whether join
> statistics should be recreated when any column in the relation is
modified via
> ALTER COLUMN SET DATA TYPE or ALTER COLUMN SET EXPRESSION.

Good call! I'll make sure to include these edge cases in the next
revision.

Best,
Alex

--
Alexandra Wang
EDB: https://www.enterprisedb.com

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-05-14T23:13:26Z

Patch needed a rebase, so here's v5.

I've dropped the changes to catversion.h so hopefully I won't need to
rebase too often. Sorry about the noise!

While I was at it, I also addressed the issues Jian mentioned -- all
minor fixes in parse_utilcmd.c (a one-line detection fix for the ALTER
COLUMN error, an error guard for whole-row variables, and rewording
"equijoin" to "equality join"). Other than that, there are no major
changes in v5 compared to v2-v4. At this stage I'd really appreciate
feedback on the overall design approach.

Best,
Alex

-- 
Alexandra Wang
EDB: https://www.enterprisedb.com

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-05-15T05:08:56Z

Attached v6. It should fix the CI failures on NetBSD/Windows by
changing the ALTER TYPE invalidation test added in v5 from
text->varchar(100) to integer->numeric, avoiding encoding-dependent
width estimates.

Best,
Alex


-- 
Alexandra Wang
EDB: https://www.enterprisedb.com

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-05-15T15:30:31Z

Here's v7, another attempt to fix the unstable tests.

Best,
Alex

On Thu, May 14, 2026 at 10:08 PM Alexandra Wang <
alexandra.wang.oss@gmail.com> wrote:

> Attached v6. It should fix the CI failures on NetBSD/Windows by
> changing the ALTER TYPE invalidation test added in v5 from
> text->varchar(100) to integer->numeric, avoiding encoding-dependent
> width estimates.
>
> Best,
> Alex
>
>
> --
> Alexandra Wang
> EDB: https://www.enterprisedb.com
>


-- 
Alexandra Wang
EDB: https://www.enterprisedb.com

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

Tom Lane <tgl@sss.pgh.pa.us> — 2026-05-21T20:25:13Z

Alexandra Wang <alexandra.wang.oss@gmail.com> writes:
> Here's v7, another attempt to fix the unstable tests.

Hi Alexandra,

I signed up for an in-person review of this at PGConf.dev, but
the schedule doesn't seem to be working in favor of making that
happen.  If you see this and happen to run into me in the
hallway, I'm happy to chat, but in any case here are my
rather-hasty review notes.

I think it's okay if v1 only handles 2-way joins, as long as the
catalog representation is prepared for more.  Restricting to
cases where we can do index-based sampling seems fine too.
Those things could be relaxed later if it seems worthwhile,
but we'd have a creditable feature even without.

I didn't read the sampling code in any detail.  I think you will
need to put more thought into what is user-friendly behavior
in case the required index doesn't exist or doesn't have the
right properties.  (I think the tests for that might not be
strong enough, either.)

I think you could simplify some code noticeably if you included the
anchor rel's OID as the first element of stxjoinrels[].  Yeah,
it'd be redundant with stxrelid, but so what?  It's not like 
pg_statistic_ext rows are narrow enough that anyone would notice
the extra 4 bytes.  I think this would simplify some of the
relationships within the data structures, too, eg all varnos in
the expressions could be considered to reference stxjoinrels[].

I don't love stxkeyrefs[].  I wonder if it's time to throw away
stxkeys[], represent all the target columns as regular expression
trees in stxexprs, and then special-case columns that are simple
Vars where appropriate at execution.

(In the same vein, I dislike the grammar's separation of plain
columns from expressions; I'd like to replace stats_params
with expr_list and sort it all out later.  But perhaps that's
material for a separate patch.)

We will need to put more thought into permissions: I don't think
requiring all the tables to have the same owner is workable.
(What happens if someone tries to ALTER OWNER later?)  However,
if they don't all have the same owner, there are potential security
problems, so the right restriction is not obvious.  This is not
necessary to solve now; there are bigger questions to worry about.
But we'll need an answer before it's committable.

It's not too soon to write some user-facing documentation.
CREATE STATISTICS man page obviously needs attention, but
also the discussion of extended stats in perform.sgml.
And catalogs.sgml.  I find that writing that sort of stuff
helps to clarify where one's design is weak.

			regards, tom lane

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

Chengpeng Yan <chengpeng_yan@outlook.com> — 2026-05-25T12:15:47Z

Hi,

> On May 15, 2026, at 23:30, Alexandra Wang <alexandra.wang.oss@gmail.com> wrote:
> 
> Here's v7, another attempt to fix the unstable tests.

Thanks for working on this. I have a few design comments about the lifecycle
and the intended scope of the join statistic.

First, the index dependency contract seems worth clarifying. CREATE STATISTICS
records a normal dependency on the selected index, so DROP INDEX is blocked
unless CASCADE is used, although that index is not part of the statistics
definition. But ANALYZE appears to re-discover a suitable index when refreshing
the statistic. Is the index intended to be part of the statistic's persistent
contract, or only a creation-time proof that index-based sampling is possible?
If the latter, should DROP INDEX still be blocked when another equivalent index
exists?

Second, this seems related to the earlier concern that ANALYZE is per-table.
The statistic is owned by the anchor relation, but its contents depend on the
probed relation too. In the current patch, ANALYZE on the probed relation can
refresh its own statistics without refreshing the join statistic. If the
probed relation has changed substantially, that leaves a possible staleness
gap where the planner combines fresh base-table statistics with stale
cross-relation skew information.

Third, the contract for non-unique indexes on the probed side seems worth
clarifying. The comments define raw_sel as anchor-relative:
P(join AND covered_filters) / anchor_totalrows, roughly Jf / anchor_totalrows,
where Jf is the number of joined rows satisfying the covered filters. But the
implementation computes raw_sel from MCV frequencies. Since the MCV list is
built from sampled joined rows, a plain MCV frequency is naturally measured
inside that joined sample, roughly Jf / J where J is the sampled join-result
size. It would be useful to clarify when those two quantities are expected to
be equivalent, especially when a non-unique probed-side index allows one
anchor row to contribute multiple joined rows.

These two measures are close in FK-like cases where the joined sample size
tracks the anchor sample size. With a non-unique lookup, one anchor row may
appear many times in the joined sample. For example, if one key matches many
red rows and another key matches only one blue row, red may dominate the
joined sample because of match multiplicity. That frequency describes the
distribution within the joined result, but not how many matching joined rows
are produced per anchor row. It would be useful to state whether such
one-to-many joins are outside the current supported scope, or how the
MCV-derived raw_sel accounts for how many joined rows each anchor row
contributed before it is converted into planner join selectivity.

--
Best regards,
Chengpeng Yan

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

Tomas Vondra <tomas@vondra.me> — 2026-05-25T14:34:51Z

On 5/21/26 22:25, Tom Lane wrote:
> Alexandra Wang <alexandra.wang.oss@gmail.com> writes:
>> Here's v7, another attempt to fix the unstable tests.
> 
> Hi Alexandra,
> 
> I signed up for an in-person review of this at PGConf.dev, but
> the schedule doesn't seem to be working in favor of making that
> happen.  If you see this and happen to run into me in the
> hallway, I'm happy to chat, but in any case here are my
> rather-hasty review notes.
> 
> I think it's okay if v1 only handles 2-way joins, as long as the
> catalog representation is prepared for more.  Restricting to
> cases where we can do index-based sampling seems fine too.
> Those things could be relaxed later if it seems worthwhile,
> but we'd have a creditable feature even without.
> 

+1

My assumption is allowing larger joins would be a somewhat mechanical.
I'm not aware of additional problems on top of 2-way joins.

I think we should aim to support larger joins. At the unconference there
were suggestions maybe it would be enough to support 2-way joins, but
it's not hard to construct cases where that's no sufficient. Consider a
fact table, joining to two dimensions. It's common for the dimensions to
be correlated in various ways, and 2-way joins can't handle these cases.

> I didn't read the sampling code in any detail.  I think you will
> need to put more thought into what is user-friendly behavior
> in case the required index doesn't exist or doesn't have the
> right properties.  (I think the tests for that might not be
> strong enough, either.)
> 

What would be the most "user-friendly behavior" in this case?

I think we can either (a) refuse defining/building the join statistics
in this case, or (b) fallback to sampling not requiring an index (but
then it'll be way more expensive).

I think (a) should be fine for now, i.e. we should require an index.
Most of the joins will be on FK constraints, or something like that (the
FK may not be defined, but there will be a PK on one side).

Not sure if we should simply refuse building the stats, or if it's
enough to detect this while building the statistics. I'd say enforcing
this during DDL (CREATE STATISTICS, DROP INDEX, ...) is better,
otherwise users may not notice the statistics stopped building.

> I think you could simplify some code noticeably if you included the
> anchor rel's OID as the first element of stxjoinrels[].  Yeah,
> it'd be redundant with stxrelid, but so what?  It's not like 
> pg_statistic_ext rows are narrow enough that anyone would notice
> the extra 4 bytes.  I think this would simplify some of the
> relationships within the data structures, too, eg all varnos in
> the expressions could be considered to reference stxjoinrels[].
> 
> I don't love stxkeyrefs[].  I wonder if it's time to throw away
> stxkeys[], represent all the target columns as regular expression
> trees in stxexprs, and then special-case columns that are simple
> Vars where appropriate at execution.
> 

+1, I don't see a reason to not store the anchor rel separately.

> (In the same vein, I dislike the grammar's separation of plain
> columns from expressions; I'd like to replace stats_params
> with expr_list and sort it all out later.  But perhaps that's
> material for a separate patch.)
> 

FWIW the extended stats copied this from pg_index, which also stores
keys and expressions separately. I suppose there was a reason for that,
most likely performance - is cheaper to compare attnums than
expressions, and plain keys are much more common.

Maybe that's no longer true, or maybe it's not as important for extended
stats (there's likely fewer of those, compared to indexes).

> We will need to put more thought into permissions: I don't think
> requiring all the tables to have the same owner is workable.
> (What happens if someone tries to ALTER OWNER later?)  However,
> if they don't all have the same owner, there are potential security
> problems, so the right restriction is not obvious.  This is not
> necessary to solve now; there are bigger questions to worry about.
> But we'll need an answer before it's committable.
> 

I have not thought about this at all, but what can we do if the tables
have different owners? I suppose we could require the stxowner to have
SELECT privilege on the joined relations (instead of owning them).

> It's not too soon to write some user-facing documentation.
> CREATE STATISTICS man page obviously needs attention, but
> also the discussion of extended stats in perform.sgml.
> And catalogs.sgml.  I find that writing that sort of stuff
> helps to clarify where one's design is weak.
> 

+1

regards

-- 
Tomas Vondra

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

Tom Lane <tgl@sss.pgh.pa.us> — 2026-05-25T15:03:57Z

Tomas Vondra <tomas@vondra.me> writes:
> On 5/21/26 22:25, Tom Lane wrote:
>> I don't love stxkeyrefs[].  I wonder if it's time to throw away
>> stxkeys[], represent all the target columns as regular expression
>> trees in stxexprs, and then special-case columns that are simple
>> Vars where appropriate at execution.
>> (In the same vein, I dislike the grammar's separation of plain
>> columns from expressions; I'd like to replace stats_params
>> with expr_list and sort it all out later.  But perhaps that's
>> material for a separate patch.)

> FWIW the extended stats copied this from pg_index, which also stores
> keys and expressions separately. I suppose there was a reason for that,
> most likely performance - is cheaper to compare attnums than
> expressions, and plain keys are much more common.

I think I might be to blame for the separate storage of indexprs.
If so, the motivation was to avoid breakage of older code that only
knew about indkey[].  (Of course, such code would necessarily fail
on indexes with expressions, but we wanted to avoid breakage for the
common case of no-expressions.)  I don't think that consideration is
nearly as pressing for extended stats.  There's probably a lot less
client-side code that knows about extended stats at all, and what
there is seems more likely to rely on the server-side display
functions than to dig into the catalog details for itself.  Also,
if there is anything that's looking at pg_statistic_ext details,
it will need work anyway after this patch; there's no way around that.

>> We will need to put more thought into permissions: I don't think
>> requiring all the tables to have the same owner is workable.

> I have not thought about this at all, but what can we do if the tables
> have different owners? I suppose we could require the stxowner to have
> SELECT privilege on the joined relations (instead of owning them).

Yeah, the rough idea I had was to require ownership on the anchor
table and SELECT on the rest.  But it's not terribly clear what
to do if that SELECT privilege gets revoked.

I also wonder to what extent we have a problem with users of the
anchor table being able to infer something about the contents of the
other tables via plan choices, and whether it matters if they can.
They may well be able to make the same inferences anyway from query
results.  For that matter, if a user is able to issue a query for
which a set of extended join stats is relevant, it seems likely that
that must mean she has SELECT on the other tables anyway.  But
maybe I'm missing some case where that wouldn't be true.

			regards, tom lane

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-05-27T17:49:44Z

Hi Tom and Tomas,

Thank you so much for the feedback!

On Mon, May 25, 2026 at 8:04 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Tomas Vondra <tomas@vondra.me> writes:
> > On 5/21/26 22:25, Tom Lane wrote:
> >> I don't love stxkeyrefs[].  I wonder if it's time to throw away
> >> stxkeys[], represent all the target columns as regular expression
> >> trees in stxexprs, and then special-case columns that are simple
> >> Vars where appropriate at execution.
> >> (In the same vein, I dislike the grammar's separation of plain
> >> columns from expressions; I'd like to replace stats_params
> >> with expr_list and sort it all out later.  But perhaps that's
> >> material for a separate patch.)
>
> > FWIW the extended stats copied this from pg_index, which also stores
> > keys and expressions separately. I suppose there was a reason for that,
> > most likely performance - is cheaper to compare attnums than
> > expressions, and plain keys are much more common.
>
> I think I might be to blame for the separate storage of indexprs.
> If so, the motivation was to avoid breakage of older code that only
> knew about indkey[].  (Of course, such code would necessarily fail
> on indexes with expressions, but we wanted to avoid breakage for the
> common case of no-expressions.)  I don't think that consideration is
> nearly as pressing for extended stats.  There's probably a lot less
> client-side code that knows about extended stats at all, and what
> there is seems more likely to rely on the server-side display
> functions than to dig into the catalog details for itself.  Also,
> if there is anything that's looking at pg_statistic_ext details,
> it will need work anyway after this patch; there's no way around that.

I'm working on removing stxkeys[] as a prerequisite commit before the main
join
stats patch, representing all target columns as Var nodes in stxexprs, as
you
both suggested.

One question about the pg_stats_ext view: currently it has two complementary
columns:

- attnames (name[]) — Names of the columns included in the statistics object
- exprs (text[]) — Expressions included in the statistics object

With stxkeys gone from the catalog, should the view:

(a) Stay as-is: keep attnames and exprs as separate columns with the same
semantics. Implemented via a helper function that extracts plain column
names
from the unified stxexprs.

or

(b) Mirror the catalog: remove attnames, make exprs show all entries (both
column names and expressions together in one text[] array).

Any preference?

-- 
Alexandra Wang
EDB: https://www.enterprisedb.com

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

Tomas Vondra <tomas@vondra.me> — 2026-05-27T19:08:34Z


On 5/27/26 19:49, Alexandra Wang wrote:
> Hi Tom and Tomas,
> 
> Thank you so much for the feedback!
> 
> On Mon, May 25, 2026 at 8:04 AM Tom Lane <tgl@sss.pgh.pa.us
> <mailto:tgl@sss.pgh.pa.us>> wrote:
>> Tomas Vondra <tomas@vondra.me <mailto:tomas@vondra.me>> writes:
>> > On 5/21/26 22:25, Tom Lane wrote:
>> >> I don't love stxkeyrefs[].  I wonder if it's time to throw away
>> >> stxkeys[], represent all the target columns as regular expression
>> >> trees in stxexprs, and then special-case columns that are simple
>> >> Vars where appropriate at execution.
>> >> (In the same vein, I dislike the grammar's separation of plain
>> >> columns from expressions; I'd like to replace stats_params
>> >> with expr_list and sort it all out later.  But perhaps that's
>> >> material for a separate patch.)
>>
>> > FWIW the extended stats copied this from pg_index, which also stores
>> > keys and expressions separately. I suppose there was a reason for that,
>> > most likely performance - is cheaper to compare attnums than
>> > expressions, and plain keys are much more common.
>>
>> I think I might be to blame for the separate storage of indexprs.
>> If so, the motivation was to avoid breakage of older code that only
>> knew about indkey[].  (Of course, such code would necessarily fail
>> on indexes with expressions, but we wanted to avoid breakage for the
>> common case of no-expressions.)  I don't think that consideration is
>> nearly as pressing for extended stats.  There's probably a lot less
>> client-side code that knows about extended stats at all, and what
>> there is seems more likely to rely on the server-side display
>> functions than to dig into the catalog details for itself.  Also,
>> if there is anything that's looking at pg_statistic_ext details,
>> it will need work anyway after this patch; there's no way around that.
> 
> I'm working on removing stxkeys[] as a prerequisite commit before the
> main join
> stats patch, representing all target columns as Var nodes in stxexprs,
> as you
> both suggested.
> 
> One question about the pg_stats_ext view: currently it has two complementary
> columns:
> 
> - attnames (name[]) — Names of the columns included in the statistics object
> - exprs (text[]) — Expressions included in the statistics object
> 
> With stxkeys gone from the catalog, should the view:
> 
> (a) Stay as-is: keep attnames and exprs as separate columns with the same
> semantics. Implemented via a helper function that extracts plain column
> names
> from the unified stxexprs.
> 
> or
> 
> (b) Mirror the catalog: remove attnames, make exprs show all entries (both
> column names and expressions together in one text[] array).
> 
> Any preference?
> 

My 2c: AFAIR there's no fundamental reason to keep those two lists
separate, other than that expressions were "bolted on" later, after we
already had stats on plain attributes. In hindsight, it might have been
better to just unify the view back then, probably.

I personally would be OK with just unifying adjusting the view, and
showing a single list (with both attributes and expressions). IIUC the
plan is to just store a list of expressions anyway, with attributes
represented as Vars. So the view would have to do more work just to
produce the "old" output, with little benefit.

The one argument against this that I can think of is possibly breaking
tools that use this view. IIRC pg_dump is reading the view when
exporting/importing the statistics. That might need some adjustments
(and there's also pg_stats_ext_exprs), but maybe it's easier to keep the
view consistent.

Also, maybe this is one more argument against the "optimizer view" idea
Corey mentioned in Vancouver last week? Because surely we'll want to
include the join statistics in export/import, and for the view approach
we'd need to invent a fair amount of code to do that. Maybe?


regards

-- 
Tomas Vondra

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

Tom Lane <tgl@sss.pgh.pa.us> — 2026-05-27T20:31:16Z

Tomas Vondra <tomas@vondra.me> writes:
> On 5/27/26 19:49, Alexandra Wang wrote:
>> One question about the pg_stats_ext view: currently it has two complementary
>> columns:
>> 
>> - attnames (name[]) — Names of the columns included in the statistics object
>> - exprs (text[]) — Expressions included in the statistics object
>> 
>> With stxkeys gone from the catalog, should the view:
>> (a) Stay as-is: keep attnames and exprs as separate columns with the same
>> semantics. Implemented via a helper function that extracts plain column
>> names from the unified stxexprs.
>> or
>> (b) Mirror the catalog: remove attnames, make exprs show all entries (both
>> column names and expressions together in one text[] array).

> My 2c: AFAIR there's no fundamental reason to keep those two lists
> separate, other than that expressions were "bolted on" later, after we
> already had stats on plain attributes. In hindsight, it might have been
> better to just unify the view back then, probably.

Yeah.  There are some other oddities that arise from that: expressions
get shoved to the end.  For example, if I put in

create statistics my_stats (mcv) on ten, (ten+four), four from tenk1;

pg_dump will regurgitate that as

CREATE STATISTICS public.my_stats (mcv) ON four, ten, (ten + four) FROM public.tenk1;

and I see that that column ordering is consistent with what appears in
pg_stats_ext and perhaps other places.  I'd expect a rewritten version
to stop doing that and preserve the user-written column order.
So there are going to be some potential minor incompatibilities for
anything that is looking too closely at this view, and it seems to
me that it might be better for such code to fail noisily rather than
perhaps silently mis-associate stats with columns.

(It might be a good idea to have some test cases that exercise this
kind of scenario in pg_upgrade, especially now that we are trying to
transfer extended stats in upgrades...)

			regards, tom lane

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

Corey Huinker <corey.huinker@gmail.com> — 2026-05-27T22:02:20Z

>
> Also, maybe this is one more argument against the "optimizer view" idea
> Corey mentioned in Vancouver last week? Because surely we'll want to
> include the join statistics in export/import, and for the view approach
> we'd need to invent a fair amount of code to do that. Maybe?
>

We definitely want join statistics in the export/import.

To my mind, having stats on certain views would be extremely simple for
export/import, we'd simply have one more relkind that makes it into the
system views pg_stats and pg_stats_ext, and the statistics for that new
relation would plug into pg_statistic with no catalog change to
pg_statistic whatsoever. Additionally, allowing certain kinds of views (or
a relation relkind that's functionally equivalent to a view) to have
statistics makes it easy to define extended statistics on those views, with
no catalog change to pg_statistic_ext.

Having something in pg_class to anchor existing per-attribute and
multi-attribute stats off of seems like a big win to me. We'd get all
pre-existing statistics types for free, statistics kinds provided by
extensions for free, extended stats for free, import and export for free.
Well, not free, we just have to remove the exclusion that views (or
whatever relkind we create) can't have stats.

Having said all that, the statistics import code reads from
pg_statistic_ext but obviously never modifies it, it's all about
constructing the pg_statistic_ext_data row, and it need to only concern
itself with importing to the current version, so internal catalog changes
to pg_statistic_ext wouldn't be that big of a deal.

If, however, we want to stick with the notion that all non-relation,
not-attribute stats are extended stats, then we have to remodel a bit:

- as Tom and Tomas mentioned, we'd probably want to dispense with the
negative attnums and stxexprs, as those are already a bit of a pain to deal
with. That might be worth of a patch even without join statistics.

- we'd want a way to express stats for all the individual
columns/expressions defined in the join stats object, i.e. "what is the MCV
of B.name for rows joined by A on A.b_id"?

- we'd want some way of excluding the non-interesting combinations of
columns. If we had a stat on A.qty, A.price, B.cust_name, C.sale_date,
D.item_name, then we'd have 5-factorial MCV combinations in addition to the
5 single-column stats, and the (A.qty, A.price) combinations can already be
covered by a non-join extended stat.

It's those things that make optimizer views so attractive to me - we
already have a way to store individual column stats (pg_statistic) and shut
them off when not interesting (pg_attribute.attstattarget), and extended
statistics are a great way to describe which combinations of columns are
interesting to us.

Typing all this has me thinking that there may be a third way:

- statistics objects become pg_class objects, stxkeys and stxexprs  become
pg_attribute rows
- pg_statisic_ext keeps (stxrelid, stxstattarget, stxkind), adds stxid
(pointing to new pg_class object)  sort of like pg_index
- pg_statistic_ext_data remains as-is

and we'd set per-column stats collection like ALTER STATISTICS foo ALTER
COLUMN.

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

Tomas Vondra <tomas@vondra.me> — 2026-05-28T01:29:15Z

On 5/28/26 00:02, Corey Huinker wrote:
>     Also, maybe this is one more argument against the "optimizer view" idea
>     Corey mentioned in Vancouver last week? Because surely we'll want to
>     include the join statistics in export/import, and for the view approach
>     we'd need to invent a fair amount of code to do that. Maybe?
> 
> 
> We definitely want join statistics in the export/import. 
> 
> To my mind, having stats on certain views would be extremely simple for
> export/import, we'd simply have one more relkind that makes it into the
> system views pg_stats and pg_stats_ext, and the statistics for that new
> relation would plug into pg_statistic with no catalog change to
> pg_statistic whatsoever. Additionally, allowing certain kinds of views
> (or a relation relkind that's functionally equivalent to a view) to have
> statistics makes it easy to define extended statistics on those views,
> with no catalog change to pg_statistic_ext.
> 

Ah, so you're proposing supporting CREATE STATISTICS on some views? I
guess that's one way to support stats on joins, without having to rework
the schema. I'm still not a huge fan of it, because it just uses views
as a workaround to store the join definition, nothing else. To me it
seems a weird to require creating a new relation just for this, and we
already envisioned CREATE STATISTICS would cover joins. My guess is that
may be why DB2 did it this way, as they probably didn't have anything
like extended stats at that point.

> Having something in pg_class to anchor existing per-attribute and multi-
> attribute stats off of seems like a big win to me. We'd get all pre-
> existing statistics types for free, statistics kinds provided by
> extensions for free, extended stats for free, import and export for
> free. Well, not free, we just have to remove the exclusion that views
> (or whatever relkind we create) can't have stats.
> 

TBH the grammar / catalog stuff seems like a relatively minor part of
this patch. To me, the difficult part seems to be the sampling / analyze
part, and then matching it to the query during planning. And all of this
seems exactly the same no matter how the stats are defined.

OTOH maybe allowing CREATE STATISTICS on views would be independently
useful too, once we have the later parts. Not sure.

> Having said all that, the statistics import code reads from
> pg_statistic_ext but obviously never modifies it, it's all about
> constructing the pg_statistic_ext_data row, and it need to only concern
> itself with importing to the current version, so internal catalog
> changes to pg_statistic_ext wouldn't be that big of a deal.
> 
> If, however, we want to stick with the notion that all non-relation,
> not-attribute stats are extended stats, then we have to remodel a bit:
> 
> - as Tom and Tomas mentioned, we'd probably want to dispense with the
> negative attnums and stxexprs, as those are already a bit of a pain to
> deal with. That might be worth of a patch even without join statistics.
> 
> - we'd want a way to express stats for all the individual columns/
> expressions defined in the join stats object, i.e. "what is the MCV of
> B.name for rows joined by A on A.b_id"?
> 

Maybe I misunderstand, but don't we already do this for statistics on
expressions?

> - we'd want some way of excluding the non-interesting combinations of
> columns. If we had a stat on A.qty, A.price, B.cust_name, C.sale_date,
> D.item_name, then we'd have 5-factorial MCV combinations in addition to
> the 5 single-column stats, and the (A.qty, A.price) combinations can
> already be covered by a non-join extended stat.
> 

I don't follow. What 5-factorial combinations? We only ever build a
single MCV for a given statistics object.

> It's those things that make optimizer views so attractive to me - we
> already have a way to store individual column stats (pg_statistic) and
> shut them off when not interesting (pg_attribute.attstattarget), and
> extended statistics are a great way to describe which combinations of
> columns are interesting to us.
> 

I may be missing something, but I honestly the only benefit of views I
can think of is already having the join definition in a catalog.

> Typing all this has me thinking that there may be a third way:
> 
> - statistics objects become pg_class objects, stxkeys and stxexprs 
> become pg_attribute rows
> - pg_statisic_ext keeps (stxrelid, stxstattarget, stxkind), adds stxid
> (pointing to new pg_class object)  sort of like pg_index
> - pg_statistic_ext_data remains as-is
> 
> and we'd set per-column stats collection like ALTER STATISTICS foo ALTER
> COLUMN.

I don't follow. Why should statistics object be pg_class objects? In my
mind pg_class is meant for "relations" (as in, table-like things), and
statistics objects are not like that. I suppose this is related to your
earlier suggestion

  Having something in pg_class to anchor existing per-attribute and
  multi-attribute stats off of seems like a big win to me.

but it's not clear to me why would that be? All statistics are tied to a
relation (or multiple relations) in the end, and I don't see why would
the view make anything simpler. What are the wins?

Could you elaborate? It's entirely possible I just don't see something
obvious, or maybe you explained this in Vancouver and I managed to
forget the details. Sorry about that.

regards

-- 
Tomas Vondra

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

Corey Huinker <corey.huinker@gmail.com> — 2026-05-28T19:03:26Z

>
> > To my mind, having stats on certain views would be extremely simple for
> > export/import, we'd simply have one more relkind that makes it into the
> > system views pg_stats and pg_stats_ext, and the statistics for that new
> > relation would plug into pg_statistic with no catalog change to
> > pg_statistic whatsoever. Additionally, allowing certain kinds of views
> > (or a relation relkind that's functionally equivalent to a view) to have
> > statistics makes it easy to define extended statistics on those views,
> > with no catalog change to pg_statistic_ext.
> >
>
> Ah, so you're proposing supporting CREATE STATISTICS on some views? I
> guess that's one way to support stats on joins, without having to rework
> the schema. I'm still not a huge fan of it, because it just uses views
> as a workaround to store the join definition, nothing else. To me it
> seems a weird to require creating a new relation just for this, and we
> already envisioned CREATE STATISTICS would cover joins. My guess is that
> may be why DB2 did it this way, as they probably didn't have anything
> like extended stats at that point.
>

They did have extended stats.

Here are some example RUNSTATS calls from
https://www.ibm.com/docs/en/db2/11.5.x?topic=commands-runstats

    RUNSTATS ON TABLE employee ON ALL COLUMNS AND COLUMNS ((JOB, WORKDEPT,
SEX))
        WITH DISTRIBUTION

In our lingo, this is roughly:

    CREATE STATISTICS foo ON (job, workdept, sex) FROM employee;
    ANALYZE employee;

And you can tweak individual columns

    RUNSTATS ON VIEW product_sales_view
     WITH DISTRIBUTION ON COLUMNS (category NUM_FREQVALUES 100
NUM_QUANTILES 100,
    type, product_key) DEFAULT NUM_FREQVALUES 50 NUM_QUANTILES 50

But the lesson I took away from this doc and corroborated by meeting with
someone who used to work on DB2 planner is that they have an equivalent of
extended stats.

>
> > Having something in pg_class to anchor existing per-attribute and multi-
> > attribute stats off of seems like a big win to me. We'd get all pre-
> > existing statistics types for free, statistics kinds provided by
> > extensions for free, extended stats for free, import and export for
> > free. Well, not free, we just have to remove the exclusion that views
> > (or whatever relkind we create) can't have stats.
> >
>
> TBH the grammar / catalog stuff seems like a relatively minor part of
> this patch. To me, the difficult part seems to be the sampling / analyze
> part, and then matching it to the query during planning. And all of this
> seems exactly the same no matter how the stats are defined.
>

I agree that the catalog stuff is minor relative to the work matching
queries to the join node trees associated with a set of join stats,
wherever that resides.

The sampling analyze part doesn't strike me as too hard. The worst case
scenario is that we take the columns+join definition, swap the "anchor"
table out replacing it with the EphemeralNamedRelation of the fetched row
sample from the anchor table, and just run that, letting SPI figure out
which indexes can be used.

The question of _when_ to analyze is a bit trickier, as was pointed out by
Chenpeng Yan, and I suspect that any "anchor" table with join stats on it
will need to be analyzed once any one of the tables it joins to has hit the
threshold.


> OTOH maybe allowing CREATE STATISTICS on views would be independently
> useful too, once we have the later parts. Not sure.
>

I think so as well, which is why I'd like to leave that option open.


> > - we'd want a way to express stats for all the individual columns/
> > expressions defined in the join stats object, i.e. "what is the MCV of
> > B.name for rows joined by A on A.b_id"?
> >
>
> Maybe I misunderstand, but don't we already do this for statistics on
> expressions?
>

We can CREATE STATISTICS foo on (upper(name)) FROM table, if that's what
you're asking.

But that isn't what I'm saying. Given tables A, B, and C which can join on
A.b_id = B.id and A.c_id = c.id, we already have pg_statistic stats for
B.name, but that's across B in a vacuum. I'm assuming that there's also
value in having the stats for B.name filtered and weighted by how often (if
at all) the B row is joined to A, and those stats would be shaped exactly
like the pg_statistic row for B.name. We could view that as correlating
B.name against the primary key of A, but that seems odd to me.

Additionally, we might want the ability to have correlative stats of B.name
with c.purchase_date. With the views idea, that would just be:

      CREATE STATISTICS foo ON (b_name, c_purchase_date) FROM
my_statistics_view.

So we'd have regular stats to draw upon from my_statistics view, and those
would have our cardinality estimates given the precondition of the row
surviving the join criteria, and we'd further have the correlative
statistics of two columns each from tabled joined to A. And that's
something not even DB2 can do now given their 2-table join limitation.


> I don't follow. What 5-factorial combinations? We only ever build a
> single MCV for a given statistics object.
>

Sorry, I was thinking about pg_ndistinct and pg_dependencies.

For MCV that would give us the most common tuples of (B.name,
C.purchase_date, D.promotion_code, a.quantity, a.amount), but that only
helps when we need all of those columns, not a subset of them.


> I may be missing something, but I honestly the only benefit of views I
> can think of is already having the join definition in a catalog.
>

That's the biggest benefit for sure, but the other benefit is we can have
the per-column stats in pg_statistic as I detailed above, and further do
extended statistics, as we both addressed above.


> I don't follow. Why should statistics object be pg_class objects? In my
> mind pg_class is meant for "relations" (as in, table-like things), and
> statistics objects are not like that. I suppose this is related to your
> earlier suggestion
>
>   Having something in pg_class to anchor existing per-attribute and
>   multi-attribute stats off of seems like a big win to me.
>

It is, but it would also allow us to avoid having a declared view, and then
altering that view to allow statistics.

It would make it more complicated to express which elements of the join
were worthy of correlative stats, so in that sense having a view with a
name is conceptually simpler.


> but it's not clear to me why would that be? All statistics are tied to a
> relation (or multiple relations) in the end, and I don't see why would
> the view make anything simpler. What are the wins?
>

The view would allow us to put a wider range of stats on all of the columns
that could be found through that defined join, using the mechanisms we
already have available to us.

It would further allow us to declare that multiple subsets of those columns
are interesting enough to warrant correlative (extended) statistics.


> Could you elaborate? It's entirely possible I just don't see something
> obvious, or maybe you explained this in Vancouver and I managed to
> forget the details. Sorry about that.


No worries, Vancouver was a whirlwind of ideas around this topic. My head
is still swimming.

Another way of thinking about this is that it would give us the stats that
we could get from a materialized view, with the ability to define extended
stats on top of that materialized view, but without the costs of
maintaining a materialized view, and without the restriction that a query
has to directly reference the materialized view.

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

Tomas Vondra <tomas@vondra.me> — 2026-06-22T19:03:33Z

Hi Alexandra,

I finally had a bit of time to take a look at this again today. AFAIK
nothing was posted since pgconf.dev last month, so I took a look at the
v7 to do at least something. I assume you may have an updated patch, but
chances are it's not too different.

First, it's great you keep working on this. I really hope we can get
something done for PG 20, I'll try to help with that.

Here's a couple review comments, in no particular order - it's simply in
the order 'git difftool' presented me the code in. Also, some of this is
definitely nitpicky / cosmetic.


1) statsmds.c

Does it make sense to check list_length(stmt->relations) at all?
Consider this code:

  /*
   * Examine the FROM clause. We support either: 1. Single RangeVar for
   * single-table statistics 2. JoinExpr for join statistics
   */
  if (list_length(stmt->relations) != 1)
      ereport(ERROR,
              (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
               errmsg("only a single relation or JOIN is ...")));

I guess when I wrote that code, I imagined we'd get either a list with a
single single rel (for single-rel stats), or a list of rels (for a
join). But clearly, that does not happen. We seem to get a single-item
list with a RangeVar or JoinExpr, right? So maybe the check is wrong?


2) statsmds.c

Isn't this check overly strict? Shouldn't we complain only in ambiguous
cases, with the same column in multiple tables?

  /* Join stats require table-qualified column names */
  if (isjoin)
      ereport(ERROR,
              (errcode(ERRCODE_INVALID_COLUMN_REFERENCE),
               errmsg("join statistics require table-qualified ...")));


3) statscmds.c

Hmmm, we're now using only MCVs for joins, so this restriction makes
sense. How temporary is this restriction? I was hoping we might use some
of the stats for other purposes (e.g. ndistinct would be useful for
estimating GROUP BY on top of a join - or is that impossible?).

Of course, we should not relax the restriction only when we actually
support those cases. Just a thought.

  /*
   * For join statistics, only MCV is currently supported.
   */
  if (isjoin && (build_ndistinct || build_dependencies ||
build_expressions))
      ereport(ERROR,
              (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
               errmsg("only MCV statistics are supported for join ...


4) statscmds.c

I'm a bit confused by the code in CreateStatistics, and how it copies
some of the code between the isjoin and !isjoin branches. But not all
code. For example in this block

  else if (IsA(selem->expr, Var)) /* column reference in parens */

it has this

  /* Treat virtual generated columns as expressions */
  if (get_attgenerated(relid, var->varattno) ==
                           ATTRIBUTE_GENERATED_VIRTUAL)

but only in the !isjoin branch. What happens with generated columns in
the isjoin branch?


5) statscmds.c?

  /* Join stats only support simple column references */
  if (isjoin)
      ereport(ERROR,
              (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
               errmsg("expressions are not supported in join ...")));

Presumably that's just a temporary limitation, to keep the patch simple?
And it'll eventually go away, esp. if we end up merging the keys and
exprs into a single list, as discussed in Vancouver.


6) statscmds.c

I don't understand how the detection of duplicate columns (after this
comment) works for the join case, without doing any qsort (like the
single-table branch does).

   * For join stats, preserve user-declared column order and check for
   * duplicate (varno, attnum) pairs.


7) statscmds.c

I'm not sure I understand this bit:

 * If there are no dependencies on a column, give the statistics object
 * an auto dependency on the whole table.  In most cases, this will be
 * ...
 * Join stats are excluded because they span two tables (no single
 * "whole table" exists).

Why would there be no dependencies on a column - maybe when there are
just expressions? But join stats don't allow that right now, right? So
when would that happen? And if we allow expressions for join stats, what
would happen for joins stats? Or is it OK to just not have a dependency?


8) statsmds.c

In general, some of the code is getting a bit too hard to read, with the
next isjoin and !isjoin branches. I get how we got this code, but it'd
be nice to refactor / clean this up a bit in some way. Perhaps it'd help
if some of the code was moved to separate "helpers" functions, to keep
the "main" functions (like CreateStatistics) somewhat readable?


9) costsize.c

adds the include in the wrong place ;-)


10) clausesel.c

I'm a bit confused by this comment in clauselist_selectivity_ext:

   * Note: FK-based joins are already handled by
   * get_foreign_key_join_selectivity() which runs before
   * clauselist_selectivity().  This primarily benefits:

Why does this matter here that FK joins were already handled?

Also, for the join stats we consider both the baserestrictinfos and the
join clause together, in case the MCV covers both (and there's some sort
of correlation). I suppose the FK joins don't consider that info, so
those estimates miss the information?


12) plancat.c

I'd ditch the "_list" suffixes from the local variables. I don't think
it helps, it just makes everything longer:

      /* Join statistics fields */
      List       *joinrels_list = NIL;
      List       *keyattrs_list = NIL;
      List       *keyrefs_list = NIL;
      List       *joinconds = NIL;


13) random thought - How does this handle non-inner joins? Or does it
make sense only for inner joins?


14) extended_stats.c

I don't think StatExtEntry should have two ways to represent the same
information - I mean, we have a Bitmapset of columns for single-table
stats, but that does not work for join stats, so the patch adds a bunch
of new fields.

IMHO if the old way does not work for joins, maybe we should ditch it
entirely and use the new approach even for single-rel code. Probably
switch in a separate preparatory commit, before adding the join stats.

Also, I don't love having multiple "coordinated" lists - one for attnums
and one for varnos. Wouldn't it be better to have a single list, with
elements being a new struct with varno + varattnum fields (or whatever
else we need)? Maybe there even is a struct we could reuse?


15) ruleutils.c

I suspect this code in pg_get_statisticsobj_worker works right when the
relation name happens to be long (NAMEDATALEN-1 characters). Won't that
truncate the generated string in "buf"?

  if (strcmp(all_aliases[i], all_aliases[j]) == 0)
  {
      char        buf[NAMEDATALEN];

      suffix++;
      snprintf(buf, sizeof(buf), "%s_%d",
               get_relation_name(all_reloids[i]), suffix);
      all_aliases[i] = pstrdup(buf);

      /* Restart scan to check for further conflicts */
      j = -1;
  }


That's all I have right now. I haven't reviewed the code in join_mcv.c
in detail yet. That's a rather dense code with not that many comments,
so I want to be 100% sure I'm not reviewing stale code.


regards

-- 
Tomas Vondra

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

Alexandra Wang <alexandra.wang.oss@gmail.com> — 2026-06-23T11:02:41Z

Hi all,

Attached is v8 of the join statistics patch. This revision focuses mainly on
the catalog-representation feedback from the earlier v7 reviews. Thanks Tom,
Tomas, Chengpeng, and Corey!

Changes since v7:

0001: a new preparatory commit (Tom + Tomas feedback). This is a
standalone prerequisite refactor, independent of join statistics.
- Removed the stxkeys column from pg_statistic_ext; all target columns
  are now Var nodes in stxexprs alongside the complex expressions.
- Removed the attnames column from the pg_stats_ext view accordingly.

Tomas pointed out earlier that representing keys as expressions rather than
attnums might cost planning time, so I benchmarked 0001 to measure planning
latency, as below. Build: CFLAGS='-g -O3'.

Table DDLs:
  CREATE TABLE t (a int, b int, c int, d int, e int,
                  f int, g int, h int, i int, j int);
  INSERT INTO t SELECT
      mod(i,10), mod(i,13), mod(i,17), mod(i,19), mod(i,23),
      mod(i,29), mod(i,31), mod(i,37), mod(i,41), mod(i,43)
  FROM generate_series(1, 100000) s(i);

Two statistics configurations (all targets are plain columns):

  -- 3 stats
  CREATE STATISTICS s1 (mcv)          ON a, b, c       FROM t;
  CREATE STATISTICS s2 (ndistinct)    ON a, b, c, d    FROM t;
  CREATE STATISTICS s3 (dependencies) ON a, b, c       FROM t;
  ANALYZE t;

  -- 10 stats
  CREATE STATISTICS s1  (mcv)       ON a, b, c          FROM t;
  CREATE STATISTICS s2  (mcv)       ON b, c, d          FROM t;
  CREATE STATISTICS s3  (mcv)       ON c, d, e          FROM t;
  CREATE STATISTICS s4  (mcv)       ON d, e, f          FROM t;
  CREATE STATISTICS s5  (mcv)       ON e, f, g          FROM t;
  CREATE STATISTICS s6  (mcv)       ON f, g, h          FROM t;
  CREATE STATISTICS s7  (mcv)       ON g, h, i          FROM t;
  CREATE STATISTICS s8  (mcv)       ON h, i, j          FROM t;
  CREATE STATISTICS s9  (ndistinct) ON a, b, c, d, e    FROM t;
  CREATE STATISTICS s10 (ndistinct) ON f, g, h, i, j    FROM t;
  ANALYZE t;

pgbench query:

  EXPLAIN SELECT * FROM t WHERE a = 1 AND b = 2 AND c = 3;

pgbench command:

  pgbench -n -c1 -j1 -T30 -f query.sql

Results:
Median plan latency, before 0001 (with stxkeys) vs after:

                before     after
   3 stats:    0.122 ms   0.123 ms   (+0.001 ms)
  10 stats:    0.121 ms   0.125 ms   (+0.004 ms)

So the ~1-4 us per plan overhead at 10 stats objects is negligible.

0002: the main join statistics patch
- stxkeyrefs is gone (Tom's feedback).
- The anchor relation's OID is now the first element of stxjoinrels
  (stxjoinrels[0] == stxrelid), so every varno uniformly references
stxjoinrels[varno-1] (Tom + Tomas feedback).
- Updated permissions for creating join stats: you must own the anchor
  and have SELECT on the other table(s); that SELECT is rechecked for
the stats owner at ANALYZE time, and the stats are not refreshed if
the privilege has been revoked (Tom's feedback).
- Added documentation and more test coverage.

A few questions on where to take this next:

1. N-way joins. Tomas, you made the case that 2-way isn't enough (a
fact table joining two correlated dimensions). The catalog is already
prepared for n-way, but ANALYZE skips collection with a warning.
Should extending collection to n-way be the next piece, or would you
rather see the 2-way version land first?

2. Other statistics kinds such as ndistinct and functional dependencies.
Are those other stats kinds must haves in the initial commit?

3. Index-requirement semantics (Chengpeng, Tom, Tomas). Currently a
suitable index on the probed join column is required: CREATE
STATISTICS errors if none exists, and a NORMAL dependency on the
chosen index makes DROP INDEX require CASCADE (so the stats can't
silently stop building). ANALYZE re-selects the best available index
on each run. Is this what we want? The alternatives I considered:
   a. Drop the index requirement and add a non-index (sequential-scan)
sampling fallback. This is the most user-friendly, and not necessarily
slower when the joined tables are small.
   b. Pin the specific index by storing its OID in the catalog. This
makes the dependency exact, but I'm unsure how it should interact with
REINDEX: REINDEX CONCURRENTLY swaps the index to a new OID — the
NORMAL dependency follows automatically, but a stored OID would need
to be updated explicitly.
   c. Block DROP INDEX only when it would remove the last suitable
index (allowing it while an equivalent remains). Also user-friendly,
but I haven't found a clean way to implement it.

I'm currently inclined either to keep the present behavior for v1, or
to go with (a) and add the seq-scan fallback. Would appreciate your
thoughts.

On Mon, Jun 22, 2026 at 12:03 PM Tomas Vondra <tomas@vondra.me> wrote:

> I finally had a bit of time to take a look at this again today. AFAIK
> nothing was posted since pgconf.dev last month, so I took a look at the
> v7 to do at least something. I assume you may have an updated patch, but
> chances are it's not too different.
>

Thank you so much, Tomas, for the detailed review. I was just about to
post v8 when your feedback arrived. I addressed some of your most
recent feedback (#9, #12, #15). I didn't want you reviewing stale
code, so I'm posting what I have now and will follow up on the rest.

Best,
Alex

-- 
Alexandra Wang
EDB: https://www.enterprisedb.com

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

Tomas Vondra <tomas@vondra.me> — 2026-07-03T11:51:37Z

Hi Alexandra,

On 6/23/26 13:02, Alexandra Wang wrote:
> Hi all,
> 
> Attached is v8 of the join statistics patch. This revision focuses mainly on
> the catalog-representation feedback from the earlier v7 reviews. Thanks Tom,
> Tomas, Chengpeng, and Corey!
> 
> Changes since v7:
> 
> 0001: a new preparatory commit (Tom + Tomas feedback). This is a
> standalone prerequisite refactor, independent of join statistics.
> - Removed the stxkeys column from pg_statistic_ext; all target columns
>   are now Var nodes in stxexprs alongside the complex expressions.
> - Removed the attnames column from the pg_stats_ext view accordingly.
> 

Thanks for the v8 patch. I think 0001 looks pretty good, I only have a
couple minor comments / questions regarding it:

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?

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.

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?

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.

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.

Overall, I think 0001 goes in the right direction, and maybe we should
even apply it early, without waiting for the rest of the patch series.
It seems like an improvement.

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?

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?

> Tomas pointed out earlier that representing keys as expressions rather than
> attnums might cost planning time, so I benchmarked 0001 to measure planning
> latency, as below. Build: CFLAGS='-g -O3'.
> 
> Table DDLs:
>   CREATE TABLE t (a int, b int, c int, d int, e int,
>                   f int, g int, h int, i int, j int);
>   INSERT INTO t SELECT
>       mod(i,10), mod(i,13), mod(i,17), mod(i,19), mod(i,23),
>       mod(i,29), mod(i,31), mod(i,37), mod(i,41), mod(i,43)
>   FROM generate_series(1, 100000) s(i);
> 
> Two statistics configurations (all targets are plain columns):
> 
>   -- 3 stats
>   CREATE STATISTICS s1 (mcv)          ON a, b, c       FROM t;
>   CREATE STATISTICS s2 (ndistinct)    ON a, b, c, d    FROM t;
>   CREATE STATISTICS s3 (dependencies) ON a, b, c       FROM t;
>   ANALYZE t;
> 
>   -- 10 stats
>   CREATE STATISTICS s1  (mcv)       ON a, b, c          FROM t;
>   CREATE STATISTICS s2  (mcv)       ON b, c, d          FROM t;
>   CREATE STATISTICS s3  (mcv)       ON c, d, e          FROM t;
>   CREATE STATISTICS s4  (mcv)       ON d, e, f          FROM t;
>   CREATE STATISTICS s5  (mcv)       ON e, f, g          FROM t;
>   CREATE STATISTICS s6  (mcv)       ON f, g, h          FROM t;
>   CREATE STATISTICS s7  (mcv)       ON g, h, i          FROM t;
>   CREATE STATISTICS s8  (mcv)       ON h, i, j          FROM t;
>   CREATE STATISTICS s9  (ndistinct) ON a, b, c, d, e    FROM t;
>   CREATE STATISTICS s10 (ndistinct) ON f, g, h, i, j    FROM t;
>   ANALYZE t;
> 
> pgbench query:
> 
>   EXPLAIN SELECT * FROM t WHERE a = 1 AND b = 2 AND c = 3;
> 
> pgbench command:
> 
>   pgbench -n -c1 -j1 -T30 -f query.sql
> 
> Results:
> Median plan latency, before 0001 (with stxkeys) vs after:
> 
>                 before     after
>    3 stats:    0.122 ms   0.123 ms   (+0.001 ms)
>   10 stats:    0.121 ms   0.125 ms   (+0.004 ms)
> 
> So the ~1-4 us per plan overhead at 10 stats objects is negligible.
> 

I agree, this looks fine. I wasn't really worried about it, it was just
the one thing that seemed like a possible issue.

> 0002: the main join statistics patch
> - stxkeyrefs is gone (Tom's feedback).
> - The anchor relation's OID is now the first element of stxjoinrels
>   (stxjoinrels[0] == stxrelid), so every varno uniformly references
> stxjoinrels[varno-1] (Tom + Tomas feedback).
> - Updated permissions for creating join stats: you must own the anchor
>   and have SELECT on the other table(s); that SELECT is rechecked for
> the stats owner at ANALYZE time, and the stats are not refreshed if
> the privilege has been revoked (Tom's feedback).
> - Added documentation and more test coverage.
> 

I haven't looked at the 0002 in detail, AFAIK my comments from June 22
still apply.

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?

I noticed a couple more details for 0002:

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

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

> A few questions on where to take this next:
> 
> 1. N-way joins. Tomas, you made the case that 2-way isn't enough (a
> fact table joining two correlated dimensions). The catalog is already
> prepared for n-way, but ANALYZE skips collection with a warning.
> Should extending collection to n-way be the next piece, or would you
> rather see the 2-way version land first?
> 

I don't think n-way joins have to be supported from the beginning, but
it would be good to have an experimental patch doing that in the patch
series. In my experience it helps with getting the infrastructure ready
for supporting it later.

> 2. Other statistics kinds such as ndistinct and functional dependencies.
> Are those other stats kinds must haves in the initial commit?
> 

I think this is similar. I think it's fine to not support all these
statistical kinds in the initial commit, but it'd help to have some sort
of experimental patch.

> 3. Index-requirement semantics (Chengpeng, Tom, Tomas). Currently a
> suitable index on the probed join column is required: CREATE
> STATISTICS errors if none exists, and a NORMAL dependency on the
> chosen index makes DROP INDEX require CASCADE (so the stats can't
> silently stop building). ANALYZE re-selects the best available index
> on each run. Is this what we want? The alternatives I considered:
>    a. Drop the index requirement and add a non-index (sequential-scan)
> sampling fallback. This is the most user-friendly, and not necessarily
> slower when the joined tables are small.
>    b. Pin the specific index by storing its OID in the catalog. This
> makes the dependency exact, but I'm unsure how it should interact with
> REINDEX: REINDEX CONCURRENTLY swaps the index to a new OID — the
> NORMAL dependency follows automatically, but a stored OID would need
> to be updated explicitly.
>    c. Block DROP INDEX only when it would remove the last suitable
> index (allowing it while an equivalent remains). Also user-friendly,
> but I haven't found a clean way to implement it.
> 
> I'm currently inclined either to keep the present behavior for v1, or
> to go with (a) and add the seq-scan fallback. Would appreciate your
> thoughts.
> 

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.

regards

-- 
Tomas Vondra