Skip redundant DISTINCT enforcement (setop branches, provably-unique input)

Hi,

There was an enhancement request sent to the bug reporting list titled
"BUG #19575: Enhancement for Redundant DISTINCT in set-operation
branches".

After looking at the issue, I had Claude (Fable, high effort) take a
stab at it, so I'm posting that here in case anyone wants to take a
look. I had another AI review it in 2 rounds of revisions, and then
got Claude to review it again from scratch. Here is that proposal:

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

A recent report to -bugs [1] observed that a DISTINCT inside a branch of a
UNION/INTERSECT/EXCEPT is enforced even though the set operation eliminates
duplicates anyway, roughly doubling execution time. That's not a bug — we
plan what the query says — but it is a missed optimization, and it turns out
to be cheap to fix. Attached are two patches against master.

Neither patch touches the parse tree: parse->distinctClause is left intact
in both cases, and we merely refrain from building the paths that would
enforce it. (Think of it like sorting: we don't "remove redundant ORDER
BYs", we just don't insert a Sort when the input already satisfies the
pathkeys. Here the DISTINCT is an obligation that something else already
discharges.)

0001: Skip enforcing a set-operation child's DISTINCT when an ancestor set
operation will fully deduplicate its output anyway.

The setop recursion in prepunion.c now tracks a dedup_above flag:
- set for the children of any non-ALL UNION/INTERSECT/EXCEPT;
- passed through UNION ALL unchanged, since UNION ALL preserves row
membership and a downstream dedup only cares about membership;
- passed through INTERSECT ALL unchanged too. INTERSECT ALL changes
its inputs' multiplicities (it emits min(m,n) copies), but not its
output's membership: min(m,n) > 0 iff m > 0 and n > 0. So while a
DISTINCT below a top-level INTERSECT ALL must be kept, one below an
INTERSECT ALL that itself feeds a deduplicating ancestor is still
redundant, and we elide it;
- force-cleared for both children of EXCEPT ALL, which is genuinely
multiplicity-sensitive. This isn't just about copy counts: in
(SELECT DISTINCT x FROM a) EXCEPT ALL (SELECT x FROM b)
dropping the DISTINCT changes which values max(m-n,0) leaves
positive, i.e. membership, so nothing above an EXCEPT ALL may
subsume a DISTINCT below it. There are regression tests for both
the INTERSECT ALL pass-through and the EXCEPT ALL counterexample.

The flag rides the existing subquery_planner(..., setops) channel
(adding a parameter), and grouping_planner skips the distinct step
when it's set — unless the child uses DISTINCT ON (changes which rows
survive) or has a LIMIT/OFFSET (dedup-before-limit changes which rows
are emitted). Window functions and volatile tlist entries are fine:
enforcement runs after they're evaluated, so skipping it changes
neither evaluation counts nor membership.

build_setop_child_paths' group-count estimation previously assumed
"child had DISTINCT => output already mostly unique"; when enforcement
was skipped it now falls through to estimate_num_groups(), which gives
the right answer either way.

Children of a recursive UNION keep their DISTINCT for now; the
interaction with the worktable seemed subtle enough to stay
conservative in this patch.

0002: Skip enforcing DISTINCT when the input is provably distinct already.

Motivated by the common ORM-ish shape
SELECT DISTINCT x FROM (SELECT x FROM t GROUP BY x) ss;
which today runs two identical HashAggregates back to back. When the
query reads exactly one subquery RTE (no joins — joins can multiply
rows), every DISTINCT column is a plain Var of it, and the subquery's
own structure proves distinctness, we skip the outer enforcement. The
proof is entirely the existing query_supports_distinctness() /
query_is_distinct_for() machinery that join removal already relies on,
so DISTINCT, GROUP BY, aggregation-without-GROUP-BY, and non-ALL set
operations in the subquery all work, including the superset case
(unique on {a} => unique on {a,b}) and the collation/operator
compatibility checks. WHERE quals are fine (filtering can't introduce
duplicates); target SRFs and window functions bail out conservatively.

This patch intentionally derives distinctness only from relational
operators explicitly present in the query tree (DISTINCT, GROUP BY,
aggregation, non-ALL set operations). It performs no inference from
schema metadata (primary keys, unique indexes, foreign keys,
functional dependencies, or join predicates) and introduces no new
uniqueness analysis beyond the query_is_distinct_for() infrastructure
the planner already uses for join removal; structural reasoning of
this kind has decades of prior art (Paulley & Larson 1994; our own
remove_useless_groupby_columns since 9.6). Extending the optimization
to exploit catalog metadata is deliberately left out of scope.
Besides being a substantially larger planner project, it raises
separate prior-art and intellectual-property questions that are
better considered independently.

Numbers (assert-enabled build, so absolute values are pessimistic; the
tables are the -bugs report's 100k-row lhs/rhs; medians of 3):

master patched
(DISTINCT..) UNION (DISTINCT..) 262 ms 145 ms
(DISTINCT..) INTERSECT (DISTINCT..) 166 ms 83 ms
(DISTINCT..) EXCEPT (DISTINCT..) 167 ms 71 ms
DISTINCT over GROUP BY subquery 116 ms 82 ms

Plan shape for the first query goes from two branch HashAggregates feeding
a third to a single HashAggregate over a plain Append; the parallel-plan
situation also improves, since the raw child paths (including partial
paths) now flow into the setop directly.

Both patches pass check-world here (regress, isolation, plpgsql,
postgres_fdw explicitly re-run). New regression coverage is in union.sql
(all the subsumption/blocking combinations, plus the EXCEPT ALL membership
counterexample as a results test) and select_distinct.sql.

Future directions, not attempted here: treating distinctness as a path
property (the UniqueKeys idea) would restore a cost-based choice between
branch-level and setop-level dedup rather than 0001's always-skip — though
I couldn't construct a case where branch-level enforcement wins by more
than noise, since under a hash-based parent it's a strictly extra pass and
under a sorted parent the child's sort happens regardless. It would also
subsume 0002's single-subquery restriction. DISTINCT ON elision when
groups provably have one row is another small follow-up. Also, a setop
branch that carries its own ORDER BY/LIMIT becomes a separate query level,
and the flag deliberately stops at that boundary (a nested setop tree in
such a branch restarts with the flag cleared); that could be threaded
through if it ever matters in practice.

[1] https://www.postgresql.org/message-id/19575-7ce4e703a249ba27%40postgresql.org

--
Thom