v2-0004-Fix-bogus-decisions-about-whether-we-want-pre-sor.patch

From 7ec25e0de0810a0130914ed6f691049859d4917c Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Tue, 19 Nov 2024 20:51:54 -0500
Subject: [PATCH v2 4/5] Fix bogus decisions about whether we want pre-sorted
 child paths.

As things stand, recurse_set_operations unconditionally passes down
root->parse->setOperations to subquery_planner, which then applies
set_operation_ordered_results_useful to it to decide whether we care
about producing pre-sorted paths for the subquery.

This is flat wrong.

The main problem is that root->parse->setOperations is not necessarily
the relevant ancestor node.  In the test case added here, we have
UNION ALL atop a child UNION, and the existing logic fails to
recognize that it could use pre-sorted paths for the child UNION step.

A lesser problem is that set_operation_ordered_results_useful is
inadequate anyway: it will falsely claim that we could use pre-sorted
paths for a recursive UNION.

A better way to do this is for each caller of recurse_set_operations
to pass down the relevant parent node.  Then we can further specify
that the caller should pass NULL if it has no use for pre-sorted
paths, and then we can get rid of set_operation_ordered_results_useful
altogether, eliminating the need to keep it in sync with the code that
is actually doing the work.

Note: this patch makes generate_nonunion_paths pass down the non-UNION
node as parent.  generate_nonunion_paths doesn't yet do anything with
the pre-sorted paths that will result, so no regression test plans
change.  If we were going to leave it like this, we'd pass down NULL
instead.
---
 src/backend/optimizer/plan/planner.c   |  7 ++-
 src/backend/optimizer/prep/prepunion.c | 65 +++++++++++++-------------
 src/include/optimizer/prep.h           |  1 -
 src/test/regress/expected/union.out    | 14 ++++++
 src/test/regress/sql/union.sql         |  4 ++
 5 files changed, 54 insertions(+), 37 deletions(-)

diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 1f78dc3d53..df168d46ac 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -608,7 +608,7 @@ standard_planner(Query *parse, const char *query_string, int cursorOptions,
  * setops is used for set operation subqueries to provide the subquery with
  * 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.
+ * child, or when a child of a set op that isn't interested in sorted input.
  *
  * Basically, this routine does the stuff that should only be done once
  * per Query object.  It then calls grouping_planner.  At one time,
@@ -1342,7 +1342,7 @@ preprocess_phv_expression(PlannerInfo *root, Expr *expr)
  * setops is used for set operation subqueries to provide the subquery with
  * 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.
+ * child, or when a child of a set op that isn't interested in sorted input.
  *
  * Returns nothing; the useful output is in the Paths we attach to the
  * (UPPERREL_FINAL, NULL) upperrel in *root.  In addition,
@@ -3621,8 +3621,7 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 									  tlist);
 
 	/* setting setop_pathkeys might be useful to the union planner */
