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

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

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

Tomas Vondra <tomas(at)vondra(dot)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

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

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

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(dot)huinker(at)gmail(dot)com>
wrote:

> On Mon, Dec 1, 2025 at 1:02 PM Tomas Vondra <tomas(at)vondra(dot)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(at)vondra(dot)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

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

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

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

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

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

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

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

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

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

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

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

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

On Tue, Apr 28, 2026 at 10:59 PM Alexandra Wang <
alexandra(dot)wang(dot)oss(at)gmail(dot)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

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

Here's the rebased patch, it only needed a catalog version bump.

Best,
Alex

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

On Wed, May 6, 2026 at 8:19 PM Alexandra Wang
<alexandra(dot)wang(dot)oss(at)gmail(dot)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/

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(dot)wang(dot)oss(at)gmail(dot)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(dot)universality(at)gmail(dot)com> wrote:
> On Wed, May 6, 2026 at 8:19 PM Alexandra Wang
> <alexandra(dot)wang(dot)oss(at)gmail(dot)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

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

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

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

Best,
Alex

On Thu, May 14, 2026 at 10:08 PM Alexandra Wang <
alexandra(dot)wang(dot)oss(at)gmail(dot)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

Alexandra Wang <alexandra(dot)wang(dot)oss(at)gmail(dot)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

Hi,

> On May 15, 2026, at 23:30, Alexandra Wang <alexandra(dot)wang(dot)oss(at)gmail(dot)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

On 5/21/26 22:25, Tom Lane wrote:
> Alexandra Wang <alexandra(dot)wang(dot)oss(at)gmail(dot)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

Tomas Vondra <tomas(at)vondra(dot)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

Hi Tom and Tomas,

Thank you so much for the feedback!

On Mon, May 25, 2026 at 8:04 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Tomas Vondra <tomas(at)vondra(dot)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

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(at)sss(dot)pgh(dot)pa(dot)us
> <mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us>> wrote:
>> Tomas Vondra <tomas(at)vondra(dot)me <mailto:tomas(at)vondra(dot)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

Tomas Vondra <tomas(at)vondra(dot)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

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

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

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

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

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(at)vondra(dot)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

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

Hi,

Thanks to everyone who has worked on and reviewed the join MCV
statistics feature. It's a nice piece of work and addresses a real,
long-standing gap in the planner's estimation for correlated joins.

While testing the v8-* patches, I found a case where ANALYZE on a table
with a join MCV statistics takes ~10 minutes.

Example:

```
CREATE TABLE other_tbl (id serial PRIMARY KEY, fk int);
CREATE INDEX other_tbl_fk_idx ON other_tbl(fk);
INSERT INTO other_tbl  (fk) SELECT 1 FROM generate_series(1, 500000);
VACUUM other_tbl;

CREATE TABLE anchor_tbl (id serial PRIMARY KEY, fk int);
INSERT INTO anchor_tbl (fk) SELECT 1 FROM generate_series(1, 20000);
VACUUM anchor_tbl;

\timing on
ANALYZE other_tbl, anchor_tbl;
Time: 36,438 ms
\timing off

CREATE STATISTICS anchor_other_join_stats (mcv)
ON anchor_tbl.fk
FROM anchor_tbl JOIN other_tbl ON anchor_tbl.fk = other_tbl.fk;

\timing on
ANALYZE other_tbl, anchor_tbl;
Time: 566027,223 ms (09:26,027)
\timing off
```

I profiled the running ANALYZE backend. The breakdown is:

    sample_index                              64.02%   (all ANALYZE time)
    |-- index_getnext_slot                    64.02%
        |-- index_fetch_heap                  58.25%
        |   `-- heapam_index_fetch_tuple      56.73%
        |       |-- LockBuffer                29.47%
        |       |   |-- BufferLockAcquire      8.75%
        |       |   |-- BufferLockUnlock      12.09%
        |       |   `-- BufferLockAttempt      6.39%
        |       |-- heap_hot_search_buffer    15.88%
        |       `-- HeapTupleSatisfiesMVCC    ~5.2%
        `-- index_getnext_tid -> btgettuple
                -> _bt_next -> _bt_readnextpage 5.77%  <- actual btree
