Properly pathify the union planner

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 22cae37a1e..51e6dd028c 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -11194,6 +11194,11 @@ DROP INDEX base_tbl1_idx;
 DROP INDEX base_tbl2_idx;
 DROP INDEX async_p3_idx;
 -- UNION queries
+SET enable_sort TO off;
+SET enable_incremental_sort TO off;
+-- Adjust fdw_startup_cost so that we get an unordered path in the Append.
+-- XXX or is it better to just accept the plan change?
+ALTER SERVER loopback2 OPTIONS (ADD fdw_startup_cost '0.00');
 EXPLAIN (VERBOSE, COSTS OFF)
 INSERT INTO result_tbl
 (SELECT a, b, 'AAA' || c FROM async_p1 ORDER BY a LIMIT 10)
@@ -11275,6 +11280,9 @@ SELECT * FROM result_tbl ORDER BY a;
 (12 rows)
 
 DELETE FROM result_tbl;
+RESET enable_incremental_sort;
+RESET enable_sort;
+ALTER SERVER loopback2 OPTIONS (DROP fdw_startup_cost);
 -- Disable async execution if we use gating Result nodes for pseudoconstant
 -- quals
 EXPLAIN (VERBOSE, COSTS OFF)
diff --git a/contrib/postgres_fdw/sql/postgres_fdw.sql b/contrib/postgres_fdw/sql/postgres_fdw.sql
index 075da4ff86..e638402e16 100644
--- a/contrib/postgres_fdw/sql/postgres_fdw.sql
+++ b/contrib/postgres_fdw/sql/postgres_fdw.sql
@@ -3733,6 +3733,12 @@ DROP INDEX base_tbl2_idx;
 DROP INDEX async_p3_idx;
 
 -- UNION queries
+SET enable_sort TO off;
+SET enable_incremental_sort TO off;
+-- Adjust fdw_startup_cost so that we get an unordered path in the Append.
+-- XXX or is it better to just accept the plan change?
+ALTER SERVER loopback2 OPTIONS (ADD fdw_startup_cost '0.00');
+
 EXPLAIN (VERBOSE, COSTS OFF)
 INSERT INTO result_tbl
 (SELECT a, b, 'AAA' || c FROM async_p1 ORDER BY a LIMIT 10)
@@ -3759,6 +3765,10 @@ UNION ALL
 SELECT * FROM result_tbl ORDER BY a;
 DELETE FROM result_tbl;
 
+RESET enable_incremental_sort;
+RESET enable_sort;
+ALTER SERVER loopback2 OPTIONS (DROP fdw_startup_cost);
+
 -- Disable async execution if we use gating Result nodes for pseudoconstant
 -- quals
 EXPLAIN (VERBOSE, COSTS OFF)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 7fa502d6e2..740c0c530d 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -2856,6 +2856,55 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 	MemoryContextSwitchTo(oldcontext);
 }
 
+/*
+ * add_setop_child_rel_equivalences
+ *		Add equivalence members for each non-resjunk target in 'child_tlist'
+ *		to the EquivalenceClass in the corresponding setop_pathkey's pk_class.
+ *
+ * 'root' is the PlannerInfo belonging to the top-level set operation.
+ * 'child_relids' are the Relids of the child relation we're adding
+ * EquivalenceMembers for.
+ * 'child_tlist' is the target list for the setop child relation.  The target
+ * list expressions are what we add as EquivalenceMembers.
+ * 'setop_pathkeys' is a list of PathKeys which must contain an entry for each
+ * non-resjunk target in 'child_tlist'.
+ */
+void
+add_setop_child_rel_equivalences(PlannerInfo *root, Relids child_relids,
+								 List *child_tlist, List *setop_pathkeys)
+{
+	ListCell   *lc;
+	ListCell   *lc2 = list_head(setop_pathkeys);
+
+	foreach(lc, child_tlist)
+	{
+		TargetEntry *tle = lfirst_node(TargetEntry, lc);
+		PathKey    *pk;
+
+		if (tle->resjunk)
+			continue;
+
+		if (lc2 == NULL)
+			elog(ERROR, "too few pathkeys for set operation");
+
+		pk = lfirst_node(PathKey, lc2);
+
+		/*
+		 * We can safely pass the parent member as the first member in the
+		 * members list as this is added first in build_setop_pathkeys. XXX,
+		 * yeah but is that a good assumption to make?
+		 */
+		add_eq_member(pk->pk_eclass,
+					  tle->expr,
+					  child_relids,
+					  NULL,		/* XXX need to fake up a join domain? */
+					  linitial(pk->pk_eclass->ec_members),
+					  exprType((Node *) tle->expr));
+
+		lc2 = lnext(setop_pathkeys, lc2);
+	}
+}
+
 
 /*
  * generate_implied_equalities_for_column
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index fdb60aaa8d..bb6278fff4 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -786,6 +786,71 @@ build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
 	return retval;
 }
 
+/*
+ * build_setop_pathkeys
+ *	  Build and return a list of PathKeys, one for each non-junk target in
+ *	  'tlist'.
+ */
+List *
+build_setop_pathkeys(PlannerInfo *root, SetOperationStmt *op,
+					 Relids relids, List *tlist)
+{
+	ListCell   *lc;
+	ListCell   *sgccell = list_head(op->groupClauses);
+	List	   *retval = NIL;
+
+	foreach(lc, tlist)
+	{
+		TargetEntry *tle = lfirst_node(TargetEntry, lc);
+		SortGroupClause *sgc;
+
+		Oid			opfamily;
+		Oid			opcintype;
+		int16		strategy;
+		PathKey    *cpathkey;
+
+		if (tle->resjunk)
+			continue;
+
+		/*
+		 * XXX query_is_distinct_for() is happy to Assert this, should this do
+		 * that rather than ERROR?
+		 */
+		if (sgccell == NULL)
+			elog(ERROR, "too few group clauses");
+
+		sgc = lfirst_node(SortGroupClause, sgccell);
+
+		/* Find the operator in pg_amop --- failure shouldn't happen */
+		if (!get_ordering_op_properties(sgc->sortop,
+										&opfamily, &opcintype, &strategy))
+			elog(ERROR, "operator %u is not a valid ordering operator",
+				 sgc->eqop);
+
+		cpathkey = make_pathkey_from_sortinfo(root,
+											  tle->expr,
+											  opfamily,
+											  opcintype,
+											  exprCollation((Node *) tle->expr),
+											  false,
+											  sgc->nulls_first,
+											  0,
+											  relids,
+											  true);
+		retval = lappend(retval, cpathkey);
+		sgccell = lnext(op->groupClauses, sgccell);
+
+		/*
+		 * There's no need to look for redundant pathkeys as set operations
+		 * have no ability to have non-child constants in an EquivalenceClass.
+		 * Let's just make sure that remains true.
+		 */
+		Assert(!EC_MUST_BE_REDUNDANT(cpathkey->pk_eclass));
+	}
+
+	return retval;
+}
+
 /*
  * build_expression_pathkey
  *	  Build a pathkeys list that describes an ordering by a single expression
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index a8cea5efe1..479110bed4 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -126,12 +126,16 @@ typedef struct
 {
 	List	   *activeWindows;	/* active windows, if any */
 	grouping_sets_data *gset_data;	/* grouping sets data, if any */
+	SetOperationStmt *setop;	/* parent set operation or NULL if not a
+								 * subquery belonging to a set operation */
 } standard_qp_extra;
 
 /* Local functions */
 static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind);
 static void preprocess_qual_conditions(PlannerInfo *root, Node *jtnode);
 static void grouping_planner(PlannerInfo *root, double tuple_fraction);
+static Path *build_final_modify_table_path(PlannerInfo *root,
+										   RelOptInfo *final_rel, Path *path);
 static grouping_sets_data *preprocess_grouping_sets(PlannerInfo *root);
 static List *remap_to_groupclause_idx(List *groupClause, List *gsets,
 									  int *tleref_to_colnum_map);
@@ -1505,6 +1509,18 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 		qp_extra.activeWindows = activeWindows;
 		qp_extra.gset_data = gset_data;
 
+		/*
+		 * Check if we're a subquery for a set operation.  If we are, store
+		 * the SetOperationStmt in qp_extra.
+		 */
+		if (root->parent_root != NULL &&
+			root->parent_root->parse->setOperations != NULL &&
+			IsA(root->parent_root->parse->setOperations, SetOperationStmt))
+			qp_extra.setop =
+				(SetOperationStmt *) root->parent_root->parse->setOperations;
+		else
+			qp_extra.setop = NULL;
+
 		/*
 		 * Generate the best unsorted and presorted paths for the scan/join
 		 * portion of this Query, ie the processing represented by the
@@ -1753,6 +1769,13 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 	foreach(lc, current_rel->pathlist)
 	{
 		Path	   *path = (Path *) lfirst(lc);
+		Path	   *input_path;
+
+		/*
+		 * Keep record of the unmodified path so that we can still tell which
+		 * one is the cheapest_input_path.
+		 */
+		input_path = path;
 
 		/*
 		 * If there is a FOR [KEY] UPDATE/SHARE clause, add the LockRows node.
@@ -1781,191 +1804,86 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 		}
 
 		/*
-		 * If this is an INSERT/UPDATE/DELETE/MERGE, add the ModifyTable node.
+		 * Create paths to suit final sort order required for setop_pathkeys.
+		 * Here we'll sort the cheapest input path (if not sorted already) and
+		 * incremental sort any paths which are partially sorted.  We also
+		 * include the cheapest path as-is so that the set operation can be
+		 * cheaply implemented using a method which does not require the input
+		 * to be sorted.
 		 */
-		if (parse->commandType != CMD_SELECT)
+		if (root->setop_pathkeys != NIL)
 		{
-			Index		rootRelation;
-			List	   *resultRelations = NIL;
-			List	   *updateColnosLists = NIL;
-			List	   *withCheckOptionLists = NIL;
-			List	   *returningLists = NIL;
-			List	   *mergeActionLists = NIL;
-			List	   *rowMarks;
-
-			if (bms_membership(root->all_result_relids) == BMS_MULTIPLE)
-			{
-				/* Inherited UPDATE/DELETE/MERGE */
-				RelOptInfo *top_result_rel = find_base_rel(root,
-														   parse->resultRelation);
-				int			resultRelation = -1;
+			Path	   *cheapest_input_path = current_rel->cheapest_total_path;
+			bool		is_sorted;
+			int			presorted_keys;
 
-				/* Pass the root result rel forward to the executor. */
-				rootRelation = parse->resultRelation;
+			is_sorted = pathkeys_count_contained_in(root->setop_pathkeys,
+													path->pathkeys,
+													&presorted_keys);
 
-				/* Add only leaf children to ModifyTable. */
-				while ((resultRelation = bms_next_member(root->leaf_result_relids,
-														 resultRelation)) >= 0)
+			if (!is_sorted)
+			{
+				/*
+				 * Try at least sorting the cheapest path and also try
+				 * incrementally sorting any path which is partially sorted
+				 * already (no need to deal with paths which have presorted
+				 * keys when incremental sort is disabled unless it's the
+				 * cheapest input path).
+				 */
+				if (input_path != cheapest_input_path)
 				{
-					RelOptInfo *this_result_rel = find_base_rel(root,
-																resultRelation);
-
-					/*
-					 * Also exclude any leaf rels that have turned dummy since
-					 * being added to the list, for example, by being excluded
-					 * by constraint exclusion.
-					 */
-					if (IS_DUMMY_REL(this_result_rel))
+					if (presorted_keys == 0 || !enable_incremental_sort)
 						continue;
-
-					/* Build per-target-rel lists needed by ModifyTable */
-					resultRelations = lappend_int(resultRelations,
-												  resultRelation);
-					if (parse->commandType == CMD_UPDATE)
-					{
-						List	   *update_colnos = root->update_colnos;
-
-						if (this_result_rel != top_result_rel)
-							update_colnos =
-								adjust_inherited_attnums_multilevel(root,
-																	update_colnos,
-																	this_result_rel->relid,
-																	top_result_rel->relid);
-						updateColnosLists = lappend(updateColnosLists,
-													update_colnos);
-					}
-					if (parse->withCheckOptions)
-					{
-						List	   *withCheckOptions = parse->withCheckOptions;
-
-						if (this_result_rel != top_result_rel)
-							withCheckOptions = (List *)
-								adjust_appendrel_attrs_multilevel(root,
-																  (Node *) withCheckOptions,
-																  this_result_rel,
-																  top_result_rel);
-						withCheckOptionLists = lappend(withCheckOptionLists,
-													   withCheckOptions);
-					}
-					if (parse->returningList)
-					{
-						List	   *returningList = parse->returningList;
-
-						if (this_result_rel != top_result_rel)
-							returningList = (List *)
-								adjust_appendrel_attrs_multilevel(root,
-																  (Node *) returningList,
-																  this_result_rel,
-																  top_result_rel);
-						returningLists = lappend(returningLists,
-												 returningList);
-					}
-					if (parse->mergeActionList)
-					{
-						ListCell   *l;
-						List	   *mergeActionList = NIL;
-
-						/*
-						 * Copy MergeActions and translate stuff that
-						 * references attribute numbers.
-						 */
-						foreach(l, parse->mergeActionList)
-						{
-							MergeAction *action = lfirst(l),
-									   *leaf_action = copyObject(action);
-
-							leaf_action->qual =
-								adjust_appendrel_attrs_multilevel(root,
-																  (Node *) action->qual,
-																  this_result_rel,
-																  top_result_rel);
-							leaf_action->targetList = (List *)
-								adjust_appendrel_attrs_multilevel(root,
-																  (Node *) action->targetList,
-																  this_result_rel,
-																  top_result_rel);
-							if (leaf_action->commandType == CMD_UPDATE)
-								leaf_action->updateColnos =
-									adjust_inherited_attnums_multilevel(root,
-																		action->updateColnos,
-																		this_result_rel->relid,
-																		top_result_rel->relid);
-							mergeActionList = lappend(mergeActionList,
-													  leaf_action);
-						}
-
-						mergeActionLists = lappend(mergeActionLists,
-												   mergeActionList);
-					}
 				}
-
-				if (resultRelations == NIL)
+				else
 				{
 					/*
-					 * We managed to exclude every child rel, so generate a
-					 * dummy one-relation plan using info for the top target
-					 * rel (even though that may not be a leaf target).
-					 * Although it's clear that no data will be updated or
-					 * deleted, we still need to have a ModifyTable node so
-					 * that any statement triggers will be executed.  (This
-					 * could be cleaner if we fixed nodeModifyTable.c to allow
-					 * zero target relations, but that probably wouldn't be a
-					 * net win.)
+					 * If this is an INSERT/UPDATE/DELETE/MERGE, add a
+					 * ModifyTable path.
 					 */
-					resultRelations = list_make1_int(parse->resultRelation);
-					if (parse->commandType == CMD_UPDATE)
-						updateColnosLists = list_make1(root->update_colnos);
-					if (parse->withCheckOptions)
-						withCheckOptionLists = list_make1(parse->withCheckOptions);
-					if (parse->returningList)
-						returningLists = list_make1(parse->returningList);
-					if (parse->mergeActionList)
-						mergeActionLists = list_make1(parse->mergeActionList);
-				}
-			}
-			else
-			{
-				/* Single-relation INSERT/UPDATE/DELETE/MERGE. */
-				rootRelation = 0;	/* there's no separate root rel */
-				resultRelations = list_make1_int(parse->resultRelation);
-				if (parse->commandType == CMD_UPDATE)
-					updateColnosLists = list_make1(root->update_colnos);
-				if (parse->withCheckOptions)
-					withCheckOptionLists = list_make1(parse->withCheckOptions);
-				if (parse->returningList)
-					returningLists = list_make1(parse->returningList);
-				if (parse->mergeActionList)
-					mergeActionLists = list_make1(parse->mergeActionList);
-			}
+					if (parse->commandType != CMD_SELECT)
+						path = build_final_modify_table_path(root,
+															 final_rel,
+															 path);
 
-			/*
-			 * If there was a FOR [KEY] UPDATE/SHARE clause, the LockRows node
-			 * will have dealt with fetching non-locked marked rows, else we
-			 * need to have ModifyTable do that.
-			 */
-			if (parse->rowMarks)
-				rowMarks = NIL;
-			else
-				rowMarks = root->rowMarks;
+					/*
+					 * The union planner might want to try a hash-based method
+					 * of executing the set operation, so let's provide the
+					 * cheapest input path so that it can do that as cheaply
+					 * as possible.  If the cheapest_input_path happens to be
+					 * already correctly sorted then we'll add it to final_rel
+					 * at the end of the loop.
+					 */
+					add_path(final_rel, path);
+				}
 
-			path = (Path *)
-				create_modifytable_path(root, final_rel,
-										path,
-										parse->commandType,
-										parse->canSetTag,
-										parse->resultRelation,
-										rootRelation,
-										root->partColsUpdated,
-										resultRelations,
-										updateColnosLists,
-										withCheckOptionLists,
-										returningLists,
-										rowMarks,
-										parse->onConflict,
-										mergeActionLists,
-										assign_special_exec_param(root));
+				/*
+				 * We've no need to consider both a sort and incremental sort.
+				 * We'll just do a sort if there are no presorted keys and an
+				 * incremental sort when there are presorted keys.
+				 */
+				if (presorted_keys == 0 || !enable_incremental_sort)
+					path = (Path *) create_sort_path(root,
+													 final_rel,
+													 path,
+													 root->setop_pathkeys,
+													 limit_tuples);
+				else
+					path = (Path *) create_incremental_sort_path(root,
+																 final_rel,
+																 path,
+																 root->setop_pathkeys,
+																 presorted_keys,
+																 limit_tuples);
+			}
 		}
 
+		/*
+		 * If this is an INSERT/UPDATE/DELETE/MERGE, add a ModifyTable path.
+		 */
+		if (parse->commandType != CMD_SELECT)
+			path = build_final_modify_table_path(root, final_rel, path);
+
 		/* And shove it into final_rel */
 		add_path(final_rel, path);
 	}
@@ -1978,12 +1896,125 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 		!limit_needed(parse))
 	{
 		Assert(!parse->rowMarks && parse->commandType == CMD_SELECT);
+
+		/*
+		 * XXX adding all of these seems excessive. Why not just the cheapest?
+		 */
 		foreach(lc, current_rel->partial_pathlist)
 		{
 			Path	   *partial_path = (Path *) lfirst(lc);
 
 			add_partial_path(final_rel, partial_path);
 		}
+
+		/*
+		 * When planning for set operations, try sorting the cheapest partial
+		 * path.
+		 */
+		if (root->setop_pathkeys != NIL &&
+			current_rel->partial_pathlist != NIL)
+		{
+			Path	   *cheapest_partial_path;
+
+			cheapest_partial_path = linitial(current_rel->partial_pathlist);
+
+			/*
+			 * If cheapest partial path doesn't need a sort, this is redundant
+			 * with what's already been tried.
+			 */
+			if (!pathkeys_contained_in(root->setop_pathkeys,
+									   cheapest_partial_path->pathkeys))
+			{
+				Path	   *path;
+				double		total_groups;
+
+				path = (Path *) create_sort_path(root,
+												 final_rel,
+												 cheapest_partial_path,
+												 root->setop_pathkeys,
+												 limit_tuples);
+
+				total_groups = cheapest_partial_path->rows *
+					cheapest_partial_path->parallel_workers;
+				path = (Path *) create_gather_merge_path(root,
+														 final_rel,
+														 path,
+														 path->pathtarget,
+														 root->setop_pathkeys,
+														 NULL,
+														 &total_groups);
+
+				add_path(final_rel, path);
+			}
+
+			/*
+			 * Consider incremental sort with a gather merge on partial paths.
+			 *
+			 * We can also skip the entire loop when we only have a single
+			 * pathkey in setop_pathkeys because we can't have partially
+			 * sorted paths when there's just a single pathkey to sort by.
+			 */
+			if (enable_incremental_sort &&
+				list_length(root->setop_pathkeys) > 1)
+			{
+				foreach(lc, current_rel->partial_pathlist)
+				{
+					Path	   *input_path = (Path *) lfirst(lc);
+					Path	   *sorted_path;
+					bool		is_sorted;
+					int			presorted_keys;
+					double		total_groups;
+
+					/*
+					 * We don't care if this is the cheapest partial path - we
+					 * can't simply skip it, because it may be partially
+					 * sorted in which case we want to consider adding
+					 * incremental sort (instead of full sort, which is what
+					 * happens above).
+					 */
+
+					is_sorted =
+						pathkeys_count_contained_in(root->setop_pathkeys,
+													input_path->pathkeys,
+													&presorted_keys);
+
+					/*
+					 * No point in adding incremental sort on fully sorted
+					 * paths.
+					 */
+					if (is_sorted)
+						continue;
+
+					if (presorted_keys == 0)
+						continue;
+
+					/*
+					 * Since we have presorted keys, consider incremental
+					 * sort.
+					 */
+					sorted_path = (Path *)
+						create_incremental_sort_path(root,
+													 final_rel,
+													 input_path,
+													 root->setop_pathkeys,
+													 presorted_keys,
+													 limit_tuples);
+					total_groups =
+						input_path->rows * input_path->parallel_workers;
+					sorted_path = (Path *)
+						create_gather_merge_path(root,
+												 final_rel,
+												 sorted_path,
+												 sorted_path->pathtarget,
+												 root->setop_pathkeys,
+												 NULL,
+												 &total_groups);
+
+					add_path(final_rel, sorted_path);
+				}
+			}
+
+		}
 	}
 
 	extra.limit_needed = limit_needed(parse);
@@ -2009,6 +2040,187 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 	/* Note: currently, we leave it to callers to do set_cheapest() */
 }
 
