Re: Remove redundant DISTINCT when GROUP BY already guarantees uniqueness

Picking up on David's point about UniqueKeys: that direction makes sense
to me, and I agree that removing DISTINCT only in the GROUP BY case
seems too narrow by itself.

I spent some time getting hands-on with the existing patch series and
trying to understand where the harder parts are. I'd like to help move
this forward if that would be useful.

As a starting point, I rebased Antonín's 2024-04 set (the rebase of
Andy Fan's v3, plus 0002-0004) onto current master. It is in better
shape than I expected:

- The core .c files apply cleanly with a 3-way merge; I only saw two
trivial header conflicts.
- It compiles after two mechanical API-drift fixes:
get_eclass_for_sort_expr() has gained a Relids argument, and direct
access to TupleDescData.attrs[] needs to become TupleDescAttr().
- In the cases I checked, it behaves as intended: DISTINCT over a
primary key collapses to a plain scan, and

SELECT DISTINCT u.id
FROM u JOIN t ON u.t_id = t.id

drops the DISTINCT via join propagation, since the join to t's
primary key cannot duplicate rows from u. The corresponding
duplicating-join case still keeps the DISTINCT.
- The bundled uniquekey regression test passes. The only diffs I saw
against the 2024 expected output is plan/annotation churn from
intervening core work, such as self-join-elimination "Replaces:"
lines and incremental-sort costing. I did not see result-data
changes.

One useful thing that has changed since that patch was written is that
RelOptInfo.notnullattnums now exists in core. That seems to make the
patch's own notnullattrs mostly redundant. It is not a blind
substitution, since the encodings differ and the patch also augments
notnullattrs with subquery-derived non-null facts in the 0004 path, but
I think this part can probably be slimmed down by seeding from
notnullattnums while keeping it augmentable.

Before spending much more time on the multi-join scaling problem, I
looked a bit on how other optimizers deal with similar issues. The main
thing I took away is that derived-key enumeration can become expensive
surprisingly quickly:

- Calcite appears to have hit this with unique-key enumeration over
composite keys; the fix there was to cap the result and fall back
to "not known unique" on overflow.
- CockroachDB's FuncDepSet takes a different approach and avoids
enumerating all candidate keys, instead keeping a single minimal
candidate key.
- The NULL issue seems closely related to the strict-vs-lax
distinction from the FD literature. PostgreSQL already has both
ideas in nearby code: the NOT NULL / NULLS NOT DISTINCT gate in
distinct_is_redundant(), and the different requirements in
relation_has_unique_index_for().

So my current thought is to stay fairly close to the patch's existing
keys-over-EquivalenceClasses model. EC-index sets are canonical, which
is attractive because it gives order-independence across join search
without introducing a larger FD framework.

The shape I was considering is:

1. tag each key as strict or lax, derived at the base relation from
attnotnull and indnullsnotdistinct, so the same facility can serve
both index-uniqueness and DISTINCT/GROUP BY-style consumers;

2. track only "interesting" keys, for example keys relevant to
DISTINCT, GROUP BY, ORDER BY, or merge clauses, reduce those to
minimal keys, and use a hard cap with fallback to "unknown" to
avoid unbounded growth;

3. keep the representation extensible enough that a strict/lax flag
and constants, e.g. () -> A, can be added later, without trying to
build a full FD closure engine now.

A few questions before I sink more time into this:

- Is reviving Antonín's rebase a reasonable path, or is there newer
WIP I should start from instead?
- Does the keys-only + strict/lax + interesting-keys-with-cap approach
match what people had in mind, or is the preference to move toward a
fuller FD model?
- I pushed the rebased branch here, in case it is useful as a starting
point:

https://github.com/systay/postgres/tree/uk-rebase

I also have more detailed notes on the design tradeoffs, but I did not
want to make this mail longer unless that would be useful.

On Fri, Jun 12, 2026 at 5:19 AM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>
> On Mon, 8 Jun 2026 at 23:12, Ilia Evdokimov
> <ilya(dot)evdokimov(at)tantorlabs(dot)com> wrote:
> > When a query contains both DISTINCT and GROUP BY, planner currently
> > always creates a separate plan node to eliminate duplicate output rows.
> > However, if GROUP BY is present, each output row already corresponds to
> > exactly one group - meaning the rows produced by GROUP BY are already
> > unique on their group keys. Any DISTINCT clause that covers all those
> > group keys therefore adds no filtering and the de-duplication step is
> > pure overhead.
>
> I think only doing something just for that case is likely too narrow a scope.
>
> In [1], I wrote:
> > Sometime in the future, I'd like to see some sort of UniqueKeys List
> > in RelOptInfo which is initially populated by using looking at the
> > unique indexes during build_simple_rel(). The idea is that these
> > UniqueKeys would get propagated into RELOPT_JOINRELs when the join
> > condition matches a set of unique keys on the other side of the join.
> > e.g. If the outer side of the join had a UniqueKey matching the join
> > condition then we could take all of the UniqueKeys from the RelOptInfo
> > for the inner side of the join (and vice versa). This infrastructure
> > would allow us to no-op a DISTINCT when the RelOptInfo has targetlist
> > items which completely cover at least one UniqueKey set, or not bother
> > performing a sort for a GROUP BY when the GROUP BY clause is covered
> > by a UniqueKey.
>
> There was some work on that by Andy Fan after I wrote a prototype for
> it. I didn't have much spare bandwidth to take a serious look at that
> patch at the time. However, I still think it's the best way to solve
> this as it allows the relevant UniqueKeys to be propagated up each
> join level and we'll know exactly what the results are unique on at
> each join level. Doing this would allow many more optimisations than
> just skipping redundant DISTINCT columns or operations.
>
> One example is: SELECT t1.id,sum(t1.col) FROM t1 INNER JOIN t2 ON
> t1.t2_id = t2.unique_column GROUP BY t1.id; This would be able to do
> a simple Group Aggregate without sorting as there's guaranteed to be 1
> row per group.
>
> It also allows the unique join optimisation to be based on the unique
> keys rather than calculating that from looking at unique indexes or
> the properties of a subquery.
>
> I believe the latest work on UniqueKeys is in [2].
>
> David
>
> [1] https://postgr.es/m/CAKJS1f-uSUr9dw6j48S5g3zMS=w-vp2oCNZzfriW2yVLAXj9iw@mail.gmail.com
> [2] https://postgr.es/m/flat/7mlamswjp81p.fsf%40e18c07352.et15sqa
>
>