traversal

The overwhelming majority is spent fetching heap tables, buffer locking
for every single index entry examined. I also attached flamegraph of it.

At this point it isn't obvious to me how to cut down that cleanly, so if
anyone can see a good way to address it, I'd very much welcome the input.

--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/

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

+1

> The main question I have is whether maybe we should get rid of the
> columns vs. expressions in more places. Currently the patch removes that
> from the catalog, but then it still "restores" this difference when
> reading the statistics information, so that both StatExtEntry and
> StatisticExtInfo still store this separately. But do we need to?
>

I'd be in favor of this. It was a pain interleaving the expressions in
every time we found a negative attnum, and it also prevented skippping
ahead to to desired attribute because we had to know that we had consumed
all "previous" expressions. Good riddance to that.

> It means we still need two loops in a lot of places, first over columns
> and then over expressions. If we treated everything as expressions,
> wouldn't it be simpler?
>

That might be the best way.

> I noticed a couple more details for 0002:
>
> - I didn't realize we require the user to pick the "anchor" table and
> put it first in the CREATE STATISTICS command:
>
> CREATE INDEX ON t1 (a);
> CREATE STATISTICS (mcv) on t1.b, t1.c, t2.e, t2.f from t1 join t2
> ON (t1.a = t2.d);
> ERROR: no suitable index on "t2" column "d" for join statistics
> HINT: Create an index on the join column to enable index-based join
> sampling.
>
> In this example both t1 and t2 could have be an anchor table. So maybe
> we could try determining the anchor table automatically? But maybe there
> are issues, e.g. what if there are multiple candidates?
>

It's true there could be multiple candidates, but I think we want a clearly
defined anchor table because that is the table that controls when these
stats are refreshed, as it is the one that has the real rowsample, and all
the others are joins off of that.

That could mean that we have essentially the same extended stats object on
two different tables, differing only in the syntax required to specify the
different anchor table, but such situations should be rare.

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

I'm iffy on this.

On the one hand, it would be helpful information for the fact-like tables
in the join, and even if we adopt the "view can have stats" version that
I'm advocating we could still have \d discover that through a pg_depend.

On the other hand, extended stats declared on a big fact-dimension join
would result in \d on a dimension table showing a bunch of extended stats
objects which would be peripheral information at best.

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

While they don't have to be there from the very beginning, I fear that not
including them will cause us to paint ourselves into a corner somewhere.

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

I'm a big proponent of "a" here. The negative consequence of a missing
index is a slow ANALYZE, remedied by creating the index.

"b" creates a maintenance headache. If we lock ourselves into index x1, and
x1 gets bloated, how do we switch to a compacted x2 index? If x1 is dropped
and rebuilt, must we rebuild the stats object? If x1 is dropped by
(x1,y1,z1) exists, couldn't we live with that
sub-optimal-but-better-than-seqscan index?

"c" creates a situation where the user experiences no negative consequences
for dropping 1..N-1 indexes, but the last index fails for a reason that
didn't previously prevent the others from being dropped.

Hi there,

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

Here's v9:

0001: a minor bug fix
0002: the refactor commit that unifies columns and expressions into a
single list in the pg_statistic_ext catalog, the pg_stats_ext view,
and the in-memory StatExtEntry and StatisticExtInfo structs. The
user-written order of columns and expressions is preserved in the
catalog, the view, the \dX display, and in the MCV data.
0003: the join mcv commit, now with bug fixes and more test coverage.
0004: improve default auto-generated statistics name

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

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

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

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

See more details in the following quote reply:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Here are the results on v9:

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

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

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

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

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

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

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

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

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

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

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

Agreed. I will followup on this one.

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

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

Best,
Alex

Hi Alexanda,

Thanks for the v9 patch! Here's a bunch of review comments. I think
0001, 0002 and 0004 are not far from committable. I still need to do
more review on 0002, but I don't expect major issues.

I'd move 0004 right after 0002, so that we can get it out of the way. It
seems more like a consequence of 0002 than related to join stats.

0001 - Fix memory leak in make_build_data()