+static Path *
+build_final_modify_table_path(PlannerInfo *root, RelOptInfo *final_rel,
+							  Path *path)
+{
+	Query	   *parse = root->parse;
+	Index		rootRelation;
+	List	   *resultRelations = NIL;
+	List	   *updateColnosLists = NIL;
+	List	   *withCheckOptionLists = NIL;
+	List	   *returningLists = NIL;
+	List	   *mergeActionLists = NIL;
+	List	   *rowMarks;
+
+	if (bms_membership(root->all_result_relids) == BMS_MULTIPLE)
+	{
+		/* Inherited UPDATE/DELETE/MERGE */
+		RelOptInfo *top_result_rel = find_base_rel(root,
+												   parse->resultRelation);
+		int			resultRelation = -1;
+
+		/* Pass the root result rel forward to the executor. */
+		rootRelation = parse->resultRelation;
+
+		/* Add only leaf children to ModifyTable. */
+		while ((resultRelation = bms_next_member(root->leaf_result_relids,
+												 resultRelation)) >= 0)
+		{
+			RelOptInfo *this_result_rel = find_base_rel(root, resultRelation);
+
+			/*
+			 * Also exclude any leaf rels that have turned dummy since being
+			 * added to the list, for example, by being excluded by constraint
+			 * exclusion.
+			 */
+			if (IS_DUMMY_REL(this_result_rel))
+				continue;
+
+			/* Build per-target-rel lists needed by ModifyTable */
+			resultRelations = lappend_int(resultRelations, resultRelation);
+			if (parse->commandType == CMD_UPDATE)
+			{
+				List	   *update_colnos = root->update_colnos;
+
+				if (this_result_rel != top_result_rel)
+					update_colnos =
+						adjust_inherited_attnums_multilevel(root,
+															update_colnos,
+															this_result_rel->relid,
+															top_result_rel->relid);
+				updateColnosLists = lappend(updateColnosLists, update_colnos);
+			}
+			if (parse->withCheckOptions)
+			{
+				List	   *withCheckOptions = parse->withCheckOptions;
+
+				if (this_result_rel != top_result_rel)
+					withCheckOptions = (List *)
+						adjust_appendrel_attrs_multilevel(root,
+														  (Node *) withCheckOptions,
+														  this_result_rel,
+														  top_result_rel);
+				withCheckOptionLists = lappend(withCheckOptionLists,
+											   withCheckOptions);
+			}
+			if (parse->returningList)
+			{
+				List	   *returningList = parse->returningList;
+
+				if (this_result_rel != top_result_rel)
+					returningList = (List *)
+						adjust_appendrel_attrs_multilevel(root,
+														  (Node *) returningList,
+														  this_result_rel,
+														  top_result_rel);
+				returningLists = lappend(returningLists, returningList);
+			}
+			if (parse->mergeActionList)
+			{
+				ListCell   *l;
+				List	   *mergeActionList = NIL;
+
+				/*
+				 * Copy MergeActions and translate stuff that references
+				 * attribute numbers.
+				 */
+				foreach(l, parse->mergeActionList)
+				{
+					MergeAction *action = lfirst(l),
+							   *leaf_action = copyObject(action);
+
+					leaf_action->qual =
+						adjust_appendrel_attrs_multilevel(root,
+														  (Node *) action->qual,
+														  this_result_rel,
+														  top_result_rel);
+					leaf_action->targetList = (List *)
+						adjust_appendrel_attrs_multilevel(root,
+														  (Node *) action->targetList,
+														  this_result_rel,
+														  top_result_rel);
+					if (leaf_action->commandType == CMD_UPDATE)
+						leaf_action->updateColnos =
+							adjust_inherited_attnums_multilevel(root,
+																action->updateColnos,
+																this_result_rel->relid,
+																top_result_rel->relid);
+					mergeActionList = lappend(mergeActionList, leaf_action);
+				}
+
+				mergeActionLists = lappend(mergeActionLists, mergeActionList);
+			}
+		}
+
+		if (resultRelations == NIL)
+		{
+			/*
+			 * We managed to exclude every child rel, so generate a dummy
+			 * one-relation plan using info for the top target rel (even
+			 * though that may not be a leaf target). Although it's clear that
+			 * no data will be updated or deleted, we still need to have a
+			 * ModifyTable node so that any statement triggers will be
+			 * executed.  (This could be cleaner if we fixed nodeModifyTable.c
+			 * to allow zero target relations, but that probably wouldn't be a
+			 * net win.)
+			 */
+			resultRelations = list_make1_int(parse->resultRelation);
+			if (parse->commandType == CMD_UPDATE)
+				updateColnosLists = list_make1(root->update_colnos);
+			if (parse->withCheckOptions)
+				withCheckOptionLists = list_make1(parse->withCheckOptions);
+			if (parse->returningList)
+				returningLists = list_make1(parse->returningList);
+			if (parse->mergeActionList)
+				mergeActionLists = list_make1(parse->mergeActionList);
+		}
+	}
+	else
+	{
+		/* Single-relation INSERT/UPDATE/DELETE/MERGE. */
+		rootRelation = 0;		/* there's no separate root rel */
+		resultRelations = list_make1_int(parse->resultRelation);
+		if (parse->commandType == CMD_UPDATE)
+			updateColnosLists = list_make1(root->update_colnos);
+		if (parse->withCheckOptions)
+			withCheckOptionLists = list_make1(parse->withCheckOptions);
+		if (parse->returningList)
+			returningLists = list_make1(parse->returningList);
+		if (parse->mergeActionList)
+			mergeActionLists = list_make1(parse->mergeActionList);
+	}
+
+	/*
+	 * If there was a FOR [KEY] UPDATE/SHARE clause, the LockRows node will
+	 * have dealt with fetching non-locked marked rows, else we need to have
+	 * ModifyTable do that.
+	 */
+	if (parse->rowMarks)
+		rowMarks = NIL;
+	else
+		rowMarks = root->rowMarks;
+
+	path = (Path *) create_modifytable_path(root,
+											final_rel,
+											path,
+											parse->commandType,
+											parse->canSetTag,
+											parse->resultRelation,
+											rootRelation,
+											root->partColsUpdated,
+											resultRelations,
+											updateColnosLists,
+											withCheckOptionLists,
+											returningLists,
+											rowMarks,
+											parse->onConflict,
+											mergeActionLists,
+											assign_special_exec_param(root));
+
+	return path;
+}
+
 /*
  * Do preprocessing for groupingSets clause and related data.  This handles the
  * preliminary steps of expanding the grouping sets, organizing them into lists
@@ -3524,6 +3736,38 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 									  parse->sortClause,
 									  tlist);
 
+	/* setting setop_pathkeys might be useful to the union planner */
+	if (qp_extra->setop != NULL &&
+		set_operation_ordered_results_useful(qp_extra->setop))
+	{
+		List	   *groupClauses;
+		ListCell   *lc;
+		bool		sortable;
+
+		foreach(lc, root->processed_tlist)
+		{
+			TargetEntry *tle = lfirst_node(TargetEntry, lc);
+
+			if (tle->resjunk)
+				continue;
+
+			tle->ressortgroupref = tle->resno;
+		}
+
+		groupClauses = generate_setop_grouplist(qp_extra->setop, tlist);
+
+		root->setop_pathkeys =
+			make_pathkeys_for_sortclauses_extended(root,
+												   &groupClauses,
+												   tlist,
+												   false,
+												   &sortable);
+		if (!sortable)
+			root->setop_pathkeys = NIL;
+	}
+	else
+		root->setop_pathkeys = NIL;
+
 	/*
 	 * Figure out whether we want a sorted result from query_planner.
 	 *
@@ -3533,7 +3777,9 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 	 * sortable DISTINCT clause that's more rigorous than the ORDER BY clause,
 	 * we try to produce output that's sufficiently well sorted for the
 	 * DISTINCT.  Otherwise, if there is an ORDER BY clause, we want to sort
-	 * by the ORDER BY clause.
+	 * by the ORDER BY clause.  Otherwise, if we're a subquery being planned
+	 * for a set operation with a sortable targetlist, we want to sort by the
+	 * target list.
 	 *
 	 * Note: if we have both ORDER BY and GROUP BY, and ORDER BY is a superset
 	 * of GROUP BY, it would be tempting to request sort by ORDER BY --- but
@@ -3551,6 +3797,8 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 		root->query_pathkeys = root->distinct_pathkeys;
 	else if (root->sort_pathkeys)
 		root->query_pathkeys = root->sort_pathkeys;
+	else if (root->setop_pathkeys != NIL)
+		root->query_pathkeys = root->setop_pathkeys;
 	else
 		root->query_pathkeys = NIL;
 }
@@ -5306,11 +5554,8 @@ create_ordered_paths(PlannerInfo *root,
 		(*create_upper_paths_hook) (root, UPPERREL_ORDERED,
 									input_rel, ordered_rel, NULL);
 
-	/*
-	 * No need to bother with set_cheapest here; grouping_planner does not
-	 * need us to do it.
-	 */
-	Assert(ordered_rel->pathlist != NIL);
+	/* Now choose the best path(s) */
+	set_cheapest(ordered_rel);
 
 	return ordered_rel;
 }
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 8eaa734916..6ee828aff5 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -51,11 +51,15 @@ static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
 										  bool junkOK,
 										  int flag, List *refnames_tlist,
 										  List **pTargetList,
+										  bool *istrivial_tlist,
 										  double *pNumGroups);
 static RelOptInfo *generate_recursion_path(SetOperationStmt *setOp,
 										   PlannerInfo *root,
 										   List *refnames_tlist,
 										   List **pTargetList);
+static void build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
+									bool trivial_tlist, List *child_tlist,
+									List *interesting_pathkeys);
 static RelOptInfo *generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 										List *refnames_tlist,
 										List **pTargetList);
@@ -65,9 +69,8 @@ static RelOptInfo *generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *ro
 static List *plan_union_children(PlannerInfo *root,
 								 SetOperationStmt *top_union,
 								 List *refnames_tlist,
-								 List **tlist_list);
-static Path *make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
-							   PlannerInfo *root);
+								 List **tlist_list,
+								 List **istrivial_tlist);
 static void postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
 								Path *input_path,
@@ -84,7 +87,6 @@ static List *generate_append_tlist(List *colTypes, List *colCollations,
 								   bool flag,
 								   List *input_tlists,
 								   List *refnames_tlist);
-static List *generate_setop_grouplist(SetOperationStmt *op, List *targetlist);
 
 
 /*
@@ -160,6 +162,8 @@ plan_set_operations(PlannerInfo *root)
 	}
 	else
 	{
+		bool		trivial_tlist;
+
 		/*
 		 * Recurse on setOperations tree to generate paths for set ops. The
 		 * final output paths should have just the column types shown as the
@@ -171,6 +175,7 @@ plan_set_operations(PlannerInfo *root)
 										   true, -1,
 										   leftmostQuery->targetList,
 										   &top_tlist,
+										   &trivial_tlist,
 										   NULL);
 	}
 
@@ -180,6 +185,33 @@ 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 could benefit but
+	 * additional path work.
+	 */
+
+	/* sorted paths are not deemed of any additional use for this setop */
+	return false;
+}
+
 /*
  * recurse_set_operations
  *	  Recursively handle one step in a tree of set operations
@@ -200,6 +232,10 @@ plan_set_operations(PlannerInfo *root)
  * the logic in this file depends on flag columns being marked resjunk.
  * Pending a redesign of how that works, this is the easy way out.
  *
+ * 'istrivial_tlist' is an output parameter and is set to true when the
+ * pTargetList can be deemed to be a trivial target list as determined by
+ * generate_setop_tlist().
+ *
  * We don't have to care about typmods here: the only allowed difference
  * between set-op input and output typmods is input is a specific typmod
  * and output is -1, and that does not require a coercion.
@@ -210,9 +246,12 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   bool junkOK,
 					   int flag, List *refnames_tlist,
 					   List **pTargetList,
+					   bool *istrivial_tlist,
 					   double *pNumGroups)
 {
-	RelOptInfo *rel = NULL;		/* keep compiler quiet */
+	RelOptInfo *rel;
+
+	*istrivial_tlist = true;	/* for now */
 
 	/* Guard against stack overflow due to overly complex setop nests */
 	check_stack_depth();
@@ -224,8 +263,6 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		Query	   *subquery = rte->subquery;
 		PlannerInfo *subroot;
 		RelOptInfo *final_rel;
-		Path	   *subpath;
-		Path	   *path;
 		List	   *tlist;
 		bool		trivial_tlist;
 
@@ -262,61 +299,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 		/* Return the fully-fledged tlist to caller, too */
 		*pTargetList = tlist;
-
-		/*
-		 * Mark rel with estimated output rows, width, etc.  Note that we have
-		 * to do this before generating outer-query paths, else
-		 * cost_subqueryscan is not happy.
-		 */
-		set_subquery_size_estimates(root, rel);
-
-		/*
-		 * Since we may want to add a partial path to this relation, we must
-		 * set its consider_parallel flag correctly.
-		 */
+		*istrivial_tlist = trivial_tlist;
 		final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
-		rel->consider_parallel = final_rel->consider_parallel;
-
-		/*
-		 * For the moment, we consider only a single Path for the subquery.
-		 * This should change soon (make it look more like
-		 * set_subquery_pathlist).
-		 */
-		subpath = get_cheapest_fractional_path(final_rel,
-											   root->tuple_fraction);
-
-		/*
-		 * Stick a SubqueryScanPath atop that.
-		 *
-		 * We don't bother to determine the subquery's output ordering since
-		 * it won't be reflected in the set-op result anyhow; so just label
-		 * the SubqueryScanPath with nil pathkeys.  (XXX that should change
-		 * soon too, likely.)
-		 */
-		path = (Path *) create_subqueryscan_path(root, rel, subpath,
-												 trivial_tlist,
-												 NIL, NULL);
-
-		add_path(rel, path);
-
-		/*
-		 * If we have a partial path for the child relation, we can use that
-		 * to build a partial path for this relation.  But there's no point in
-		 * considering any path but the cheapest.
-		 */
-		if (rel->consider_parallel && bms_is_empty(rel->lateral_relids) &&
-			final_rel->partial_pathlist != NIL)
-		{
-			Path	   *partial_subpath;
-			Path	   *partial_path;
-
-			partial_subpath = linitial(final_rel->partial_pathlist);
-			partial_path = (Path *)
-				create_subqueryscan_path(root, rel, partial_subpath,
-										 trivial_tlist,
-										 NIL, NULL);
-			add_partial_path(rel, partial_path);
-		}
 
 		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
@@ -341,11 +325,11 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 			if (subquery->groupClause || subquery->groupingSets ||
 				subquery->distinctClause ||
 				subroot->hasHavingQual || subquery->hasAggs)
-				*pNumGroups = subpath->rows;
+				*pNumGroups = final_rel->rows;
 			else
 				*pNumGroups = estimate_num_groups(subroot,
 												  get_tlist_exprs(subroot->parse->targetList, false),
-												  subpath->rows,
+												  final_rel->rows,
 												  NULL,
 												  NULL);
 		}
@@ -394,6 +378,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 												*pTargetList,
 												refnames_tlist,
 												&trivial_tlist);
+			*istrivial_tlist = trivial_tlist;
 			target = create_pathtarget(root, *pTargetList);
 
 			/* Apply projection to each path */
@@ -424,16 +409,16 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 				lfirst(lc) = path;
 			}
 		}
+		postprocess_setop_rel(root, rel);
 	}
 	else
 	{
 		elog(ERROR, "unrecognized node type: %d",
 			 (int) nodeTag(setOp));
 		*pTargetList = NIL;
+		rel = NULL;				/* keep compiler quiet */
 	}
 
-	postprocess_setop_rel(root, rel);
-
 	return rel;
 }
 
@@ -452,7 +437,9 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	Path	   *lpath;
 	Path	   *rpath;
 	List	   *lpath_tlist;
+	bool		lpath_trivial_tlist;
 	List	   *rpath_tlist;
+	bool		rpath_trivial_tlist;
 	List	   *tlist;
 	List	   *groupList;
 	double		dNumGroups;
@@ -472,7 +459,10 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 								  false, -1,
 								  refnames_tlist,
 								  &lpath_tlist,
-								  NULL);
+								  &lpath_trivial_tlist, NULL);
+	if (lrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, lrel, lpath_trivial_tlist, lpath_tlist,
+								NULL);
 	lpath = lrel->cheapest_total_path;
 	/* The right path will want to look at the left one ... */
 	root->non_recursive_path = lpath;
@@ -481,7 +471,11 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 								  false, -1,
 								  refnames_tlist,
 								  &rpath_tlist,
+								  &rpath_trivial_tlist,
 								  NULL);
+	if (rrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, rrel, rpath_trivial_tlist, rpath_tlist,
+								NULL);
 	rpath = rrel->cheapest_total_path;
 	root->non_recursive_path = NULL;
 
@@ -543,6 +537,103 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	return result_rel;
 }
 
+/*
+ * build_setop_child_paths
+ *		Build paths for the set op child relation denoted by 'rel'.
+ *
+ * If 'interesting_pathkeys' is non-NIL then also include paths that suit
+ * these pathkeys if such paths are present in the rel's subroot
+ * UPPERREL_FINAL relation.
+ */
+static void
+build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
+						bool trivial_tlist, List *child_tlist,
+						List *interesting_pathkeys)
+{
+	RelOptInfo *final_rel;
+	ListCell   *lc;
+
+	/* it can't be a set op child rel if it's not a subquery */
+	Assert(rel->rtekind == RTE_SUBQUERY);
+
+	/*
+	 * When sorting, add child rel equivalences so that they're available to
+	 * the MergeAppend.
+	 */
+	if (interesting_pathkeys)
+		add_setop_child_rel_equivalences(root,
+										 rel->relids,
+										 child_tlist,
+										 interesting_pathkeys);
+
+	/*
+	 * Mark rel with estimated output rows, width, etc.  Note that we have to
+	 * do this before generating outer-query paths, else cost_subqueryscan is
+	 * not happy.
+	 */
+	set_subquery_size_estimates(root, rel);
+
+	/*
+	 * Since we may want to add a partial path to this relation, we must set
+	 * its consider_parallel flag correctly.
+	 */
+	final_rel = fetch_upper_rel(rel->subroot, UPPERREL_FINAL, NULL);
+	rel->consider_parallel = final_rel->consider_parallel;
+
+	/*
+	 * For each Path that subquery_planner produced, make a SubqueryScanPath
+	 * in the outer query.
+	 */
+	foreach(lc, final_rel->pathlist)
+	{
+		Path	   *subpath = (Path *) lfirst(lc);
+		List	   *pathkeys;
+
+		/* Convert subpath's pathkeys to outer representation */
+		pathkeys = convert_subquery_pathkeys(root, rel, subpath->pathkeys,
+											 make_tlist_from_pathtarget(subpath->pathtarget));
+
+		/* Generate outer path using this subpath */
+		add_path(rel, (Path *) create_subqueryscan_path(root,
+														rel,
+														subpath,
+														trivial_tlist,
+														pathkeys,
+														NULL));
+	}
+
+	/* if outer rel allows parallelism, do same for partial paths */
+	if (rel->consider_parallel && bms_is_empty(rel->lateral_relids))
+	{
+		/* if consider_parallel is false, there should be no partial paths */
+		Assert(final_rel->consider_parallel ||
+			   final_rel->partial_pathlist == NIL);
+
+		/* generate subquery paths for each partial path */
+		foreach(lc, final_rel->partial_pathlist)
+		{
+			Path	   *subpath = (Path *) lfirst(lc);
+			List	   *pathkeys;
+
+			/* convert subpath's pathkeys to outer representation */
+			pathkeys = convert_subquery_pathkeys(root, rel,
+												 subpath->pathkeys,
+												 make_tlist_from_pathtarget(subpath->pathtarget));
+
+			/* generate outer path using this subpath */
+			add_partial_path(rel,
+							 (Path *) create_subqueryscan_path(root,
+															   rel,
+															   subpath,
+															   trivial_tlist,
+															   pathkeys,
+															   NULL));
+		}
+	}
+
+	postprocess_setop_rel(root, rel);
+}
+
 /*
  * Generate paths for a UNION or UNION ALL node
  */
@@ -553,30 +644,23 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 {
 	Relids		relids = NULL;
 	RelOptInfo *result_rel;
-	double		save_fraction = root->tuple_fraction;
 	ListCell   *lc;
+	ListCell   *lc2;
+	ListCell   *lc3;
 	List	   *pathlist = NIL;
+	List	   *ordered_pathlist = NIL;
 	List	   *partial_pathlist = NIL;
 	bool		partial_paths_valid = true;
 	bool		consider_parallel = true;
 	List	   *rellist;
 	List	   *tlist_list;
+	List	   *trivial_tlist_list;
 	List	   *tlist;
-	Path	   *path;
-
-	/*
-	 * If plain UNION, tell children to fetch all tuples.
-	 *
-	 * Note: in UNION ALL, we pass the top-level tuple_fraction unmodified to
-	 * each arm of the UNION ALL.  One could make a case for reducing the
-	 * tuple fraction for later arms (discounting by the expected size of the
-	 * earlier arms' results) but it seems not worth the trouble. The normal
-	 * case where tuple_fraction isn't already zero is a LIMIT at top level,
-	 * and passing it down as-is is usually enough to get the desired result
-	 * of preferring fast-start plans.
-	 */
-	if (!op->all)
-		root->tuple_fraction = 0.0;
+	List	   *groupList = NIL;
+	Path	   *apath;
+	Path	   *gpath = NULL;
+	bool		try_sorted;
+	List	   *union_pathkeys = NIL;
 
 	/*
 	 * If any of my children are identical UNION nodes (same op, all-flag, and
@@ -584,7 +668,11 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	rellist = plan_union_children(root, op, refnames_tlist, &tlist_list);
+	rellist = plan_union_children(root,
+								  op,
+								  refnames_tlist,
+								  &tlist_list,
+								  &trivial_tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -595,16 +683,68 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 */
 	tlist = generate_append_tlist(op->colTypes, op->colCollations, false,
 								  tlist_list, refnames_tlist);
-
 	*pTargetList = tlist;
 
+	/* For for UNIONs (not UNION ALL), try sorting, if sorting is possible */
+	try_sorted = !op->all && grouping_is_sortable(op->groupClauses);
+
+	if (try_sorted)
+	{
+		/* determine the pathkeys for sorting by the whole target list */
+		union_pathkeys = build_setop_pathkeys(root,
+											  op,
+											  bms_make_singleton(0),
+											  tlist);
+		groupList = generate_setop_grouplist(op, tlist);
+	}
+
+	/*
+	 * Now that we've got the append target list, we can build the union child
+	 * paths.
+	 */
+	forthree(lc, rellist, lc2, trivial_tlist_list, lc3, tlist_list)
+	{
+		RelOptInfo *rel = lfirst(lc);
+		bool		trivial_tlist = lfirst_int(lc2);
+		List	   *child_tlist = lfirst_node(List, lc3);
+
+		/* only build paths for the union children */
+		if (rel->rtekind == RTE_SUBQUERY)
+			build_setop_child_paths(root, rel, trivial_tlist, child_tlist,
+									union_pathkeys);
+	}
+
 	/* Build path lists and relid set. */
 	foreach(lc, rellist)
 	{
 		RelOptInfo *rel = lfirst(lc);
+		Path	   *ordered_path;
+
 
 		pathlist = lappend(pathlist, rel->cheapest_total_path);
 
+		if (try_sorted)
+		{
+			ordered_path = get_cheapest_path_for_pathkeys(rel->pathlist,
+														  union_pathkeys,
+														  NULL,
+														  TOTAL_COST,
+														  false);
+
+			if (ordered_path != NULL)
+				ordered_pathlist = lappend(ordered_pathlist, ordered_path);
+			else
+			{
+				/*
+				 * If we can't find a sorted path, just give up trying to
+				 * generate a list of correctly sorted child paths.  This can
+				 * happen when type coercion was added to the targetlist due
+				 * to mismatching types from the union children.
+				 */
+				try_sorted = false;
+			}
+		}
+
 		if (consider_parallel)
 		{
 			if (!rel->consider_parallel)
@@ -626,28 +766,21 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
 	result_rel->reltarget = create_pathtarget(root, tlist);
 	result_rel->consider_parallel = consider_parallel;
+	result_rel->consider_startup = (root->tuple_fraction > 0);
 
 	/*
-	 * Append the child results together.
+	 * Append the child results together using the cheapest paths from each
+	 * union child.
 	 */
-	path = (Path *) create_append_path(root, result_rel, pathlist, NIL,
-									   NIL, NULL, 0, false, -1);
-
-	/*
-	 * For UNION ALL, we just need the Append path.  For UNION, need to add
-	 * node(s) to remove duplicates.
-	 */
-	if (!op->all)
-		path = make_union_unique(op, path, tlist, root);
-
-	add_path(result_rel, path);
+	apath = (Path *) create_append_path(root, result_rel, pathlist, NIL,
+										NIL, NULL, 0, false, -1);
 
 	/*
 	 * Estimate number of groups.  For now we just assume the output is unique
 	 * --- this is certainly true for the UNION case, and we want worst-case
 	 * estimates anyway.
 	 */
-	result_rel->rows = path->rows;
+	result_rel->rows = apath->rows;
 
 	/*
 	 * Now consider doing the same thing using the partial paths plus Append
@@ -655,7 +788,7 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 */
 	if (partial_paths_valid)
 	{
-		Path	   *ppath;
+		Path	   *papath;
 		int			parallel_workers = 0;
 
 		/* Find the highest number of workers requested for any subpath. */
@@ -684,21 +817,136 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 		}
 		Assert(parallel_workers > 0);
 
-		ppath = (Path *)
+		papath = (Path *)
 			create_append_path(root, result_rel, NIL, partial_pathlist,
-							   NIL, NULL,
-							   parallel_workers, enable_parallel_append,
-							   -1);
-		ppath = (Path *)
-			create_gather_path(root, result_rel, ppath,
+							   NIL, NULL, parallel_workers,
+							   enable_parallel_append, -1);
+		gpath = (Path *)
+			create_gather_path(root, result_rel, papath,
 							   result_rel->reltarget, NULL, NULL);
-		if (!op->all)
-			ppath = make_union_unique(op, ppath, tlist, root);
-		add_path(result_rel, ppath);
 	}
 
-	/* Undo effects of possibly forcing tuple_fraction to 0 */
-	root->tuple_fraction = save_fraction;
+	if (!op->all)
+	{
+		double		dNumGroups;
+		bool		can_sort = grouping_is_sortable(groupList);
+		bool		can_hash = grouping_is_hashable(groupList);
+
+		/*
+		 * XXX for the moment, take the number of distinct groups as equal to
+		 * the total input size, ie, the worst case.  This is too
+		 * conservative, but it's not clear how to get a decent estimate of
+		 * the true size.  One should note as well the propensity of novices
+		 * to write UNION rather than UNION ALL even when they don't expect
+		 * any duplicates...
+		 */
+		dNumGroups = apath->rows;
+
+		if (can_hash)
+		{
+			Path	   *path;
+
+			/*
+			 * Try a hash aggregate plan on 'apath'.  This is the cheapest
+			 * available path containing each append child.
+			 */
+			path = (Path *) create_agg_path(root,
+											result_rel,
+											apath,
+											create_pathtarget(root, tlist),
+											AGG_HASHED,
+											AGGSPLIT_SIMPLE,
+											groupList,
+											NIL,
+											NULL,
+											dNumGroups);
+			add_path(result_rel, path);
+
+			/* Try hash aggregate on the Gather path, if valid */
+			if (gpath != NULL)
+			{
+				/* Hashed aggregate plan --- no sort needed */
+				path = (Path *) create_agg_path(root,
+												result_rel,
+												gpath,
+												create_pathtarget(root, tlist),
+												AGG_HASHED,
+												AGGSPLIT_SIMPLE,
+												groupList,
+												NIL,
+												NULL,
+												dNumGroups);
+				add_path(result_rel, path);
+			}
+		}
+
+		if (can_sort)
+		{
+			Path	   *path = apath;
+
+			if (groupList != NIL)
+				path = (Path *) create_sort_path(root, result_rel, path,
+												 make_pathkeys_for_sortclauses(root, groupList, tlist),
+												 -1.0);
+
+			path = (Path *) create_upper_unique_path(root,
+													 result_rel,
+													 path,
+													 list_length(path->pathkeys),
+													 dNumGroups);
+
+			add_path(result_rel, path);
+
+			/* Try Sort -> Unique on the Gather path, if set */
+			if (gpath != NULL)
+			{
+				path = gpath;
+
+				path = (Path *) create_sort_path(root, result_rel, path,
+												 make_pathkeys_for_sortclauses(root, groupList, tlist),
+												 -1.0);
+
+				path = (Path *) create_upper_unique_path(root,
+														 result_rel,
+														 path,
+														 list_length(path->pathkeys),
+														 dNumGroups);
+				add_path(result_rel, path);
+			}
+		}
+
+		/*
+		 * Try making a MergeAppend path if we managed to find a path with the
+		 * correct pathkeys for each union child.
+		 */
+		if (try_sorted && groupList != NIL)
+		{
+			Path	   *path;
+
+			path = (Path *) create_merge_append_path(root,
+													 result_rel,
+													 ordered_pathlist,
+													 union_pathkeys,
+													 NULL);
+
+			/* and make the MergeAppend unique */
+			path = (Path *) create_upper_unique_path(root,
+													 result_rel,
+													 path,
+													 list_length(tlist),
+													 path->rows);
+
+			add_path(result_rel, path);
+		}
+	}
+	else
+	{
+		/* UNION ALL */
+		add_path(result_rel, apath);
+
+		if (gpath != NULL)
+			add_path(result_rel, gpath);
+	}
 
 	return result_rel;
 }
@@ -724,6 +972,8 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
 			   *tlist,
 			   *groupList,
 			   *pathlist;
+	bool		lpath_trivial_tlist,
+				rpath_trivial_tlist;
 	double		dLeftGroups,
 				dRightGroups,
 				dNumGroups,
@@ -743,14 +993,22 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
 								  false, 0,
 								  refnames_tlist,
 								  &lpath_tlist,
+								  &lpath_trivial_tlist,
 								  &dLeftGroups);
