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/