- I think this is fine, ready to go. It should have been addressed, per
the XXX comment. Can it be a problem in backbranches too, or is it
somehow more serious with join stats? Or did you just notice the XXX
comment? I'm asking because of backpatching.

0002 - Unify extended statistics columns and expressions

I think there's a couple issuses.

- The psql describe code still checks (sversion >= 190000), but that's
now wrong, it needs to check 200000. A simple rebase omission, but
it can lead to failures on 19.

- This replaces simple O(1) bitmapset checks with list walks in a couple
places. I know we already tested how much more expensive this is, but
I keep wondering if it might get worse with enough statistics and/or
if we end up increasing the limit on statistics columns.

I'm not saying we should not do this, or that the patch is wrong, but
maybe there's a data structure / representation we could use to save
on the overhead. Not sure, just spitballing.

0003 - Add join MCV statistics for selectivity estimation

- I think it's not strict enough when validating the join clauses.

Consider this example:

----
create table a (x int, y int);
create table b (p int, q int);
create statistics on a.x, a.y from a join b on (a.x = a.y);
----

This leads to a crash in CreateStatistics(), in this part

indexed_var = (lvar->varno > rvar->varno) ? lvar : rvar;
Assert(indexed_var->varno > 1);

Whic is not surprising, because the "join clause" is not actually
connecting the two relations, it only references "a". I suppose this
should be rejected in transformStatsStmt(), in stxjoinconds checks.

Also, looking at the error wording:

ERROR: join statistics require a single equality join condition per
pair of tables

Won't that be a bit confusing once we start supporting larger joins?
It seems to suggest we require a join clause for each pair, but I
don't think we need that - it should be enough to have enough clauses
to have connected join graph, no?

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

- This seems wrong:

Oid rel_oids[STATS_MAX_DIMENSIONS + 1];

STATS_MAX_DIMENSIONS is the number of dimensions, not the number of
relations. We can have joins with no columns in the statistic, so we
could exceed this limit.

Right now it works, because we only allow 2-way joins, but we want to
relax that. Maybe we want to have a similar limit, in which case we
should have a separate constant with an appropriate name.

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

CREATE TABLE t1 (id int);

CREATE TABLE t2 (id int, val int) PARTITION BY RANGE (id);
CREATE TABLE t2_1 PARTITION OF t2 FOR VALUES FROM (0) TO (100);
CREATE TABLE t2_2 PARTITION OF t2 FOR VALUES FROM (100) TO (200);

CREATE INDEX t2_idx ON t2 (id);

INSERT INTO t1 SELECT g FROM generate_series(1, 199) g;
INSERT INTO t2 SELECT g, g % 10 FROM generate_series(1, 199) g;

CREATE STATISTICS s (mcv)
ON t2.val
FROM t1 JOIN t2 ON t1.id = t2.id;

ANALYZE t1;

which crashes in sample_index() like this:

Program received signal SIGSEGV, Segmentation fault.
table_index_fetch_begin (rel=0x758dddcb5600, flags=0)
1258 return rel->rd_tableam->index_fetch_begin(rel, flags);

because this is sampling t2, which is a RELKIND_PARTITIONED_TABLE,
and as such has rel->rd_tableam = NULL.

I suppose the sampling needs to do something smarter for partitioned
tables, but I'm not sure how much more complex, or if it's worth it.
I suppose it might need to do "manual Append" or something like that.
It could be quite complex for nested partitioning schemes.

Maybe it'd be better to just use SPI for this. That is, generate a
regular query, and let the planner/executor handle the partitioning
part. Just a random thought, I haven't tried fixing the current code
or implementing the SPI thing.

- I think pg_stats_ext and pg_stats_ext_exprs need fixes to check RLS
for all relations, not just for the anchor one. Otherwise the join
MCV could show stats the role should not be able to see.

Example:

----
CREATE ROLE test_rls_owner;
CREATE SCHEMA test_rls AUTHORIZATION test_rls_owner;

SET ROLE test_rls_owner;

CREATE TABLE test_rls.anchor (id int, filler int);
CREATE TABLE test_rls.secret (id int, secret text);