+	if (lrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, lrel, lpath_trivial_tlist, lpath_tlist,
+								NULL);
 	lpath = lrel->cheapest_total_path;
 	rrel = recurse_set_operations(op->rarg, root,
 								  op->colTypes, op->colCollations,
 								  false, 1,
 								  refnames_tlist,
 								  &rpath_tlist,
+								  &rpath_trivial_tlist,
 								  &dRightGroups);
+	if (rrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, rrel, rpath_trivial_tlist, rpath_tlist,
+								NULL);
 	rpath = rrel->cheapest_total_path;
 
 	/* Undo effects of forcing tuple_fraction to 0 */
@@ -887,13 +1145,16 @@ static List *
 plan_union_children(PlannerInfo *root,
 					SetOperationStmt *top_union,
 					List *refnames_tlist,
-					List **tlist_list)
+					List **tlist_list,
+					List **istrivial_tlist)
 {
 	List	   *pending_rels = list_make1(top_union);
 	List	   *result = NIL;
 	List	   *child_tlist;
+	bool		trivial_tlist;
 
 	*tlist_list = NIL;
+	*istrivial_tlist = NIL;
 
 	while (pending_rels != NIL)
 	{
@@ -932,75 +1193,15 @@ plan_union_children(PlannerInfo *root,
 														false, -1,
 														refnames_tlist,
 														&child_tlist,
+														&trivial_tlist,
 														NULL));
 		*tlist_list = lappend(*tlist_list, child_tlist);
+		*istrivial_tlist = lappend_int(*istrivial_tlist, trivial_tlist);
 	}
 
 	return result;
 }
 
-/*
- * Add nodes to the given path tree to unique-ify the result of a UNION.
- */
-static Path *
-make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
-				  PlannerInfo *root)
-{
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
-	List	   *groupList;
-	double		dNumGroups;
-
-	/* Identify the grouping semantics */
-	groupList = generate_setop_grouplist(op, tlist);
-
-	/*
-	 * XXX for the moment, take the number of distinct groups as equal to the
-	 * total input size, ie, the worst case.  This is too conservative, but
-	 * it's not clear how to get a decent estimate of the true size.  One
-	 * should note as well the propensity of novices to write UNION rather
-	 * than UNION ALL even when they don't expect any duplicates...
-	 */
-	dNumGroups = path->rows;
-
-	/* Decide whether to hash or sort */
-	if (choose_hashed_setop(root, groupList, path,
-							dNumGroups, dNumGroups,
-							"UNION"))
-	{
-		/* Hashed aggregate plan --- no sort needed */
-		path = (Path *) create_agg_path(root,
-										result_rel,
-										path,
-										create_pathtarget(root, tlist),
-										AGG_HASHED,
-										AGGSPLIT_SIMPLE,
-										groupList,
-										NIL,
-										NULL,
-										dNumGroups);
-	}
-	else
-	{
-		/* Sort and Unique */
-		if (groupList)
-			path = (Path *)
-				create_sort_path(root,
-								 result_rel,
-								 path,
-								 make_pathkeys_for_sortclauses(root,
-															   groupList,
-															   tlist),
-								 -1.0);
-		path = (Path *) create_upper_unique_path(root,
-												 result_rel,
-												 path,
-												 list_length(path->pathkeys),
-												 dNumGroups);
-	}
-
-	return path;
-}
-
 /*
  * postprocess_setop_rel - perform steps required after adding paths
  */
@@ -1406,7 +1607,7 @@ generate_append_tlist(List *colTypes, List *colCollations,
  * setop.  So what we need to do here is copy that list and install
  * proper sortgrouprefs into it (copying those from the targetlist).
  */
-static List *
+List *
 generate_setop_grouplist(SetOperationStmt *op, List *targetlist)
 {
 	List	   *grouplist = copyObject(op->groupClauses);
@@ -1420,11 +1621,7 @@ generate_setop_grouplist(SetOperationStmt *op, List *targetlist)
 		SortGroupClause *sgc;
 
 		if (tle->resjunk)
-		{
-			/* resjunk columns should not have sortgrouprefs */
-			Assert(tle->ressortgroupref == 0);
 			continue;			/* ignore resjunk columns */
-		}
 
 		/* non-resjunk columns should have sortgroupref = resno */
 		Assert(tle->ressortgroupref == tle->resno);
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 0b1d17b9d3..66cae83ee1 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -587,11 +587,22 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 			parent_rel->pathlist = foreach_delete_current(parent_rel->pathlist,
 														  p1);
 
+#ifdef NOT_USED
+
+			/*
+			 * XXX fixme.  When creating the final upper rel paths for queries
+			 * which have setop_pathkey set,  we'll at the cheapest path as-is
+			 * also try sorting the cheapest path. If the costs of each are
+			 * fuzzily the same then we might choose to pfree the cheapest
+			 * path.  That's bad as the sort uses that path.
+			 */
+
 			/*
 			 * Delete the data pointed-to by the deleted cell, if possible
 			 */
 			if (!IsA(old_path, IndexPath))
 				pfree(old_path);
+#endif
 		}
 		else
 		{
@@ -1237,6 +1248,9 @@ create_tidrangescan_path(PlannerInfo *root, RelOptInfo *rel,
  *
  * Note that we must handle subpaths = NIL, representing a dummy access path.
  * Also, there are callers that pass root = NULL.
+ * 'rows', when passed as a non-negative number will be used to overwrite the
+ * returned path's row estimate.  Otherwise the row estimate is calculated
+ * by totaling the rows from 'subpaths'.
  */
 AppendPath *
 create_append_path(PlannerInfo *root,
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index ed85dc7414..1c59e111b6 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -397,6 +397,8 @@ struct PlannerInfo
 	List	   *distinct_pathkeys;
 	/* sortClause pathkeys, if any */
 	List	   *sort_pathkeys;
+	/* set operator pathkeys, if any */
+	List	   *setop_pathkeys;
 
 	/* Canonicalised partition schemes used in the query. */
 	List	   *part_schemes pg_node_attr(read_write_ignore);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9e7408c7ec..114e023c3b 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -173,6 +173,9 @@ extern void add_child_join_rel_equivalences(PlannerInfo *root,
 											AppendRelInfo **appinfos,
 											RelOptInfo *parent_joinrel,
 											RelOptInfo *child_joinrel);
+extern void add_setop_child_rel_equivalences(PlannerInfo *root, Relids relids,
+											 List *tlist,
+											 List *setop_pathkeys);
 extern List *generate_implied_equalities_for_column(PlannerInfo *root,
 													RelOptInfo *rel,
 													ec_matches_callback_type callback,
@@ -217,6 +220,8 @@ extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
 								  ScanDirection scandir);
 extern List *build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
 									  ScanDirection scandir, bool *partialkeys);
+extern List *build_setop_pathkeys(PlannerInfo *root, SetOperationStmt *op,
+								  Relids relids, List *tlist);
 extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr,
 									  Oid opno,
 									  Relids rel, bool create_it);
diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h
index 54fd61c9c3..bc2d716c0c 100644
--- a/src/include/optimizer/prep.h
+++ b/src/include/optimizer/prep.h
@@ -53,6 +53,7 @@ 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);
+extern List *generate_setop_grouplist(SetOperationStmt *op, List *targetlist);
 
 #endif							/* PREP_H */
diff --git a/src/test/regress/expected/collate.icu.utf8.out b/src/test/regress/expected/collate.icu.utf8.out
index 97bbe53b64..5485bdfb0b 100644
--- a/src/test/regress/expected/collate.icu.utf8.out
+++ b/src/test/regress/expected/collate.icu.utf8.out
@@ -1396,6 +1396,7 @@ SELECT x FROM test3cs WHERE x ~ 'a';
  abc
 (1 row)
 
+SET enable_hashagg TO off;
 SELECT x FROM test1cs UNION SELECT x FROM test2cs ORDER BY x;
   x  
 -----
@@ -1448,6 +1449,7 @@ SELECT DISTINCT x FROM test3cs ORDER BY x;
  ghi
 (4 rows)
 
+RESET enable_hashagg;
 SELECT count(DISTINCT x) FROM test3cs;
  count 
 -------
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 7fdb685313..5fd54a10b1 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1472,14 +1472,19 @@ explain (costs off) select * from t union select * from t order by 1,3;
    Sort Key: t.a, t.c
    Presorted Key: t.a
    ->  Unique
-         ->  Sort
+         ->  Merge Append
                Sort Key: t.a, t.b, t.c
-               ->  Gather
+               ->  Gather Merge
                      Workers Planned: 2
-                     ->  Parallel Append
+                     ->  Sort
+                           Sort Key: t.a, t.b, t.c
                            ->  Parallel Seq Scan on t
+               ->  Gather Merge
+                     Workers Planned: 2
+                     ->  Sort
+                           Sort Key: t_1.a, t_1.b, t_1.c
                            ->  Parallel Seq Scan on t t_1
-(11 rows)
+(16 rows)
 
 -- Full sort, not just incremental sort can be pushed below a gather merge path
 -- by generate_useful_gather_paths.
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
index 64cebe4833..5e8143f7ea 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -370,16 +370,16 @@ select count(*) from
 explain (costs off)
 select count(*) from
   ( select unique1 from tenk1 intersect select fivethous from tenk1 ) ss;
-                                     QUERY PLAN                                     
-------------------------------------------------------------------------------------
+                                 QUERY PLAN                                 
+----------------------------------------------------------------------------
  Aggregate
    ->  Subquery Scan on ss
          ->  HashSetOp Intersect
                ->  Append
-                     ->  Subquery Scan on "*SELECT* 2"
-                           ->  Seq Scan on tenk1
                      ->  Subquery Scan on "*SELECT* 1"
-                           ->  Index Only Scan using tenk1_unique1 on tenk1 tenk1_1
+                           ->  Index Only Scan using tenk1_unique1 on tenk1
+                     ->  Subquery Scan on "*SELECT* 2"
+                           ->  Seq Scan on tenk1 tenk1_1
 (8 rows)
 
 select count(*) from
@@ -412,16 +412,17 @@ set enable_hashagg to off;
 explain (costs off)
 select count(*) from
   ( select unique1 from tenk1 union select fivethous from tenk1 ) ss;
-                              QUERY PLAN                              
-----------------------------------------------------------------------
+                           QUERY PLAN                           
+----------------------------------------------------------------
  Aggregate
    ->  Unique
-         ->  Sort
+         ->  Merge Append
                Sort Key: tenk1.unique1
-               ->  Append
-                     ->  Index Only Scan using tenk1_unique1 on tenk1
+               ->  Index Only Scan using tenk1_unique1 on tenk1
+               ->  Sort
+                     Sort Key: tenk1_1.fivethous
                      ->  Seq Scan on tenk1 tenk1_1
-(7 rows)
+(8 rows)
 
 select count(*) from
   ( select unique1 from tenk1 union select fivethous from tenk1 ) ss;
@@ -433,18 +434,18 @@ select count(*) from
 explain (costs off)
 select count(*) from
   ( select unique1 from tenk1 intersect select fivethous from tenk1 ) ss;
-                                        QUERY PLAN                                        
-------------------------------------------------------------------------------------------
+                                    QUERY PLAN                                    
+----------------------------------------------------------------------------------
  Aggregate
    ->  Subquery Scan on ss
          ->  SetOp Intersect
                ->  Sort
-                     Sort Key: "*SELECT* 2".fivethous
+                     Sort Key: "*SELECT* 1".unique1
                      ->  Append
-                           ->  Subquery Scan on "*SELECT* 2"
-                                 ->  Seq Scan on tenk1
                            ->  Subquery Scan on "*SELECT* 1"
-                                 ->  Index Only Scan using tenk1_unique1 on tenk1 tenk1_1
+                                 ->  Index Only Scan using tenk1_unique1 on tenk1
+                           ->  Subquery Scan on "*SELECT* 2"
+                                 ->  Seq Scan on tenk1 tenk1_1
 (10 rows)
 
 select count(*) from
@@ -950,16 +951,8 @@ select except select;
 -- check hashed implementation
 set enable_hashagg = true;
 set enable_sort = false;
-explain (costs off)
-select from generate_series(1,5) union select from generate_series(1,3);
-                           QUERY PLAN                           
-----------------------------------------------------------------
- HashAggregate
-   ->  Append
-         ->  Function Scan on generate_series
-         ->  Function Scan on generate_series generate_series_1
-(4 rows)
-
+-- We've no way to check hashed UNION as the empty pathkeys in the Append are
+-- fine to make use of Unique, which is cheaper than HashAggregate.
 explain (costs off)
 select from generate_series(1,5) intersect select from generate_series(1,3);
                               QUERY PLAN                              
@@ -972,10 +965,6 @@ select from generate_series(1,5) intersect select from generate_series(1,3);
                ->  Function Scan on generate_series generate_series_1
 (6 rows)
 
-select from generate_series(1,5) union select from generate_series(1,3);
---
-(1 row)
-
 select from generate_series(1,5) union all select from generate_series(1,3);
 --
 (8 rows)
@@ -1102,16 +1091,17 @@ explain (costs off)
   UNION
   SELECT * FROM t2) t
  WHERE ab = 'ab';
-                    QUERY PLAN                     
----------------------------------------------------
- HashAggregate
-   Group Key: ((t1.a || t1.b))
-   ->  Append
-         ->  Index Scan using t1_ab_idx on t1
-               Index Cond: ((a || b) = 'ab'::text)
-         ->  Index Only Scan using t2_pkey on t2
-               Index Cond: (ab = 'ab'::text)
-(7 rows)
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: ((t1.a || t1.b))
+         ->  Append
+               ->  Index Scan using t1_ab_idx on t1
+                     Index Cond: ((a || b) = 'ab'::text)
+               ->  Index Only Scan using t2_pkey on t2
+                     Index Cond: (ab = 'ab'::text)
+(8 rows)
 
 --
 -- Test that ORDER BY for UNION ALL can be pushed down to inheritance
diff --git a/src/test/regress/sql/collate.icu.utf8.sql b/src/test/regress/sql/collate.icu.utf8.sql
index 3db9e25913..96d5d6b11c 100644
--- a/src/test/regress/sql/collate.icu.utf8.sql
+++ b/src/test/regress/sql/collate.icu.utf8.sql
@@ -555,6 +555,7 @@ SELECT x FROM test3cs WHERE x LIKE 'a%';
 SELECT x FROM test3cs WHERE x ILIKE 'a%';
 SELECT x FROM test3cs WHERE x SIMILAR TO 'a%';
 SELECT x FROM test3cs WHERE x ~ 'a';
+SET enable_hashagg TO off;
 SELECT x FROM test1cs UNION SELECT x FROM test2cs ORDER BY x;
 SELECT x FROM test2cs UNION SELECT x FROM test1cs ORDER BY x;
 SELECT x FROM test1cs INTERSECT SELECT x FROM test2cs;
@@ -562,6 +563,7 @@ SELECT x FROM test2cs INTERSECT SELECT x FROM test1cs;
 SELECT x FROM test1cs EXCEPT SELECT x FROM test2cs;
 SELECT x FROM test2cs EXCEPT SELECT x FROM test1cs;
 SELECT DISTINCT x FROM test3cs ORDER BY x;
+RESET enable_hashagg;
 SELECT count(DISTINCT x) FROM test3cs;
 SELECT x, count(*) FROM test3cs GROUP BY x ORDER BY x;
 SELECT x, row_number() OVER (ORDER BY x), rank() OVER (ORDER BY x) FROM test3cs ORDER BY x;
diff --git a/src/test/regress/sql/union.sql b/src/test/regress/sql/union.sql
index 599013e7c9..8d1a45c174 100644
--- a/src/test/regress/sql/union.sql
+++ b/src/test/regress/sql/union.sql
@@ -302,12 +302,11 @@ select except select;
 set enable_hashagg = true;
 set enable_sort = false;
 
-explain (costs off)
-select from generate_series(1,5) union select from generate_series(1,3);
+-- We've no way to check hashed UNION as the empty pathkeys in the Append are
+-- fine to make use of Unique, which is cheaper than HashAggregate.
 explain (costs off)
 select from generate_series(1,5) intersect select from generate_series(1,3);
 
-select from generate_series(1,5) union select from generate_series(1,3);
 select from generate_series(1,5) union all select from generate_series(1,3);
 select from generate_series(1,5) intersect select from generate_series(1,3);
 select from generate_series(1,5) intersect all select from generate_series(1,3);

From f2fb47a38003e76aa06b5c6dd2afbeaedef36561 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Tue, 6 Feb 2024 11:11:21 +0800
Subject: [PATCH v1] review diff

---
 src/backend/optimizer/path/pathkeys.c  | 96 +++++++++-----------------
 src/backend/optimizer/plan/planner.c   | 84 +---------------------
 src/backend/optimizer/prep/prepunion.c | 77 +++++++++++++++++++--
 src/backend/optimizer/util/pathnode.c  | 11 ---
 src/include/optimizer/paths.h          |  2 -
 5 files changed, 104 insertions(+), 166 deletions(-)

diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 2eb144f1df..e0281ef84c 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -985,71 +985,6 @@ build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
 	return retval;
 }
 
