Tracking per-RelOptInfo uniqueness during planning

Hi Richard:

This has been proposed several times over the years. The most recent
and most developed attempts are the work by Andy Fan and David Rowley
[1]. This patch takes a lot from that work and the discussion around
it: the basic shape of a per-RelOptInfo list of unique keys, built
bottom-up, with the keys expressed over ECs in the same spirit as
pathkeys.

Yes, it was started around 2021... and great to know lot of work is still
applicable today. and I'm glad that you can continue with this.

One of the main things that are different in this patch is how
outer-join nullability is represented, which was one of the harder
parts of the earlier attempts.

A UniqueKey is a set of ECs plus a single boolean "nullable" flag, and
keys are always kept over the base (un-nulled) ECs. The flag records
whether an outer join may have introduced NULLs into the key columns,
rather than recomputing that from the members' varnullingrels and NOT
NULL information at each lookup.

The payoff is that one structure serves two kinds of consumer with
different needs. When the flag is false the guarantee is NULL-aware,
which is what justifies removing a DISTINCT or GROUP BY. When it is
true, distinctness is guaranteed only among rows whose key columns are
all non-NULL; that is weaker, but still enough to prove a join
inner-unique or to match a strict join clause, where a NULL key row
cannot match anything anyway. Keeping keys on the base EC also makes
stacked outer joins fall out naturally, with no per-join remapping.

Another thing that is different in this patch is that the join-level
derivation is more thorough: a side's key is preserved when the other
side is unique for the join clauses, the union of a key from each side
is a key of the join, and an inner join's strict clauses can
strengthen a nullable key back to non-nullable.

This is nice.

Also, in addition to base and join relations, this patch also derives
unique keys for subqueries and for the query's upper relations. And
it makes the unique keys usable in more cases:

* removing a redundant DISTINCT step;
* removing a redundant GROUP BY step;
* proving a join inner-unique in innerrel_is_unique(), now including
multi-relation inner sides and not just base relations;
* skipping the unique-ification of a semijoin's RHS that is already
distinct.

Besides the above user case, if the user case (3) "Figure out more
interesting pathkey after join with normal UniqueKey" at [1]/messages/by-id/7mlamswjp81p.fsf@e18c07352.et15sqa is correct,
it would be another promising user case.

[1]: /messages/by-id/7mlamswjp81p.fsf@e18c07352.et15sqa

--
Best Regards
Andy Fan

Richard Guo <guofenglinux@gmail.com> wrote:

This has been proposed several times over the years. The most recent
and most developed attempts are the work by Andy Fan and David Rowley
[1]. This patch takes a lot from that work and the discussion around
it: the basic shape of a per-RelOptInfo list of unique keys, built
bottom-up, with the keys expressed over ECs in the same spirit as
pathkeys.

Thanks for working on this. Following is my initial review.

What makes it a bit difficult for me to think about the logic is the
'nullable' field of the UniqueKey structure. I don't think the name is very
descriptive. It seems to indicate that an OJ generated problematic NULL values
that affect uniqueness of the output, however populate_plain_rel_uniquekeys()
appears to set the sometimes as well.

I think the field name should rather give a hint about potential use of the
unique key, rather then telling how it was derived. Would something like
'null_equality' or 'consider_nulls_equal' make sense? In such a case, TRUE
value would then mean "the path output is unique even if NULL values are
considered equal".

Another thing I don't understand is in get_interesting_unique_ecs():

base_relids = bms_difference(ec->ec_relids, root->outer_join_rels);

if (bms_membership(base_relids) == BMS_MULTIPLE)
result = add_base_ec_positions(root, result, ec);

Do we really need more than one non-nullable rels? Note that the function
calls add_base_ec_positions(), for wich IMO a single non-nullable relation is
sufficient:

/* If ec is already a base EC, we add its own position */
if (!bms_overlap(ec->ec_relids, root->outer_join_rels))
return bms_add_member(result, ec->ec_index);