INSERT INTO test_rls.anchor SELECT g, g FROM generate_series(1, 100) g;
INSERT INTO test_rls.secret
SELECT g, CASE WHEN g <= 50 THEN 'secret-1' ELSE 'secret-2' END
FROM generate_series(1, 100) g;

CREATE INDEX test_rls_secret_id_idx ON test_rls.secret (id);

-- nobody can read any rows
ALTER TABLE test_rls.secret ENABLE ROW LEVEL SECURITY;
ALTER TABLE test_rls.secret FORCE ROW LEVEL SECURITY;

CREATE STATISTICS test_rls.test_stat (mcv)
ON anchor.filler, secret.secret
FROM test_rls.anchor JOIN test_rls.secret ON anchor.id = secret.id;

ANALYZE test_rls.anchor;

-- owner cannot read anything from secret table ...
SELECT count(*) AS visible_secret_rows FROM test_rls.secret;

-- ... but its values show up here
SELECT exprs,
count(*) FILTER (WHERE v LIKE 'secret%') AS leaked_mcv_items,
min(v) FILTER (WHERE v LIKE 'secret%') AS example_leaked_value
FROM pg_stats_ext, unnest(most_common_vals) AS v
WHERE statistics_schemaname = 'test_rls'
AND statistics_name = 'test_stat'
GROUP BY exprs;

RESET ROLE;

DROP SCHEMA test_rls CASCADE;
DROP ROLE test_rls_owner;
----

AFAIK the regular privileges don't have similar issue because the
view definition has unnest(s.stxjoinrels) with a pg_has_role check,
so I guess that should do a similar check for RLS.

- It seems a bit unfortunate that creating statistics on a join, with
tables owned by different users, this restricts what the owner of the
non-anchor tables can do. Consider a statistics on t1-t2 join, owned
by u1 and u2.

----
CREATE ROLE u1;
CREATE ROLE u2;
GRANT USAGE, CREATE ON SCHEMA public to u1;
GRANT USAGE, CREATE ON SCHEMA public to u2;

SET ROLE u2;
CREATE TABLE t2 (a int, b int);
CREATE INDEX ON t2 (a);

RESET ROLE;
GRANT SELECT ON t2 TO u1;

SET ROLE u1;
CREATE TABLE t1 (a int, b int);
CREATE STATISTICS s (mcv) ON t1.a, t1.b, t2.a, t2.b
FROM t1 JOIN t2 ON (t1.a = t2.a);

ANALYZE t1;

SET ROLE u2;
DROP INDEX t2_a_idx;
ERROR: cannot drop index t2_a_idx because other objects depend on it
----

At this point, u2 is in an unfortunate situation. Can't drop the
index, can't drop the statistics (because it's owned by u1). The DROP
INDEX fails even if there's another index usable for sampling, which
is a bit weird - I don't know if we have other cases tied to a single
index (except maybe for PK indexes).

The user can't even drop the statistic object, because that's owned
by u1, of course. OTOH, the u2 user can drop the whole table t2, and
that *will* drop the whole statistics.

Seems a bit weird. I recall there was some discussion about users,
but I don't recall the details or what behavior I argued for.

- I suspect join_mcv_clause_selectivity is not quite right, resulting
in incorrect estimates. Consider this trivial join example:

---
CREATE TABLE t1 (id int);
CREATE TABLE t2 (id int, val text);

-- 1000 rows on the anchor side, only 10 of them join, 9 of those
-- have 'hit'
INSERT INTO t1 SELECT g FROM generate_series(1, 1000) g;
INSERT INTO t2
SELECT g, CASE WHEN g <= 9 THEN 'hit' ELSE 'miss' END
FROM generate_series(1, 10) g;

CREATE INDEX t2_idx ON t2 (id);

CREATE STATISTICS test_stat (mcv)
ON t2.val
FROM t1 JOIN t2 ON t1.id = t2.id;

ANALYZE t1;
ANALYZE t2;

-- 'hit' matches 9 of the 10 joining rows, so the frequency is 0.9
SELECT statistics_name, exprs, most_common_vals, most_common_freqs
FROM pg_stats_ext
WHERE statistics_name = 'test_stat';