-/*
- * build_setop_pathkeys
- *	  Build and return a list of PathKeys, one for each non-junk target in
- *	  'tlist'.
- */
-List *
-build_setop_pathkeys(PlannerInfo *root, SetOperationStmt *op,
-					 Relids relids, List *tlist)
-{
-	ListCell   *lc;
-	ListCell   *sgccell = list_head(op->groupClauses);
-	List	   *retval = NIL;
-
-	foreach(lc, tlist)
-	{
-		TargetEntry *tle = lfirst_node(TargetEntry, lc);
-		SortGroupClause *sgc;
-
-		Oid			opfamily;
-		Oid			opcintype;
-		int16		strategy;
-		PathKey    *cpathkey;
-
-		if (tle->resjunk)
-			continue;
-
-		/*
-		 * XXX query_is_distinct_for() is happy to Assert this, should this do
-		 * that rather than ERROR?
-		 */
-		if (sgccell == NULL)
-			elog(ERROR, "too few group clauses");
-
-		sgc = lfirst_node(SortGroupClause, sgccell);
-
-		/* Find the operator in pg_amop --- failure shouldn't happen */
-		if (!get_ordering_op_properties(sgc->sortop,
-										&opfamily, &opcintype, &strategy))
-			elog(ERROR, "operator %u is not a valid ordering operator",
-				 sgc->eqop);
-
-		cpathkey = make_pathkey_from_sortinfo(root,
-											  tle->expr,
-											  opfamily,
-											  opcintype,
-											  exprCollation((Node *) tle->expr),
-											  false,
-											  sgc->nulls_first,
-											  0,
-											  relids,
-											  true);
-		retval = lappend(retval, cpathkey);
-		sgccell = lnext(op->groupClauses, sgccell);
-
-		/*
-		 * There's no need to look for redundant pathkeys as set operations
-		 * have no ability to have non-child constants in an EquivalenceClass.
-		 * Let's just make sure that remains true.
-		 */
-		Assert(!EC_MUST_BE_REDUNDANT(cpathkey->pk_eclass));
-	}
-
-	return retval;
-}
-
 /*
  * build_expression_pathkey
  *	  Build a pathkeys list that describes an ordering by a single expression
@@ -2251,6 +2186,34 @@ pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
 	return n;
 }
 
+/*
+ * pathkeys_useful_for_setop
+ *		Count the number of pathkeys that are useful for meeting the ordering
+ *		requested by the query's set operation.
+ *
+ * Because we the have the possibility of incremental sort, a prefix list of
+ * keys is potentially useful for improving the performance of the set
+ * operation's ordering. Thus we return 0, if no valuable keys are found, or
+ * the number of leading keys shared by the list and the set operation's
+ * ordering..
+ */
+static int
+pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
+{
+	int			n_common_pathkeys;
+
+	if (root->setop_pathkeys == NIL)
+		return 0;				/* no special setop ordering requested */
+
+	if (pathkeys == NIL)
+		return 0;				/* unordered path */
+
+	(void) pathkeys_count_contained_in(root->setop_pathkeys, pathkeys,
+									   &n_common_pathkeys);
+
+	return n_common_pathkeys;
+}
+
 /*
  * truncate_useless_pathkeys
  *		Shorten the given pathkey list to just the useful pathkeys.
@@ -2268,6 +2231,9 @@ truncate_useless_pathkeys(PlannerInfo *root,
 	if (nuseful2 > nuseful)
 		nuseful = nuseful2;
 	nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
+	if (nuseful2 > nuseful)
+		nuseful = nuseful2;
+	nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
 	if (nuseful2 > nuseful)
 		nuseful = nuseful2;
 
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 5cb140c049..47006edeae 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -1769,13 +1769,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 	foreach(lc, current_rel->pathlist)
 	{
 		Path	   *path = (Path *) lfirst(lc);
-		Path	   *input_path;
-
-		/*
-		 * Keep record of the unmodified path so that we can still tell which
-		 * one is the cheapest_input_path.
-		 */
-		input_path = path;
 
 		/*
 		 * If there is a FOR [KEY] UPDATE/SHARE clause, add the LockRows node.
@@ -1804,82 +1797,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 		}
 
 		/*
-		 * Create paths to suit final sort order required for setop_pathkeys.
-		 * Here we'll sort the cheapest input path (if not sorted already) and
-		 * incremental sort any paths which are partially sorted.  We also
-		 * include the cheapest path as-is so that the set operation can be
-		 * cheaply implemented using a method which does not require the input
-		 * to be sorted.
-		 */
-		if (root->setop_pathkeys != NIL)
-		{
-			Path	   *cheapest_input_path = current_rel->cheapest_total_path;
-			bool		is_sorted;
-			int			presorted_keys;
-
-			is_sorted = pathkeys_count_contained_in(root->setop_pathkeys,
-													path->pathkeys,
-													&presorted_keys);
-
-			if (!is_sorted)
-			{
-				/*
-				 * Try at least sorting the cheapest path and also try
-				 * incrementally sorting any path which is partially sorted
-				 * already (no need to deal with paths which have presorted
-				 * keys when incremental sort is disabled unless it's the
-				 * cheapest input path).
-				 */
-				if (input_path != cheapest_input_path)
-				{
-					if (presorted_keys == 0 || !enable_incremental_sort)
-						continue;
-				}
-				else
-				{
-					/*
-					 * If this is an INSERT/UPDATE/DELETE/MERGE, add a
-					 * ModifyTable path.
-					 */
-					if (parse->commandType != CMD_SELECT)
-						path = build_final_modify_table_path(root,
-															 final_rel,
-															 path);
-
-					/*
-					 * The union planner might want to try a hash-based method
-					 * of executing the set operation, so let's provide the
-					 * cheapest input path so that it can do that as cheaply
-					 * as possible.  If the cheapest_input_path happens to be
-					 * already correctly sorted then we'll add it to final_rel
-					 * at the end of the loop.
-					 */
-					add_path(final_rel, path);
-				}
-
-				/*
-				 * We've no need to consider both a sort and incremental sort.
-				 * We'll just do a sort if there are no presorted keys and an
-				 * incremental sort when there are presorted keys.
-				 */
-				if (presorted_keys == 0 || !enable_incremental_sort)
-					path = (Path *) create_sort_path(root,
-													 final_rel,
-													 path,
-													 root->setop_pathkeys,
-													 limit_tuples);
-				else
-					path = (Path *) create_incremental_sort_path(root,
-																 final_rel,
-																 path,
-																 root->setop_pathkeys,
-																 presorted_keys,
-																 limit_tuples);
-			}
-		}
-
-		/*
-		 * If this is an INSERT/UPDATE/DELETE/MERGE, add a ModifyTable path.
+		 * If this is an INSERT/UPDATE/DELETE/MERGE, add the ModifyTable node.
 		 */
 		if (parse->commandType != CMD_SELECT)
 			path = build_final_modify_table_path(root, final_rel, path);
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index dfdf2ec0a9..b0938e0110 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -588,6 +588,74 @@ build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
 	{
 		Path	   *subpath = (Path *) lfirst(lc);
 		List	   *pathkeys;
+		Path	   *cheapest_input_path = final_rel->cheapest_total_path;
+		List	   *setop_pathkeys = rel->subroot->setop_pathkeys;
+		bool		is_sorted;
+		int			presorted_keys;
+
+		/*
+		 * Include the cheapest path as-is so that the set operation can be
+		 * cheaply implemented using a method which does not require the input
+		 * to be sorted.
+		 */
+		if (subpath == cheapest_input_path)
+		{
+			/* Convert subpath's pathkeys to outer representation */
+			pathkeys = convert_subquery_pathkeys(root, rel, subpath->pathkeys,
+												 make_tlist_from_pathtarget(subpath->pathtarget));
+
+			/* Generate outer path using this subpath */
+			add_path(rel, (Path *) create_subqueryscan_path(root,
+															rel,
+															subpath,
+															trivial_tlist,
+															pathkeys,
+															NULL));
+		}
+
+		/*
+		 * Create paths to suit final sort order required for setop_pathkeys.
+		 * Here we'll sort the cheapest input path (if not sorted already) and
+		 * incremental sort any paths which are partially sorted.
+		 */
+		is_sorted = pathkeys_count_contained_in(setop_pathkeys,
+												subpath->pathkeys,
+												&presorted_keys);
+
+		if (!is_sorted)
+		{
+			double limittuples = rel->subroot->limit_tuples;
+
+			/*
+			 * Try at least sorting the cheapest path and also try
+			 * incrementally sorting any path which is partially sorted
+			 * already (no need to deal with paths which have presorted
+			 * keys when incremental sort is disabled unless it's the
+			 * cheapest input path).
+			 */
+			if (subpath != cheapest_input_path &&
+				(presorted_keys == 0 || !enable_incremental_sort))
+				continue;
+
+			/*
+			 * We've no need to consider both a sort and incremental sort.
+			 * We'll just do a sort if there are no presorted keys and an
+			 * incremental sort when there are presorted keys.
+			 */
+			if (presorted_keys == 0 || !enable_incremental_sort)
+				subpath = (Path *) create_sort_path(root,
+													final_rel,
+													subpath,
+													setop_pathkeys,
+													limittuples);
+			else
+				subpath = (Path *) create_incremental_sort_path(root,
+																final_rel,
+																subpath,
+																setop_pathkeys,
+																presorted_keys,
+																limittuples);
+		}
 
 		/* Convert subpath's pathkeys to outer representation */
 		pathkeys = convert_subquery_pathkeys(root, rel, subpath->pathkeys,
@@ -690,12 +758,11 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 
 	if (try_sorted)
 	{
-		/* determine the pathkeys for sorting by the whole target list */
-		union_pathkeys = build_setop_pathkeys(root,
-											  op,
-											  bms_make_singleton(0),
-											  tlist);
+		/* Identify the grouping semantics */
 		groupList = generate_setop_grouplist(op, tlist);
+
+		/* Determine the pathkeys for sorting by the whole target list */
+		union_pathkeys = make_pathkeys_for_sortclauses(root, groupList, tlist);
 	}
 
 	/*
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index e375cd52b5..64a2cd1045 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -587,22 +587,11 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 			parent_rel->pathlist = foreach_delete_current(parent_rel->pathlist,
 														  p1);
 
-#ifdef NOT_USED
-
-			/*
-			 * XXX fixme.  When creating the final upper rel paths for queries
-			 * which have setop_pathkey set,  we'll at the cheapest path as-is
-			 * also try sorting the cheapest path. If the costs of each are
-			 * fuzzily the same then we might choose to pfree the cheapest
-			 * path.  That's bad as the sort uses that path.
-			 */
-
 			/*
 			 * Delete the data pointed-to by the deleted cell, if possible
 			 */
 			if (!IsA(old_path, IndexPath))
 				pfree(old_path);
-#endif
 		}
 		else
 		{
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 7dc3507e8d..1165e98c5b 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -222,8 +222,6 @@ extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
 								  ScanDirection scandir);
 extern List *build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
 									  ScanDirection scandir, bool *partialkeys);
-extern List *build_setop_pathkeys(PlannerInfo *root, SetOperationStmt *op,
-								  Relids relids, List *tlist);
 extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr,
 									  Oid opno,
 									  Relids rel, bool create_it);
-- 
2.31.0

From f562dd8b80bd0b7c2d66ee9633434a1e5be82e04 Mon Sep 17 00:00:00 2001
From: "yizhi.fzh" <yizhi.fzh@alibaba-inc.com>
Date: Wed, 7 Feb 2024 07:00:33 +0800
Subject: [PATCH v1 1/1] Remove the unnecessary checks for pathkey routines

both pathkeys_count_contained_in and foreach can handle the NIL input,
so no need the extra checks.
---
 src/backend/optimizer/path/pathkeys.c | 10 ----------
 1 file changed, 10 deletions(-)

diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 82ff31273b..98334e5c52 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -2126,12 +2126,6 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
 {
 	int			n_common_pathkeys;
 
-	if (root->query_pathkeys == NIL)
-		return 0;				/* no special ordering requested */
-
-	if (pathkeys == NIL)
-		return 0;				/* unordered path */
-
 	(void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
 									   &n_common_pathkeys);
 
@@ -2167,10 +2161,6 @@ pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
 	if (root->group_pathkeys == NIL)
 		return 0;
 
-	/* unordered path */
-	if (pathkeys == NIL)
-		return 0;
-
 	/* walk the pathkeys and search for matching group key */
 	foreach(key, pathkeys)
 	{
-- 
2.34.1

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index b5a38aeb21..62b7103d0c 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -11454,6 +11454,10 @@ DROP INDEX base_tbl1_idx;
 DROP INDEX base_tbl2_idx;
 DROP INDEX async_p3_idx;
 -- UNION queries
+SET enable_sort TO off;
+SET enable_incremental_sort TO off;
+-- Adjust fdw_startup_cost so that we get an unordered path in the Append.
+ALTER SERVER loopback2 OPTIONS (ADD fdw_startup_cost '0.00');
 EXPLAIN (VERBOSE, COSTS OFF)
 INSERT INTO result_tbl
 (SELECT a, b, 'AAA' || c FROM async_p1 ORDER BY a LIMIT 10)
@@ -11535,6 +11539,9 @@ SELECT * FROM result_tbl ORDER BY a;
 (12 rows)
 
 DELETE FROM result_tbl;
+RESET enable_incremental_sort;
+RESET enable_sort;
+ALTER SERVER loopback2 OPTIONS (DROP fdw_startup_cost);
 -- Disable async execution if we use gating Result nodes for pseudoconstant
 -- quals
 EXPLAIN (VERBOSE, COSTS OFF)
diff --git a/contrib/postgres_fdw/sql/postgres_fdw.sql b/contrib/postgres_fdw/sql/postgres_fdw.sql
index f410c3db4e..0ed9c5d61f 100644
--- a/contrib/postgres_fdw/sql/postgres_fdw.sql
+++ b/contrib/postgres_fdw/sql/postgres_fdw.sql
@@ -3857,6 +3857,11 @@ DROP INDEX base_tbl2_idx;
 DROP INDEX async_p3_idx;
 
 -- UNION queries
+SET enable_sort TO off;
+SET enable_incremental_sort TO off;
+-- Adjust fdw_startup_cost so that we get an unordered path in the Append.
+ALTER SERVER loopback2 OPTIONS (ADD fdw_startup_cost '0.00');
+
 EXPLAIN (VERBOSE, COSTS OFF)
 INSERT INTO result_tbl
 (SELECT a, b, 'AAA' || c FROM async_p1 ORDER BY a LIMIT 10)
@@ -3883,6 +3888,10 @@ UNION ALL
 SELECT * FROM result_tbl ORDER BY a;
 DELETE FROM result_tbl;
 
+RESET enable_incremental_sort;
+RESET enable_sort;
+ALTER SERVER loopback2 OPTIONS (DROP fdw_startup_cost);
+
 -- Disable async execution if we use gating Result nodes for pseudoconstant
 -- quals
 EXPLAIN (VERBOSE, COSTS OFF)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 4bd60a09c6..c036911309 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -2867,6 +2867,58 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 	MemoryContextSwitchTo(oldcontext);
 }
 
+/*
+ * add_setop_child_rel_equivalences
+ *		Add equivalence members for each non-resjunk target in 'child_tlist'
+ *		to the EquivalenceClass in the corresponding setop_pathkey's pk_class.
+ *
+ * 'root' is the PlannerInfo belonging to the top-level set operation.
+ * 'child_relids' are the Relids of the child relation we're adding
+ * EquivalenceMembers for.
+ * 'child_tlist' is the target list for the setop child relation.  The target
+ * list expressions are what we add as EquivalenceMembers.
+ * 'setop_pathkeys' is a list of PathKeys which must contain an entry for each
+ * non-resjunk target in 'child_tlist'.
+ */
+void
+add_setop_child_rel_equivalences(PlannerInfo *root, Relids child_relids,
+								 List *child_tlist, List *setop_pathkeys)
+{
+	ListCell   *lc;
+	ListCell   *lc2 = list_head(setop_pathkeys);
+
+	foreach(lc, child_tlist)
+	{
+		TargetEntry *tle = lfirst_node(TargetEntry, lc);
+		EquivalenceMember *parent_em;
+		PathKey    *pk;
+
+		if (tle->resjunk)
+			continue;
+
+		if (lc2 == NULL)
+			elog(ERROR, "too few pathkeys for set operation");
+
+		pk = lfirst_node(PathKey, lc2);
+		parent_em = linitial(pk->pk_eclass->ec_members);
+
+		/*
+		 * We can safely pass the parent member as the first member in the
+		 * ec_members list as this is added first in generate_union_paths,
+		 * likewise, the JoinDomain can be that of the initial member of the
+		 * Pathkey's EquivalenceClass.
+		 */
+		add_eq_member(pk->pk_eclass,
+					  tle->expr,
+					  child_relids,
+					  parent_em->em_jdomain,
+					  parent_em,
+					  exprType((Node *) tle->expr));
+
+		lc2 = lnext(setop_pathkeys, lc2);
+	}
+}
+
 
 /*
  * generate_implied_equalities_for_column
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index bcc1b7a9eb..13f2eb5bed 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -2203,6 +2203,22 @@ pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
 	return n;
 }
 
+/*
+ * pathkeys_useful_for_setop
+ *		Count the number of leading common pathkeys root's 'setop_pathkeys' in
+ *		'pathkeys'.
+ */
+static int
+pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
+{
+	int			n_common_pathkeys;
+
+	(void) pathkeys_count_contained_in(root->setop_pathkeys, pathkeys,
+									   &n_common_pathkeys);
+
+	return n_common_pathkeys;
+}
+
 /*
  * truncate_useless_pathkeys
  *		Shorten the given pathkey list to just the useful pathkeys.
@@ -2220,6 +2236,9 @@ truncate_useless_pathkeys(PlannerInfo *root,
 	if (nuseful2 > nuseful)
 		nuseful = nuseful2;
 	nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
+	if (nuseful2 > nuseful)
+		nuseful = nuseful2;
+	nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
 	if (nuseful2 > nuseful)
 		nuseful = nuseful2;
 
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index be4e182869..33627dd4ea 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -58,6 +58,7 @@
 #include "optimizer/tlist.h"
 #include "parser/analyze.h"
 #include "parser/parse_agg.h"
+#include "parser/parse_clause.h"
 #include "parser/parse_relation.h"
 #include "parser/parsetree.h"
 #include "partitioning/partdesc.h"
@@ -126,6 +127,8 @@ typedef struct
 {
 	List	   *activeWindows;	/* active windows, if any */
 	grouping_sets_data *gset_data;	/* grouping sets data, if any */
+	SetOperationStmt *setop;	/* parent set operation or NULL if not a
+								 * subquery belonging to a set operation */
 } standard_qp_extra;
 
 /* Local functions */
@@ -256,6 +259,8 @@ static bool group_by_has_partkey(RelOptInfo *input_rel,
 								 List *targetList,
 								 List *groupClause);
 static int	common_prefix_cmp(const void *a, const void *b);
+static List *generate_setop_child_grouplist(SetOperationStmt *op,
+											List *targetlist);
 
 
 /*****************************************************************************
@@ -1507,6 +1512,18 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 		qp_extra.activeWindows = activeWindows;
 		qp_extra.gset_data = gset_data;
 
+		/*
+		 * Check if we're a subquery for a set operation.  If we are, store
+		 * the SetOperationStmt in qp_extra.
+		 */
+		if (root->parent_root != NULL &&
+			root->parent_root->parse->setOperations != NULL &&
+			IsA(root->parent_root->parse->setOperations, SetOperationStmt))
+			qp_extra.setop =
+				(SetOperationStmt *) root->parent_root->parse->setOperations;
+		else
+			qp_extra.setop = NULL;
+
 		/*
 		 * Generate the best unsorted and presorted paths for the scan/join
 		 * portion of this Query, ie the processing represented by the
@@ -3440,6 +3457,27 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 									  parse->sortClause,
 									  tlist);
 
+	/* setting setop_pathkeys might be useful to the union planner */
+	if (qp_extra->setop != NULL &&
+		set_operation_ordered_results_useful(qp_extra->setop))
+	{
+		List	   *groupClauses;
+		bool		sortable;
+
+		groupClauses = generate_setop_child_grouplist(qp_extra->setop, tlist);
+
+		root->setop_pathkeys =
+			make_pathkeys_for_sortclauses_extended(root,
+												   &groupClauses,
+												   tlist,
+												   false,
+												   &sortable);
+		if (!sortable)
+			root->setop_pathkeys = NIL;
+	}
+	else
+		root->setop_pathkeys = NIL;
+
 	/*
 	 * Figure out whether we want a sorted result from query_planner.
 	 *
@@ -3449,7 +3487,9 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 	 * sortable DISTINCT clause that's more rigorous than the ORDER BY clause,
 	 * we try to produce output that's sufficiently well sorted for the
 	 * DISTINCT.  Otherwise, if there is an ORDER BY clause, we want to sort
-	 * by the ORDER BY clause.
+	 * by the ORDER BY clause.  Otherwise, if we're a subquery being planned
+	 * for a set operation which can benefit from presorted results and have a
+	 * sortable targetlist, we want to sort by the target list.
 	 *
 	 * Note: if we have both ORDER BY and GROUP BY, and ORDER BY is a superset
 	 * of GROUP BY, it would be tempting to request sort by ORDER BY --- but
@@ -3467,6 +3507,8 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 		root->query_pathkeys = root->distinct_pathkeys;
 	else if (root->sort_pathkeys)
 		root->query_pathkeys = root->sort_pathkeys;
+	else if (root->setop_pathkeys != NIL)
+		root->query_pathkeys = root->setop_pathkeys;
 	else
 		root->query_pathkeys = NIL;
 }
@@ -7862,3 +7904,47 @@ group_by_has_partkey(RelOptInfo *input_rel,
 
 	return true;
 }
+
+/*
+ * generate_setop_child_grouplist
+ *		Build a SortGroupClause list defining the sort/grouping properties
+ *		of the child of a set operation.
+ *
+ * This is similar to generate_setop_grouplist() but differs as the setop
+ * child query's targetlist entries may already have a tleSortGroupRef
+ * assigned for other purposes, such as GROUP BYs.  Here we keep the
+ * SortGroupClause list in the same order as 'op' groupClauses and just adjust
+ * the tleSortGroupRef to reference the TargetEntry's 'ressortgroupref'.
+ */
+static List *
+generate_setop_child_grouplist(SetOperationStmt *op, List *targetlist)
+{
+	List	   *grouplist = copyObject(op->groupClauses);
+	ListCell   *lg;
+	ListCell   *lt;
+
+	lg = list_head(grouplist);
+	foreach(lt, targetlist)
+	{
+		TargetEntry *tle = (TargetEntry *) lfirst(lt);
+		SortGroupClause *sgc;
+
+		if (tle->resjunk)
+		{
+			/* resjunk columns should not have sortgrouprefs */
+			Assert(tle->ressortgroupref == 0);
+			continue;			/* ignore resjunk columns */
+		}
+
+		/* non-resjunk columns should have grouping clauses */
+		Assert(lg != NULL);
+		sgc = (SortGroupClause *) lfirst(lg);
+		lg = lnext(grouplist, lg);
+
+		/* assign a tleSortGroupRef, or reuse the existing one */
+		sgc->tleSortGroupRef = assignSortGroupRef(tle, targetlist);
+		tle->ressortgroupref = sgc->tleSortGroupRef;
+	}
+	Assert(lg == NULL);
+	return grouplist;
+}
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index c939b5a45f..7af99ca71c 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -51,11 +51,15 @@ static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
 										  bool junkOK,
 										  int flag, List *refnames_tlist,
 										  List **pTargetList,
+										  bool *istrivial_tlist,
 										  double *pNumGroups);
 static RelOptInfo *generate_recursion_path(SetOperationStmt *setOp,
 										   PlannerInfo *root,
 										   List *refnames_tlist,
 										   List **pTargetList);
+static void build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
+									bool trivial_tlist, List *child_tlist,
+									List *interesting_pathkeys);
 static RelOptInfo *generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 										List *refnames_tlist,
 										List **pTargetList);
@@ -65,9 +69,8 @@ static RelOptInfo *generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *ro
 static List *plan_union_children(PlannerInfo *root,
 								 SetOperationStmt *top_union,
 								 List *refnames_tlist,
-								 List **tlist_list);
-static Path *make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
-							   PlannerInfo *root);
+								 List **tlist_list,
+								 List **istrivial_tlist);
 static void postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
 								Path *input_path,
@@ -160,6 +163,8 @@ plan_set_operations(PlannerInfo *root)
 	}
 	else
 	{
+		bool		trivial_tlist;
+
 		/*
 		 * Recurse on setOperations tree to generate paths for set ops. The
 		 * final output paths should have just the column types shown as the
@@ -171,6 +176,7 @@ plan_set_operations(PlannerInfo *root)
 										   true, -1,
 										   leftmostQuery->targetList,
 										   &top_tlist,
+										   &trivial_tlist,
 										   NULL);
 	}
 
@@ -180,6 +186,33 @@ 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.
+	 */
+
+	/* sorted paths are not deemed of any additional use for this setop */
+	return false;
+}
+
 /*
  * recurse_set_operations
  *	  Recursively handle one step in a tree of set operations
@@ -200,6 +233,10 @@ plan_set_operations(PlannerInfo *root)
  * the logic in this file depends on flag columns being marked resjunk.
  * Pending a redesign of how that works, this is the easy way out.
  *
+ * 'istrivial_tlist' is an output parameter and is set to true when the
+ * pTargetList is deemed to be a trivial target list as determined by
+ * generate_setop_tlist().
+ *
  * We don't have to care about typmods here: the only allowed difference
  * between set-op input and output typmods is input is a specific typmod
  * and output is -1, and that does not require a coercion.
@@ -210,9 +247,12 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   bool junkOK,
 					   int flag, List *refnames_tlist,
 					   List **pTargetList,
+					   bool *istrivial_tlist,
 					   double *pNumGroups)
 {
-	RelOptInfo *rel = NULL;		/* keep compiler quiet */
+	RelOptInfo *rel;
+
+	*istrivial_tlist = true;	/* for now */
 
 	/* Guard against stack overflow due to overly complex setop nests */
 	check_stack_depth();
@@ -224,8 +264,6 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		Query	   *subquery = rte->subquery;
 		PlannerInfo *subroot;
 		RelOptInfo *final_rel;
-		Path	   *subpath;
-		Path	   *path;
 		List	   *tlist;
 		bool		trivial_tlist;
 
@@ -262,61 +300,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 		/* Return the fully-fledged tlist to caller, too */
 		*pTargetList = tlist;
-
-		/*
-		 * Mark rel with estimated output rows, width, etc.  Note that we have
-		 * to do this before generating outer-query paths, else
-		 * cost_subqueryscan is not happy.
-		 */
-		set_subquery_size_estimates(root, rel);
-
-		/*
-		 * Since we may want to add a partial path to this relation, we must
-		 * set its consider_parallel flag correctly.
-		 */
+		*istrivial_tlist = trivial_tlist;
 		final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
-		rel->consider_parallel = final_rel->consider_parallel;
-
-		/*
-		 * For the moment, we consider only a single Path for the subquery.
-		 * This should change soon (make it look more like
-		 * set_subquery_pathlist).
-		 */
-		subpath = get_cheapest_fractional_path(final_rel,
-											   root->tuple_fraction);
-
-		/*
-		 * Stick a SubqueryScanPath atop that.
-		 *
-		 * We don't bother to determine the subquery's output ordering since
-		 * it won't be reflected in the set-op result anyhow; so just label
-		 * the SubqueryScanPath with nil pathkeys.  (XXX that should change
-		 * soon too, likely.)
-		 */
-		path = (Path *) create_subqueryscan_path(root, rel, subpath,
-												 trivial_tlist,
-												 NIL, NULL);
-
-		add_path(rel, path);
-
-		/*
-		 * If we have a partial path for the child relation, we can use that
-		 * to build a partial path for this relation.  But there's no point in
-		 * considering any path but the cheapest.
-		 */
-		if (rel->consider_parallel && bms_is_empty(rel->lateral_relids) &&
-			final_rel->partial_pathlist != NIL)
-		{
-			Path	   *partial_subpath;
-			Path	   *partial_path;
-
-			partial_subpath = linitial(final_rel->partial_pathlist);
-			partial_path = (Path *)
-				create_subqueryscan_path(root, rel, partial_subpath,
-										 trivial_tlist,
-										 NIL, NULL);
-			add_partial_path(rel, partial_path);
-		}
 
 		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
@@ -341,11 +326,11 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 			if (subquery->groupClause || subquery->groupingSets ||
 				subquery->distinctClause ||
 				subroot->hasHavingQual || subquery->hasAggs)
-				*pNumGroups = subpath->rows;
+				*pNumGroups = final_rel->rows;
 			else
 				*pNumGroups = estimate_num_groups(subroot,
 												  get_tlist_exprs(subroot->parse->targetList, false),
-												  subpath->rows,
+												  final_rel->rows,
 												  NULL,
 												  NULL);
 		}
@@ -394,6 +379,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 												*pTargetList,
 												refnames_tlist,
 												&trivial_tlist);
+			*istrivial_tlist = trivial_tlist;
 			target = create_pathtarget(root, *pTargetList);
 
 			/* Apply projection to each path */
@@ -424,16 +410,16 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 				lfirst(lc) = path;
 			}
 		}
+		postprocess_setop_rel(root, rel);
 	}
 	else
 	{
 		elog(ERROR, "unrecognized node type: %d",
 			 (int) nodeTag(setOp));
 		*pTargetList = NIL;
+		rel = NULL;				/* keep compiler quiet */
 	}
 
-	postprocess_setop_rel(root, rel);
-
 	return rel;
 }
 