Besides that, why do you create the ECs for unique keys in advance
("eagerly"), rather than creating them when actually needed ("lazily"? Is the
reason that you only want to construct new ECs from the existing ones (because
it's easier to retrieve the operator info), and thus the set of new ECs is
does not depend on the uniqueness-related properties of relations?

I think that in the earlier versions of the patch, creation of the ECs was
driven by target expressions. This way we can generate more unique keys, but
construction of the corresponding ECs may be more difficult.

A few comments on coding:

* in populate_subquery_rel_uniquekeys(), I think the test

if (subquery->hasTargetSRFs)
return;

should appear at the very beginning, even before calling
get_interesting_unique_ecs(), because it's very cheap.

* populate_joinrel_uniquekeys()

/*
* Preservation of the RHS keys, if the LHS is unique for the clauses.
* Across a left join they become nullable, and an empty key does not
* survive null-extension (one null-extended row per unmatched LHS row).
*/
if (rhs->uniquekeys != NIL &&
!bms_overlap(rhs->lateral_relids, lhs->relids) &&
side_is_unique(root, joinrel, lhs, rhs, jointype, restrictlist))
{
foreach_node(UniqueKey, ukey, rhs->uniquekeys)
{
if (jointype == JOIN_INNER)
add_uniquekey(joinrel, ukey->eclass_indexes, ukey->nullable);
else if (!bms_is_empty(ukey->eclass_indexes))
add_uniquekey(joinrel, ukey->eclass_indexes, true);
}
}

1. If jointype != JOIN_INNER, shouldn't we assert that it's JOIN_LEFT?

2. For the left join, should add_uniquekey() alwyas be called with
nullable=true? If the LHS has uniquekeys at the same time, then the
null-extended rows should be unique too, so the uniquekeys of the join might
still be usable as a proof that the DISTINCT step is not necessary. (Of
course, the 'nullable' attribute of the LHS uniquekeys matters in this case.)

* translate_subquery_uniquekeys()

A comment explaining why 'subroot' can be NULL would make sense:

if (subroot == NULL)
return;

A few more minor suggestions are attached.

A suggestion for future improvement (or have I missed that the patch already
does that?): we can add unique keys to the grouping paths created due to eager
aggregation.

--
Antonin Houska
Web: https://www.cybertec-postgresql.com

On Thu, Jul 30, 2026 at 4:06 AM Antonin Houska <ah@cybertec.at> wrote:

Thanks for working on this. Following is my initial review.

Thanks for reviewing!

What makes it a bit difficult for me to think about the logic is the
'nullable' field of the UniqueKey structure. I don't think the name is very
descriptive. It seems to indicate that an OJ generated problematic NULL values
that affect uniqueness of the output, however populate_plain_rel_uniquekeys()
appears to set the sometimes as well.

Fair point. I didn't put much thought into the naming in v1. I've
renamed it to 'null_aware' in v2, which is a better name I believe.

Another thing I don't understand is in get_interesting_unique_ecs():

base_relids = bms_difference(ec->ec_relids, root->outer_join_rels);

if (bms_membership(base_relids) == BMS_MULTIPLE)
result = add_base_ec_positions(root, result, ec);

Do we really need more than one non-nullable rels? Note that the function
calls add_base_ec_positions(), for wich IMO a single non-nullable relation is
sufficient:

/* If ec is already a base EC, we add its own position */
if (!bms_overlap(ec->ec_relids, root->outer_join_rels))
return bms_add_member(result, ec->ec_index);

These are answering different questions. BMS_MULTIPLE decides which
ECs are worth tracking keys over; it isn't a precondition of
add_base_ec_positions(), which we do call with single-member ECs a bit
further down, from add_ojclause_ecs().

The reason we need the BMS_MULTIPLE check is that an EC covering one
base relation can't generate a join clause, so no consumer would ever
look it up through uniquekeys_match_join_clauses(). Single-relation
ECs still enter the set when another consumer can use them: the
DISTINCT columns, the GROUP BY columns, and both sides of a
mergejoinable outer-join clause. These are added later in that
function.

Removing the test wouldn't give wrong answers, but it would defeat the
point of interesting_unique_ecs, which is to bound how many keys we
track.

Besides that, why do you create the ECs for unique keys in advance
("eagerly"), rather than creating them when actually needed ("lazily"? Is the
reason that you only want to construct new ECs from the existing ones (because
it's easier to retrieve the operator info), and thus the set of new ECs is
does not depend on the uniqueness-related properties of relations?

Partly for the reason you guess. The more concrete reason is that
interesting_unique_ecs is a set of positions in root->eq_classes,
consumed while we build the base relations' keys. So the base EC must
already exist, and already be listed in rel->eclass_indexes.

A few comments on coding:

* in populate_subquery_rel_uniquekeys(), I think the test

if (subquery->hasTargetSRFs)
return;

should appear at the very beginning, even before calling
get_interesting_unique_ecs(), because it's very cheap.

Hmm, I don't think so. It guards only the set-operation branch
underneath it, not the whole function. A subquery with tlist SRFs can
still have unique keys to translate. "SELECT DISTINCT a,
generate_series(1,2) g FROM t" is distinct over (a, g): the DISTINCT
is applied above the SRF expansion, so the subquery's final relation
carries that key and we want it in the parent.

* populate_joinrel_uniquekeys()

/*
* Preservation of the RHS keys, if the LHS is unique for the clauses.
* Across a left join they become nullable, and an empty key does not
* survive null-extension (one null-extended row per unmatched LHS row).
*/
if (rhs->uniquekeys != NIL &&
!bms_overlap(rhs->lateral_relids, lhs->relids) &&
side_is_unique(root, joinrel, lhs, rhs, jointype, restrictlist))
{
foreach_node(UniqueKey, ukey, rhs->uniquekeys)
{
if (jointype == JOIN_INNER)
add_uniquekey(joinrel, ukey->eclass_indexes, ukey->nullable);
else if (!bms_is_empty(ukey->eclass_indexes))
add_uniquekey(joinrel, ukey->eclass_indexes, true);
}
}

1. If jointype != JOIN_INNER, shouldn't we assert that it's JOIN_LEFT?

Yeah, we can have this Assert.

2. For the left join, should add_uniquekey() alwyas be called with
nullable=true? If the LHS has uniquekeys at the same time, then the
null-extended rows should be unique too, so the uniquekeys of the join might
still be usable as a proof that the DISTINCT step is not necessary. (Of
course, the 'nullable' attribute of the LHS uniquekeys matters in this case.)

The RHS key on its own isn't usable for that. Two unmatched LHS rows
produce two null-extended output rows whose RHS key columns are all
NULL, so they are equal on that key once NULLs count as equal. No LHS
property can change that, because the key doesn't mention the LHS.

What you're describing is the Combination rule a few lines below,
which adds the union of one key from each side, and that one does keep
its NULL-awareness across a left join.

A comment explaining why 'subroot' can be NULL would make sense:

if (subroot == NULL)
return;

Added in v2.

A few more minor suggestions are attached.

I absorbed into v2 some of your suggestions here. Thanks!

A suggestion for future improvement (or have I missed that the patch already
does that?): we can add unique keys to the grouping paths created due to eager
aggregation.

Yeah, that's still in my to-do list, which also includes support for
appendrels, partitionwise child joins, UNION ALL parents, RTE_VALUES,
or RTE_RESULT, etc.

- Richard

On Fri, Aug 14, 2026 at 9:17 AM Richard Guo <guofenglinux@gmail.com> wrote:

Yeah, that's still in my to-do list, which also includes support for
appendrels, partitionwise child joins, UNION ALL parents, RTE_VALUES,
or RTE_RESULT, etc.

Here is v3 of this patchset.

0001 is the same as v2, except that it also restores NULL-awareness to
a key that lost it at semijoins, in addition to inner joins.

0002 teaches UniqueKeys about appendrel children and child joins. For
now it simply has the child relations, and the child join relations
built for a partitionwise join, inherit their parent's keys. This
works because a child relation emits a subset of its parent's rows,
and a subset of a distinct set is distinct.

In theory, we can inspect the child relation's unique indexes and
build UniqueKeys of its own. A partition can have a unique index that
its parent cannot. Such keys hold for the child alone and must not
reach the parent. I have left that out. Deducing those keys afresh
means running the join deduction once per child join, which spends
planning time on every child join to reproduce the parent's answer in
nearly every case.

0003 teaches UniqueKeys about the grouped relations that eager
aggregation builds. Partial aggregation keeps one row per group, so a
grouped relation is distinct over its grouping expressions. Unlike
the query's own grouping step, this one has joins above it, so the key
can prove such a join inner-unique.

A nice suprise is that this fits eager aggregation quite well. Eager
aggregation is already obliged to group by every column an upper join
needs, so the key we deduce always contains the ECs of the clauses of
the joins above it. So whenever the grouped relation contributes
nothing further, we can always get an inner-unique join.

Please ignore the costsize.c changes in 0003. That's a fix to a known
right-semi/right-anti hash join costing issue. See [1]/messages/by-id/CAMbWs49XwhSC=e8_yeEaGKmKNyWR3DHH0p+e4k-bR_pgRiN8nQ@mail.gmail.com.

[1]: /messages/by-id/CAMbWs49XwhSC=e8_yeEaGKmKNyWR3DHH0p+e4k-bR_pgRiN8nQ@mail.gmail.com

- Richard

Hi,

Thank you for working on this - I'll be running it through my own
benchmarks as well.

On 8/18/26 04:14, Richard Guo wrote:

Here is v3 of this patchset.

But first, in v3-0001 `create_partial_unique_paths()` builds
`partial_unique_rel` via memcpy from `input_rel` but never resets the
`unique_keys` field. Unlike the structural fields memcpy legitimately
carries over, `uniquekeys` describes uniqueness of this specific rel's
output - same category as rows/reltarget/pathlist, which the function
already resets - so it should be reset too rather than silently
inherited from `input_rel`. It's harmless today since nothing reads it
there, but it's the kind of state field a future no-op check could pick
up and use wrongly.

planner.c: create_partial_unique_paths()
```
 partial_unique_rel->cheapest_parameterized_paths = NIL;
+partial_unique_rel->uniquekeys = NIL;

 /* Estimate number of output rows */
```

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

On Tue, Aug 18, 2026 at 9:31 PM Ilia Evdokimov
<ilya.evdokimov@tantorlabs.com> wrote:

planner.c: create_partial_unique_paths()
```
partial_unique_rel->cheapest_parameterized_paths = NIL;
+partial_unique_rel->uniquekeys = NIL;

/* Estimate number of output rows */
```

Thanks. Fixed in v4. v4 also drops the costsize.c changes from 0003,
as the costing issue has been fixed on master.

- Richard

Richard Guo <guofenglinux@gmail.com> wrote:

Thanks. Fixed in v4. v4 also drops the costsize.c changes from 0003,
as the costing issue has been fixed on master.

A few more comments:

* populate_joinrel_uniquekeys()

Shouldn't we care about the number of unique keys created by the combination
technique? If most / all relations do have the unique keys, the list of keys
can grow exponentially as we keep adding relations to the join.

* uniquekeys_match_join_clauses()

/*
* Nullable keys are fine here: rows with NULL key values cannot match any
* outer row through these strict clauses.
*/

I'm not able to find where the callers check the strictness of the clauses.

Also, "Nullable" => "null-unaware" ?

* strengthen_uniquekeys_for_join()

In the header comment:

"The caller must have established that every clause holds of every output" =>
"...holds for ..." ?

I also tried to adjust one comment regarding "strengthening" of the unique
keys - see the attached diff. The original wording was hard form me to
understand, so I elaborated it more in detail. (Of course it's possible that I
missed the point altogether.)

Comments on regression tests:

v4-0001
-------

* The following

+-- a key column equated to a constant drops out of the key
+explain (costs off) select distinct b from uk_pk2 where a = 5;
+               QUERY PLAN               
+----------------------------------------
+ Bitmap Heap Scan on uk_pk2
+   Recheck Cond: (a = 5)
+   ->  Bitmap Index Scan on uk_pk2_pkey
+         Index Cond: (a = 5)
+(4 rows)

does not seem prove what the comment claims because explicit grouping is (for
different reason, probably due to the unique key not being a subset of the
DISTINCT clause) needed even without the WHERE clause:

explain (costs off) select distinct b from uk_pk2;
QUERY PLAN
--------------------------
HashAggregate
Group Key: b
-> Seq Scan on uk_pk2
(3 rows)

* To test the translation of the unique keys into the outer query,

+--
+-- Subquery-in-FROM keys
+--
+-- a DISTINCT inside is translated into the outer query
+explain (costs off) select distinct a, b from (select distinct a, b from uk_pk2) s;
+     QUERY PLAN     
+--------------------
+ Seq Scan on uk_pk2
+(1 row)
+
+-- likewise a GROUP BY
+explain (costs off) select distinct a, b from (select a, b from uk_pk2 group by a, b) s;
+     QUERY PLAN     
+--------------------
+ Seq Scan on uk_pk2
+(1 row)

I think neither DISTINCT nor GROUP BY is needed in the subquery. The subquery should have the appropriate unique keys anyway:

explain (costs off) select distinct a, b from (select a, b from uk_pk2) s;
QUERY PLAN
--------------------
Seq Scan on uk_pk2
(1 row)

* What's the point of the OFFSET clause here?

+-- a key deduced inside the subquery's own join search
+explain (costs off)
+select distinct x from
+  (select uk_p.id as x from uk_p join uk_q on uk_p.id = uk_q.id offset 0) s;
+            QUERY PLAN            
+----------------------------------
+ Hash Join
+   Hash Cond: (uk_p.id = uk_q.id)
+   ->  Seq Scan on uk_p
+   ->  Hash
+         ->  Seq Scan on uk_q
+(5 rows)

I'm getting the same plan w/o that.

* I was wondering what's specific about CROSS JOIN (v03-0001)

+-- one side's key alone is not a key of a cross join
+explain (costs off) select distinct uk_p.id from uk_p cross join uk_q;
+                     QUERY PLAN                      
+-----------------------------------------------------
+ Unique
+   ->  Nested Loop
+         ->  Index Only Scan using uk_p_pkey on uk_p
+         ->  Materialize
+               ->  Seq Scan on uk_q
+(5 rows)

but debugger session revealed that populate_plain_rel_uniquekeys() does not
find the ECs for uk_q. I think it's because the table is not mentioned in the
DISTINCT clause. Once I added it, the appropriate unique key seems to exist,
even when the join is CROSS JOIN:

explain (costs off) select distinct uk_p.id, uk_q.id from uk_p cross join uk_q;
QUERY PLAN
------------------------------
Nested Loop
-> Seq Scan on uk_p
-> Materialize
-> Seq Scan on uk_q
(4 rows)

* Regarding FULL JOIN

+-- a full join null-extends both sides, so nothing survives
+explain (costs off)
+select distinct uk_p.id from uk_p full join uk_q on uk_p.id = uk_q.id;

don't we also need a query whith "DISTINCT uk_q.id" clause?

* I'm not sure the unique keys are tested here

+-- the RHS of this semijoin is already distinct, so it is not unique-ified
+explain (costs off)
+select * from uk_p, uk_q where (uk_p.id, uk_q.id) in (select a, b from uk_pk2);
+               QUERY PLAN                
+-----------------------------------------
+ Hash Join
+   Hash Cond: (uk_pk2.b = uk_q.id)
+   ->  Hash Join
+         Hash Cond: (uk_pk2.a = uk_p.id)
+         ->  Seq Scan on uk_pk2
+         ->  Hash
+               ->  Seq Scan on uk_p
+   ->  Hash
+         ->  Seq Scan on uk_q
+(9 rows)

I'm getting the same plan even if I comment out the fast path (i.e. the use of
the unique keys) in rel_is_distinct_for().

* Is this comment

+-- across a left join the RHS key covers only the matched rows
+explain (costs off) select distinct uk_d1.u from uk_d2 left join uk_d1 on uk_d2.id = uk_d1.u;

saying that the RHS "loses its NULL-awareness", as tested earlier in the
script, or is it a different problem?

v4-0002
-------

* Maybe

"A partitioned table's unique index must include ..."
=>
"A partitioned table's unique index key must include ..."

* " ... an inheritance parent has none"

Does that mean " ... an inheritance parent has no unique indexes", because
inheritance parent is treated as if it had no indexes at all, per
get_relation_info()?

/*
* Make list of indexes. Ignore indexes on system catalogs if told to.
* Don't bother with indexes from traditional inheritance parents. For
* partitioned tables, we need a list of at least unique indexes as these
* serve as unique proofs for certain planner optimizations. However,
* let's not discriminate here and just record all partitioned indexes
* whether they're unique indexes or not.
*/

v4-0003
-------

* The patch seems to handle grouped child relation, so it'd make sense to have
a test for that.

--
Antonin Houska
Web: https://www.cybertec-postgresql.com

Would it make sense to add an `enable_uniquekeys GUC`, enabled by
default? UniqueKeys can eliminate DISTINCT/GROUP BY steps and mark joins
as inner-unique, so an incorrect uniqueness proof could affect query
results. A switch would help diagnose regressions and temporarily
disable the optimization if an issue is found. Eager aggregation and
self-join elimination already have such switches:
`enable_eager_aggregate` and `enable_self_join_elimination`.

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