-- with join stats: estimated 900 rows, actual 9
EXPLAIN (ANALYZE, TIMING OFF, SUMMARY OFF)
SELECT *
FROM t1 JOIN t2 ON t1.id = t2.id
WHERE t2.val = 'hit';

DROP STATISTICS repro_sel_s;

-- without join stats: estimated 9 rows, actual 9
EXPLAIN (ANALYZE, TIMING OFF, SUMMARY OFF)
SELECT *
FROM t1 JOIN t2 ON t1.id = t2.id
WHERE t2.val = 'hit';
--

I don't have the energy and time to check join_mcv_clause_selectivity
in detail right now, but it seems to me it might be confused whether
it should calculate P(join | filters) or P(join AND filters).

I believe it should calculate the former, but it seems to calculate
the latter (at least that's what the comments say).

Two more comments: While looking at calc_joinrel_size_estimate, I
noticed the selectivity calculated for semi/anti joins is very
different. I wonder if join_mcv_clause_selectivity needs to account
for this too, so that it calculates the right thing for semi/anti?

Also, I'm a bit unsure about this bit:

/*
* Cross-check: the MCV-based estimate shouldn't be lower than
* what the standard join estimator would produce (eqjoinsel on
* per-column stats only, no extended stats). If our estimate is
* lower, skip this stat and fall back to the standard estimate.
*/
standard_sel = clause_selectivity_ext(...);
if (raw_sel < standard_sel)
continue;

It's not quite clear to me if this is really true, especially when
the statistics covers some additional filters etc. I'd like to see
some valid examples where this kicks in.

In fact, how could it be correct? Consider a perfect MCV (covering
all values in the join), with impossible filters. That is, filters
that have no matches in the join.

Made up example:

--
CREATE TABLE t1 (a int, b int);
CREATE TABLE t2 (c int, d int);
INSERT INTO t1 SELECT i, mod(i,2) FROM generate_series(1,100) S(i);
INSERT INTO t2 SELECT i, mod(i+1,2) FROM generate_series(1,100) S(i);

SELECT * FROM t1 JOIN t2 ON (t1.a = t2.c)
WHERE t1.b = 0 AND t2.d = 0;
--

This is estimated to return 25 rows, because each WHERE clause matches
50% rows, and 0.5 * 0.5 = 0.25. But if we create a join statistic on
(a,b,c,d), then we *know* there are no matches.

So why should we compare this to standard_sel, which is guaranteed to
be "> 0" and override the "better" selectivity, calcualted from the
join MCV? Seems a bit strange. The other (raw_sel <= 0) checks seem
a bit suspicious too.

Moreover, isn't raw_sel an estimate for (join AND covered filters)
while standard_sel is just for the join clause. Does it even make
sense to compare those? Aren't the values fundamentally different?
(Assuming join_mcv_clause_selectivity should really calculate this
selectivity, and not P(join|filters))

- I realized join_mcv_clause_selectivity now works for individual join
clauses, i.e. joins on multiple equality clauses are not supported.
I don't recall if this was agreed as a simplification for V1, maybe
it was? I think it's acceptable, but I wonder if we actually are
handling such cases correctly?

If it's calculating (join AND filters), won't it apply the filters
multiple times - once for each join clause? We should have some
tests for such joins, even if we don't support them now.

0004 - Improve auto-generated names for extended statistics

- Seems reasonable. I'd probably move it right after 0002, so that we
can commit it before the main join stats.

- One thing I'd consider is not repeating the table name for every
attribute - that seems excessive. Maybe only when it changes, so
that for example (t1.a, t1.b, t2.c, t2.d) would get t1_a_b_t2_c_d.

I did briefly look at the performance issue reported by Ilya's, and
I think it's not surprising it takes so long. It's a rather contrived
example, because both tables have just a single value "1" in the join
column (there is a PK column, but the join clause is not using it).

So we simply read 20k rows with "1" from the anchor table, and then for
each one "sample" the second table with 500k rows, all containing "1".
So the sampling code goes through 10,000,000,000 rows, pretty much.

Most joins won't be like that, of course. But we need to be prepared
for less severe cases (a couple values with many matches in the sampled
table, etc.). I believe we improve the sampling by doing three things:

1) Deduplicate the values in "anchor" table, and build all the samples
in one pass (IIRC we still need to build an independent sample for
each individual value - before deduplication).