@@ -452,7 +438,9 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	Path	   *lpath;
 	Path	   *rpath;
 	List	   *lpath_tlist;
+	bool		lpath_trivial_tlist;
 	List	   *rpath_tlist;
+	bool		rpath_trivial_tlist;
 	List	   *tlist;
 	List	   *groupList;
 	double		dNumGroups;
@@ -472,7 +460,10 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 								  false, -1,
 								  refnames_tlist,
 								  &lpath_tlist,
-								  NULL);
+								  &lpath_trivial_tlist, NULL);
+	if (lrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, lrel, lpath_trivial_tlist, lpath_tlist,
+								NIL);
 	lpath = lrel->cheapest_total_path;
 	/* The right path will want to look at the left one ... */
 	root->non_recursive_path = lpath;
@@ -481,7 +472,11 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 								  false, -1,
 								  refnames_tlist,
 								  &rpath_tlist,
+								  &rpath_trivial_tlist,
 								  NULL);
+	if (rrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, rrel, rpath_trivial_tlist, rpath_tlist,
+								NIL);
 	rpath = rrel->cheapest_total_path;
 	root->non_recursive_path = NULL;
 
@@ -543,6 +538,256 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	return result_rel;
 }
 
+/*
+ * build_setop_child_paths
+ *		Build paths for the set op child relation denoted by 'rel'.
+ *
+ * If 'interesting_pathkeys' is non-NIL then also include paths that suit
+ * these pathkeys, sorting any unsorted paths as required.
+ */
+static void
+build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
+						bool trivial_tlist, List *child_tlist,
+						List *interesting_pathkeys)
+{
+	RelOptInfo *final_rel;
+	List	   *setop_pathkeys = rel->subroot->setop_pathkeys;
+	ListCell   *lc;
+
+	/* it can't be a set op child rel if it's not a subquery */
+	Assert(rel->rtekind == RTE_SUBQUERY);
+
+	/* when sorting is needed, add child rel equivalences */
+	if (interesting_pathkeys != NIL)
+		add_setop_child_rel_equivalences(root,
+										 rel->relids,
+										 child_tlist,
+										 interesting_pathkeys);
+
+	/*
+	 * Mark rel with estimated output rows, width, etc.  Note that we have to
+	 * do this before generating outer-query paths, else cost_subqueryscan is
+	 * not happy.
+	 */
+	set_subquery_size_estimates(root, rel);
+
+	/*
+	 * Since we may want to add a partial path to this relation, we must set
+	 * its consider_parallel flag correctly.
+	 */
+	final_rel = fetch_upper_rel(rel->subroot, UPPERREL_FINAL, NULL);
+	rel->consider_parallel = final_rel->consider_parallel;
+
+	/* Generate subquery scan paths for any interesting path in final_rel */
+	foreach(lc, final_rel->pathlist)
+	{
+		Path	   *subpath = (Path *) lfirst(lc);
+		List	   *pathkeys;
+		Path	   *cheapest_input_path = final_rel->cheapest_total_path;
+		bool		is_sorted;
+		int			presorted_keys;
+
+		/*
+		 * Include the cheapest path as-is so that the set operation can be
+		 * cheaply implemented using a method which does not require the input
+		 * to be sorted.
+		 */
+		if (subpath == cheapest_input_path)
+		{
+			/* Convert subpath's pathkeys to outer representation */
+			pathkeys = convert_subquery_pathkeys(root, rel, subpath->pathkeys,
+												 make_tlist_from_pathtarget(subpath->pathtarget));
+
+			/* Generate outer path using this subpath */
+			add_path(rel, (Path *) create_subqueryscan_path(root,
+															rel,
+															subpath,
+															trivial_tlist,
+															pathkeys,
+															NULL));
+		}
+
+		/* skip dealing with sorted paths if the setop doesn't need them */
+		if (interesting_pathkeys == NIL)
+			continue;
+
+		/*
+		 * Create paths to suit final sort order required for setop_pathkeys.
+		 * Here we'll sort the cheapest input path (if not sorted already) and
+		 * incremental sort any paths which are partially sorted.
+		 */
+		is_sorted = pathkeys_count_contained_in(setop_pathkeys,
+												subpath->pathkeys,
+												&presorted_keys);
+
+		if (!is_sorted)
+		{
+			double		limittuples = rel->subroot->limit_tuples;
+
+			/*
+			 * Try at least sorting the cheapest path and also try
+			 * incrementally sorting any path which is partially sorted
+			 * already (no need to deal with paths which have presorted keys
+			 * when incremental sort is disabled unless it's the cheapest
+			 * input path).
+			 */
+			if (subpath != cheapest_input_path &&
+				(presorted_keys == 0 || !enable_incremental_sort))
+				continue;
+
+			/*
+			 * We've no need to consider both a sort and incremental sort.
+			 * We'll just do a sort if there are no presorted keys and an
+			 * incremental sort when there are presorted keys.
+			 */
+			if (presorted_keys == 0 || !enable_incremental_sort)
+				subpath = (Path *) create_sort_path(rel->subroot,
+													final_rel,
+													subpath,
+													setop_pathkeys,
+													limittuples);
+			else
+				subpath = (Path *) create_incremental_sort_path(rel->subroot,
+																final_rel,
+																subpath,
+																setop_pathkeys,
+																presorted_keys,
+																limittuples);
+		}
+
+		/* Add the sorted path unless the cheapest path is already sorted. */
+		if (subpath != cheapest_input_path)
+		{
+			/* Convert subpath's pathkeys to outer representation */
+			pathkeys = convert_subquery_pathkeys(root, rel, subpath->pathkeys,
+												 make_tlist_from_pathtarget(subpath->pathtarget));
+
+			/* Generate outer path using this subpath */
+			add_path(rel, (Path *) create_subqueryscan_path(root,
+															rel,
+															subpath,
+															trivial_tlist,
+															pathkeys,
+															NULL));
+		}
+	}
+
+	/* if consider_parallel is false, there should be no partial paths */
+	Assert(final_rel->consider_parallel ||
+		   final_rel->partial_pathlist == NIL);
+
+	/* if rel allows parallelism, do same for partial paths */
+	if (rel->consider_parallel && bms_is_empty(rel->lateral_relids) &&
+		final_rel->partial_pathlist != NIL)
+	{
+		Path	   *cheapest_partial_path;
+		bool		is_sorted;
+		int			presorted_keys;
+
+		cheapest_partial_path = linitial(final_rel->partial_pathlist);
+
+		/* generate interesting subquery paths for each partial path */
+		foreach(lc, final_rel->partial_pathlist)
+		{
+			Path	   *subpath = (Path *) lfirst(lc);
+			List	   *pathkeys;
+
+			/*
+			 * Include the cheapest partial path as-is so that the set
+			 * operation can be cheaply implemented using a method which does
+			 * not require the input to be sorted.
+			 */
+			if (subpath == cheapest_partial_path)
+			{
+				/* convert subpath's pathkeys to outer representation */
+				pathkeys = convert_subquery_pathkeys(root, rel,
+													 subpath->pathkeys,
+													 make_tlist_from_pathtarget(subpath->pathtarget));
+
+				/* generate outer path using this subpath */
+				add_partial_path(rel,
+								 (Path *) create_subqueryscan_path(root,
+																   rel,
+																   subpath,
+																   trivial_tlist,
+																   pathkeys,
+																   NULL));
+			}
+
+			/* skip dealing with sorted paths if the setop doesn't need them */
+			if (interesting_pathkeys == NIL)
+				continue;
+
+
+			/*
+			 * As above, create paths to suit final sort order required for
+			 * setop_pathkeys.  We sort the cheapest partial path (if not
+			 * sorted already) and incremental sort any paths which are
+			 * partially sorted.
+			 */
+			is_sorted = pathkeys_count_contained_in(setop_pathkeys,
+													subpath->pathkeys,
+													&presorted_keys);
+
+			if (!is_sorted)
+			{
+				double		limittuples = rel->subroot->limit_tuples;
+
+				/*
+				 * Try at least sorting the cheapest partial path and also try
+				 * incrementally sorting any path which is partially sorted
+				 * already (no need to deal with paths which have presorted
+				 * keys when incremental sort is disabled unless it's the
+				 * cheapest input path).
+				 */
+				if (subpath != cheapest_partial_path &&
+					(presorted_keys == 0 || !enable_incremental_sort))
+					continue;
+
+				/*
+				 * We've no need to consider both a sort and incremental sort.
+				 * We'll just do a sort if there are no presorted keys and an
+				 * incremental sort when there are presorted keys.
+				 */
+				if (presorted_keys == 0 || !enable_incremental_sort)
+					subpath = (Path *) create_sort_path(rel->subroot,
+														final_rel,
+														subpath,
+														setop_pathkeys,
+														limittuples);
+				else
+					subpath = (Path *) create_incremental_sort_path(rel->subroot,
+																	final_rel,
+																	subpath,
+																	setop_pathkeys,
+																	presorted_keys,
+																	limittuples);
+			}
+
+			/*
+			 * Add the sorted path unless the cheapest path is already sorted.
+			 */
+			if (subpath != cheapest_partial_path)
+			{
+				/* Convert subpath's pathkeys to outer representation */
+				pathkeys = convert_subquery_pathkeys(root, rel, subpath->pathkeys,
+													 make_tlist_from_pathtarget(subpath->pathtarget));
+
+				/* Generate outer path using this subpath */
+				add_partial_path(rel,
+								 (Path *) create_subqueryscan_path(root,
+																   rel,
+																   subpath,
+																   trivial_tlist,
+																   pathkeys,
+																   NULL));
+			}
+		}
+	}
+
+	postprocess_setop_rel(root, rel);
+}
+
 /*
  * Generate paths for a UNION or UNION ALL node
  */
@@ -553,30 +798,23 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 {
 	Relids		relids = NULL;
 	RelOptInfo *result_rel;
-	double		save_fraction = root->tuple_fraction;
 	ListCell   *lc;
-	List	   *pathlist = NIL;
+	ListCell   *lc2;
+	ListCell   *lc3;
+	List	   *cheapest_pathlist = NIL;
+	List	   *ordered_pathlist = NIL;
 	List	   *partial_pathlist = NIL;
 	bool		partial_paths_valid = true;
 	bool		consider_parallel = true;
 	List	   *rellist;
 	List	   *tlist_list;
+	List	   *trivial_tlist_list;
 	List	   *tlist;
-	Path	   *path;
-
-	/*
-	 * If plain UNION, tell children to fetch all tuples.
-	 *
-	 * Note: in UNION ALL, we pass the top-level tuple_fraction unmodified to
-	 * each arm of the UNION ALL.  One could make a case for reducing the
-	 * tuple fraction for later arms (discounting by the expected size of the
-	 * earlier arms' results) but it seems not worth the trouble. The normal
-	 * case where tuple_fraction isn't already zero is a LIMIT at top level,
-	 * and passing it down as-is is usually enough to get the desired result
-	 * of preferring fast-start plans.
-	 */
-	if (!op->all)
-		root->tuple_fraction = 0.0;
+	List	   *groupList = NIL;
+	Path	   *apath;
+	Path	   *gpath = NULL;
+	bool		try_sorted;
+	List	   *union_pathkeys = NIL;
 
 	/*
 	 * If any of my children are identical UNION nodes (same op, all-flag, and
@@ -584,7 +822,11 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	rellist = plan_union_children(root, op, refnames_tlist, &tlist_list);
+	rellist = plan_union_children(root,
+								  op,
+								  refnames_tlist,
+								  &tlist_list,
+								  &trivial_tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -595,15 +837,66 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 */
 	tlist = generate_append_tlist(op->colTypes, op->colCollations, false,
 								  tlist_list, refnames_tlist);
-
 	*pTargetList = tlist;
 
+	/* For for UNIONs (not UNION ALL), try sorting, if sorting is possible */
+	try_sorted = !op->all && grouping_is_sortable(op->groupClauses);
+
+	if (try_sorted)
+	{
+		/* Identify the grouping semantics */
+		groupList = generate_setop_grouplist(op, tlist);
+
+		/* Determine the pathkeys for sorting by the whole target list */
+		union_pathkeys = make_pathkeys_for_sortclauses(root, groupList, tlist);
+	}
+
+	/*
+	 * Now that we've got the append target list, we can build the union child
+	 * paths.
+	 */
+	forthree(lc, rellist, lc2, trivial_tlist_list, lc3, tlist_list)
+	{
+		RelOptInfo *rel = lfirst(lc);
+		bool		trivial_tlist = lfirst_int(lc2);
+		List	   *child_tlist = lfirst_node(List, lc3);
+
+		/* only build paths for the union children */
+		if (rel->rtekind == RTE_SUBQUERY)
+			build_setop_child_paths(root, rel, trivial_tlist, child_tlist,
+									union_pathkeys);
+	}
+
 	/* Build path lists and relid set. */
 	foreach(lc, rellist)
 	{
 		RelOptInfo *rel = lfirst(lc);
+		Path	   *ordered_path;
 
-		pathlist = lappend(pathlist, rel->cheapest_total_path);
+		cheapest_pathlist = lappend(cheapest_pathlist,
+									rel->cheapest_total_path);
+
+		if (try_sorted)
+		{
+			ordered_path = get_cheapest_path_for_pathkeys(rel->pathlist,
+														  union_pathkeys,
+														  NULL,
+														  TOTAL_COST,
+														  false);
+
+			if (ordered_path != NULL)
+				ordered_pathlist = lappend(ordered_pathlist, ordered_path);
+			else
+			{
+				/*
+				 * If we can't find a sorted path, just give up trying to
+				 * generate a list of correctly sorted child paths.  This can
+				 * happen when type coercion was added to the targetlist due
+				 * to mismatching types from the union children.
+				 */
+				try_sorted = false;
+			}
+		}
 
 		if (consider_parallel)
 		{
@@ -626,28 +919,21 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
 	result_rel->reltarget = create_pathtarget(root, tlist);
 	result_rel->consider_parallel = consider_parallel;
+	result_rel->consider_startup = (root->tuple_fraction > 0);
 
 	/*
-	 * Append the child results together.
+	 * Append the child results together using the cheapest paths from each
+	 * union child.
 	 */
-	path = (Path *) create_append_path(root, result_rel, pathlist, NIL,
-									   NIL, NULL, 0, false, -1);
-
-	/*
-	 * For UNION ALL, we just need the Append path.  For UNION, need to add
-	 * node(s) to remove duplicates.
-	 */
-	if (!op->all)
-		path = make_union_unique(op, path, tlist, root);
-
-	add_path(result_rel, path);
+	apath = (Path *) create_append_path(root, result_rel, cheapest_pathlist,
+										NIL, NIL, NULL, 0, false, -1);
 
 	/*
 	 * Estimate number of groups.  For now we just assume the output is unique
 	 * --- this is certainly true for the UNION case, and we want worst-case
 	 * estimates anyway.
 	 */
-	result_rel->rows = path->rows;
+	result_rel->rows = apath->rows;
 
 	/*
 	 * Now consider doing the same thing using the partial paths plus Append
@@ -655,7 +941,7 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 */
 	if (partial_paths_valid)
 	{
-		Path	   *ppath;
+		Path	   *papath;
 		int			parallel_workers = 0;
 
 		/* Find the highest number of workers requested for any subpath. */
@@ -684,21 +970,136 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 		}
 		Assert(parallel_workers > 0);
 
-		ppath = (Path *)
+		papath = (Path *)
 			create_append_path(root, result_rel, NIL, partial_pathlist,
-							   NIL, NULL,
-							   parallel_workers, enable_parallel_append,
-							   -1);
-		ppath = (Path *)
-			create_gather_path(root, result_rel, ppath,
+							   NIL, NULL, parallel_workers,
+							   enable_parallel_append, -1);
+		gpath = (Path *)
+			create_gather_path(root, result_rel, papath,
 							   result_rel->reltarget, NULL, NULL);
-		if (!op->all)
-			ppath = make_union_unique(op, ppath, tlist, root);
-		add_path(result_rel, ppath);
 	}
 
-	/* Undo effects of possibly forcing tuple_fraction to 0 */
-	root->tuple_fraction = save_fraction;
+	if (!op->all)
+	{
+		double		dNumGroups;
+		bool		can_sort = grouping_is_sortable(groupList);
+		bool		can_hash = grouping_is_hashable(groupList);
+
+		/*
+		 * XXX for the moment, take the number of distinct groups as equal to
+		 * the total input size, i.e., the worst case.  This is too
+		 * conservative, but it's not clear how to get a decent estimate of
+		 * the true size.  One should note as well the propensity of novices
+		 * to write UNION rather than UNION ALL even when they don't expect
+		 * any duplicates...
+		 */
+		dNumGroups = apath->rows;
+
+		if (can_hash)
+		{
+			Path	   *path;
+
+			/*
+			 * Try a hash aggregate plan on 'apath'.  This is the cheapest
+			 * available path containing each append child.
+			 */
+			path = (Path *) create_agg_path(root,
+											result_rel,
+											apath,
+											create_pathtarget(root, tlist),
+											AGG_HASHED,
+											AGGSPLIT_SIMPLE,
+											groupList,
+											NIL,
+											NULL,
+											dNumGroups);
+			add_path(result_rel, path);
+
+			/* Try hash aggregate on the Gather path, if valid */
+			if (gpath != NULL)
+			{
+				/* Hashed aggregate plan --- no sort needed */
+				path = (Path *) create_agg_path(root,
+												result_rel,
+												gpath,
+												create_pathtarget(root, tlist),
+												AGG_HASHED,
+												AGGSPLIT_SIMPLE,
+												groupList,
+												NIL,
+												NULL,
+												dNumGroups);
+				add_path(result_rel, path);
+			}
+		}
+
+		if (can_sort)
+		{
+			Path	   *path = apath;
+
+			if (groupList != NIL)
+				path = (Path *) create_sort_path(root, result_rel, path,
+												 make_pathkeys_for_sortclauses(root, groupList, tlist),
+												 -1.0);
+
+			path = (Path *) create_upper_unique_path(root,
+													 result_rel,
+													 path,
+													 list_length(path->pathkeys),
+													 dNumGroups);
+
+			add_path(result_rel, path);
+
+			/* Try Sort -> Unique on the Gather path, if set */
+			if (gpath != NULL)
+			{
+				path = gpath;
+
+				path = (Path *) create_sort_path(root, result_rel, path,
+												 make_pathkeys_for_sortclauses(root, groupList, tlist),
+												 -1.0);
+
+				path = (Path *) create_upper_unique_path(root,
+														 result_rel,
+														 path,
+														 list_length(path->pathkeys),
+														 dNumGroups);
+				add_path(result_rel, path);
+			}
+		}
+
+		/*
+		 * Try making a MergeAppend path if we managed to find a path with the
+		 * correct pathkeys in each union child query.
+		 */
+		if (try_sorted && groupList != NIL)
+		{
+			Path	   *path;
+
+			path = (Path *) create_merge_append_path(root,
+													 result_rel,
+													 ordered_pathlist,
+													 union_pathkeys,
+													 NULL);
+
+			/* and make the MergeAppend unique */
+			path = (Path *) create_upper_unique_path(root,
+													 result_rel,
+													 path,
+													 list_length(tlist),
+													 path->rows);
+
+			add_path(result_rel, path);
+		}
+	}
+	else
+	{
+		/* UNION ALL */
+		add_path(result_rel, apath);
+
+		if (gpath != NULL)
+			add_path(result_rel, gpath);
+	}
 
 	return result_rel;
 }
@@ -724,6 +1125,8 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
 			   *tlist,
 			   *groupList,
 			   *pathlist;
+	bool		lpath_trivial_tlist,
+				rpath_trivial_tlist;
 	double		dLeftGroups,
 				dRightGroups,
 				dNumGroups,
@@ -743,14 +1146,22 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
 								  false, 0,
 								  refnames_tlist,
 								  &lpath_tlist,
+								  &lpath_trivial_tlist,
 								  &dLeftGroups);
+	if (lrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, lrel, lpath_trivial_tlist, lpath_tlist,
+								NIL);
 	lpath = lrel->cheapest_total_path;
 	rrel = recurse_set_operations(op->rarg, root,
 								  op->colTypes, op->colCollations,
 								  false, 1,
 								  refnames_tlist,
 								  &rpath_tlist,
+								  &rpath_trivial_tlist,
 								  &dRightGroups);
+	if (rrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, rrel, rpath_trivial_tlist, rpath_tlist,
+								NIL);
 	rpath = rrel->cheapest_total_path;
 
 	/* Undo effects of forcing tuple_fraction to 0 */
@@ -887,13 +1298,16 @@ static List *
 plan_union_children(PlannerInfo *root,
 					SetOperationStmt *top_union,
 					List *refnames_tlist,
-					List **tlist_list)
+					List **tlist_list,
+					List **istrivial_tlist)
 {
 	List	   *pending_rels = list_make1(top_union);
 	List	   *result = NIL;
 	List	   *child_tlist;
+	bool		trivial_tlist;
 
 	*tlist_list = NIL;
+	*istrivial_tlist = NIL;
 
 	while (pending_rels != NIL)
 	{
@@ -932,75 +1346,15 @@ plan_union_children(PlannerInfo *root,
 														false, -1,
 														refnames_tlist,
 														&child_tlist,
+														&trivial_tlist,
 														NULL));
 		*tlist_list = lappend(*tlist_list, child_tlist);
+		*istrivial_tlist = lappend_int(*istrivial_tlist, trivial_tlist);
 	}
 
 	return result;
 }
 
-/*
- * Add nodes to the given path tree to unique-ify the result of a UNION.
- */
-static Path *
-make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
-				  PlannerInfo *root)
-{
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
-	List	   *groupList;
-	double		dNumGroups;
-
-	/* Identify the grouping semantics */
-	groupList = generate_setop_grouplist(op, tlist);
-
-	/*
-	 * XXX for the moment, take the number of distinct groups as equal to the
-	 * total input size, ie, the worst case.  This is too conservative, but
-	 * it's not clear how to get a decent estimate of the true size.  One
-	 * should note as well the propensity of novices to write UNION rather
-	 * than UNION ALL even when they don't expect any duplicates...
-	 */
-	dNumGroups = path->rows;
-
-	/* Decide whether to hash or sort */
-	if (choose_hashed_setop(root, groupList, path,
-							dNumGroups, dNumGroups,
-							"UNION"))
-	{
-		/* Hashed aggregate plan --- no sort needed */
-		path = (Path *) create_agg_path(root,
-										result_rel,
-										path,
-										create_pathtarget(root, tlist),
-										AGG_HASHED,
-										AGGSPLIT_SIMPLE,
-										groupList,
-										NIL,
-										NULL,
-										dNumGroups);
-	}
-	else
-	{
-		/* Sort and Unique */
-		if (groupList)
-			path = (Path *)
-				create_sort_path(root,
-								 result_rel,
-								 path,
-								 make_pathkeys_for_sortclauses(root,
-															   groupList,
-															   tlist),
-								 -1.0);
-		path = (Path *) create_upper_unique_path(root,
-												 result_rel,
-												 path,
-												 list_length(path->pathkeys),
-												 dNumGroups);
-	}
-
-	return path;
-}
-
 /*
  * postprocess_setop_rel - perform steps required after adding paths
  */
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 534692bee1..b3069516b2 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -397,6 +397,8 @@ struct PlannerInfo
 	List	   *distinct_pathkeys;
 	/* sortClause pathkeys, if any */
 	List	   *sort_pathkeys;
+	/* set operator pathkeys, if any */
+	List	   *setop_pathkeys;
 
 	/* Canonicalised partition schemes used in the query. */
 	List	   *part_schemes pg_node_attr(read_write_ignore);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 0e8a9c94ba..1165e98c5b 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -174,6 +174,9 @@ extern void add_child_join_rel_equivalences(PlannerInfo *root,
 											AppendRelInfo **appinfos,
 											RelOptInfo *parent_joinrel,
 											RelOptInfo *child_joinrel);
