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
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 9c040ecefc8..c2925cd9522 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2837,7 +2837,7 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
/* Generate a subroot and Paths for the subquery */
plan_name = choose_plan_name(root->glob, rte->eref->aliasname, false);
rel->subroot = subquery_planner(root->glob, subquery, plan_name,
- root, NULL, false, tuple_fraction, NULL);
+ root, NULL, false, tuple_fraction, NULL, false);
/* Isolate the params needed by this specific subplan */
rel->subplan_params = root->plan_params;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 3225185d16f..66352a4a624 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -151,7 +151,7 @@ static Bitmapset *find_having_conflicts(Query *parse, Index group_rtindex);
static Oid having_var_grouping_eqop(Var *var, void *context);
static Oid group_var_eqop(Query *parse, Var *var);
static void grouping_planner(PlannerInfo *root, double tuple_fraction,
- SetOperationStmt *setops);
+ SetOperationStmt *setops, bool dedup_above);
static grouping_sets_data *preprocess_grouping_sets(PlannerInfo *root);
static List *remap_to_groupclause_idx(List *groupClause, List *gsets,
int *tleref_to_colnum_map);
@@ -530,7 +530,7 @@ standard_planner(Query *parse, const char *query_string, int cursorOptions,
/* primary planning entry point (may recurse for subqueries) */
root = subquery_planner(glob, parse, NULL, NULL, NULL, false,
- tuple_fraction, NULL);
+ tuple_fraction, NULL, false);
/* Select best Path and turn it into a Plan */
final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
@@ -749,6 +749,9 @@ standard_planner(Query *parse, const char *query_string, int cursorOptions,
* the context in which it's being used so that Paths correctly sorted for the
* set operation can be generated. NULL when not planning a set operation
* child, or when a child of a set op that isn't interested in sorted input.
+ * dedup_above is true if this query is a set-operation child whose output
+ * will be fully deduplicated by an ancestor set operation, letting us skip
+ * enforcing this query's own DISTINCT clause; see grouping_planner.
*
* Basically, this routine does the stuff that should only be done once
* per Query object. It then calls grouping_planner. At one time,
@@ -770,7 +773,7 @@ PlannerInfo *
subquery_planner(PlannerGlobal *glob, Query *parse, char *plan_name,
PlannerInfo *parent_root, PlannerInfo *alternative_root,
bool hasRecursion, double tuple_fraction,
- SetOperationStmt *setops)
+ SetOperationStmt *setops, bool dedup_above)
{
PlannerInfo *root;
List *newWithCheckOptions;
@@ -813,6 +816,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse, char *plan_name,
memset(root->upper_targets, 0, sizeof(root->upper_targets));
root->processed_groupClause = NIL;
root->processed_distinctClause = NIL;
+ root->distinct_elided = false;
root->processed_tlist = NIL;
root->update_colnos = NIL;
root->grouping_map = NULL;
@@ -1392,7 +1396,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse, char *plan_name,
/*
* Do the main planning.
*/
- grouping_planner(root, tuple_fraction, setops);
+ grouping_planner(root, tuple_fraction, setops, dedup_above);
/*
* Capture the set of outer-level param IDs we have access to, for use in
@@ -1691,6 +1695,9 @@ preprocess_phv_expression(PlannerInfo *root, Expr *expr)
* the context in which it's being used so that Paths correctly sorted for the
* set operation can be generated. NULL when not planning a set operation
* child, or when a child of a set op that isn't interested in sorted input.
+ * dedup_above is true if this query is a set-operation child whose output
+ * will be fully deduplicated by an ancestor set operation, letting us skip
+ * enforcing this query's own DISTINCT clause.
*
* Returns nothing; the useful output is in the Paths we attach to the
* (UPPERREL_FINAL, NULL) upperrel in *root. In addition,
@@ -1702,7 +1709,7 @@ preprocess_phv_expression(PlannerInfo *root, Expr *expr)
*/
static void
grouping_planner(PlannerInfo *root, double tuple_fraction,
- SetOperationStmt *setops)
+ SetOperationStmt *setops, bool dedup_above)
{
Query *parse = root->parse;
int64 offset_est = 0;
@@ -2104,9 +2111,31 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
*/
if (parse->distinctClause)
{
- current_rel = create_distinct_paths(root,
- current_rel,
- sort_input_target);
+ if (dedup_above &&
+ !parse->hasDistinctOn &&
+ parse->limitCount == NULL &&
+ parse->limitOffset == NULL)
+ {
+ /*
+ * This query is a set-operation child whose output will be
+ * fully deduplicated by an ancestor set operation, so
+ * enforcing DISTINCT here cannot affect the query's final
+ * result: the ancestor's dedup sees the same row membership
+ * either way. (Window functions and volatile tlist entries
+ * are fine: enforcement happens after they're evaluated, so
+ * skipping it changes neither evaluation counts nor row
+ * membership. A LIMIT/OFFSET would make the dedup
+ * semantically significant, and DISTINCT ON changes which
+ * rows survive, so those cases keep the enforcement.) We
+ * must not modify parse->distinctClause itself; we merely
+ * refrain from building the paths that would enforce it.
+ */
+ root->distinct_elided = true;
+ }
+ else
+ current_rel = create_distinct_paths(root,
+ current_rel,
+ sort_input_target);
}
} /* end of if (setOperations) */
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 6aa8971c95d..762c3d19dc3 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -224,7 +224,7 @@ make_subplan(PlannerInfo *root, Query *orig_subquery,
/* Generate Paths for the subquery */
subroot = subquery_planner(root->glob, subquery,
choose_plan_name(root->glob, sublinkstr, true),
- root, NULL, false, tuple_fraction, NULL);
+ root, NULL, false, tuple_fraction, NULL, false);
/* Isolate the params needed by this specific subplan */
plan_params = root->plan_params;
@@ -274,7 +274,7 @@ make_subplan(PlannerInfo *root, Query *orig_subquery,
/* Generate Paths for the ANY subquery; we'll need all rows */
plan_name = choose_plan_name(root->glob, sublinkstr, true);
subroot = subquery_planner(root->glob, subquery, plan_name,
- root, subroot, false, 0.0, NULL);
+ root, subroot, false, 0.0, NULL, false);
/* Isolate the params needed by this specific subplan */
plan_params = root->plan_params;
@@ -973,7 +973,7 @@ SS_process_ctes(PlannerInfo *root)
*/
subroot = subquery_planner(root->glob, subquery,
choose_plan_name(root->glob, cte->ctename, false),
- root, NULL, cte->cterecursive, 0.0, NULL);
+ root, NULL, cte->cterecursive, 0.0, NULL, false);
/*
* Since the current query level doesn't yet contain any RTEs, it
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index b136f12ff3b..bf854c4dce9 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -43,6 +43,7 @@
static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
SetOperationStmt *parentOp,
+ bool dedup_above,
List *colTypes, List *colCollations,
List *refnames_tlist,
List **pTargetList,
@@ -56,13 +57,16 @@ static void build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
List *interesting_pathkeys,
double *pNumGroups);
static RelOptInfo *generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
+ bool dedup_above,
List *refnames_tlist,
List **pTargetList);
static RelOptInfo *generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
+ bool dedup_above,
List *refnames_tlist,
List **pTargetList);
static List *plan_union_children(PlannerInfo *root,
SetOperationStmt *top_union,
+ bool child_dedup_above,
List *refnames_tlist,
List **tlist_list,
List **istrivial_tlist);
@@ -163,6 +167,7 @@ plan_set_operations(PlannerInfo *root)
*/
setop_rel = recurse_set_operations((Node *) topop, root,
NULL, /* no parent */
+ false, /* no dedup above */
topop->colTypes, topop->colCollations,
leftmostQuery->targetList,
&top_tlist,
@@ -189,6 +194,15 @@ plan_set_operations(PlannerInfo *root)
* getting sorted output from this step. ("Sorted" means "sorted according
* to the default btree opclasses of the result column datatypes".)
*
+ * dedup_above is true if some ancestor set operation will fully deduplicate
+ * this step's output rows, making duplicate-elimination work below this
+ * point semantically redundant. It is propagated to leaf subqueries so
+ * that grouping_planner can skip enforcing a redundant DISTINCT there.
+ * Note that it can only be passed down through ancestors that preserve row
+ * membership (UNION ALL, and INTERSECT ALL, whose output multiplicities
+ * depend on its inputs' but whose output membership does not); the truly
+ * multiplicity-sensitive EXCEPT ALL resets it for both its children.
+ *
* Returns a RelOptInfo for the subtree, as well as these output parameters:
* *pTargetList: receives the fully-fledged tlist for the subtree's top plan
* *istrivial_tlist: true if, and only if, datatypes between parent and child
@@ -213,6 +227,7 @@ plan_set_operations(PlannerInfo *root)
static RelOptInfo *
recurse_set_operations(Node *setOp, PlannerInfo *root,
SetOperationStmt *parentOp,
+ bool dedup_above,
List *colTypes, List *colCollations,
List *refnames_tlist,
List **pTargetList,
@@ -252,7 +267,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
subroot = rel->subroot = subquery_planner(root->glob, subquery,
plan_name, root, NULL,
false, root->tuple_fraction,
- parentOp);
+ parentOp, dedup_above);
/*
* It should not be possible for the primitive query to contain any
@@ -280,11 +295,11 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
/* UNIONs are much different from INTERSECT/EXCEPT */
if (op->op == SETOP_UNION)
- rel = generate_union_paths(op, root,
+ rel = generate_union_paths(op, root, dedup_above,
refnames_tlist,
pTargetList);
else
- rel = generate_nonunion_paths(op, root,
+ rel = generate_nonunion_paths(op, root, dedup_above,
refnames_tlist,
pTargetList);
@@ -392,6 +407,8 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
*/
lrel = recurse_set_operations(setOp->larg, root,
NULL, /* no value in sorted results */
+ false, /* recursive-union dedup semantics
+ * are subtle; stay conservative */
setOp->colTypes, setOp->colCollations,
refnames_tlist,
&lpath_tlist,
@@ -404,6 +421,7 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
root->non_recursive_path = lpath;
rrel = recurse_set_operations(setOp->rarg, root,
NULL, /* no value in sorted results */
+ false, /* ditto */
setOp->colTypes, setOp->colCollations,
refnames_tlist,
&rpath_tlist,
@@ -672,8 +690,8 @@ build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
Query *subquery = subroot->parse;
if (subquery->groupClause || subquery->groupingSets ||
- subquery->distinctClause || subroot->hasHavingQual ||
- subquery->hasAggs)
+ subroot->hasHavingQual || subquery->hasAggs ||
+ (subquery->distinctClause && !subroot->distinct_elided))
*pNumGroups = rel->cheapest_total_path->rows;
else
*pNumGroups = estimate_num_groups(subroot,
@@ -686,9 +704,12 @@ build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
/*
* Generate paths for a UNION or UNION ALL node
+ *
+ * dedup_above is as for recurse_set_operations.
*/
static RelOptInfo *
generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
+ bool dedup_above,
List *refnames_tlist,
List **pTargetList)
{
@@ -718,9 +739,14 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
* colTypes/colCollations) then they can be merged into this node so that
* we generate only one Append/MergeAppend and unique-ification for the
* lot. Recurse to find such nodes.
+ *
+ * A UNION deduplicates its children's outputs, so their own DISTINCTs
+ * are redundant; a UNION ALL preserves row membership, so any ancestor's
+ * dedup guarantee passes through unchanged.
*/
rellist = plan_union_children(root,
op,
+ op->all ? dedup_above : true,
refnames_tlist,
&tlist_list,
&trivial_tlist_list);
@@ -1039,9 +1065,12 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
/*
* Generate paths for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
+ *
+ * dedup_above is as for recurse_set_operations.
*/
static RelOptInfo *
generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
+ bool dedup_above,
List *refnames_tlist,
List **pTargetList)
{
@@ -1067,15 +1096,34 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
bool can_sort;
bool can_hash;
SetOpCmd cmd;
+ bool child_dedup_above;
/*
* Tell children to fetch all tuples.
*/
root->tuple_fraction = 0.0;
- /* Recurse on children */
+ /*
+ * Recurse on children. INTERSECT and EXCEPT deduplicate their children's
+ * outputs, so the children's own DISTINCTs are redundant. INTERSECT ALL
+ * changes its inputs' multiplicities (min(m,n) copies) but preserves row
+ * membership -- min(m,n) > 0 iff m > 0 and n > 0 -- so an ancestor's
+ * dedup guarantee passes through it unchanged, as for UNION ALL. EXCEPT
+ * ALL is truly multiplicity-sensitive: removing a DISTINCT below it can
+ * change which rows it emits at all (max(m-n,0) > 0 depends on m and n),
+ * not just how many copies, so it resets the flag for both children; see
+ * the regression tests.
+ */
+ if (!op->all)
+ child_dedup_above = true;
+ else if (op->op == SETOP_INTERSECT)
+ child_dedup_above = dedup_above;
+ else
+ child_dedup_above = false;
+
lrel = recurse_set_operations(op->larg, root,
op,
+ child_dedup_above,
op->colTypes, op->colCollations,
refnames_tlist,
&lpath_tlist,
@@ -1083,6 +1131,7 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
rrel = recurse_set_operations(op->rarg, root,
op,
+ child_dedup_above,
op->colTypes, op->colCollations,
refnames_tlist,
&rpath_tlist,
@@ -1388,10 +1437,14 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
*
* NOTE: we can also pull a UNION ALL up into a UNION, since the distinct
* output rows will be lost anyway.
+ *
+ * child_dedup_above is passed down unchanged to each child's
+ * recurse_set_operations call; see there.
*/
static List *
plan_union_children(PlannerInfo *root,
SetOperationStmt *top_union,
+ bool child_dedup_above,
List *refnames_tlist,
List **tlist_list,
List **istrivial_tlist)
@@ -1436,6 +1489,7 @@ plan_union_children(PlannerInfo *root,
*/
result = lappend(result, recurse_set_operations(setOp, root,
top_union->all ? NULL : top_union,
+ child_dedup_above,
top_union->colTypes,
top_union->colCollations,
refnames_tlist,
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 27a2c6815b7..944500e0e8f 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -639,6 +639,8 @@ struct PlannerInfo
bool placeholdersFrozen;
/* true if planning a recursive WITH item */
bool hasRecursion;
+ /* true if a DISTINCT clause's enforcement was skipped (see planner.c) */
+ bool distinct_elided;
/* true if a planner extension may replan this subquery */
bool assumeReplanning;
diff --git a/src/include/optimizer/planner.h b/src/include/optimizer/planner.h
index 9c4950b340f..3838048c496 100644
--- a/src/include/optimizer/planner.h
+++ b/src/include/optimizer/planner.h
@@ -65,7 +65,8 @@ extern PlannerInfo *subquery_planner(PlannerGlobal *glob, Query *parse,
PlannerInfo *parent_root,
PlannerInfo *alternative_root,
bool hasRecursion, double tuple_fraction,
- SetOperationStmt *setops);
+ SetOperationStmt *setops,
+ bool dedup_above);
extern RowMarkType select_rowmark_type(RangeTblEntry *rte,
LockClauseStrength strength);
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
index 84abcd6b14f..89bad01d273 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -1706,3 +1706,184 @@ join (select ten from tenk1 union select ten from onek) s on s.ten = t.unique1;
Index Cond: (unique1 = tenk1.ten)
(8 rows)
+-- Test removal of redundant branch-level DISTINCT beneath a set operation
+-- that already eliminates duplicates.
+-- All three non-ALL setops subsume the branches' DISTINCT
+explain (costs off)
+(select distinct four from tenk1) union (select distinct ten from tenk1);
+ QUERY PLAN
+---------------------------------------
+ HashAggregate
+ Group Key: tenk1.four
+ -> Append
+ -> Seq Scan on tenk1
+ -> Seq Scan on tenk1 tenk1_1
+(5 rows)
+
+explain (costs off)
+(select distinct four from tenk1) intersect (select distinct ten from tenk1);
+ QUERY PLAN
+---------------------------------
+ HashSetOp Intersect
+ -> Seq Scan on tenk1
+ -> Seq Scan on tenk1 tenk1_1
+(3 rows)
+
+explain (costs off)
+(select distinct four from tenk1) except (select distinct ten from tenk1);
+ QUERY PLAN
+---------------------------------
+ HashSetOp Except
+ -> Seq Scan on tenk1
+ -> Seq Scan on tenk1 tenk1_1
+(3 rows)
+
+-- UNION ALL does not subsume
+explain (costs off)
+(select distinct four from tenk1) union all (select distinct ten from tenk1);
+ QUERY PLAN
+---------------------------------------
+ Append
+ -> HashAggregate
+ Group Key: tenk1.four
+ -> Seq Scan on tenk1
+ -> HashAggregate
+ Group Key: tenk1_1.ten
+ -> Seq Scan on tenk1 tenk1_1
+(7 rows)
+
+-- ... but subsumption passes through UNION ALL to an outer UNION
+explain (costs off)
+((select distinct four from tenk1) union all (select distinct ten from tenk1))
+union (select 1);
+ QUERY PLAN
+---------------------------------------
+ HashAggregate
+ Group Key: tenk1.four
+ -> Append
+ -> Seq Scan on tenk1
+ -> Seq Scan on tenk1 tenk1_1
+ -> Result
+(6 rows)
+
+-- INTERSECT ALL changes multiplicities but not membership: no subsumption on
+-- its own, but an ancestor's dedup passes through it
+explain (costs off)
+(select distinct four from tenk1) intersect all (select ten from tenk1);
+ QUERY PLAN
+-------------------------------------
+ HashSetOp Intersect All
+ -> Sort
+ Sort Key: tenk1.four
+ -> HashAggregate
+ Group Key: tenk1.four
+ -> Seq Scan on tenk1
+ -> Seq Scan on tenk1 tenk1_1
+(7 rows)
+
+explain (costs off)
+((select distinct four from tenk1) intersect all (select ten from tenk1))
+union (select 1);
+ QUERY PLAN
+---------------------------------------------
+ HashAggregate
+ Group Key: tenk1.four
+ -> Append
+ -> HashSetOp Intersect All
+ -> Seq Scan on tenk1
+ -> Seq Scan on tenk1 tenk1_1
+ -> Result
+(7 rows)
+
+-- EXCEPT ALL is multiplicity-sensitive: no subsumption from any ancestor
+explain (costs off)
+((select distinct four from tenk1) except all (select ten from tenk1))
+union (select 1);
+ QUERY PLAN
+-------------------------------------------------------
+ Unique
+ -> Sort
+ Sort Key: tenk1.four
+ -> Append
+ -> HashSetOp Except All
+ -> Sort
+ Sort Key: tenk1.four
+ -> HashAggregate
+ Group Key: tenk1.four
+ -> Seq Scan on tenk1
+ -> Seq Scan on tenk1 tenk1_1
+ -> Result
+(12 rows)
+
+-- DISTINCT ON and LIMIT block elision
+explain (costs off)
+(select distinct on (four) four from tenk1) union (select ten from tenk1);
+ QUERY PLAN
+-------------------------------------------
+ HashAggregate
+ Group Key: tenk1.four
+ -> Append
+ -> Unique
+ -> Sort
+ Sort Key: tenk1.four
+ -> Seq Scan on tenk1
+ -> Seq Scan on tenk1 tenk1_1
+(8 rows)
+
+explain (costs off)
+(select distinct four from tenk1 limit 2) union (select ten from tenk1);
+ QUERY PLAN
+-------------------------------------------------
+ HashAggregate
+ Group Key: tenk1.four
+ -> Append
+ -> Sort
+ Sort Key: tenk1.four
+ -> Limit
+ -> HashAggregate
+ Group Key: tenk1.four
+ -> Seq Scan on tenk1
+ -> Seq Scan on tenk1 tenk1_1
+(10 rows)
+
+-- EXCEPT ALL membership counterexample: the DISTINCT below EXCEPT ALL is
+-- semantically significant even under an outer UNION
+create temp table ea_l(x int);
+create temp table ea_r(x int);
+insert into ea_l values (1),(1),(2);
+insert into ea_r values (1);
+select x from ((select distinct x from ea_l) except all (select x from ea_r)) s
+order by x;
+ x
+---
+ 2
+(1 row)
+
+-- ... whereas below INTERSECT ALL it is not: with or without the DISTINCT,
+-- the result's membership (and hence the outer UNION's output) is the same
+select x from
+ (((select distinct x from ea_l) intersect all (select x from ea_l))
+ union (select 7)) s
+order by x;
+ x
+---
+ 1
+ 2
+ 7
+(3 rows)
+
+-- results with/without redundant DISTINCT must agree
+select count(*) from
+ ((select distinct four from tenk1) union (select distinct ten from tenk1)) s;
+ count
+-------
+ 10
+(1 row)
+
+select count(*) from
+ ((select four from tenk1) union (select ten from tenk1)) s;
+ count
+-------
+ 10
+(1 row)
+
diff --git a/src/test/regress/sql/union.sql b/src/test/regress/sql/union.sql
index c8de276c2b5..c6e221e00e4 100644
--- a/src/test/regress/sql/union.sql
+++ b/src/test/regress/sql/union.sql
@@ -674,3 +674,55 @@ select null::int[] union all select null::int[] union all select null::bigint[];
explain (costs off)
select * from tenk1 t
join (select ten from tenk1 union select ten from onek) s on s.ten = t.unique1;
+
+-- Test removal of redundant branch-level DISTINCT beneath a set operation
+-- that already eliminates duplicates.
+-- All three non-ALL setops subsume the branches' DISTINCT
+explain (costs off)
+(select distinct four from tenk1) union (select distinct ten from tenk1);
+explain (costs off)
+(select distinct four from tenk1) intersect (select distinct ten from tenk1);
+explain (costs off)
+(select distinct four from tenk1) except (select distinct ten from tenk1);
+-- UNION ALL does not subsume
+explain (costs off)
+(select distinct four from tenk1) union all (select distinct ten from tenk1);
+-- ... but subsumption passes through UNION ALL to an outer UNION
+explain (costs off)
+((select distinct four from tenk1) union all (select distinct ten from tenk1))
+union (select 1);
+-- INTERSECT ALL changes multiplicities but not membership: no subsumption on
+-- its own, but an ancestor's dedup passes through it
+explain (costs off)
+(select distinct four from tenk1) intersect all (select ten from tenk1);
+explain (costs off)
+((select distinct four from tenk1) intersect all (select ten from tenk1))
+union (select 1);
+-- EXCEPT ALL is multiplicity-sensitive: no subsumption from any ancestor
+explain (costs off)
+((select distinct four from tenk1) except all (select ten from tenk1))
+union (select 1);
+-- DISTINCT ON and LIMIT block elision
+explain (costs off)
+(select distinct on (four) four from tenk1) union (select ten from tenk1);
+explain (costs off)
+(select distinct four from tenk1 limit 2) union (select ten from tenk1);
+-- EXCEPT ALL membership counterexample: the DISTINCT below EXCEPT ALL is
+-- semantically significant even under an outer UNION
+create temp table ea_l(x int);
+create temp table ea_r(x int);
+insert into ea_l values (1),(1),(2);
+insert into ea_r values (1);
+select x from ((select distinct x from ea_l) except all (select x from ea_r)) s
+order by x;
+-- ... whereas below INTERSECT ALL it is not: with or without the DISTINCT,
+-- the result's membership (and hence the outer UNION's output) is the same
+select x from
+ (((select distinct x from ea_l) intersect all (select x from ea_l))
+ union (select 7)) s
+order by x;
+-- results with/without redundant DISTINCT must agree
+select count(*) from
+ ((select distinct four from tenk1) union (select distinct ten from tenk1)) s;
+select count(*) from
+ ((select four from tenk1) union (select ten from tenk1)) s;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 66352a4a624..bee916b833c 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -208,6 +208,7 @@ static void create_one_window_path(PlannerInfo *root,
PathTarget *output_target,
WindowFuncLists *wflists,
List *activeWindows);
+static bool distinct_input_provably_unique(PlannerInfo *root);
static RelOptInfo *create_distinct_paths(PlannerInfo *root,
RelOptInfo *input_rel,
PathTarget *target);
@@ -2132,6 +2133,14 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
*/
root->distinct_elided = true;
}
+ else if (distinct_input_provably_unique(root))
+ {
+ /*
+ * The input is already distinct on the DISTINCT columns, so
+ * enforcement would be a no-op; skip building it.
+ */
+ root->distinct_elided = true;
+ }
else
current_rel = create_distinct_paths(root,
current_rel,
@@ -5067,6 +5076,79 @@ create_one_window_path(PlannerInfo *root,
add_path(window_rel, path);
}
+/*
+ * distinct_input_provably_unique
+ * Detect whether this query's DISTINCT clause is a no-op because its
+ * input is provably distinct on the DISTINCT columns already.
+ *
+ * We handle only the simple but common shape where the query reads exactly
+ * one subquery RTE (no joins -- joining can multiply rows) and every
+ * DISTINCT column is a plain Var of that subquery, and the subquery's own
+ * query structure (DISTINCT, GROUP BY, aggregation, non-ALL set operation)
+ * proves distinctness via query_is_distinct_for(). WHERE quals are fine:
+ * filtering cannot introduce duplicates. We derive distinctness only from
+ * the subquery's structure, never from catalog uniqueness metadata.
+ *
+ * We bail out on target SRFs (they multiply rows after the subquery scan),
+ * and conservatively on window functions, though those merely add columns.
+ * DISTINCT ON is out too: with more than one row per group it changes which
+ * rows survive, so proving groups of one would need all ON columns covered;
+ * we don't bother. The caller must not modify parse->distinctClause; on a
+ * true return it merely refrains from building enforcement paths.
+ */
+static bool
+distinct_input_provably_unique(PlannerInfo *root)
+{
+ Query *parse = root->parse;
+ RangeTblRef *rtr;
+ RangeTblEntry *rte;
+ List *distinct_cols = NIL;
+ ListCell *lc;
+
+ if (parse->hasDistinctOn)
+ return false;
+
+ /* bail out on anything that complicates the proof */
+ if (parse->hasTargetSRFs || parse->hasWindowFuncs || parse->hasAggs ||
+ parse->groupClause || parse->groupingSets || parse->havingQual)
+ return false;
+
+ /* the input must be exactly one subquery RTE */
+ if (list_length(parse->jointree->fromlist) != 1)
+ return false;
+ rtr = (RangeTblRef *) linitial(parse->jointree->fromlist);
+ if (!IsA(rtr, RangeTblRef))
+ return false;
+ rte = root->simple_rte_array[rtr->rtindex];
+ if (rte->rtekind != RTE_SUBQUERY)
+ return false;
+ if (!query_supports_distinctness(rte->subquery))
+ return false;
+
+ /* every DISTINCT column must be a plain Var of that subquery */
+ foreach(lc, root->processed_distinctClause)
+ {
+ SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
+ TargetEntry *tle = get_sortgroupclause_tle(sgc, root->processed_tlist);
+ Var *var = (Var *) tle->expr;
+ DistinctColInfo *info;
+
+ if (!IsA(var, Var) ||
+ var->varno != rtr->rtindex ||
+ var->varlevelsup != 0 ||
+ var->varattno <= 0)
+ return false;
+
+ info = palloc_object(DistinctColInfo);
+ info->colno = var->varattno;
+ info->opid = sgc->eqop;
+ info->collid = var->varcollid;
+ distinct_cols = lappend(distinct_cols, info);
+ }
+
+ return query_is_distinct_for(rte->subquery, distinct_cols);
+}
+
/*
* create_distinct_paths
*
diff --git a/src/test/regress/expected/select_distinct.out b/src/test/regress/expected/select_distinct.out
index 741f7238742..c90f5a2f796 100644
--- a/src/test/regress/expected/select_distinct.out
+++ b/src/test/regress/expected/select_distinct.out
@@ -596,3 +596,110 @@ SELECT DISTINCT y, x FROM distinct_tbl ORDER BY y;
RESET enable_hashagg;
DROP TABLE distinct_tbl;
+--
+-- Skip DISTINCT enforcement when the input is provably distinct already
+-- (structural proof via the input subquery's own DISTINCT/GROUP BY/setop).
+--
+-- elided: grouped subquery proves distinctness
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT four FROM (SELECT four FROM tenk1 GROUP BY four) ss;
+ QUERY PLAN
+-------------------------
+ HashAggregate
+ Group Key: tenk1.four
+ -> Seq Scan on tenk1
+(3 rows)
+
+-- elided: superset of the unique columns is still unique
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT four, c FROM
+ (SELECT four, count(*) AS c FROM tenk1 GROUP BY four) ss;
+ QUERY PLAN
+-------------------------
+ HashAggregate
+ Group Key: tenk1.four
+ -> Seq Scan on tenk1
+(3 rows)
+
+-- elided: aggregate without GROUP BY returns one row
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT c FROM (SELECT count(*) AS c FROM tenk1) ss;
+ QUERY PLAN
+----------------------------------------------------
+ Aggregate
+ -> Index Only Scan using tenk1_hundred on tenk1
+(2 rows)
+
+-- elided: non-ALL setop output is unique; WHERE cannot break uniqueness
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT x FROM
+ (SELECT four AS x FROM tenk1 UNION SELECT ten FROM tenk1) ss WHERE x > 2;
+ QUERY PLAN
+---------------------------------------
+ HashAggregate
+ Group Key: tenk1.four
+ -> Append
+ -> Seq Scan on tenk1
+ Filter: (four > 2)
+ -> Seq Scan on tenk1 tenk1_1
+ Filter: (ten > 2)
+(7 rows)
+
+-- not elided: subset of output that isn't the unique key
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT c FROM
+ (SELECT four, count(*) AS c FROM tenk1 GROUP BY four) ss;
+ QUERY PLAN
+-------------------------------------------
+ Unique
+ -> Sort
+ Sort Key: ss.c
+ -> Subquery Scan on ss
+ -> HashAggregate
+ Group Key: tenk1.four
+ -> Seq Scan on tenk1
+(7 rows)
+
+-- not elided: joining two unique subqueries can duplicate rows
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT a.four FROM
+ (SELECT four FROM tenk1 GROUP BY four) a,
+ (SELECT ten FROM tenk1 GROUP BY ten) b;
+ QUERY PLAN
+---------------------------------------------------------
+ Unique
+ -> Sort
+ Sort Key: tenk1_1.four
+ -> Nested Loop
+ -> HashAggregate
+ Group Key: tenk1.ten
+ -> Seq Scan on tenk1
+ -> Materialize
+ -> HashAggregate
+ Group Key: tenk1_1.four
+ -> Seq Scan on tenk1 tenk1_1
+(11 rows)
+
+-- not elided: UNION ALL proves nothing
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT x FROM
+ (SELECT four AS x FROM tenk1 UNION ALL SELECT ten FROM tenk1) ss;
+ QUERY PLAN
+---------------------------------------
+ HashAggregate
+ Group Key: tenk1.four
+ -> Append
+ -> Seq Scan on tenk1
+ -> Seq Scan on tenk1 tenk1_1
+(5 rows)
+
+-- results sanity
+SELECT DISTINCT four FROM (SELECT four FROM tenk1 GROUP BY four) ss ORDER BY 1;
+ four
+------
+ 0
+ 1
+ 2
+ 3
+(4 rows)
+
diff --git a/src/test/regress/sql/select_distinct.sql b/src/test/regress/sql/select_distinct.sql
index 2ed1616b098..773b1695436 100644
--- a/src/test/regress/sql/select_distinct.sql
+++ b/src/test/regress/sql/select_distinct.sql
@@ -274,3 +274,37 @@ SELECT DISTINCT y, x FROM distinct_tbl ORDER BY y;
RESET enable_hashagg;
DROP TABLE distinct_tbl;
+
+--
+-- Skip DISTINCT enforcement when the input is provably distinct already
+-- (structural proof via the input subquery's own DISTINCT/GROUP BY/setop).
+--
+-- elided: grouped subquery proves distinctness
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT four FROM (SELECT four FROM tenk1 GROUP BY four) ss;
+-- elided: superset of the unique columns is still unique
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT four, c FROM
+ (SELECT four, count(*) AS c FROM tenk1 GROUP BY four) ss;
+-- elided: aggregate without GROUP BY returns one row
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT c FROM (SELECT count(*) AS c FROM tenk1) ss;
+-- elided: non-ALL setop output is unique; WHERE cannot break uniqueness
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT x FROM
+ (SELECT four AS x FROM tenk1 UNION SELECT ten FROM tenk1) ss WHERE x > 2;
+-- not elided: subset of output that isn't the unique key
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT c FROM
+ (SELECT four, count(*) AS c FROM tenk1 GROUP BY four) ss;
+-- not elided: joining two unique subqueries can duplicate rows
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT a.four FROM
+ (SELECT four FROM tenk1 GROUP BY four) a,
+ (SELECT ten FROM tenk1 GROUP BY ten) b;
+-- not elided: UNION ALL proves nothing
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT x FROM
+ (SELECT four AS x FROM tenk1 UNION ALL SELECT ten FROM tenk1) ss;
+-- results sanity
+SELECT DISTINCT four FROM (SELECT four FROM tenk1 GROUP BY four) ss ORDER BY 1;