-	if (qp_extra->setop != NULL &&
-		set_operation_ordered_results_useful(qp_extra->setop))
+	if (qp_extra->setop != NULL)
 	{
 		List	   *groupClauses;
 		bool		sortable;
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 21513dbb19..e92a088334 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -39,6 +39,7 @@
 
 
 static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
+										  SetOperationStmt *parentOp,
 										  List *colTypes, List *colCollations,
 										  List *refnames_tlist,
 										  List **pTargetList,
@@ -156,6 +157,7 @@ plan_set_operations(PlannerInfo *root)
 		 * output from the top-level node.
 		 */
 		setop_rel = recurse_set_operations((Node *) topop, root,
+										   NULL,	/* no parent */
 										   topop->colTypes, topop->colCollations,
 										   leftmostQuery->targetList,
 										   &top_tlist,
@@ -168,44 +170,31 @@ plan_set_operations(PlannerInfo *root)
 	return setop_rel;
 }
 
-/*
- * set_operation_ordered_results_useful
- *		Return true if the given SetOperationStmt can be executed by utilizing
- *		paths that provide sorted input according to the setop's targetlist.
- *		Returns false when sorted paths are not any more useful then unsorted
- *		ones.
- */
-bool
-set_operation_ordered_results_useful(SetOperationStmt *setop)
-{
-	/*
-	 * Paths sorted by the targetlist are useful for UNION as we can opt to
-	 * MergeAppend the sorted paths then Unique them.  Ordered paths are no
-	 * more useful than unordered ones for UNION ALL.
-	 */
-	if (!setop->all && setop->op == SETOP_UNION)
-		return true;
-
-	/*
-	 * EXCEPT / EXCEPT ALL / INTERSECT / INTERSECT ALL cannot yet utilize
-	 * correctly sorted input paths.
-	 */
-	return false;
-}
-
 /*
  * recurse_set_operations
  *	  Recursively handle one step in a tree of set operations
  *
+ * setOp: current step (could be a SetOperationStmt or a leaf RangeTblRef)
+ * parentOp: parent step, or NULL if none (but see below)
  * colTypes: OID list of set-op's result column datatypes
  * colCollations: OID list of set-op's result column collations
  * refnames_tlist: targetlist to take column names from
  *
+ * parentOp should be passed as NULL unless that step is interested in
+ * getting sorted output from this step.  ("Sorted" means "sorted according
+ * to the default btree opclasses of the result column datatypes".)
+ *
  * 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
  * match.
  *
+ * If setOp is a leaf node, this function plans the sub-query but does
+ * not populate the pathlist of the returned RelOptInfo.  The caller will
+ * generate SubqueryScan paths using useful path(s) of the subquery (see
+ * build_setop_child_paths).  But this function does build the paths for
+ * set-operation nodes.
+ *
  * The pTargetList output parameter is mostly redundant with the pathtarget
  * of the returned RelOptInfo, but for the moment we need it because much of
  * the logic in this file depends on flag columns being marked resjunk.
@@ -218,6 +207,7 @@ set_operation_ordered_results_useful(SetOperationStmt *setop)
  */
 static RelOptInfo *
 recurse_set_operations(Node *setOp, PlannerInfo *root,
+					   SetOperationStmt *parentOp,
 					   List *colTypes, List *colCollations,
 					   List *refnames_tlist,
 					   List **pTargetList,
@@ -234,7 +224,6 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 	{
 		RangeTblRef *rtr = (RangeTblRef *) setOp;
 		RangeTblEntry *rte = root->simple_rte_array[rtr->rtindex];
-		SetOperationStmt *setops;
 		Query	   *subquery = rte->subquery;
 		PlannerInfo *subroot;
 		List	   *tlist;
@@ -249,15 +238,13 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		Assert(root->plan_params == NIL);
 
 		/*
-		 * Pass the set operation details to the subquery_planner to have it
-		 * consider generating Paths correctly ordered for the set operation.
+		 * Generate a subroot and Paths for the subquery.  If we have a
+		 * parentOp, pass that down to encourage subquery_planner to consider
+		 * suitably-sorted Paths.
 		 */
-		setops = castNode(SetOperationStmt, root->parse->setOperations);
-
-		/* Generate a subroot and Paths for the subquery */
 		subroot = rel->subroot = subquery_planner(root->glob, subquery, root,
 												  false, root->tuple_fraction,
-												  setops);
+												  parentOp);
 
 		/*
 		 * It should not be possible for the primitive query to contain any
@@ -396,6 +383,7 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	 * separately without any intention of combining them into one Append.
 	 */
 	lrel = recurse_set_operations(setOp->larg, root,
+								  NULL, /* no value in sorted results */
 								  setOp->colTypes, setOp->colCollations,
 								  refnames_tlist,
 								  &lpath_tlist,
@@ -407,6 +395,7 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	/* The right path will want to look at the left one ... */
 	root->non_recursive_path = lpath;
 	rrel = recurse_set_operations(setOp->rarg, root,
+								  NULL, /* no value in sorted results */
 								  setOp->colTypes, setOp->colCollations,
 								  refnames_tlist,
 								  &rpath_tlist,
@@ -479,6 +468,10 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
  * build_setop_child_paths
  *		Build paths for the set op child relation denoted by 'rel'.
  *
+ * 'rel' is an RTE_SUBQUERY relation.  We have already generated paths within
+ * the subquery's subroot; the task here is to create SubqueryScan paths for
+ * 'rel', representing scans of the useful subquery paths.
+ *
  * interesting_pathkeys: if not NIL, also include paths that suit these
  * pathkeys, sorting any unsorted paths as required.
  * *pNumGroups: if not NULL, we estimate the number of distinct groups
@@ -1032,6 +1025,7 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
 
 	/* Recurse on children */
 	lrel = recurse_set_operations(op->larg, root,
+								  op,
 								  op->colTypes, op->colCollations,
 								  refnames_tlist,
 								  &lpath_tlist,
@@ -1043,6 +1037,7 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
 		dLeftGroups = lrel->rows;
 
 	rrel = recurse_set_operations(op->rarg, root,
+								  op,
 								  op->colTypes, op->colCollations,
 								  refnames_tlist,
 								  &rpath_tlist,
@@ -1285,8 +1280,14 @@ plan_union_children(PlannerInfo *root,
 
 		/*
 		 * Not same, so plan this child separately.
+		 *
+		 * If top_union isn't a UNION ALL, then we are interested in sorted
+		 * output from the child, so pass top_union as parentOp.  Note that
+		 * this isn't necessarily the child node's immediate SetOperationStmt
+		 * parent, but that's fine: it's the effective parent.
 		 */
 		result = lappend(result, recurse_set_operations(setOp, root,
+														top_union->all ? NULL : top_union,
 														top_union->colTypes,
 														top_union->colCollations,
 														refnames_tlist,
diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h
index a52dec285d..74bb6c1d3b 100644
--- a/src/include/optimizer/prep.h
+++ b/src/include/optimizer/prep.h
@@ -53,6 +53,5 @@ extern void preprocess_aggrefs(PlannerInfo *root, Node *clause);
  * prototypes for prepunion.c
  */
 extern RelOptInfo *plan_set_operations(PlannerInfo *root);
-extern bool set_operation_ordered_results_useful(SetOperationStmt *setop);
 
 #endif							/* PREP_H */
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
index 9474b01510..3e1adbd992 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -466,6 +466,20 @@ select unique1 from tenk1 except select unique2 from tenk1 where unique2 != 10;
       10
 (1 row)
 
+explain (costs off)
+select f1 from int4_tbl union all
+  (select unique1 from tenk1 union select unique2 from tenk1);
+                               QUERY PLAN                               
+------------------------------------------------------------------------
+ Append
+   ->  Seq Scan on int4_tbl
+   ->  Unique
+         ->  Merge Append
+               Sort Key: tenk1.unique1
+               ->  Index Only Scan using tenk1_unique1 on tenk1
+               ->  Index Only Scan using tenk1_unique2 on tenk1 tenk1_1
+(7 rows)
+
 reset enable_hashagg;
 -- non-hashable type
 set enable_hashagg to on;
diff --git a/src/test/regress/sql/union.sql b/src/test/regress/sql/union.sql
index f8826514e4..10030ec1c5 100644
--- a/src/test/regress/sql/union.sql
+++ b/src/test/regress/sql/union.sql
@@ -156,6 +156,10 @@ explain (costs off)
 select unique1 from tenk1 except select unique2 from tenk1 where unique2 != 10;
 select unique1 from tenk1 except select unique2 from tenk1 where unique2 != 10;
 
+explain (costs off)
+select f1 from int4_tbl union all
+  (select unique1 from tenk1 union select unique2 from tenk1);
+
 reset enable_hashagg;
 
 -- non-hashable type
-- 
2.43.5