+extern void add_setop_child_rel_equivalences(PlannerInfo *root, Relids relids,
+											 List *tlist,
+											 List *setop_pathkeys);
 extern List *generate_implied_equalities_for_column(PlannerInfo *root,
 													RelOptInfo *rel,
 													ec_matches_callback_type callback,
diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h
index 8e00716dc8..a52dec285d 100644
--- a/src/include/optimizer/prep.h
+++ b/src/include/optimizer/prep.h
@@ -53,6 +53,6 @@ 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/collate.icu.utf8.out b/src/test/regress/expected/collate.icu.utf8.out
index 7a05c75967..3b6c318a63 100644
--- a/src/test/regress/expected/collate.icu.utf8.out
+++ b/src/test/regress/expected/collate.icu.utf8.out
@@ -1396,6 +1396,7 @@ SELECT x FROM test3cs WHERE x ~ 'a';
  abc
 (1 row)
 
+SET enable_hashagg TO off;
 SELECT x FROM test1cs UNION SELECT x FROM test2cs ORDER BY x;
   x  
 -----
@@ -1448,6 +1449,7 @@ SELECT DISTINCT x FROM test3cs ORDER BY x;
  ghi
 (4 rows)
 
+RESET enable_hashagg;
 SELECT count(DISTINCT x) FROM test3cs;
  count 
 -------
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 7fdb685313..5fd54a10b1 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1472,14 +1472,19 @@ explain (costs off) select * from t union select * from t order by 1,3;
    Sort Key: t.a, t.c
    Presorted Key: t.a
    ->  Unique
-         ->  Sort
+         ->  Merge Append
                Sort Key: t.a, t.b, t.c
-               ->  Gather
+               ->  Gather Merge
                      Workers Planned: 2
-                     ->  Parallel Append
+                     ->  Sort
+                           Sort Key: t.a, t.b, t.c
                            ->  Parallel Seq Scan on t
+               ->  Gather Merge
+                     Workers Planned: 2
+                     ->  Sort
+                           Sort Key: t_1.a, t_1.b, t_1.c
                            ->  Parallel Seq Scan on t t_1
-(11 rows)
+(16 rows)
 
 -- Full sort, not just incremental sort can be pushed below a gather merge path
 -- by generate_useful_gather_paths.
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
index 73e320bad4..b8d6b112f1 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -370,16 +370,16 @@ select count(*) from
 explain (costs off)
 select count(*) from
   ( select unique1 from tenk1 intersect select fivethous from tenk1 ) ss;
-                                     QUERY PLAN                                     
-------------------------------------------------------------------------------------
+                                 QUERY PLAN                                 
+----------------------------------------------------------------------------
  Aggregate
    ->  Subquery Scan on ss
          ->  HashSetOp Intersect
                ->  Append
-                     ->  Subquery Scan on "*SELECT* 2"
-                           ->  Seq Scan on tenk1
                      ->  Subquery Scan on "*SELECT* 1"
-                           ->  Index Only Scan using tenk1_unique1 on tenk1 tenk1_1
+                           ->  Index Only Scan using tenk1_unique1 on tenk1
+                     ->  Subquery Scan on "*SELECT* 2"
+                           ->  Seq Scan on tenk1 tenk1_1
 (8 rows)
 
 select count(*) from
@@ -412,16 +412,17 @@ set enable_hashagg to off;
 explain (costs off)
 select count(*) from
   ( select unique1 from tenk1 union select fivethous from tenk1 ) ss;
-                              QUERY PLAN                              
-----------------------------------------------------------------------
+                           QUERY PLAN                           
+----------------------------------------------------------------
  Aggregate
    ->  Unique
-         ->  Sort
+         ->  Merge Append
                Sort Key: tenk1.unique1
-               ->  Append
-                     ->  Index Only Scan using tenk1_unique1 on tenk1
+               ->  Index Only Scan using tenk1_unique1 on tenk1
+               ->  Sort
+                     Sort Key: tenk1_1.fivethous
                      ->  Seq Scan on tenk1 tenk1_1
-(7 rows)
+(8 rows)
 
 select count(*) from
   ( select unique1 from tenk1 union select fivethous from tenk1 ) ss;
@@ -433,18 +434,18 @@ select count(*) from
 explain (costs off)
 select count(*) from
   ( select unique1 from tenk1 intersect select fivethous from tenk1 ) ss;
-                                        QUERY PLAN                                        
-------------------------------------------------------------------------------------------
+                                    QUERY PLAN                                    
+----------------------------------------------------------------------------------
  Aggregate
    ->  Subquery Scan on ss
          ->  SetOp Intersect
                ->  Sort
-                     Sort Key: "*SELECT* 2".fivethous
+                     Sort Key: "*SELECT* 1".unique1
                      ->  Append
-                           ->  Subquery Scan on "*SELECT* 2"
-                                 ->  Seq Scan on tenk1
                            ->  Subquery Scan on "*SELECT* 1"
-                                 ->  Index Only Scan using tenk1_unique1 on tenk1 tenk1_1
+                                 ->  Index Only Scan using tenk1_unique1 on tenk1
+                           ->  Subquery Scan on "*SELECT* 2"
+                                 ->  Seq Scan on tenk1 tenk1_1
 (10 rows)
 
 select count(*) from
@@ -950,16 +951,8 @@ select except select;
 -- check hashed implementation
 set enable_hashagg = true;
 set enable_sort = false;
-explain (costs off)
-select from generate_series(1,5) union select from generate_series(1,3);
-                           QUERY PLAN                           
-----------------------------------------------------------------
- HashAggregate
-   ->  Append
-         ->  Function Scan on generate_series
-         ->  Function Scan on generate_series generate_series_1
-(4 rows)
-
+-- We've no way to check hashed UNION as the empty pathkeys in the Append are
+-- fine to make use of Unique, which is cheaper than HashAggregate.
 explain (costs off)
 select from generate_series(1,5) intersect select from generate_series(1,3);
                               QUERY PLAN                              
@@ -972,10 +965,6 @@ select from generate_series(1,5) intersect select from generate_series(1,3);
                ->  Function Scan on generate_series generate_series_1
 (6 rows)
 
-select from generate_series(1,5) union select from generate_series(1,3);
---
-(1 row)
-
 select from generate_series(1,5) union all select from generate_series(1,3);
 --
 (8 rows)
@@ -1102,16 +1091,17 @@ explain (costs off)
   UNION
   SELECT * FROM t2) t
  WHERE ab = 'ab';
-                    QUERY PLAN                     
----------------------------------------------------
- HashAggregate
-   Group Key: ((t1.a || t1.b))
-   ->  Append
-         ->  Index Scan using t1_ab_idx on t1
-               Index Cond: ((a || b) = 'ab'::text)
-         ->  Index Only Scan using t2_pkey on t2
-               Index Cond: (ab = 'ab'::text)
-(7 rows)
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: ((t1.a || t1.b))
+         ->  Append
+               ->  Index Scan using t1_ab_idx on t1
+                     Index Cond: ((a || b) = 'ab'::text)
+               ->  Index Only Scan using t2_pkey on t2
+                     Index Cond: (ab = 'ab'::text)
+(8 rows)
 
 --
 -- Test that ORDER BY for UNION ALL can be pushed down to inheritance
diff --git a/src/test/regress/sql/collate.icu.utf8.sql b/src/test/regress/sql/collate.icu.utf8.sql
index 3db9e25913..96d5d6b11c 100644
--- a/src/test/regress/sql/collate.icu.utf8.sql
+++ b/src/test/regress/sql/collate.icu.utf8.sql
@@ -555,6 +555,7 @@ SELECT x FROM test3cs WHERE x LIKE 'a%';
 SELECT x FROM test3cs WHERE x ILIKE 'a%';
 SELECT x FROM test3cs WHERE x SIMILAR TO 'a%';
 SELECT x FROM test3cs WHERE x ~ 'a';
+SET enable_hashagg TO off;
 SELECT x FROM test1cs UNION SELECT x FROM test2cs ORDER BY x;
 SELECT x FROM test2cs UNION SELECT x FROM test1cs ORDER BY x;
 SELECT x FROM test1cs INTERSECT SELECT x FROM test2cs;
@@ -562,6 +563,7 @@ SELECT x FROM test2cs INTERSECT SELECT x FROM test1cs;
 SELECT x FROM test1cs EXCEPT SELECT x FROM test2cs;
 SELECT x FROM test2cs EXCEPT SELECT x FROM test1cs;
 SELECT DISTINCT x FROM test3cs ORDER BY x;
+RESET enable_hashagg;
 SELECT count(DISTINCT x) FROM test3cs;
 SELECT x, count(*) FROM test3cs GROUP BY x ORDER BY x;
 SELECT x, row_number() OVER (ORDER BY x), rank() OVER (ORDER BY x) FROM test3cs ORDER BY x;
diff --git a/src/test/regress/sql/union.sql b/src/test/regress/sql/union.sql
index 6c509ac80c..3be29acb04 100644
--- a/src/test/regress/sql/union.sql
+++ b/src/test/regress/sql/union.sql
@@ -302,12 +302,11 @@ select except select;
 set enable_hashagg = true;
 set enable_sort = false;
 
-explain (costs off)
-select from generate_series(1,5) union select from generate_series(1,3);
+-- We've no way to check hashed UNION as the empty pathkeys in the Append are
+-- fine to make use of Unique, which is cheaper than HashAggregate.
 explain (costs off)
 select from generate_series(1,5) intersect select from generate_series(1,3);
 
-select from generate_series(1,5) union select from generate_series(1,3);
 select from generate_series(1,5) union all select from generate_series(1,3);
 select from generate_series(1,5) intersect select from generate_series(1,3);
 select from generate_series(1,5) intersect all select from generate_series(1,3);

From 52250debeeb6dd70e4f3cb2aa992dda7c091eb4c Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Tue, 12 Mar 2024 22:33:11 +1300
Subject: [PATCH v0] Enhance convert_subquery_pathkeys

Have this try to use query_pathkeys if those keys are compatible with
the subquery.  This can eliminate sorting of subqueries by working a bit
harder to see if certain pathkeys in the subquery are not present
because they're redundant.

A bit more work needs to be done here.  subquery_matches_pathkeys()
needs to be further enhanced to search the next query_pathkey once it
matches.  This will allow queries such as:

select * from (select a,b from t where a=b limit 10) order by a,b;

to use an index on t(a,b).  subquery_matches_pathkeys currently fails to
match this as it skips to the next sub_pathkey, of which there is none.
---
 src/backend/optimizer/path/pathkeys.c | 123 ++++++++++++++++++++++++++
 1 file changed, 123 insertions(+)

diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 3f1a4050e7..8003821e06 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1049,6 +1049,120 @@ build_expression_pathkey(PlannerInfo *root,
 	return pathkeys;
 }
 
+static EquivalenceClass *
+find_subquery_eclass(EquivalenceClass *eclass, RelOptInfo *rel, List *subquery_tlist)
+{
+	ListCell *lc;
+
+	foreach (lc, eclass->ec_members)
+	{
+		EquivalenceMember *em = lfirst_node(EquivalenceMember, lc);
+		ListCell *lc2;
+
+		/*
+		 * Ignore child members unless they belong to the requested rel.
+		 */
+		if (em->em_is_child && !bms_is_subset(em->em_relids, rel->relids))
+			continue;
+
+		foreach (lc2, subquery_tlist)
+		{
+			TargetEntry *tle = (TargetEntry *) lfirst(lc2);
+			EquivalenceClass *sub_ec;
+			Var *outer_var;
+
+			outer_var = find_var_for_subquery_tle(rel, tle);
+
+			if (!equal(outer_var, em->em_expr))
+				continue;
+
+			sub_ec = get_eclass_for_sort_expr(rel->subroot,
+											  (Expr *) tle->expr,
+											  eclass->ec_opfamilies,
+											  em->em_datatype,
+											  exprCollation((Node *) em->em_expr),
+											  0,
+											  NULL,
+											  false);
+
+			if (sub_ec)
+				return sub_ec;
+		}
+	}
+
+	return NULL;
+}
+
+/*
+ * subquery_matches_pathkeys
+ *		Check if the subquery in 'rel' with the given 'subquery_pathkeys'
+ *		implements 'query_pathkeys', taking into account that some of the
+ *		given 'subquery_pathkeys' may have been marked as redundant or
+ *		consecutive query_pathkeys may have been merged into a single
+ *		EquivalenceClass in the subquery.
+ *
+ * 'query_pathkeys' must not be an empty List.
+ */
+static bool
+subquery_matches_pathkeys(PlannerInfo *root, RelOptInfo *rel,
+						  List *subquery_pathkeys, List *subquery_tlist,
+						  List *query_pathkeys)
+{
+	ListCell *sub_lc = list_head(subquery_pathkeys);
+	ListCell *lc;
+
+	Assert(query_pathkeys != NIL);
+
+	foreach (lc, query_pathkeys)
+	{
+		PathKey *pathkey = lfirst_node(PathKey, lc);
+		EquivalenceClass *eclass = pathkey->pk_eclass;
+		EquivalenceClass *sub_eclass;
+		PathKey *sub_pathkey;
+
+		/*
+		 * Look through every member in this eclass and look to see if there's
+		 * a subquery target mentioning one of the eclass's members.  If found
+		 * search for an eclass for that subquery target and return it.
+		 */
+		sub_eclass = find_subquery_eclass(eclass, rel, subquery_tlist);
+
+		if (sub_eclass == NULL)
+			return false;
+
+		if (EC_MUST_BE_REDUNDANT(sub_eclass))
+		{
+			/*
+			 * The subquery pathkey must have been removed because it's redundant.
+			 * skip to the next query_pathkey
+			 */
+			continue;
+		}
+
+		if (sub_lc == NULL)
+			return false;
+
+		sub_pathkey = lfirst_node(PathKey, sub_lc);
+
+		/* if the eclass matches then skip to the next sub_pathkey */
+		if (sub_eclass == sub_pathkey->pk_eclass)
+		{
+			/* matching eclasses.  Check for matching properties */
+			if (sub_pathkey->pk_strategy != pathkey->pk_strategy ||
+				sub_pathkey->pk_nulls_first != pathkey->pk_nulls_first)
+				return false;
+
+			/* 1:1 match. Skip to the next pathkeys */
+			/* TODO try matching this sub_pathkey to the next query_pathkey */
+			sub_lc = lnext(subquery_pathkeys, sub_lc);
+		}
+		else
+			return false;
+	}
+
+	return true;
+}
+
 /*
  * convert_subquery_pathkeys
  *	  Build a pathkeys list that describes the ordering of a subquery's
@@ -1075,6 +1189,15 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 	int			outer_query_keys = list_length(root->query_pathkeys);
 	ListCell   *i;
 
+	/* XXX should this be a List of Lists of interesting pathkeys? */
+	if (root->query_pathkeys != NIL &&
+		subquery_matches_pathkeys(root,
+								  rel,
+								  subquery_pathkeys,
+								  subquery_tlist,
+								  root->query_pathkeys))
+		return root->query_pathkeys;
+
 	foreach(i, subquery_pathkeys)
 	{
 		PathKey    *sub_pathkey = (PathKey *) lfirst(i);
-- 
2.40.1.windows.1

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 58a603ac56..70fb791306 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -11495,6 +11495,10 @@ DROP INDEX base_tbl1_idx;
 DROP INDEX base_tbl2_idx;
 DROP INDEX async_p3_idx;
 -- UNION queries
+SET enable_sort TO off;
+SET enable_incremental_sort TO off;
+-- Adjust fdw_startup_cost so that we get an unordered path in the Append.
+ALTER SERVER loopback2 OPTIONS (ADD fdw_startup_cost '0.00');
 EXPLAIN (VERBOSE, COSTS OFF)
 INSERT INTO result_tbl
 (SELECT a, b, 'AAA' || c FROM async_p1 ORDER BY a LIMIT 10)
@@ -11576,6 +11580,9 @@ SELECT * FROM result_tbl ORDER BY a;
 (12 rows)
 
 DELETE FROM result_tbl;
+RESET enable_incremental_sort;
+RESET enable_sort;
+ALTER SERVER loopback2 OPTIONS (DROP fdw_startup_cost);
 -- Disable async execution if we use gating Result nodes for pseudoconstant
 -- quals
 EXPLAIN (VERBOSE, COSTS OFF)
diff --git a/contrib/postgres_fdw/sql/postgres_fdw.sql b/contrib/postgres_fdw/sql/postgres_fdw.sql
index e3d147de6d..5fffc4c53b 100644
--- a/contrib/postgres_fdw/sql/postgres_fdw.sql
+++ b/contrib/postgres_fdw/sql/postgres_fdw.sql
@@ -3877,6 +3877,11 @@ DROP INDEX base_tbl2_idx;
 DROP INDEX async_p3_idx;
 
 -- UNION queries
+SET enable_sort TO off;
+SET enable_incremental_sort TO off;
+-- Adjust fdw_startup_cost so that we get an unordered path in the Append.
+ALTER SERVER loopback2 OPTIONS (ADD fdw_startup_cost '0.00');
+
 EXPLAIN (VERBOSE, COSTS OFF)
 INSERT INTO result_tbl
 (SELECT a, b, 'AAA' || c FROM async_p1 ORDER BY a LIMIT 10)
@@ -3903,6 +3908,10 @@ UNION ALL
 SELECT * FROM result_tbl ORDER BY a;
 DELETE FROM result_tbl;
 
+RESET enable_incremental_sort;
+RESET enable_sort;
+ALTER SERVER loopback2 OPTIONS (DROP fdw_startup_cost);
+
 -- Disable async execution if we use gating Result nodes for pseudoconstant
 -- quals
 EXPLAIN (VERBOSE, COSTS OFF)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 4bd60a09c6..c036911309 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -2867,6 +2867,58 @@ add_child_join_rel_equivalences(PlannerInfo *root,
 	MemoryContextSwitchTo(oldcontext);
 }
 
+/*
+ * add_setop_child_rel_equivalences
+ *		Add equivalence members for each non-resjunk target in 'child_tlist'
+ *		to the EquivalenceClass in the corresponding setop_pathkey's pk_class.
+ *
+ * 'root' is the PlannerInfo belonging to the top-level set operation.
+ * 'child_relids' are the Relids of the child relation we're adding
+ * EquivalenceMembers for.
+ * 'child_tlist' is the target list for the setop child relation.  The target
+ * list expressions are what we add as EquivalenceMembers.
+ * 'setop_pathkeys' is a list of PathKeys which must contain an entry for each
+ * non-resjunk target in 'child_tlist'.
+ */
+void
+add_setop_child_rel_equivalences(PlannerInfo *root, Relids child_relids,
+								 List *child_tlist, List *setop_pathkeys)
+{
+	ListCell   *lc;
+	ListCell   *lc2 = list_head(setop_pathkeys);
+
+	foreach(lc, child_tlist)
+	{
+		TargetEntry *tle = lfirst_node(TargetEntry, lc);
+		EquivalenceMember *parent_em;
+		PathKey    *pk;
+
+		if (tle->resjunk)
+			continue;
+
+		if (lc2 == NULL)
+			elog(ERROR, "too few pathkeys for set operation");
+
+		pk = lfirst_node(PathKey, lc2);
+		parent_em = linitial(pk->pk_eclass->ec_members);
+
+		/*
+		 * We can safely pass the parent member as the first member in the
+		 * ec_members list as this is added first in generate_union_paths,
+		 * likewise, the JoinDomain can be that of the initial member of the
+		 * Pathkey's EquivalenceClass.
+		 */
+		add_eq_member(pk->pk_eclass,
+					  tle->expr,
+					  child_relids,
+					  parent_em->em_jdomain,
+					  parent_em,
+					  exprType((Node *) tle->expr));
+
+		lc2 = lnext(setop_pathkeys, lc2);
+	}
+}
+
 
 /*
  * generate_implied_equalities_for_column
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 3f1a4050e7..1d61881a6b 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -2191,6 +2191,22 @@ pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
 	return n;
 }
 
+/*
+ * pathkeys_useful_for_setop
+ *		Count the number of leading common pathkeys root's 'setop_pathkeys' in
+ *		'pathkeys'.
+ */
+static int
+pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
+{
+	int			n_common_pathkeys;
+
+	(void) pathkeys_count_contained_in(root->setop_pathkeys, pathkeys,
+									   &n_common_pathkeys);
+
+	return n_common_pathkeys;
+}
+
 /*
  * truncate_useless_pathkeys
  *		Shorten the given pathkey list to just the useful pathkeys.
@@ -2208,6 +2224,9 @@ truncate_useless_pathkeys(PlannerInfo *root,
 	if (nuseful2 > nuseful)
 		nuseful = nuseful2;
 	nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
+	if (nuseful2 > nuseful)
+		nuseful = nuseful2;
+	nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
 	if (nuseful2 > nuseful)
 		nuseful = nuseful2;
 
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 443ab08d75..402c573812 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -54,6 +54,7 @@
 #include "optimizer/tlist.h"
 #include "parser/analyze.h"
 #include "parser/parse_agg.h"
+#include "parser/parse_clause.h"
 #include "parser/parse_relation.h"
 #include "parser/parsetree.h"
 #include "partitioning/partdesc.h"
@@ -119,6 +120,8 @@ typedef struct
 {
 	List	   *activeWindows;	/* active windows, if any */
 	grouping_sets_data *gset_data;	/* grouping sets data, if any */
+	SetOperationStmt *setop;	/* parent set operation or NULL if not a
+								 * subquery belonging to a set operation */
 } standard_qp_extra;
 
 /* Local functions */
@@ -249,6 +252,8 @@ static bool group_by_has_partkey(RelOptInfo *input_rel,
 								 List *targetList,
 								 List *groupClause);
 static int	common_prefix_cmp(const void *a, const void *b);
+static List *generate_setop_child_grouplist(SetOperationStmt *op,
+											List *targetlist);
 
 
 /*****************************************************************************
@@ -1500,6 +1505,18 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 		qp_extra.activeWindows = activeWindows;
 		qp_extra.gset_data = gset_data;
 
+		/*
+		 * Check if we're a subquery for a set operation.  If we are, store
+		 * the SetOperationStmt in qp_extra.
+		 */
+		if (root->parent_root != NULL &&
+			root->parent_root->parse->setOperations != NULL &&
+			IsA(root->parent_root->parse->setOperations, SetOperationStmt))
+			qp_extra.setop =
+				(SetOperationStmt *) root->parent_root->parse->setOperations;
+		else
+			qp_extra.setop = NULL;
+
 		/*
 		 * Generate the best unsorted and presorted paths for the scan/join
 		 * portion of this Query, ie the processing represented by the
@@ -3433,6 +3450,27 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 									  parse->sortClause,
 									  tlist);
 
+	/* setting setop_pathkeys might be useful to the union planner */
+	if (qp_extra->setop != NULL &&
+		set_operation_ordered_results_useful(qp_extra->setop))
+	{
+		List	   *groupClauses;
+		bool		sortable;
+
+		groupClauses = generate_setop_child_grouplist(qp_extra->setop, tlist);
+
+		root->setop_pathkeys =
+			make_pathkeys_for_sortclauses_extended(root,
+												   &groupClauses,
+												   tlist,
+												   false,
+												   &sortable);
+		if (!sortable)
+			root->setop_pathkeys = NIL;
+	}
+	else
+		root->setop_pathkeys = NIL;
+
 	/*
 	 * Figure out whether we want a sorted result from query_planner.
 	 *
@@ -3442,7 +3480,9 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 	 * sortable DISTINCT clause that's more rigorous than the ORDER BY clause,
 	 * we try to produce output that's sufficiently well sorted for the
 	 * DISTINCT.  Otherwise, if there is an ORDER BY clause, we want to sort
-	 * by the ORDER BY clause.
+	 * by the ORDER BY clause.  Otherwise, if we're a subquery being planned
+	 * for a set operation which can benefit from presorted results and have a
+	 * sortable targetlist, we want to sort by the target list.
 	 *
 	 * Note: if we have both ORDER BY and GROUP BY, and ORDER BY is a superset
 	 * of GROUP BY, it would be tempting to request sort by ORDER BY --- but
@@ -3460,6 +3500,8 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 		root->query_pathkeys = root->distinct_pathkeys;
 	else if (root->sort_pathkeys)
 		root->query_pathkeys = root->sort_pathkeys;
+	else if (root->setop_pathkeys != NIL)
+		root->query_pathkeys = root->setop_pathkeys;
 	else
 		root->query_pathkeys = NIL;
 }
@@ -7855,3 +7897,47 @@ group_by_has_partkey(RelOptInfo *input_rel,
 
 	return true;
 }
+
+/*
+ * generate_setop_child_grouplist
+ *		Build a SortGroupClause list defining the sort/grouping properties
+ *		of the child of a set operation.
+ *
+ * This is similar to generate_setop_grouplist() but differs as the setop
+ * child query's targetlist entries may already have a tleSortGroupRef
+ * assigned for other purposes, such as GROUP BYs.  Here we keep the
+ * SortGroupClause list in the same order as 'op' groupClauses and just adjust
+ * the tleSortGroupRef to reference the TargetEntry's 'ressortgroupref'.
+ */
+static List *
+generate_setop_child_grouplist(SetOperationStmt *op, List *targetlist)
+{
+	List	   *grouplist = copyObject(op->groupClauses);
+	ListCell   *lg;
+	ListCell   *lt;
+
+	lg = list_head(grouplist);
+	foreach(lt, targetlist)
+	{
+		TargetEntry *tle = (TargetEntry *) lfirst(lt);
+		SortGroupClause *sgc;
+
+		if (tle->resjunk)
+		{
+			/* resjunk columns should not have sortgrouprefs */
+			Assert(tle->ressortgroupref == 0);
+			continue;			/* ignore resjunk columns */
+		}
+
+		/* non-resjunk columns should have grouping clauses */
+		Assert(lg != NULL);
+		sgc = (SortGroupClause *) lfirst(lg);
+		lg = lnext(grouplist, lg);
+
+		/* assign a tleSortGroupRef, or reuse the existing one */
+		sgc->tleSortGroupRef = assignSortGroupRef(tle, targetlist);
+		tle->ressortgroupref = sgc->tleSortGroupRef;
+	}
+	Assert(lg == NULL);
+	return grouplist;
+}
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index a5bfd7a3f7..a5ff8329b8 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -43,11 +43,15 @@ static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
 										  bool junkOK,
 										  int flag, List *refnames_tlist,
 										  List **pTargetList,