2) Do a single query to sample all values at once, by executing
something like

WHERE val IN (... unique values ...) ORDER BY val

This will become even more important with index prefetching.

3) In fact, I think we could even build samples for all values in one
pass / single index scan.

4) I wonder if we could actually use something like TABLESAMPLE, to
filter values early / before our sampling code.

But those are just ideas, I have not tried implementing any of it.

regards

--
Tomas Vondra

Hi,

> On Aug 4, 2026, at 07:06, Alexandra Wang <alexandra(dot)wang(dot)oss(at)gmail(dot)com> wrote:
>
> For this round I'd most appreciate a thorough review of 0001 and 0002
> to see whether they're committable.

I reviewed 0001 and 0002.

0001 looks good to me as well.

For 0002, in addition to Tomas's comments, I noticed an issue with an
expression that const-folds to a plain column:

```
CREATE TABLE t (a int);
INSERT INTO t SELECT g FROM generate_series(1, 100) g;

CREATE STATISTICS s
ON (CASE WHEN true THEN a END)
FROM t;

ANALYZE t;
```

On v9, the object has `stxkind = {e}`, but `stxdexpr` is NULL and
`pg_stats_ext_exprs` has no row for it. Before 0002, the same definition
produced expression statistics.

Since v9 treats an expression that const-folds to a plain column as that
column, I think this single-entry definition should be rejected, just
like a statistics object defined on a single plain column. Instead, it
is accepted with `stxkind = {e}`, but `ANALYZE` builds no expression
statistics, which seems inconsistent.

--
Best regards,
Chengpeng Yan

On 8/9/26 00:08, Tomas Vondra wrote:
> ...
>
> 0002 - Unify extended statistics columns and expressions
>
> I think there's a couple issuses.
>
> - The psql describe code still checks (sversion >= 190000), but that's
> now wrong, it needs to check 200000. A simple rebase omission, but
> it can lead to failures on 19.
>
I noticed another minor issue in the psql describe code, in parsing the
statistics definition. If you do this

create statistics "aaaa ON bbbb" (mcv) ON a, b, c FROM t;

then "\d t" shows

Statistics objects:
"public.aaaa ON bbbb" (mcv) ON bbbb" (mcv) ON a, b, c FROM t

which is clearly confused. AFIAK this happens because
pg_get_statisticsobjdef_columns_from does about this

res = pg_get_statisticsobj_worker(statextid, true);
...
on_ptr = strstr(res, " ON ");

but the strstr() fails to consider the stxname could already contain the
string " ON ", and gets confused by it.

I think it could be fixed by adding a flag to
pg_get_statisticsobj_worker, to simply not generate the initial part at
all (and then the strstr is not needed at all). Or maybe it could return
the offset where the columns begin, also makes strstr unnecessary.

regards

--
Tomas Vondra

There seems to be an issue in CreateStatistics(), triggering an assert.

Consider this:

CREATE TABLE t1 (id int);
CREATE TABLE t2 (id int, y int);

CREATE INDEX t2_idx ON t2 (id);

-- this errors-out
CREATE STATISTICS s
ON t2.y
FROM t2;

-- this crashes
CREATE STATISTICS s
ON t2.y
FROM t1 JOIN t2 ON t1.id = t2.id;

With a single-table stats, this this fails with

ERROR: cannot create extended statistics on a single non-virtual column

but with the join, this gets skipped, because it's gated by

if (numcols == 1 && !isjoin)
{
...
}

and so it hits the assert on line ~714:

Assert(ntypes > 0 && ntypes <= lengthof(types));

I suppose we joins we want to allow single-column stats, but in that
case we should be careful about properly filling some join kinds. It
probably should be treated as expression (STATS_EXT_EXPRESSIONS), but I
haven't tried.

regards

--
Tomas Vondra