+										  bool *istrivial_tlist,
 										  double *pNumGroups);
 static RelOptInfo *generate_recursion_path(SetOperationStmt *setOp,
 										   PlannerInfo *root,
 										   List *refnames_tlist,
 										   List **pTargetList);
+static void build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
+									bool trivial_tlist, List *child_tlist,
+									List *interesting_pathkeys);
 static RelOptInfo *generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 										List *refnames_tlist,
 										List **pTargetList);
@@ -57,9 +61,8 @@ static RelOptInfo *generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *ro
 static List *plan_union_children(PlannerInfo *root,
 								 SetOperationStmt *top_union,
 								 List *refnames_tlist,
-								 List **tlist_list);
-static Path *make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
-							   PlannerInfo *root);
+								 List **tlist_list,
+								 List **istrivial_tlist);
 static void postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
 								Path *input_path,
@@ -152,6 +155,8 @@ plan_set_operations(PlannerInfo *root)
 	}
 	else
 	{
+		bool		trivial_tlist;
+
 		/*
 		 * Recurse on setOperations tree to generate paths for set ops. The
 		 * final output paths should have just the column types shown as the
@@ -163,6 +168,7 @@ plan_set_operations(PlannerInfo *root)
 										   true, -1,
 										   leftmostQuery->targetList,
 										   &top_tlist,
+										   &trivial_tlist,
 										   NULL);
 	}
 
@@ -172,6 +178,33 @@ 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.
+	 */
+
+	/* sorted paths are not deemed of any additional use for this setop */
+	return false;
+}
+
 /*
  * recurse_set_operations
  *	  Recursively handle one step in a tree of set operations
@@ -192,6 +225,10 @@ plan_set_operations(PlannerInfo *root)
  * the logic in this file depends on flag columns being marked resjunk.
  * Pending a redesign of how that works, this is the easy way out.
  *
+ * 'istrivial_tlist' is an output parameter and is set to true when the
+ * pTargetList is deemed to be a trivial target list as determined by
+ * generate_setop_tlist().
+ *
  * We don't have to care about typmods here: the only allowed difference
  * between set-op input and output typmods is input is a specific typmod
  * and output is -1, and that does not require a coercion.
@@ -202,9 +239,12 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   bool junkOK,
 					   int flag, List *refnames_tlist,
 					   List **pTargetList,
+					   bool *istrivial_tlist,
 					   double *pNumGroups)
 {
-	RelOptInfo *rel = NULL;		/* keep compiler quiet */
+	RelOptInfo *rel;
+
+	*istrivial_tlist = true;	/* for now */
 
 	/* Guard against stack overflow due to overly complex setop nests */
 	check_stack_depth();
@@ -216,8 +256,6 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		Query	   *subquery = rte->subquery;
 		PlannerInfo *subroot;
 		RelOptInfo *final_rel;
-		Path	   *subpath;
-		Path	   *path;
 		List	   *tlist;
 		bool		trivial_tlist;
 
@@ -254,61 +292,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 		/* Return the fully-fledged tlist to caller, too */
 		*pTargetList = tlist;
-
-		/*
-		 * Mark rel with estimated output rows, width, etc.  Note that we have
-		 * to do this before generating outer-query paths, else
-		 * cost_subqueryscan is not happy.
-		 */
-		set_subquery_size_estimates(root, rel);
-
-		/*
-		 * Since we may want to add a partial path to this relation, we must
-		 * set its consider_parallel flag correctly.
-		 */
+		*istrivial_tlist = trivial_tlist;
 		final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
-		rel->consider_parallel = final_rel->consider_parallel;
-
-		/*
-		 * For the moment, we consider only a single Path for the subquery.
-		 * This should change soon (make it look more like
-		 * set_subquery_pathlist).
-		 */
-		subpath = get_cheapest_fractional_path(final_rel,
-											   root->tuple_fraction);
-
-		/*
-		 * Stick a SubqueryScanPath atop that.
-		 *
-		 * We don't bother to determine the subquery's output ordering since
-		 * it won't be reflected in the set-op result anyhow; so just label
-		 * the SubqueryScanPath with nil pathkeys.  (XXX that should change
-		 * soon too, likely.)
-		 */
-		path = (Path *) create_subqueryscan_path(root, rel, subpath,
-												 trivial_tlist,
-												 NIL, NULL);
-
-		add_path(rel, path);
-
-		/*
-		 * If we have a partial path for the child relation, we can use that
-		 * to build a partial path for this relation.  But there's no point in
-		 * considering any path but the cheapest.
-		 */
-		if (rel->consider_parallel && bms_is_empty(rel->lateral_relids) &&
-			final_rel->partial_pathlist != NIL)
-		{
-			Path	   *partial_subpath;
-			Path	   *partial_path;
-
-			partial_subpath = linitial(final_rel->partial_pathlist);
-			partial_path = (Path *)
-				create_subqueryscan_path(root, rel, partial_subpath,
-										 trivial_tlist,
-										 NIL, NULL);
-			add_partial_path(rel, partial_path);
-		}
 
 		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
@@ -333,11 +318,11 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 			if (subquery->groupClause || subquery->groupingSets ||
 				subquery->distinctClause ||
 				subroot->hasHavingQual || subquery->hasAggs)
-				*pNumGroups = subpath->rows;
+				*pNumGroups = final_rel->rows;
 			else
 				*pNumGroups = estimate_num_groups(subroot,
 												  get_tlist_exprs(subroot->parse->targetList, false),
-												  subpath->rows,
+												  final_rel->rows,
 												  NULL,
 												  NULL);
 		}
@@ -386,6 +371,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 												*pTargetList,
 												refnames_tlist,
 												&trivial_tlist);
+			*istrivial_tlist = trivial_tlist;
 			target = create_pathtarget(root, *pTargetList);
 
 			/* Apply projection to each path */
@@ -416,16 +402,16 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 				lfirst(lc) = path;
 			}
 		}
+		postprocess_setop_rel(root, rel);
 	}
 	else
 	{
 		elog(ERROR, "unrecognized node type: %d",
 			 (int) nodeTag(setOp));
 		*pTargetList = NIL;
+		rel = NULL;				/* keep compiler quiet */
 	}
 
-	postprocess_setop_rel(root, rel);
-
 	return rel;
 }
 
@@ -444,7 +430,9 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	Path	   *lpath;
 	Path	   *rpath;
 	List	   *lpath_tlist;
+	bool		lpath_trivial_tlist;
 	List	   *rpath_tlist;
+	bool		rpath_trivial_tlist;
 	List	   *tlist;
 	List	   *groupList;
 	double		dNumGroups;
@@ -464,7 +452,10 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 								  false, -1,
 								  refnames_tlist,
 								  &lpath_tlist,
-								  NULL);
+								  &lpath_trivial_tlist, NULL);
+	if (lrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, lrel, lpath_trivial_tlist, lpath_tlist,
+								NIL);
 	lpath = lrel->cheapest_total_path;
 	/* The right path will want to look at the left one ... */
 	root->non_recursive_path = lpath;
@@ -473,7 +464,11 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 								  false, -1,
 								  refnames_tlist,
 								  &rpath_tlist,
+								  &rpath_trivial_tlist,
 								  NULL);
+	if (rrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, rrel, rpath_trivial_tlist, rpath_tlist,
+								NIL);
 	rpath = rrel->cheapest_total_path;
 	root->non_recursive_path = NULL;
 
@@ -535,6 +530,166 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	return result_rel;
 }
 
+/*
+ * build_setop_child_paths
+ *		Build paths for the set op child relation denoted by 'rel'.
+ *
+ * If 'interesting_pathkeys' is non-NIL then also include paths that suit
+ * these pathkeys, sorting any unsorted paths as required.
+ */
+static void
+build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
+						bool trivial_tlist, List *child_tlist,
+						List *interesting_pathkeys)
+{
+	RelOptInfo *final_rel;
+	List	   *setop_pathkeys = rel->subroot->setop_pathkeys;
+	ListCell   *lc;
+
+	/* it can't be a set op child rel if it's not a subquery */
+	Assert(rel->rtekind == RTE_SUBQUERY);
+
+	/* when sorting is needed, add child rel equivalences */
+	if (interesting_pathkeys != NIL)
+		add_setop_child_rel_equivalences(root,
+										 rel->relids,
+										 child_tlist,
+										 interesting_pathkeys);
+
+	/*
+	 * Mark rel with estimated output rows, width, etc.  Note that we have to
+	 * do this before generating outer-query paths, else cost_subqueryscan is
+	 * not happy.
+	 */
+	set_subquery_size_estimates(root, rel);
+
+	/*
+	 * Since we may want to add a partial path to this relation, we must set
+	 * its consider_parallel flag correctly.
+	 */
+	final_rel = fetch_upper_rel(rel->subroot, UPPERREL_FINAL, NULL);
+	rel->consider_parallel = final_rel->consider_parallel;
+
+	/* Generate subquery scan paths for any interesting path in final_rel */
+	foreach(lc, final_rel->pathlist)
+	{
+		Path	   *subpath = (Path *) lfirst(lc);
+		List	   *pathkeys;
+		Path	   *cheapest_input_path = final_rel->cheapest_total_path;
+		bool		is_sorted;
+		int			presorted_keys;
+
+		/*
+		 * Include the cheapest path as-is so that the set operation can be
+		 * cheaply implemented using a method which does not require the input
+		 * to be sorted.
+		 */
+		if (subpath == cheapest_input_path)
+		{
+			/* Convert subpath's pathkeys to outer representation */
+			pathkeys = convert_subquery_pathkeys(root, rel, subpath->pathkeys,
+												 make_tlist_from_pathtarget(subpath->pathtarget));
+
+			/* Generate outer path using this subpath */
+			add_path(rel, (Path *) create_subqueryscan_path(root,
+															rel,
+															subpath,
+															trivial_tlist,
+															pathkeys,
+															NULL));
+		}
+
+		/* skip dealing with sorted paths if the setop doesn't need them */
+		if (interesting_pathkeys == NIL)
+			continue;
+
+		/*
+		 * Create paths to suit final sort order required for setop_pathkeys.
+		 * Here we'll sort the cheapest input path (if not sorted already) and
+		 * incremental sort any paths which are partially sorted.
+		 */
+		is_sorted = pathkeys_count_contained_in(setop_pathkeys,
+												subpath->pathkeys,
+												&presorted_keys);
+
+		if (!is_sorted)
+		{
+			double		limittuples = rel->subroot->limit_tuples;
+
+			/*
+			 * Try at least sorting the cheapest path and also try
+			 * incrementally sorting any path which is partially sorted
+			 * already (no need to deal with paths which have presorted keys
+			 * when incremental sort is disabled unless it's the cheapest
+			 * input path).
+			 */
+			if (subpath != cheapest_input_path &&
+				(presorted_keys == 0 || !enable_incremental_sort))
+				continue;
+
+			/*
+			 * We've no need to consider both a sort and incremental sort.
+			 * We'll just do a sort if there are no presorted keys and an
+			 * incremental sort when there are presorted keys.
+			 */
+			if (presorted_keys == 0 || !enable_incremental_sort)
+				subpath = (Path *) create_sort_path(rel->subroot,
+													final_rel,
+													subpath,
+													setop_pathkeys,
+													limittuples);
+			else
+				subpath = (Path *) create_incremental_sort_path(rel->subroot,
+																final_rel,
+																subpath,
+																setop_pathkeys,
+																presorted_keys,
+																limittuples);
+		}
+
+		/* Add the sorted path unless the cheapest path is already sorted. */
+		if (subpath != cheapest_input_path)
+		{
+			/* Convert subpath's pathkeys to outer representation */
+			pathkeys = convert_subquery_pathkeys(root, rel, subpath->pathkeys,
+												 make_tlist_from_pathtarget(subpath->pathtarget));
+
+			/* Generate outer path using this subpath */
+			add_path(rel, (Path *) create_subqueryscan_path(root,
+															rel,
+															subpath,
+															trivial_tlist,
+															pathkeys,
+															NULL));
+		}
+	}
+
+	/* if consider_parallel is false, there should be no partial paths */
+	Assert(final_rel->consider_parallel ||
+		   final_rel->partial_pathlist == NIL);
+
+	/*
+	 * If we have a partial path for the child relation, we can use that
+	 * to build a partial path for this relation.  But there's no point in
+	 * considering any path but the cheapest.
+	 */
+	if (rel->consider_parallel && bms_is_empty(rel->lateral_relids) &&
+		final_rel->partial_pathlist != NIL)
+	{
+		Path	   *partial_subpath;
+		Path	   *partial_path;
+
+		partial_subpath = linitial(final_rel->partial_pathlist);
+		partial_path = (Path *)
+			create_subqueryscan_path(root, rel, partial_subpath,
+									 trivial_tlist,
+									 NIL, NULL);
+		add_partial_path(rel, partial_path);
+	}
+
+	postprocess_setop_rel(root, rel);
+}
+
 /*
  * Generate paths for a UNION or UNION ALL node
  */
@@ -545,30 +700,23 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 {
 	Relids		relids = NULL;
 	RelOptInfo *result_rel;
-	double		save_fraction = root->tuple_fraction;
 	ListCell   *lc;
-	List	   *pathlist = NIL;
+	ListCell   *lc2;
+	ListCell   *lc3;
+	List	   *cheapest_pathlist = NIL;
+	List	   *ordered_pathlist = NIL;
 	List	   *partial_pathlist = NIL;
 	bool		partial_paths_valid = true;
 	bool		consider_parallel = true;
 	List	   *rellist;
 	List	   *tlist_list;
+	List	   *trivial_tlist_list;
 	List	   *tlist;
-	Path	   *path;
-
-	/*
-	 * If plain UNION, tell children to fetch all tuples.
-	 *
-	 * Note: in UNION ALL, we pass the top-level tuple_fraction unmodified to
-	 * each arm of the UNION ALL.  One could make a case for reducing the
-	 * tuple fraction for later arms (discounting by the expected size of the
-	 * earlier arms' results) but it seems not worth the trouble. The normal
-	 * case where tuple_fraction isn't already zero is a LIMIT at top level,
-	 * and passing it down as-is is usually enough to get the desired result
-	 * of preferring fast-start plans.
-	 */
-	if (!op->all)
-		root->tuple_fraction = 0.0;
+	List	   *groupList = NIL;
+	Path	   *apath;
+	Path	   *gpath = NULL;
+	bool		try_sorted;
+	List	   *union_pathkeys = NIL;
 
 	/*
 	 * If any of my children are identical UNION nodes (same op, all-flag, and
@@ -576,7 +724,11 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	rellist = plan_union_children(root, op, refnames_tlist, &tlist_list);
+	rellist = plan_union_children(root,
+								  op,
+								  refnames_tlist,
+								  &tlist_list,
+								  &trivial_tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -587,15 +739,68 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 */
 	tlist = generate_append_tlist(op->colTypes, op->colCollations, false,
 								  tlist_list, refnames_tlist);
-
 	*pTargetList = tlist;
 
+	/* For for UNIONs (not UNION ALL), try sorting, if sorting is possible */
+	try_sorted = !op->all && grouping_is_sortable(op->groupClauses);
+
+	if (try_sorted)
+	{
+		/* Identify the grouping semantics */
+		groupList = generate_setop_grouplist(op, tlist);
+
+		/* Determine the pathkeys for sorting by the whole target list */
+		union_pathkeys = make_pathkeys_for_sortclauses(root, groupList, tlist);
+
+		root->query_pathkeys = union_pathkeys;
+	}
+
+	/*
+	 * Now that we've got the append target list, we can build the union child
+	 * paths.
+	 */
+	forthree(lc, rellist, lc2, trivial_tlist_list, lc3, tlist_list)
+	{
+		RelOptInfo *rel = lfirst(lc);
+		bool		trivial_tlist = lfirst_int(lc2);
+		List	   *child_tlist = lfirst_node(List, lc3);
+
+		/* only build paths for the union children */
+		if (rel->rtekind == RTE_SUBQUERY)
+			build_setop_child_paths(root, rel, trivial_tlist, child_tlist,
+									union_pathkeys);
+	}
+
 	/* Build path lists and relid set. */
 	foreach(lc, rellist)
 	{
 		RelOptInfo *rel = lfirst(lc);
+		Path	   *ordered_path;
 
-		pathlist = lappend(pathlist, rel->cheapest_total_path);
+		cheapest_pathlist = lappend(cheapest_pathlist,
+									rel->cheapest_total_path);
+
+		if (try_sorted)
+		{
+			ordered_path = get_cheapest_path_for_pathkeys(rel->pathlist,
+														  union_pathkeys,
+														  NULL,
+														  TOTAL_COST,
+														  false);
+
+			if (ordered_path != NULL)
+				ordered_pathlist = lappend(ordered_pathlist, ordered_path);
+			else
+			{
+				/*
+				 * If we can't find a sorted path, just give up trying to
+				 * generate a list of correctly sorted child paths.  This can
+				 * happen when type coercion was added to the targetlist due
+				 * to mismatching types from the union children.
+				 */
+				try_sorted = false;
+			}
+		}
 
 		if (consider_parallel)
 		{
@@ -618,28 +823,21 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
 	result_rel->reltarget = create_pathtarget(root, tlist);
 	result_rel->consider_parallel = consider_parallel;
+	result_rel->consider_startup = (root->tuple_fraction > 0);
 
 	/*
-	 * Append the child results together.
+	 * Append the child results together using the cheapest paths from each
+	 * union child.
 	 */
-	path = (Path *) create_append_path(root, result_rel, pathlist, NIL,
-									   NIL, NULL, 0, false, -1);
-
-	/*
-	 * For UNION ALL, we just need the Append path.  For UNION, need to add
-	 * node(s) to remove duplicates.
-	 */
-	if (!op->all)
-		path = make_union_unique(op, path, tlist, root);
-
-	add_path(result_rel, path);
+	apath = (Path *) create_append_path(root, result_rel, cheapest_pathlist,
+										NIL, NIL, NULL, 0, false, -1);
 
 	/*
 	 * Estimate number of groups.  For now we just assume the output is unique
 	 * --- this is certainly true for the UNION case, and we want worst-case
 	 * estimates anyway.
 	 */
-	result_rel->rows = path->rows;
+	result_rel->rows = apath->rows;
 
 	/*
 	 * Now consider doing the same thing using the partial paths plus Append
@@ -647,7 +845,7 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 */
 	if (partial_paths_valid)
 	{
-		Path	   *ppath;
+		Path	   *papath;
 		int			parallel_workers = 0;
 
 		/* Find the highest number of workers requested for any subpath. */
@@ -676,21 +874,136 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 		}
 		Assert(parallel_workers > 0);
 
-		ppath = (Path *)
+		papath = (Path *)
 			create_append_path(root, result_rel, NIL, partial_pathlist,
-							   NIL, NULL,
-							   parallel_workers, enable_parallel_append,
-							   -1);
-		ppath = (Path *)
-			create_gather_path(root, result_rel, ppath,
+							   NIL, NULL, parallel_workers,
+							   enable_parallel_append, -1);
+		gpath = (Path *)
+			create_gather_path(root, result_rel, papath,
 							   result_rel->reltarget, NULL, NULL);
-		if (!op->all)
-			ppath = make_union_unique(op, ppath, tlist, root);
-		add_path(result_rel, ppath);
 	}
 
-	/* Undo effects of possibly forcing tuple_fraction to 0 */
-	root->tuple_fraction = save_fraction;
+	if (!op->all)
+	{
+		double		dNumGroups;
+		bool		can_sort = grouping_is_sortable(groupList);
+		bool		can_hash = grouping_is_hashable(groupList);
+
+		/*
+		 * XXX for the moment, take the number of distinct groups as equal to
+		 * the total input size, i.e., the worst case.  This is too
+		 * conservative, but it's not clear how to get a decent estimate of
+		 * the true size.  One should note as well the propensity of novices
+		 * to write UNION rather than UNION ALL even when they don't expect
+		 * any duplicates...
+		 */
+		dNumGroups = apath->rows;
+
+		if (can_hash)
+		{
+			Path	   *path;
+
+			/*
+			 * Try a hash aggregate plan on 'apath'.  This is the cheapest
+			 * available path containing each append child.
+			 */
+			path = (Path *) create_agg_path(root,
+											result_rel,
+											apath,
+											create_pathtarget(root, tlist),
+											AGG_HASHED,
+											AGGSPLIT_SIMPLE,
+											groupList,
+											NIL,
+											NULL,
+											dNumGroups);
+			add_path(result_rel, path);
+
+			/* Try hash aggregate on the Gather path, if valid */
+			if (gpath != NULL)
+			{
+				/* Hashed aggregate plan --- no sort needed */
+				path = (Path *) create_agg_path(root,
+												result_rel,
+												gpath,
+												create_pathtarget(root, tlist),
+												AGG_HASHED,
+												AGGSPLIT_SIMPLE,
+												groupList,
+												NIL,
+												NULL,
+												dNumGroups);
+				add_path(result_rel, path);
+			}
+		}
+
+		if (can_sort)
+		{
+			Path	   *path = apath;
+
+			if (groupList != NIL)
+				path = (Path *) create_sort_path(root, result_rel, path,
+												 make_pathkeys_for_sortclauses(root, groupList, tlist),
+												 -1.0);
+
+			path = (Path *) create_upper_unique_path(root,
+													 result_rel,
+													 path,
+													 list_length(path->pathkeys),
+													 dNumGroups);
+
+			add_path(result_rel, path);
+
+			/* Try Sort -> Unique on the Gather path, if set */
+			if (gpath != NULL)
+			{
+				path = gpath;
+
+				path = (Path *) create_sort_path(root, result_rel, path,
+												 make_pathkeys_for_sortclauses(root, groupList, tlist),
+												 -1.0);
+
+				path = (Path *) create_upper_unique_path(root,
+														 result_rel,
+														 path,
+														 list_length(path->pathkeys),
+														 dNumGroups);
+				add_path(result_rel, path);
+			}
+		}
+
+		/*
+		 * Try making a MergeAppend path if we managed to find a path with the
+		 * correct pathkeys in each union child query.
+		 */
+		if (try_sorted && groupList != NIL)
+		{
+			Path	   *path;
+
+			path = (Path *) create_merge_append_path(root,
+													 result_rel,
+													 ordered_pathlist,
+													 union_pathkeys,
+													 NULL);
+
+			/* and make the MergeAppend unique */
+			path = (Path *) create_upper_unique_path(root,
+													 result_rel,
+													 path,
+													 list_length(tlist),
+													 dNumGroups);
+
+			add_path(result_rel, path);
+		}
+	}
+	else
+	{
+		/* UNION ALL */
+		add_path(result_rel, apath);
+
+		if (gpath != NULL)
+			add_path(result_rel, gpath);
+	}
 
 	return result_rel;
 }
@@ -716,6 +1029,8 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
 			   *tlist,
 			   *groupList,
 			   *pathlist;
+	bool		lpath_trivial_tlist,
+				rpath_trivial_tlist;
 	double		dLeftGroups,
 				dRightGroups,
 				dNumGroups,
@@ -735,14 +1050,22 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
 								  false, 0,
 								  refnames_tlist,
 								  &lpath_tlist,
+								  &lpath_trivial_tlist,
 								  &dLeftGroups);
+	if (lrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, lrel, lpath_trivial_tlist, lpath_tlist,
+								NIL);
 	lpath = lrel->cheapest_total_path;
 	rrel = recurse_set_operations(op->rarg, root,
 								  op->colTypes, op->colCollations,
 								  false, 1,
 								  refnames_tlist,
 								  &rpath_tlist,
+								  &rpath_trivial_tlist,
 								  &dRightGroups);
+	if (rrel->rtekind == RTE_SUBQUERY)
+		build_setop_child_paths(root, rrel, rpath_trivial_tlist, rpath_tlist,
+								NIL);
 	rpath = rrel->cheapest_total_path;
 
 	/* Undo effects of forcing tuple_fraction to 0 */
@@ -879,13 +1202,16 @@ static List *
 plan_union_children(PlannerInfo *root,
 					SetOperationStmt *top_union,
 					List *refnames_tlist,
-					List **tlist_list)
+					List **tlist_list,
+					List **istrivial_tlist)
 {
 	List	   *pending_rels = list_make1(top_union);
 	List	   *result = NIL;
 	List	   *child_tlist;
+	bool		trivial_tlist;
 
 	*tlist_list = NIL;
+	*istrivial_tlist = NIL;
 
 	while (pending_rels != NIL)
 	{
@@ -924,75 +1250,15 @@ plan_union_children(PlannerInfo *root,
 														false, -1,
 														refnames_tlist,
 														&child_tlist,
+														&trivial_tlist,
 														NULL));
 		*tlist_list = lappend(*tlist_list, child_tlist);
+		*istrivial_tlist = lappend_int(*istrivial_tlist, trivial_tlist);
 	}
 
 	return result;
 }
 
-/*
- * Add nodes to the given path tree to unique-ify the result of a UNION.
- */
-static Path *
-make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
-				  PlannerInfo *root)
-{
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
-	List	   *groupList;
-	double		dNumGroups;
-
-	/* Identify the grouping semantics */
-	groupList = generate_setop_grouplist(op, tlist);
-
-	/*
-	 * XXX for the moment, take the number of distinct groups as equal to the
-	 * total input size, ie, the worst case.  This is too conservative, but
-	 * it's not clear how to get a decent estimate of the true size.  One
-	 * should note as well the propensity of novices to write UNION rather
-	 * than UNION ALL even when they don't expect any duplicates...
-	 */
-	dNumGroups = path->rows;
-
-	/* Decide whether to hash or sort */
-	if (choose_hashed_setop(root, groupList, path,
-							dNumGroups, dNumGroups,
-							"UNION"))
-	{
-		/* Hashed aggregate plan --- no sort needed */
-		path = (Path *) create_agg_path(root,
-										result_rel,
-										path,
-										create_pathtarget(root, tlist),
-										AGG_HASHED,
-										AGGSPLIT_SIMPLE,
-										groupList,
-										NIL,
-										NULL,
-										dNumGroups);
-	}
-	else
-	{
-		/* Sort and Unique */
-		if (groupList)
-			path = (Path *)
-				create_sort_path(root,
-								 result_rel,
-								 path,
-								 make_pathkeys_for_sortclauses(root,
-															   groupList,
-															   tlist),
-								 -1.0);
-		path = (Path *) create_upper_unique_path(root,
-												 result_rel,
-												 path,
-												 list_length(path->pathkeys),
-												 dNumGroups);
-	}
-
-	return path;
-}
-
 /*
  * postprocess_setop_rel - perform steps required after adding paths
  */
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 534692bee1..b3069516b2 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -397,6 +397,8 @@ struct PlannerInfo
 	List	   *distinct_pathkeys;
 	/* sortClause pathkeys, if any */
 	List	   *sort_pathkeys;
+	/* set operator pathkeys, if any */
+	List	   *setop_pathkeys;
 
 	/* Canonicalised partition schemes used in the query. */
 	List	   *part_schemes pg_node_attr(read_write_ignore);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 0e8a9c94ba..1165e98c5b 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -174,6 +174,9 @@ extern void add_child_join_rel_equivalences(PlannerInfo *root,
 											AppendRelInfo **appinfos,
 											RelOptInfo *parent_joinrel,
 											RelOptInfo *child_joinrel);
+extern void add_setop_child_rel_equivalences(PlannerInfo *root, Relids relids,
+											 List *tlist,
+											 List *setop_pathkeys);
 extern List *generate_implied_equalities_for_column(PlannerInfo *root,
 													RelOptInfo *rel,
 													ec_matches_callback_type callback,
diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h
index 8e00716dc8..a52dec285d 100644
--- a/src/include/optimizer/prep.h
+++ b/src/include/optimizer/prep.h
@@ -53,6 +53,6 @@ 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/collate.icu.utf8.out b/src/test/regress/expected/collate.icu.utf8.out
index 8ca93f4dea..4b8c8f143f 100644
--- a/src/test/regress/expected/collate.icu.utf8.out
+++ b/src/test/regress/expected/collate.icu.utf8.out
@@ -1396,6 +1396,7 @@ SELECT x FROM test3cs WHERE x ~ 'a';
  abc
 (1 row)
 
+SET enable_hashagg TO off;
 SELECT x FROM test1cs UNION SELECT x FROM test2cs ORDER BY x;
   x  
 -----
@@ -1448,6 +1449,7 @@ SELECT DISTINCT x FROM test3cs ORDER BY x;
  ghi
 (4 rows)
 
+RESET enable_hashagg;
 SELECT count(DISTINCT x) FROM test3cs;
  count 
 -------
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 7fdb685313..5fd54a10b1 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1472,14 +1472,19 @@ explain (costs off) select * from t union select * from t order by 1,3;
    Sort Key: t.a, t.c
    Presorted Key: t.a
    ->  Unique
-         ->  Sort
+         ->  Merge Append
                Sort Key: t.a, t.b, t.c
-               ->  Gather
+               ->  Gather Merge
                      Workers Planned: 2
-                     ->  Parallel Append
+                     ->  Sort
+                           Sort Key: t.a, t.b, t.c
                            ->  Parallel Seq Scan on t
+               ->  Gather Merge
+                     Workers Planned: 2
+                     ->  Sort
+                           Sort Key: t_1.a, t_1.b, t_1.c
                            ->  Parallel Seq Scan on t t_1
-(11 rows)
+(16 rows)
 
 -- Full sort, not just incremental sort can be pushed below a gather merge path
 -- by generate_useful_gather_paths.
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
index 882017afc9..c31c256b86 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -370,16 +370,16 @@ select count(*) from
 explain (costs off)
 select count(*) from
   ( select unique1 from tenk1 intersect select fivethous from tenk1 ) ss;
-                                     QUERY PLAN                                     
-------------------------------------------------------------------------------------
+                                 QUERY PLAN                                 
+----------------------------------------------------------------------------
  Aggregate
    ->  Subquery Scan on ss
          ->  HashSetOp Intersect
                ->  Append
-                     ->  Subquery Scan on "*SELECT* 2"
-                           ->  Seq Scan on tenk1
                      ->  Subquery Scan on "*SELECT* 1"
-                           ->  Index Only Scan using tenk1_unique1 on tenk1 tenk1_1
+                           ->  Index Only Scan using tenk1_unique1 on tenk1
+                     ->  Subquery Scan on "*SELECT* 2"
+                           ->  Seq Scan on tenk1 tenk1_1
 (8 rows)
 
 select count(*) from
@@ -412,16 +412,17 @@ set enable_hashagg to off;
 explain (costs off)
 select count(*) from
   ( select unique1 from tenk1 union select fivethous from tenk1 ) ss;
-                              QUERY PLAN                              
-----------------------------------------------------------------------
+                           QUERY PLAN                           
+----------------------------------------------------------------
  Aggregate
    ->  Unique
-         ->  Sort
+         ->  Merge Append
                Sort Key: tenk1.unique1
-               ->  Append
-                     ->  Index Only Scan using tenk1_unique1 on tenk1
+               ->  Index Only Scan using tenk1_unique1 on tenk1
+               ->  Sort
+                     Sort Key: tenk1_1.fivethous
                      ->  Seq Scan on tenk1 tenk1_1
-(7 rows)
+(8 rows)
 
 select count(*) from
   ( select unique1 from tenk1 union select fivethous from tenk1 ) ss;
@@ -433,18 +434,18 @@ select count(*) from
 explain (costs off)
 select count(*) from
   ( select unique1 from tenk1 intersect select fivethous from tenk1 ) ss;
-                                        QUERY PLAN                                        
-------------------------------------------------------------------------------------------
+                                    QUERY PLAN                                    
+----------------------------------------------------------------------------------
  Aggregate
    ->  Subquery Scan on ss
          ->  SetOp Intersect
                ->  Sort
-                     Sort Key: "*SELECT* 2".fivethous
+                     Sort Key: "*SELECT* 1".unique1
                      ->  Append
-                           ->  Subquery Scan on "*SELECT* 2"
-                                 ->  Seq Scan on tenk1
                            ->  Subquery Scan on "*SELECT* 1"
-                                 ->  Index Only Scan using tenk1_unique1 on tenk1 tenk1_1
+                                 ->  Index Only Scan using tenk1_unique1 on tenk1
+                           ->  Subquery Scan on "*SELECT* 2"
+                                 ->  Seq Scan on tenk1 tenk1_1
 (10 rows)
 
 select count(*) from
@@ -950,16 +951,8 @@ select except select;
 -- check hashed implementation
 set enable_hashagg = true;
 set enable_sort = false;
-explain (costs off)
-select from generate_series(1,5) union select from generate_series(1,3);
-                           QUERY PLAN                           
-----------------------------------------------------------------
- HashAggregate
-   ->  Append
-         ->  Function Scan on generate_series
-         ->  Function Scan on generate_series generate_series_1
-(4 rows)
-
+-- We've no way to check hashed UNION as the empty pathkeys in the Append are
+-- fine to make use of Unique, which is cheaper than HashAggregate.
 explain (costs off)
 select from generate_series(1,5) intersect select from generate_series(1,3);
                               QUERY PLAN                              
@@ -972,10 +965,6 @@ select from generate_series(1,5) intersect select from generate_series(1,3);
                ->  Function Scan on generate_series generate_series_1
 (6 rows)
 
-select from generate_series(1,5) union select from generate_series(1,3);
---
-(1 row)
-
 select from generate_series(1,5) union all select from generate_series(1,3);
 --
 (8 rows)
@@ -1102,16 +1091,17 @@ explain (costs off)
   UNION
   SELECT * FROM t2) t
  WHERE ab = 'ab';
-                    QUERY PLAN                     
----------------------------------------------------
- HashAggregate
-   Group Key: ((t1.a || t1.b))
-   ->  Append
-         ->  Index Scan using t1_ab_idx on t1
-               Index Cond: ((a || b) = 'ab'::text)
-         ->  Index Only Scan using t2_pkey on t2
-               Index Cond: (ab = 'ab'::text)
-(7 rows)
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: ((t1.a || t1.b))
+         ->  Append
+               ->  Index Scan using t1_ab_idx on t1
+                     Index Cond: ((a || b) = 'ab'::text)
+               ->  Index Only Scan using t2_pkey on t2
+                     Index Cond: (ab = 'ab'::text)
+(8 rows)
 
 --
 -- Test that ORDER BY for UNION ALL can be pushed down to inheritance
diff --git a/src/test/regress/sql/collate.icu.utf8.sql b/src/test/regress/sql/collate.icu.utf8.sql
index 03837de846..80f28a97d7 100644
--- a/src/test/regress/sql/collate.icu.utf8.sql
+++ b/src/test/regress/sql/collate.icu.utf8.sql
@@ -555,6 +555,7 @@ SELECT x FROM test3cs WHERE x LIKE 'a%';
 SELECT x FROM test3cs WHERE x ILIKE 'a%';
 SELECT x FROM test3cs WHERE x SIMILAR TO 'a%';
 SELECT x FROM test3cs WHERE x ~ 'a';
+SET enable_hashagg TO off;
 SELECT x FROM test1cs UNION SELECT x FROM test2cs ORDER BY x;
 SELECT x FROM test2cs UNION SELECT x FROM test1cs ORDER BY x;
 SELECT x FROM test1cs INTERSECT SELECT x FROM test2cs;
@@ -562,6 +563,7 @@ SELECT x FROM test2cs INTERSECT SELECT x FROM test1cs;
 SELECT x FROM test1cs EXCEPT SELECT x FROM test2cs;
 SELECT x FROM test2cs EXCEPT SELECT x FROM test1cs;
 SELECT DISTINCT x FROM test3cs ORDER BY x;
+RESET enable_hashagg;
 SELECT count(DISTINCT x) FROM test3cs;
 SELECT x, count(*) FROM test3cs GROUP BY x ORDER BY x;
 SELECT x, row_number() OVER (ORDER BY x), rank() OVER (ORDER BY x) FROM test3cs ORDER BY x;
diff --git a/src/test/regress/sql/union.sql b/src/test/regress/sql/union.sql
index d160db5458..5913dca8df 100644
--- a/src/test/regress/sql/union.sql
+++ b/src/test/regress/sql/union.sql
@@ -302,12 +302,11 @@ select except select;
 set enable_hashagg = true;
 set enable_sort = false;
 
-explain (costs off)
-select from generate_series(1,5) union select from generate_series(1,3);
+-- We've no way to check hashed UNION as the empty pathkeys in the Append are
+-- fine to make use of Unique, which is cheaper than HashAggregate.
 explain (costs off)
 select from generate_series(1,5) intersect select from generate_series(1,3);
 
-select from generate_series(1,5) union select from generate_series(1,3);
 select from generate_series(1,5) union all select from generate_series(1,3);
 select from generate_series(1,5) intersect select from generate_series(1,3);
 select from generate_series(1,5) intersect all select from generate_series(1,3);

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 7bad404458..26cbe2c9a2 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2494,6 +2494,7 @@ static void
 set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 					  Index rti, RangeTblEntry *rte)
 {
+	PlannerContext context;
 	Query	   *parse = root->parse;
 	Query	   *subquery = rte->subquery;
 	bool		trivial_pathtarget;
@@ -2644,10 +2645,12 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 	/* plan_params should not be in use in current query level */
 	Assert(root->plan_params == NIL);
 
+	context.hasRecursion = false;
+	context.tuple_fraction = tuple_fraction;
+	context.setops = NULL;
+
 	/* Generate a subroot and Paths for the subquery */
-	rel->subroot = subquery_planner(root->glob, subquery,
-									root,
-									false, tuple_fraction);
+	rel->subroot = subquery_planner(root->glob, subquery, root, &context);
 
 	/* 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 38d070fa00..56fa445ae8 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -127,7 +127,7 @@ typedef struct
 /* Local functions */
 static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind);
 static void preprocess_qual_conditions(PlannerInfo *root, Node *jtnode);
-static void grouping_planner(PlannerInfo *root, double tuple_fraction);
+static void grouping_planner(PlannerInfo *root, PlannerContext *context);
 static grouping_sets_data *preprocess_grouping_sets(PlannerInfo *root);
 static List *remap_to_groupclause_idx(List *groupClause, List *gsets,
 									  int *tleref_to_colnum_map);
@@ -288,6 +288,7 @@ standard_planner(Query *parse, const char *query_string, int cursorOptions,
 {
 	PlannedStmt *result;
 	PlannerGlobal *glob;
+	PlannerContext context;
 	double		tuple_fraction;
 	PlannerInfo *root;
 	RelOptInfo *final_rel;
@@ -410,9 +411,12 @@ standard_planner(Query *parse, const char *query_string, int cursorOptions,
 		tuple_fraction = 0.0;
 	}
 
+	context.hasRecursion = false;
+	context.tuple_fraction = tuple_fraction;
+	context.setops = NULL;
+
 	/* primary planning entry point (may recurse for subqueries) */
-	root = subquery_planner(glob, parse, NULL,
-							false, tuple_fraction);
+	root = subquery_planner(glob, parse, NULL, &context);
 
 	/* Select best Path and turn it into a Plan */
 	final_rel = fetch_upper_rel(root, UPPERREL_FINAL, NULL);
@@ -600,9 +604,6 @@ standard_planner(Query *parse, const char *query_string, int cursorOptions,
  * glob is the global state for the current planner run.
  * parse is the querytree produced by the parser & rewriter.
  * parent_root is the immediate parent Query's info (NULL at the top level).
- * hasRecursion is true if this is a recursive WITH query.
- * tuple_fraction is the fraction of tuples we expect will be retrieved.
- * tuple_fraction is interpreted as explained for grouping_planner, below.
  *
  * Basically, this routine does the stuff that should only be done once
  * per Query object.  It then calls grouping_planner.  At one time,
@@ -623,7 +624,7 @@ standard_planner(Query *parse, const char *query_string, int cursorOptions,
 PlannerInfo *
 subquery_planner(PlannerGlobal *glob, Query *parse,
 				 PlannerInfo *parent_root,
-				 bool hasRecursion, double tuple_fraction)
+				 PlannerContext *context)
 {
 	PlannerInfo *root;
 	List	   *newWithCheckOptions;
@@ -667,8 +668,8 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	root->hasPseudoConstantQuals = false;
 	root->hasAlternativeSubPlans = false;
 	root->placeholdersFrozen = false;
-	root->hasRecursion = hasRecursion;
-	if (hasRecursion)
+	root->hasRecursion = context->hasRecursion;
+	if (context->hasRecursion)
 		root->wt_param_id = assign_special_exec_param(root);
 	else
 		root->wt_param_id = -1;
@@ -1082,7 +1083,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	/*
 	 * Do the main planning.
 	 */
-	grouping_planner(root, tuple_fraction);
+	grouping_planner(root, context);
 
 	/*
 	 * Capture the set of outer-level param IDs we have access to, for use in
@@ -1274,14 +1275,6 @@ preprocess_phv_expression(PlannerInfo *root, Expr *expr)
  * This function adds all required top-level processing to the scan/join
  * Path(s) produced by query_planner.
  *
- * tuple_fraction is the fraction of tuples we expect will be retrieved.
- * tuple_fraction is interpreted as follows:
- *	  0: expect all tuples to be retrieved (normal case)
- *	  0 < tuple_fraction < 1: expect the given fraction of tuples available
- *		from the plan to be retrieved
- *	  tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
- *		expected to be retrieved (ie, a LIMIT specification)
- *
  * Returns nothing; the useful output is in the Paths we attach to the
  * (UPPERREL_FINAL, NULL) upperrel in *root.  In addition,
  * root->processed_tlist contains the final processed targetlist.
@@ -1291,7 +1284,7 @@ preprocess_phv_expression(PlannerInfo *root, Expr *expr)
  *--------------------
  */
 static void
-grouping_planner(PlannerInfo *root, double tuple_fraction)
+grouping_planner(PlannerInfo *root, PlannerContext *context)
 {
 	Query	   *parse = root->parse;
 	int64		offset_est = 0;
@@ -1305,6 +1298,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 	RelOptInfo *current_rel;
 	RelOptInfo *final_rel;
 	FinalPathExtraData extra;
+	double		tuple_fraction = context->tuple_fraction;
 	ListCell   *lc;
 
 	/* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
@@ -1507,16 +1501,10 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 		qp_extra.gset_data = gset_data;
 
 		/*
-		 * Check if we're a subquery for a set operation.  If we are, store
-		 * the SetOperationStmt in qp_extra.
+		 * If we're a subquery for a set operation, store the SetOperationStmt in
+		 * qp_extra.
 		 */
-		if (root->parent_root != NULL &&
-			root->parent_root->parse->setOperations != NULL &&
-			IsA(root->parent_root->parse->setOperations, SetOperationStmt))
-			qp_extra.setop =
-				(SetOperationStmt *) root->parent_root->parse->setOperations;
-		else
-			qp_extra.setop = NULL;
+		qp_extra.setop = (SetOperationStmt *) context->setops;
 
 		/*
 		 * Generate the best unsorted and presorted paths for the scan/join
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index d5fa281b10..49be10e29b 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -167,6 +167,7 @@ make_subplan(PlannerInfo *root, Query *orig_subquery,
 	bool		simple_exists = false;
 	double		tuple_fraction;
 	PlannerInfo *subroot;
+	PlannerContext context;
 	RelOptInfo *final_rel;
 	Path	   *best_path;
 	Plan	   *plan;
@@ -217,10 +218,12 @@ make_subplan(PlannerInfo *root, Query *orig_subquery,
 	/* plan_params should not be in use in current query level */
 	Assert(root->plan_params == NIL);
 
+	context.hasRecursion = false;
+	context.tuple_fraction = tuple_fraction;
+	context.setops = NULL;
+
 	/* Generate Paths for the subquery */
-	subroot = subquery_planner(root->glob, subquery,
-							   root,
-							   false, tuple_fraction);
+	subroot = subquery_planner(root->glob, subquery, root, &context);
 
 	/* Isolate the params needed by this specific subplan */
 	plan_params = root->plan_params;
@@ -265,10 +268,14 @@ make_subplan(PlannerInfo *root, Query *orig_subquery,
 										 &newtestexpr, &paramIds);
 		if (subquery)
 		{
+			PlannerContext context;
+
+			context.hasRecursion = false;
+			context.tuple_fraction = 0.0;
+			context.setops = NULL;
+
 			/* Generate Paths for the ANY subquery; we'll need all rows */
-			subroot = subquery_planner(root->glob, subquery,
-									   root,
-									   false, 0.0);
+			subroot = subquery_planner(root->glob, subquery, root, &context);
 
 			/* Isolate the params needed by this specific subplan */
 			plan_params = root->plan_params;
@@ -891,6 +898,7 @@ SS_process_ctes(PlannerInfo *root)
 		CmdType		cmdType = ((Query *) cte->ctequery)->commandType;
 		Query	   *subquery;
 		PlannerInfo *subroot;
+		PlannerContext context;
 		RelOptInfo *final_rel;
 		Path	   *best_path;
 		Plan	   *plan;
@@ -963,13 +971,16 @@ SS_process_ctes(PlannerInfo *root)
 		/* plan_params should not be in use in current query level */
 		Assert(root->plan_params == NIL);
 
+		context.hasRecursion = cte->cterecursive;
 		/*
-		 * Generate Paths for the CTE query.  Always plan for full retrieval
-		 * --- we don't have enough info to predict otherwise.
+		 * Always plan for full retrieval --- we don't have enough info to
+		 * predict otherwise.
 		 */
-		subroot = subquery_planner(root->glob, subquery,
-								   root,
-								   cte->cterecursive, 0.0);
+		context.tuple_fraction = 0.0;
+		context.setops = NULL;
+
+		/* Generate Paths for the CTE query. */
+		subroot = subquery_planner(root->glob, subquery, root, &context);
 
 		/*
 		 * 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 944afc7192..113c721602 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -242,6 +242,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 	if (IsA(setOp, RangeTblRef))
 	{
+		PlannerContext context;
 		RangeTblRef *rtr = (RangeTblRef *) setOp;
 		RangeTblEntry *rte = root->simple_rte_array[rtr->rtindex];
 		Query	   *subquery = rte->subquery;
@@ -257,11 +258,14 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		/* plan_params should not be in use in current query level */
 		Assert(root->plan_params == NIL);
 
+		context.hasRecursion = false;
+		context.tuple_fraction = root->tuple_fraction;
+		context.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);
+		subroot = rel->subroot = subquery_planner(root->glob, subquery, root,
+												  &context);
 
 		/*
 		 * It should not be possible for the primitive query to contain any
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 595eec2cbb..a3727ba2f1 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -551,6 +551,37 @@ struct PlannerInfo
 	bool		partColsUpdated;
 };
 
+/*----------
+ * PlannerContext
+ *		Per-query context to provide additional information to
+ *		subquery_planner() and grouping_planner().
+ */
+typedef struct PlannerContext
+{
+	/*
+	 * hasRecursion: must be given as true if planning recursive WITH query.
+	 */
+	bool hasRecursion;
+
+	/*--------------------
+	 * tuple_fraction is the fraction of tuples we expect will be retrieved.
+	 * tuple_fraction is interpreted as follows:
+	 *	  0: expect all tuples to be retrieved (normal case)
+	 *	  0 < tuple_fraction < 1: expect the given fraction of tuples available
+	 *		from the plan to be retrieved
+	 *	  tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
+	 *		expected to be retrieved (ie, a LIMIT specification)
+	 *--------------------
+	 */
+	double tuple_fraction;
+
+	/*
+	 * Can be set for set operation child queries to provide information on
+	 * the parent-level operation to allow them to optimize for this context
+	 */
+	SetOperationStmt *setops;
+
+} PlannerContext;
 
 /*
  * In places where it's known that simple_rte_array[] must have been prepared
diff --git a/src/include/optimizer/planner.h b/src/include/optimizer/planner.h
index e1d79ffdf3..e3c9a4e3ae 100644
--- a/src/include/optimizer/planner.h
+++ b/src/include/optimizer/planner.h
@@ -44,7 +44,7 @@ extern PlannedStmt *standard_planner(Query *parse, const char *query_string,
 
 extern PlannerInfo *subquery_planner(PlannerGlobal *glob, Query *parse,
 									 PlannerInfo *parent_root,
-									 bool hasRecursion, double tuple_fraction);
+									 PlannerContext *context);
 
 extern RowMarkType select_rowmark_type(RangeTblEntry *rte,
 									   LockClauseStrength strength);