parallel append vs. simple UNION ALL

From d5689922919f425eed266c867cfdf44f9aff8a24 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Sat, 23 Dec 2017 10:56:07 -0800
Subject: [PATCH 4/4] Consider Parallel Append as a way to implement a union
 operation in a setop tree.

---
 src/backend/optimizer/prep/prepunion.c | 93 +++++++++++++++++++++++++++++++++-
 1 file changed, 91 insertions(+), 2 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 6e5524046f..2f259ab0fe 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -298,12 +298,18 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		 */
 		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(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).
 		 */
-		final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
 		subpath = get_cheapest_fractional_path(final_rel,
 											   root->tuple_fraction);
 
@@ -320,6 +326,23 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 		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 (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,
+										 NIL, NULL);
+			add_partial_path(rel, partial_path);
+		}
+
 		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
 		 * grouping or aggregation, its output is probably mostly unique
@@ -552,6 +575,9 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	double		save_fraction = root->tuple_fraction;
 	ListCell   *lc;
 	List	   *pathlist = NIL;
+	List	   *partial_pathlist = NIL;
+	bool		partial_paths_valid = true;
+	bool		consider_parallel = true;
 	List	   *rellist;
 	List	   *tlist_list;
 	List	   *tlist;
@@ -591,18 +617,34 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
-	/* Build path list and relid set. */
+	/* Build path lists and relid set. */
 	foreach(lc, rellist)
 	{
 		RelOptInfo *rel = lfirst(lc);
 
 		pathlist = lappend(pathlist, rel->cheapest_total_path);
+
+		if (consider_parallel)
+		{
+			if (!rel->consider_parallel)
+			{
+				consider_parallel = false;
+				partial_paths_valid = false;
+			}
+			else if (rel->partial_pathlist == NIL)
+				partial_paths_valid = false;
+			else
+				partial_pathlist = lappend(partial_pathlist,
+										   linitial(rel->partial_pathlist));
+		}
+
 		relids = bms_union(relids, rel->relids);
 	}
 
 	/* Build result relation. */
 	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
 	result_rel->reltarget = create_pathtarget(root, tlist);
+	result_rel->consider_parallel = consider_parallel;
 
 	/*
 	 * Append the child results together.
@@ -626,6 +668,53 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	 */
 	result_rel->rows = path->rows;
 
+	/*
+	 * Now consider doing the same thing using the partial paths plus Append
+	 * plus Gather.
+	 */
+	if (partial_paths_valid)
+	{
+		Path	   *ppath;
+		ListCell   *lc;
+		int			parallel_workers = 0;
+
+		/* Find the highest number of workers requested for any subpath. */
+		foreach(lc, partial_pathlist)
+		{
+			Path	   *path = lfirst(lc);
+
+			parallel_workers = Max(parallel_workers, path->parallel_workers);
+		}
+		Assert(parallel_workers > 0);
+
+		/*
+		 * If the use of parallel append is permitted, always request at least
+		 * log2(# of children) paths.  We assume it can be useful to have
+		 * extra workers in this case because they will be spread out across
+		 * the children.  The precise formula is just a guess; see
+		 * add_paths_to_append_rel.
+		 */
+		if (enable_parallel_append)
+		{
+			parallel_workers = Max(parallel_workers,
+								   fls(list_length(partial_pathlist)));
+			parallel_workers = Min(parallel_workers,
+								   max_parallel_workers_per_gather);
+		}
+		Assert(parallel_workers > 0);
+
+		ppath = (Path *)
+			create_append_path(result_rel, NIL, partial_pathlist,
+							   NULL, parallel_workers, enable_parallel_append,
+							   NIL /* XXX? Is this right? */ , -1);
+		ppath = (Path *)
+			create_gather_path(root, result_rel, ppath,
+							   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;
 
-- 
2.14.3 (Apple Git-98)

From e9edd8bcd486eedf7d3b4819849c3a9f09487172 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 15:42:51 -0500
Subject: [PATCH 3/4] Generate a separate upper relation for each stage of
 setop planning.

Commit 3fc6e2d7f5b652b417fa6937c34de2438d60fa9f made setop planning
stages return paths rather than plans, but all such paths were loosely
associated with a single RelOptInfo, and only the final path was added
to the RelOptInfo.  Even at the time, it was foreseen that this should
be changed, because there is otherwise no good way for a single stage
of setop planning to return multiple paths.  With this patch, each
stage of set operation planning now creates a separate RelOptInfo;
these are distinguished by using appropriate relid sets.  Note that
this patch does nothing whatsoever about actually returning multiple
paths for the same set operation; it just makes it possible for a
future patch to do so.

Along the way, adjust things so that create_upper_paths_hook is called
for each of these new RelOptInfos rather than just once, since that
might be useful to extensions using that hook.  It might be a good
to provide an FDW API here as well, but I didn't try to do that for
now.

Patch by me.
---
 src/backend/optimizer/prep/prepunion.c | 330 ++++++++++++++++++---------------
 1 file changed, 185 insertions(+), 145 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index f387387289..6e5524046f 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -60,30 +60,29 @@ typedef struct
 	AppendRelInfo **appinfos;
 } adjust_appendrel_attrs_context;
 
-static Path *recurse_set_operations(Node *setOp, PlannerInfo *root,
+static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List *colTypes, List *colCollations,
 					   bool junkOK,
 					   int flag, List *refnames_tlist,
 					   List **pTargetList,
 					   double *pNumGroups);
-static Path *generate_recursion_path(SetOperationStmt *setOp,
+static RelOptInfo *generate_recursion_path(SetOperationStmt *setOp,
 						PlannerInfo *root,
 						List *refnames_tlist,
 						List **pTargetList);
-static Path *generate_union_path(SetOperationStmt *op, PlannerInfo *root,
+static RelOptInfo *generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 					List *refnames_tlist,
-					List **pTargetList,
-					double *pNumGroups);
-static Path *generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
+					List **pTargetList);
+static RelOptInfo *generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 					   List *refnames_tlist,
-					   List **pTargetList,
-					   double *pNumGroups);
+					   List **pTargetList);
 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);
+static void postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
 					Path *input_path,
 					double dNumGroups, double dNumOutputRows,
@@ -149,7 +148,6 @@ plan_set_operations(PlannerInfo *root)
 	RangeTblEntry *leftmostRTE;
 	Query	   *leftmostQuery;
 	RelOptInfo *setop_rel;
-	Path	   *path;
 	List	   *top_tlist;
 
 	Assert(topop);
@@ -181,57 +179,34 @@ plan_set_operations(PlannerInfo *root)
 	leftmostQuery = leftmostRTE->subquery;
 	Assert(leftmostQuery != NULL);
 
-	/*
-	 * We return our results in the (SETOP, NULL) upperrel.  For the moment,
-	 * this is also the parent rel of all Paths in the setop tree; we may well
-	 * change that in future.
-	 */
-	setop_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
-
-	/*
-	 * We don't currently worry about setting setop_rel's consider_parallel
-	 * flag, nor about allowing FDWs to contribute paths to it.
-	 */
-
 	/*
 	 * If the topmost node is a recursive union, it needs special processing.
 	 */
 	if (root->hasRecursion)
 	{
-		path = generate_recursion_path(topop, root,
-									   leftmostQuery->targetList,
-									   &top_tlist);
+		setop_rel = generate_recursion_path(topop, root,
+											leftmostQuery->targetList,
+											&top_tlist);
 	}
 	else
 	{
 		/*
 		 * Recurse on setOperations tree to generate paths for set ops. The
-		 * final output path should have just the column types shown as the
+		 * final output paths should have just the column types shown as the
 		 * output from the top-level node, plus possibly resjunk working
 		 * columns (we can rely on upper-level nodes to deal with that).
 		 */
-		path = recurse_set_operations((Node *) topop, root,
-									  topop->colTypes, topop->colCollations,
-									  true, -1,
-									  leftmostQuery->targetList,
-									  &top_tlist,
-									  NULL);
+		setop_rel = recurse_set_operations((Node *) topop, root,
+										   topop->colTypes, topop->colCollations,
+										   true, -1,
+										   leftmostQuery->targetList,
+										   &top_tlist,
+										   NULL);
 	}
 
 	/* Must return the built tlist into root->processed_tlist. */
 	root->processed_tlist = top_tlist;
 
-	/* Add only the final path to the SETOP upperrel. */
-	add_path(setop_rel, path);
-
-	/* Let extensions possibly add some more paths */
-	if (create_upper_paths_hook)
-		(*create_upper_paths_hook) (root, UPPERREL_SETOP,
-									NULL, setop_rel);
-
-	/* Select cheapest path */
-	set_cheapest(setop_rel);
-
 	return setop_rel;
 }
 
@@ -245,21 +220,21 @@ plan_set_operations(PlannerInfo *root)
  * flag: if >= 0, add a resjunk output column indicating value of flag
  * refnames_tlist: targetlist to take column names from
  *
- * Returns a path for the subtree, as well as these output parameters:
+ * Returns a RelOptInfo for the subtree, as well as these output parameters:
  * *pTargetList: receives the fully-fledged tlist for the subtree's top plan
  * *pNumGroups: if not NULL, we estimate the number of distinct groups
  *		in the result, and store it there
  *
  * The pTargetList output parameter is mostly redundant with the pathtarget
- * of the returned path, but for the moment we need it because much of 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.
+ * of the returned RelOptInfo, but for the moment we need it because much of
+ * the logic in this file depends on flag columns being marked resjunk.
+ * Pending a redesign of how that works, this is the easy way out.
  *
  * 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.
  */
-static Path *
+static RelOptInfo *
 recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List *colTypes, List *colCollations,
 					   bool junkOK,
@@ -267,6 +242,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List **pTargetList,
 					   double *pNumGroups)
 {
+	RelOptInfo *rel = NULL;		/* keep compiler quiet */
+
 	/* Guard against stack overflow due to overly complex setop nests */
 	check_stack_depth();
 
@@ -275,7 +252,6 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		RangeTblRef *rtr = (RangeTblRef *) setOp;
 		RangeTblEntry *rte = root->simple_rte_array[rtr->rtindex];
 		Query	   *subquery = rte->subquery;
-		RelOptInfo *rel;
 		PlannerInfo *subroot;
 		RelOptInfo *final_rel;
 		Path	   *subpath;
@@ -284,11 +260,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 		Assert(subquery != NULL);
 
-		/*
-		 * We need to build a RelOptInfo for each leaf subquery.  This isn't
-		 * used for much here, but it carries the subroot data structures
-		 * forward to setrefs.c processing.
-		 */
+		/* Build a RelOptInfo for this leaf subquery. */
 		rel = build_simple_rel(root, rtr->rtindex, NULL);
 
 		/* plan_params should not be in use in current query level */
@@ -307,6 +279,18 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		if (root->plan_params)
 			elog(ERROR, "unexpected outer reference in set operation subquery");
 
+		/* Figure out the appropriate target list for this subquery. */
+		tlist = generate_setop_tlist(colTypes, colCollations,
+									 flag,
+									 rtr->rtindex,
+									 true,
+									 subroot->processed_tlist,
+									 refnames_tlist);
+		rel->reltarget = create_pathtarget(root, tlist);
+
+		/* 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
@@ -334,22 +318,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		path = (Path *) create_subqueryscan_path(root, rel, subpath,
 												 NIL, NULL);
 
-		/*
-		 * Figure out the appropriate target list, and update the
-		 * SubqueryScanPath with the PathTarget form of that.
-		 */
-		tlist = generate_setop_tlist(colTypes, colCollations,
-									 flag,
-									 rtr->rtindex,
-									 true,
-									 subroot->processed_tlist,
-									 refnames_tlist);
-
-		path = apply_projection_to_path(root, rel, path,
-										create_pathtarget(root, tlist));
-
-		/* Return the fully-fledged tlist to caller, too */
-		*pTargetList = tlist;
+		add_path(rel, path);
 
 		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
@@ -378,25 +347,22 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 												  subpath->rows,
 												  NULL);
 		}
-
-		return (Path *) path;
 	}
 	else if (IsA(setOp, SetOperationStmt))
 	{
 		SetOperationStmt *op = (SetOperationStmt *) setOp;
-		Path	   *path;
 
 		/* UNIONs are much different from INTERSECT/EXCEPT */
 		if (op->op == SETOP_UNION)
-			path = generate_union_path(op, root,
-									   refnames_tlist,
-									   pTargetList,
-									   pNumGroups);
+			rel = generate_union_path(op, root,
+									  refnames_tlist,
+									  pTargetList);
 		else
-			path = generate_nonunion_path(op, root,
-										  refnames_tlist,
-										  pTargetList,
-										  pNumGroups);
+			rel = generate_nonunion_path(op, root,
+										 refnames_tlist,
+										 pTargetList);
+		if (pNumGroups)
+			*pNumGroups = rel->rows;
 
 		/*
 		 * If necessary, add a Result node to project the caller-requested
@@ -415,39 +381,70 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 			!tlist_same_datatypes(*pTargetList, colTypes, junkOK) ||
 			!tlist_same_collations(*pTargetList, colCollations, junkOK))
 		{
+			PathTarget *target;
+			ListCell   *lc;
+
 			*pTargetList = generate_setop_tlist(colTypes, colCollations,
 												flag,
 												0,
 												false,
 												*pTargetList,
 												refnames_tlist);
-			path = apply_projection_to_path(root,
-											path->parent,
-											path,
-											create_pathtarget(root,
-															  *pTargetList));
+			target = create_pathtarget(root, *pTargetList);
+
+			/* Apply projection to each path */
+			foreach(lc, rel->pathlist)
+			{
+				Path	   *subpath = (Path *) lfirst(lc);
+				Path	   *path;
+
+				Assert(subpath->param_info == NULL);
+				path = apply_projection_to_path(root, subpath->parent,
+												subpath, target);
+				/* If we had to add a Result, path is different from subpath */
+				if (path != subpath)
+					lfirst(lc) = path;
+			}
+
+			/* Apply projection to each partial path */
+			foreach(lc, rel->partial_pathlist)
+			{
+				Path	   *subpath = (Path *) lfirst(lc);
+				Path	   *path;
+
+				Assert(subpath->param_info == NULL);
+
+				/* avoid apply_projection_to_path, in case of multiple refs */
+				path = (Path *) create_projection_path(root, subpath->parent,
+													   subpath, target);
+				lfirst(lc) = path;
+			}
 		}
-		return path;
 	}
 	else
 	{
 		elog(ERROR, "unrecognized node type: %d",
 			 (int) nodeTag(setOp));
 		*pTargetList = NIL;
-		return NULL;			/* keep compiler quiet */
 	}
+
+	postprocess_setop_rel(root, rel);
+
+	return rel;
 }
 
 /*
- * Generate path for a recursive UNION node
+ * Generate paths for a recursive UNION node
  */
-static Path *
+static RelOptInfo *
 generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 						List *refnames_tlist,
 						List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	RelOptInfo *result_rel;
 	Path	   *path;
+	RelOptInfo *lrel,
+			   *rrel;
 	Path	   *lpath;
 	Path	   *rpath;
 	List	   *lpath_tlist;
@@ -466,20 +463,22 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	 * Unlike a regular UNION node, process the left and right inputs
 	 * separately without any intention of combining them into one Append.
 	 */
-	lpath = recurse_set_operations(setOp->larg, root,
-								   setOp->colTypes, setOp->colCollations,
-								   false, -1,
-								   refnames_tlist,
-								   &lpath_tlist,
-								   NULL);
+	lrel = recurse_set_operations(setOp->larg, root,
+								  setOp->colTypes, setOp->colCollations,
+								  false, -1,
+								  refnames_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;
-	rpath = recurse_set_operations(setOp->rarg, root,
-								   setOp->colTypes, setOp->colCollations,
-								   false, -1,
-								   refnames_tlist,
-								   &rpath_tlist,
-								   NULL);
+	rrel = recurse_set_operations(setOp->rarg, root,
+								  setOp->colTypes, setOp->colCollations,
+								  false, -1,
+								  refnames_tlist,
+								  &rpath_tlist,
+								  NULL);
+	rpath = rrel->cheapest_total_path;
 	root->non_recursive_path = NULL;
 
 	/*
@@ -491,6 +490,11 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
+								 bms_union(lrel->relids, rrel->relids));
+	result_rel->reltarget = create_pathtarget(root, tlist);
+
 	/*
 	 * If UNION, identify the grouping operators
 	 */
@@ -525,26 +529,30 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 											   result_rel,
 											   lpath,
 											   rpath,
-											   create_pathtarget(root, tlist),
+											   result_rel->reltarget,
 											   groupList,
 											   root->wt_param_id,
 											   dNumGroups);
 
-	return path;
+	add_path(result_rel, path);
+	postprocess_setop_rel(root, result_rel);
+	return result_rel;
 }
 
 /*
- * Generate path for a UNION or UNION ALL node
+ * Generate paths for a UNION or UNION ALL node
  */
-static Path *
+static RelOptInfo *
 generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 					List *refnames_tlist,
-					List **pTargetList,
-					double *pNumGroups)
+					List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	Relids		relids = NULL;
+	RelOptInfo *result_rel;
 	double		save_fraction = root->tuple_fraction;
-	List	   *pathlist;
+	ListCell   *lc;
+	List	   *pathlist = NIL;
+	List	   *rellist;
 	List	   *tlist_list;
 	List	   *tlist;
 	Path	   *path;
@@ -569,7 +577,7 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	pathlist = plan_union_children(root, op, refnames_tlist, &tlist_list);
+	rellist = plan_union_children(root, op, refnames_tlist, &tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -583,13 +591,24 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build path list and relid set. */
+	foreach(lc, rellist)
+	{
+		RelOptInfo *rel = lfirst(lc);
+
+		pathlist = lappend(pathlist, rel->cheapest_total_path);
+		relids = bms_union(relids, rel->relids);
+	}
+
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
+	result_rel->reltarget = create_pathtarget(root, tlist);
+
 	/*
 	 * Append the child results together.
 	 */
 	path = (Path *) create_append_path(result_rel, pathlist, NIL,
 									   NULL, 0, false, NIL, -1);
-	/* We have to manually jam the right tlist into the path; ick */
-	path->pathtarget = create_pathtarget(root, tlist);
 
 	/*
 	 * For UNION ALL, we just need the Append path.  For UNION, need to add
@@ -598,30 +617,32 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	if (!op->all)
 		path = make_union_unique(op, path, tlist, root);
 
+	add_path(result_rel, path);
+
 	/*
-	 * Estimate number of groups if caller wants it.  For now we just assume
-	 * the output is unique --- this is certainly true for the UNION case, and
-	 * we want worst-case estimates anyway.
+	 * 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.
 	 */
-	if (pNumGroups)
-		*pNumGroups = path->rows;
+	result_rel->rows = path->rows;
 
 	/* Undo effects of possibly forcing tuple_fraction to 0 */
 	root->tuple_fraction = save_fraction;
 
-	return path;
+	return result_rel;
 }
 
 /*
- * Generate path for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
+ * Generate paths for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
  */
-static Path *
+static RelOptInfo *
 generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 					   List *refnames_tlist,
-					   List **pTargetList,
-					   double *pNumGroups)
+					   List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	RelOptInfo *result_rel;
+	RelOptInfo *lrel,
+			   *rrel;
 	double		save_fraction = root->tuple_fraction;
 	Path	   *lpath,
 			   *rpath,
@@ -646,18 +667,20 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 	root->tuple_fraction = 0.0;
 
 	/* Recurse on children, ensuring their outputs are marked */
-	lpath = recurse_set_operations(op->larg, root,
-								   op->colTypes, op->colCollations,
-								   false, 0,
-								   refnames_tlist,
-								   &lpath_tlist,
-								   &dLeftGroups);
-	rpath = recurse_set_operations(op->rarg, root,
-								   op->colTypes, op->colCollations,
-								   false, 1,
-								   refnames_tlist,
-								   &rpath_tlist,
-								   &dRightGroups);
+	lrel = recurse_set_operations(op->larg, root,
+								  op->colTypes, op->colCollations,
+								  false, 0,
+								  refnames_tlist,
+								  &lpath_tlist,
+								  &dLeftGroups);
+	lpath = lrel->cheapest_total_path;
+	rrel = recurse_set_operations(op->rarg, root,
+								  op->colTypes, op->colCollations,
+								  false, 1,
+								  refnames_tlist,
+								  &rpath_tlist,
+								  &dRightGroups);
+	rpath = rrel->cheapest_total_path;
 
 	/* Undo effects of forcing tuple_fraction to 0 */
 	root->tuple_fraction = save_fraction;
@@ -695,15 +718,17 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
+								 bms_union(lrel->relids, rrel->relids));
+	result_rel->reltarget = create_pathtarget(root, tlist);;
+
 	/*
 	 * Append the child results together.
 	 */
 	path = (Path *) create_append_path(result_rel, pathlist, NIL,
 									   NULL, 0, false, NIL, -1);
 
-	/* We have to manually jam the right tlist into the path; ick */
-	path->pathtarget = create_pathtarget(root, tlist);
-
 	/* Identify the grouping semantics */
 	groupList = generate_setop_grouplist(op, tlist);
 
@@ -769,10 +794,9 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 									  dNumGroups,
 									  dNumOutputRows);
 
-	if (pNumGroups)
-		*pNumGroups = dNumGroups;
-
-	return path;
+	result_rel->rows = path->rows;
+	add_path(result_rel, path);
+	return result_rel;
 }
 
 /*
@@ -897,8 +921,6 @@ make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
 															   groupList,
 															   tlist),
 								 -1.0);
-		/* We have to manually jam the right tlist into the path; ick */
-		path->pathtarget = create_pathtarget(root, tlist);
 		path = (Path *) create_upper_unique_path(root,
 												 result_rel,
 												 path,
@@ -909,6 +931,24 @@ make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
 	return path;
 }
 
+/*
+ * postprocess_setop_rel - perform steps required after adding paths
+ */
+static void
+postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel)
+{
+	/*
+	 * We don't currently worry about allowing FDWs to contribute paths to
+	 * this relation, but give extensions a chance.
+	 */
+	if (create_upper_paths_hook)
+		(*create_upper_paths_hook) (root, UPPERREL_SETOP,
+									NULL, rel);
+
+	/* Select cheapest path */
+	set_cheapest(rel);
+}
+
 /*
  * choose_hashed_setop - should we use hashing for a set operation?
  */
-- 
2.14.3 (Apple Git-98)

From b62ca029a5fdb35f7e2060db51a84705200e841a Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 12:13:46 -0500
Subject: [PATCH 2/4] Rewrite recurse_union_children to iterate, rather than
 recurse.

Also, rename it to plan_union_chidren, so the old name wasn't
very descriptive.  This results in a small net reduction in code,
seems at least to me to be easier to understand, and saves
space on the process stack.
---
 src/backend/optimizer/prep/prepunion.c | 100 ++++++++++++++++-----------------
 1 file changed, 47 insertions(+), 53 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index b586f941a8..f387387289 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -78,10 +78,10 @@ static Path *generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 					   List *refnames_tlist,
 					   List **pTargetList,
 					   double *pNumGroups);
-static List *recurse_union_children(Node *setOp, PlannerInfo *root,
-					   SetOperationStmt *top_union,
-					   List *refnames_tlist,
-					   List **tlist_list);
+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);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
@@ -545,8 +545,6 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
 	double		save_fraction = root->tuple_fraction;
 	List	   *pathlist;
-	List	   *child_tlists1;
-	List	   *child_tlists2;
 	List	   *tlist_list;
 	List	   *tlist;
 	Path	   *path;
@@ -571,13 +569,7 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	pathlist = list_concat(recurse_union_children(op->larg, root,
-												  op, refnames_tlist,
-												  &child_tlists1),
-						   recurse_union_children(op->rarg, root,
-												  op, refnames_tlist,
-												  &child_tlists2));
-	tlist_list = list_concat(child_tlists1, child_tlists2);
+	pathlist = plan_union_children(root, op, refnames_tlist, &tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -797,56 +789,58 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
  * generate_union_path will force a fresh sort if the top level is a UNION.
  */
 static List *
-recurse_union_children(Node *setOp, PlannerInfo *root,
-					   SetOperationStmt *top_union,
-					   List *refnames_tlist,
-					   List **tlist_list)
+plan_union_children(PlannerInfo *root,
+					SetOperationStmt *top_union,
+					List *refnames_tlist,
+					List **tlist_list)
 {
-	List	   *result;
+	List	   *pending_rels = list_make1(top_union);
+	List	   *result = NIL;
 	List	   *child_tlist;
 
-	if (IsA(setOp, SetOperationStmt))
+	*tlist_list = NIL;
+
+	while (pending_rels != NIL)
 	{
-		SetOperationStmt *op = (SetOperationStmt *) setOp;
+		Node	   *setOp = linitial(pending_rels);
+
+		pending_rels = list_delete_first(pending_rels);
 
-		if (op->op == top_union->op &&
-			(op->all == top_union->all || op->all) &&
-			equal(op->colTypes, top_union->colTypes))
+		if (IsA(setOp, SetOperationStmt))
 		{
-			/* Same UNION, so fold children into parent's subpath list */
-			List	   *child_tlists1;
-			List	   *child_tlists2;
+			SetOperationStmt *op = (SetOperationStmt *) setOp;
 
-			result = list_concat(recurse_union_children(op->larg, root,
-														top_union,
-														refnames_tlist,
-														&child_tlists1),
-								 recurse_union_children(op->rarg, root,
-														top_union,
-														refnames_tlist,
-														&child_tlists2));
-			*tlist_list = list_concat(child_tlists1, child_tlists2);
-			return result;
+			if (op->op == top_union->op &&
+				(op->all == top_union->all || op->all) &&
+				equal(op->colTypes, top_union->colTypes))
+			{
+				/* Same UNION, so fold children into parent */
+				pending_rels = lcons(op->rarg, pending_rels);
+				pending_rels = lcons(op->larg, pending_rels);
+				continue;
+			}
 		}
+
+		/*
+		 * Not same, so plan this child separately.
+		 *
+		 * Note we disallow any resjunk columns in child results.  This is
+		 * necessary since the Append node that implements the union won't do
+		 * any projection, and upper levels will get confused if some of our
+		 * output tuples have junk and some don't.  This case only arises when
+		 * we have an EXCEPT or INTERSECT as child, else there won't be
+		 * resjunk anyway.
+		 */
+		result = lappend(result, recurse_set_operations(setOp, root,
+														top_union->colTypes,
+														top_union->colCollations,
+														false, -1,
+														refnames_tlist,
+														&child_tlist,
+														NULL));
+		*tlist_list = lappend(*tlist_list, child_tlist);
 	}
 
-	/*
-	 * Not same, so plan this child separately.
-	 *
-	 * Note we disallow any resjunk columns in child results.  This is
-	 * necessary since the Append node that implements the union won't do any
-	 * projection, and upper levels will get confused if some of our output
-	 * tuples have junk and some don't.  This case only arises when we have an
-	 * EXCEPT or INTERSECT as child, else there won't be resjunk anyway.
-	 */
-	result = list_make1(recurse_set_operations(setOp, root,
-											   top_union->colTypes,
-											   top_union->colCollations,
-											   false, -1,
-											   refnames_tlist,
-											   &child_tlist,
-											   NULL));
-	*tlist_list = list_make1(child_tlist);
 	return result;
 }
 
-- 
2.14.3 (Apple Git-98)

From 3d2c58b65aeecbd6484a31066ccc8b8f2ede583b Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 11:53:07 -0500
Subject: [PATCH 1/4] Let Parallel Append over simple UNION ALL have partial
 subpaths.

A simple UNION ALL gets flattened into an appendrel of subquery
RTEs, but up until now it's been impossible for the appendrel to use
the partial paths for the subqueries, so we can implement the
appendrel as a Parallel Append but only one with non-partial paths
as children.

There are three separate obstacles to removing that limitation.
First, when planning a subquery, propagate any partial paths to the
final_rel so that they are potentially visible to outer query
levels.  Second, after planning a subquery, propagate any partial
paths for the final_rel to the subquery RTE in the outer query
level in the same way we do for non-partial paths.  Third, teach
finalize_plan() to account for the possibility that the fake
parameter we use for rescan signalling when the plan contains a
Gather (Merge) node may be propagated from an outer query level.

Patch by me.

Discussion: http://postgr.es/m/CA+Tgmoa6L9A1nNCk3aTDVZLZ4KkHDn1+tm7mFyFvP+uQPS7bAg@mail.gmail.com
---
 src/backend/optimizer/path/allpaths.c  | 22 ++++++++++++++++++++++
 src/backend/optimizer/plan/planner.c   | 16 ++++++++++++++++
 src/backend/optimizer/plan/subselect.c | 10 ++++++++--
 3 files changed, 46 insertions(+), 2 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index f714247ebb..f15bddc575 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2179,6 +2179,28 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 				 create_subqueryscan_path(root, rel, subpath,
 										  pathkeys, required_outer));
 	}
+
+	/* If consider_parallel is false, there should be no partial paths. */
+	Assert(sub_final_rel->consider_parallel ||
+		   sub_final_rel->partial_pathlist == NIL);
+
+	/* Same for partial paths. */
+	foreach(lc, sub_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,
+												  pathkeys, required_outer));
+	}
 }
 
 /*
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 3e8cd1447c..6a4c5d35a6 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -2161,6 +2161,22 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		add_path(final_rel, path);
 	}
 
+	/*
+	 * Generate partial paths for final_rel, too, if outer query levels might
+	 * be able to make use of them.
+	 */
+	if (final_rel->consider_parallel && root->query_level > 1 &&
+		!limit_needed(parse))
+	{
+		Assert(!parse->rowMarks && parse->commandType == CMD_SELECT);
+		foreach(lc, current_rel->partial_pathlist)
+		{
+			Path	   *partial_path = (Path *) lfirst(lc);
+
+			add_partial_path(final_rel, partial_path);
+		}
+	}
+
 	/*
 	 * If there is an FDW that's responsible for all baserels of the query,
 	 * let it consider adding ForeignPaths.
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 46367cba63..680ffd2cf9 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -2407,10 +2407,16 @@ finalize_plan(PlannerInfo *root, Plan *plan,
 			{
 				SubqueryScan *sscan = (SubqueryScan *) plan;
 				RelOptInfo *rel;
+				Bitmapset  *subquery_params;
 
-				/* We must run SS_finalize_plan on the subquery */
+				/* We must run finalize_plan on the subquery */
 				rel = find_base_rel(root, sscan->scan.scanrelid);
-				SS_finalize_plan(rel->subroot, sscan->subplan);
+				subquery_params = rel->subroot->outer_params;
+				if (gather_param >= 0)
+					subquery_params = bms_add_member(bms_copy(subquery_params),
+													 gather_param);
+				finalize_plan(rel->subroot, sscan->subplan, gather_param,
+							  subquery_params, NULL);
 
 				/* Now we can add its extParams to the parent's params */
 				context.paramids = bms_add_members(context.paramids,
-- 
2.14.3 (Apple Git-98)

From 8cde9c92e038659ada5f591ab7f9d28d6189e2f7 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Sat, 23 Dec 2017 10:56:07 -0800
Subject: [PATCH 5/5] Consider Parallel Append as a way to implement a union
 operation in a setop tree.

---
 src/backend/optimizer/prep/prepunion.c | 93 +++++++++++++++++++++++++++++++++-
 1 file changed, 91 insertions(+), 2 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 6e5524046f..2f259ab0fe 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -298,12 +298,18 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		 */
 		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(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).
 		 */
-		final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
 		subpath = get_cheapest_fractional_path(final_rel,
 											   root->tuple_fraction);
 
@@ -320,6 +326,23 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 		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 (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,
+										 NIL, NULL);
+			add_partial_path(rel, partial_path);
+		}
+
 		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
 		 * grouping or aggregation, its output is probably mostly unique
@@ -552,6 +575,9 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	double		save_fraction = root->tuple_fraction;
 	ListCell   *lc;
 	List	   *pathlist = NIL;
+	List	   *partial_pathlist = NIL;
+	bool		partial_paths_valid = true;
+	bool		consider_parallel = true;
 	List	   *rellist;
 	List	   *tlist_list;
 	List	   *tlist;
@@ -591,18 +617,34 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
-	/* Build path list and relid set. */
+	/* Build path lists and relid set. */
 	foreach(lc, rellist)
 	{
 		RelOptInfo *rel = lfirst(lc);
 
 		pathlist = lappend(pathlist, rel->cheapest_total_path);
+
+		if (consider_parallel)
+		{
+			if (!rel->consider_parallel)
+			{
+				consider_parallel = false;
+				partial_paths_valid = false;
+			}
+			else if (rel->partial_pathlist == NIL)
+				partial_paths_valid = false;
+			else
+				partial_pathlist = lappend(partial_pathlist,
+										   linitial(rel->partial_pathlist));
+		}
+
 		relids = bms_union(relids, rel->relids);
 	}
 
 	/* Build result relation. */
 	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
 	result_rel->reltarget = create_pathtarget(root, tlist);
+	result_rel->consider_parallel = consider_parallel;
 
 	/*
 	 * Append the child results together.
@@ -626,6 +668,53 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	 */
 	result_rel->rows = path->rows;
 
+	/*
+	 * Now consider doing the same thing using the partial paths plus Append
+	 * plus Gather.
+	 */
+	if (partial_paths_valid)
+	{
+		Path	   *ppath;
+		ListCell   *lc;
+		int			parallel_workers = 0;
+
+		/* Find the highest number of workers requested for any subpath. */
+		foreach(lc, partial_pathlist)
+		{
+			Path	   *path = lfirst(lc);
+
+			parallel_workers = Max(parallel_workers, path->parallel_workers);
+		}
+		Assert(parallel_workers > 0);
+
+		/*
+		 * If the use of parallel append is permitted, always request at least
+		 * log2(# of children) paths.  We assume it can be useful to have
+		 * extra workers in this case because they will be spread out across
+		 * the children.  The precise formula is just a guess; see
+		 * add_paths_to_append_rel.
+		 */
+		if (enable_parallel_append)
+		{
+			parallel_workers = Max(parallel_workers,
+								   fls(list_length(partial_pathlist)));
+			parallel_workers = Min(parallel_workers,
+								   max_parallel_workers_per_gather);
+		}
+		Assert(parallel_workers > 0);
+
+		ppath = (Path *)
+			create_append_path(result_rel, NIL, partial_pathlist,
+							   NULL, parallel_workers, enable_parallel_append,
+							   NIL /* XXX? Is this right? */ , -1);
+		ppath = (Path *)
+			create_gather_path(root, result_rel, ppath,
+							   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;
 
-- 
2.14.3 (Apple Git-98)

From 7b79170661a9255b6237e7d3fe01a33a75c9ecc3 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 15:42:51 -0500
Subject: [PATCH 4/5] Generate a separate upper relation for each stage of
 setop planning.

Commit 3fc6e2d7f5b652b417fa6937c34de2438d60fa9f made setop planning
stages return paths rather than plans, but all such paths were loosely
associated with a single RelOptInfo, and only the final path was added
to the RelOptInfo.  Even at the time, it was foreseen that this should
be changed, because there is otherwise no good way for a single stage
of setop planning to return multiple paths.  With this patch, each
stage of set operation planning now creates a separate RelOptInfo;
these are distinguished by using appropriate relid sets.  Note that
this patch does nothing whatsoever about actually returning multiple
paths for the same set operation; it just makes it possible for a
future patch to do so.

Along the way, adjust things so that create_upper_paths_hook is called
for each of these new RelOptInfos rather than just once, since that
might be useful to extensions using that hook.  It might be a good
to provide an FDW API here as well, but I didn't try to do that for
now.

Patch by me.
---
 src/backend/optimizer/prep/prepunion.c | 330 ++++++++++++++++++---------------
 1 file changed, 185 insertions(+), 145 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index f387387289..6e5524046f 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -60,30 +60,29 @@ typedef struct
 	AppendRelInfo **appinfos;
 } adjust_appendrel_attrs_context;
 
-static Path *recurse_set_operations(Node *setOp, PlannerInfo *root,
+static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List *colTypes, List *colCollations,
 					   bool junkOK,
 					   int flag, List *refnames_tlist,
 					   List **pTargetList,
 					   double *pNumGroups);
-static Path *generate_recursion_path(SetOperationStmt *setOp,
+static RelOptInfo *generate_recursion_path(SetOperationStmt *setOp,
 						PlannerInfo *root,
 						List *refnames_tlist,
 						List **pTargetList);
-static Path *generate_union_path(SetOperationStmt *op, PlannerInfo *root,
+static RelOptInfo *generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 					List *refnames_tlist,
-					List **pTargetList,
-					double *pNumGroups);
-static Path *generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
+					List **pTargetList);
+static RelOptInfo *generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 					   List *refnames_tlist,
-					   List **pTargetList,
-					   double *pNumGroups);
+					   List **pTargetList);
 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);
+static void postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
 					Path *input_path,
 					double dNumGroups, double dNumOutputRows,
@@ -149,7 +148,6 @@ plan_set_operations(PlannerInfo *root)
 	RangeTblEntry *leftmostRTE;
 	Query	   *leftmostQuery;
 	RelOptInfo *setop_rel;
-	Path	   *path;
 	List	   *top_tlist;
 
 	Assert(topop);
@@ -181,57 +179,34 @@ plan_set_operations(PlannerInfo *root)
 	leftmostQuery = leftmostRTE->subquery;
 	Assert(leftmostQuery != NULL);
 
-	/*
-	 * We return our results in the (SETOP, NULL) upperrel.  For the moment,
-	 * this is also the parent rel of all Paths in the setop tree; we may well
-	 * change that in future.
-	 */
-	setop_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
-
-	/*
-	 * We don't currently worry about setting setop_rel's consider_parallel
-	 * flag, nor about allowing FDWs to contribute paths to it.
-	 */
-
 	/*
 	 * If the topmost node is a recursive union, it needs special processing.
 	 */
 	if (root->hasRecursion)
 	{
-		path = generate_recursion_path(topop, root,
-									   leftmostQuery->targetList,
-									   &top_tlist);
+		setop_rel = generate_recursion_path(topop, root,
+											leftmostQuery->targetList,
+											&top_tlist);
 	}
 	else
 	{
 		/*
 		 * Recurse on setOperations tree to generate paths for set ops. The
-		 * final output path should have just the column types shown as the
+		 * final output paths should have just the column types shown as the
 		 * output from the top-level node, plus possibly resjunk working
 		 * columns (we can rely on upper-level nodes to deal with that).
 		 */
-		path = recurse_set_operations((Node *) topop, root,
-									  topop->colTypes, topop->colCollations,
-									  true, -1,
-									  leftmostQuery->targetList,
-									  &top_tlist,
-									  NULL);
+		setop_rel = recurse_set_operations((Node *) topop, root,
+										   topop->colTypes, topop->colCollations,
+										   true, -1,
+										   leftmostQuery->targetList,
+										   &top_tlist,
+										   NULL);
 	}
 
 	/* Must return the built tlist into root->processed_tlist. */
 	root->processed_tlist = top_tlist;
 
-	/* Add only the final path to the SETOP upperrel. */
-	add_path(setop_rel, path);
-
-	/* Let extensions possibly add some more paths */
-	if (create_upper_paths_hook)
-		(*create_upper_paths_hook) (root, UPPERREL_SETOP,
-									NULL, setop_rel);
-
-	/* Select cheapest path */
-	set_cheapest(setop_rel);
-
 	return setop_rel;
 }
 
@@ -245,21 +220,21 @@ plan_set_operations(PlannerInfo *root)
  * flag: if >= 0, add a resjunk output column indicating value of flag
  * refnames_tlist: targetlist to take column names from
  *
- * Returns a path for the subtree, as well as these output parameters:
+ * Returns a RelOptInfo for the subtree, as well as these output parameters:
  * *pTargetList: receives the fully-fledged tlist for the subtree's top plan
  * *pNumGroups: if not NULL, we estimate the number of distinct groups
  *		in the result, and store it there
  *
  * The pTargetList output parameter is mostly redundant with the pathtarget
- * of the returned path, but for the moment we need it because much of 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.
+ * of the returned RelOptInfo, but for the moment we need it because much of
+ * the logic in this file depends on flag columns being marked resjunk.
+ * Pending a redesign of how that works, this is the easy way out.
  *
  * 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.
  */
-static Path *
+static RelOptInfo *
 recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List *colTypes, List *colCollations,
 					   bool junkOK,
@@ -267,6 +242,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List **pTargetList,
 					   double *pNumGroups)
 {
+	RelOptInfo *rel = NULL;		/* keep compiler quiet */
+
 	/* Guard against stack overflow due to overly complex setop nests */
 	check_stack_depth();
 
@@ -275,7 +252,6 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		RangeTblRef *rtr = (RangeTblRef *) setOp;
 		RangeTblEntry *rte = root->simple_rte_array[rtr->rtindex];
 		Query	   *subquery = rte->subquery;
-		RelOptInfo *rel;
 		PlannerInfo *subroot;
 		RelOptInfo *final_rel;
 		Path	   *subpath;
@@ -284,11 +260,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 		Assert(subquery != NULL);
 
-		/*
-		 * We need to build a RelOptInfo for each leaf subquery.  This isn't
-		 * used for much here, but it carries the subroot data structures
-		 * forward to setrefs.c processing.
-		 */
+		/* Build a RelOptInfo for this leaf subquery. */
 		rel = build_simple_rel(root, rtr->rtindex, NULL);
 
 		/* plan_params should not be in use in current query level */
@@ -307,6 +279,18 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		if (root->plan_params)
 			elog(ERROR, "unexpected outer reference in set operation subquery");
 
+		/* Figure out the appropriate target list for this subquery. */
+		tlist = generate_setop_tlist(colTypes, colCollations,
+									 flag,
+									 rtr->rtindex,
+									 true,
+									 subroot->processed_tlist,
+									 refnames_tlist);
+		rel->reltarget = create_pathtarget(root, tlist);
+
+		/* 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
@@ -334,22 +318,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		path = (Path *) create_subqueryscan_path(root, rel, subpath,
 												 NIL, NULL);
 
-		/*
-		 * Figure out the appropriate target list, and update the
-		 * SubqueryScanPath with the PathTarget form of that.
-		 */
-		tlist = generate_setop_tlist(colTypes, colCollations,
-									 flag,
-									 rtr->rtindex,
-									 true,
-									 subroot->processed_tlist,
-									 refnames_tlist);
-
-		path = apply_projection_to_path(root, rel, path,
-										create_pathtarget(root, tlist));
-
-		/* Return the fully-fledged tlist to caller, too */
-		*pTargetList = tlist;
+		add_path(rel, path);
 
 		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
@@ -378,25 +347,22 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 												  subpath->rows,
 												  NULL);
 		}
-
-		return (Path *) path;
 	}
 	else if (IsA(setOp, SetOperationStmt))
 	{
 		SetOperationStmt *op = (SetOperationStmt *) setOp;
-		Path	   *path;
 
 		/* UNIONs are much different from INTERSECT/EXCEPT */
 		if (op->op == SETOP_UNION)
-			path = generate_union_path(op, root,
-									   refnames_tlist,
-									   pTargetList,
-									   pNumGroups);
+			rel = generate_union_path(op, root,
+									  refnames_tlist,
+									  pTargetList);
 		else
-			path = generate_nonunion_path(op, root,
-										  refnames_tlist,
-										  pTargetList,
-										  pNumGroups);
+			rel = generate_nonunion_path(op, root,
+										 refnames_tlist,
+										 pTargetList);
+		if (pNumGroups)
+			*pNumGroups = rel->rows;
 
 		/*
 		 * If necessary, add a Result node to project the caller-requested
@@ -415,39 +381,70 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 			!tlist_same_datatypes(*pTargetList, colTypes, junkOK) ||
 			!tlist_same_collations(*pTargetList, colCollations, junkOK))
 		{
+			PathTarget *target;
+			ListCell   *lc;
+
 			*pTargetList = generate_setop_tlist(colTypes, colCollations,
 												flag,
 												0,
 												false,
 												*pTargetList,
 												refnames_tlist);
-			path = apply_projection_to_path(root,
-											path->parent,
-											path,
-											create_pathtarget(root,
-															  *pTargetList));
+			target = create_pathtarget(root, *pTargetList);
+
+			/* Apply projection to each path */
+			foreach(lc, rel->pathlist)
+			{
+				Path	   *subpath = (Path *) lfirst(lc);
+				Path	   *path;
+
+				Assert(subpath->param_info == NULL);
+				path = apply_projection_to_path(root, subpath->parent,
+												subpath, target);
+				/* If we had to add a Result, path is different from subpath */
+				if (path != subpath)
+					lfirst(lc) = path;
+			}
+
+			/* Apply projection to each partial path */
+			foreach(lc, rel->partial_pathlist)
+			{
+				Path	   *subpath = (Path *) lfirst(lc);
+				Path	   *path;
+
+				Assert(subpath->param_info == NULL);
+
+				/* avoid apply_projection_to_path, in case of multiple refs */
+				path = (Path *) create_projection_path(root, subpath->parent,
+													   subpath, target);
+				lfirst(lc) = path;
+			}
 		}
-		return path;
 	}
 	else
 	{
 		elog(ERROR, "unrecognized node type: %d",
 			 (int) nodeTag(setOp));
 		*pTargetList = NIL;
-		return NULL;			/* keep compiler quiet */
 	}
+
+	postprocess_setop_rel(root, rel);
+
+	return rel;
 }
 
 /*
- * Generate path for a recursive UNION node
+ * Generate paths for a recursive UNION node
  */
-static Path *
+static RelOptInfo *
 generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 						List *refnames_tlist,
 						List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	RelOptInfo *result_rel;
 	Path	   *path;
+	RelOptInfo *lrel,
+			   *rrel;
 	Path	   *lpath;
 	Path	   *rpath;
 	List	   *lpath_tlist;
@@ -466,20 +463,22 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	 * Unlike a regular UNION node, process the left and right inputs
 	 * separately without any intention of combining them into one Append.
 	 */
-	lpath = recurse_set_operations(setOp->larg, root,
-								   setOp->colTypes, setOp->colCollations,
-								   false, -1,
-								   refnames_tlist,
-								   &lpath_tlist,
-								   NULL);
+	lrel = recurse_set_operations(setOp->larg, root,
+								  setOp->colTypes, setOp->colCollations,
+								  false, -1,
+								  refnames_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;
-	rpath = recurse_set_operations(setOp->rarg, root,
-								   setOp->colTypes, setOp->colCollations,
-								   false, -1,
-								   refnames_tlist,
-								   &rpath_tlist,
-								   NULL);
+	rrel = recurse_set_operations(setOp->rarg, root,
+								  setOp->colTypes, setOp->colCollations,
+								  false, -1,
+								  refnames_tlist,
+								  &rpath_tlist,
+								  NULL);
+	rpath = rrel->cheapest_total_path;
 	root->non_recursive_path = NULL;
 
 	/*
@@ -491,6 +490,11 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
+								 bms_union(lrel->relids, rrel->relids));
+	result_rel->reltarget = create_pathtarget(root, tlist);
+
 	/*
 	 * If UNION, identify the grouping operators
 	 */
@@ -525,26 +529,30 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 											   result_rel,
 											   lpath,
 											   rpath,
-											   create_pathtarget(root, tlist),
+											   result_rel->reltarget,
 											   groupList,
 											   root->wt_param_id,
 											   dNumGroups);
 
-	return path;
+	add_path(result_rel, path);
+	postprocess_setop_rel(root, result_rel);
+	return result_rel;
 }
 
 /*
- * Generate path for a UNION or UNION ALL node
+ * Generate paths for a UNION or UNION ALL node
  */
-static Path *
+static RelOptInfo *
 generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 					List *refnames_tlist,
-					List **pTargetList,
-					double *pNumGroups)
+					List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	Relids		relids = NULL;
+	RelOptInfo *result_rel;
 	double		save_fraction = root->tuple_fraction;
-	List	   *pathlist;
+	ListCell   *lc;
+	List	   *pathlist = NIL;
+	List	   *rellist;
 	List	   *tlist_list;
 	List	   *tlist;
 	Path	   *path;
@@ -569,7 +577,7 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	pathlist = plan_union_children(root, op, refnames_tlist, &tlist_list);
+	rellist = plan_union_children(root, op, refnames_tlist, &tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -583,13 +591,24 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build path list and relid set. */
+	foreach(lc, rellist)
+	{
+		RelOptInfo *rel = lfirst(lc);
+
+		pathlist = lappend(pathlist, rel->cheapest_total_path);
+		relids = bms_union(relids, rel->relids);
+	}
+
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
+	result_rel->reltarget = create_pathtarget(root, tlist);
+
 	/*
 	 * Append the child results together.
 	 */
 	path = (Path *) create_append_path(result_rel, pathlist, NIL,
 									   NULL, 0, false, NIL, -1);
-	/* We have to manually jam the right tlist into the path; ick */
-	path->pathtarget = create_pathtarget(root, tlist);
 
 	/*
 	 * For UNION ALL, we just need the Append path.  For UNION, need to add
@@ -598,30 +617,32 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	if (!op->all)
 		path = make_union_unique(op, path, tlist, root);
 
+	add_path(result_rel, path);
+
 	/*
-	 * Estimate number of groups if caller wants it.  For now we just assume
-	 * the output is unique --- this is certainly true for the UNION case, and
-	 * we want worst-case estimates anyway.
+	 * 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.
 	 */
-	if (pNumGroups)
-		*pNumGroups = path->rows;
+	result_rel->rows = path->rows;
 
 	/* Undo effects of possibly forcing tuple_fraction to 0 */
 	root->tuple_fraction = save_fraction;
 
-	return path;
+	return result_rel;
 }
 
 /*
- * Generate path for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
+ * Generate paths for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
  */
-static Path *
+static RelOptInfo *
 generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 					   List *refnames_tlist,
-					   List **pTargetList,
-					   double *pNumGroups)
+					   List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	RelOptInfo *result_rel;
+	RelOptInfo *lrel,
+			   *rrel;
 	double		save_fraction = root->tuple_fraction;
 	Path	   *lpath,
 			   *rpath,
@@ -646,18 +667,20 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 	root->tuple_fraction = 0.0;
 
 	/* Recurse on children, ensuring their outputs are marked */
-	lpath = recurse_set_operations(op->larg, root,
-								   op->colTypes, op->colCollations,
-								   false, 0,
-								   refnames_tlist,
-								   &lpath_tlist,
-								   &dLeftGroups);
-	rpath = recurse_set_operations(op->rarg, root,
-								   op->colTypes, op->colCollations,
-								   false, 1,
-								   refnames_tlist,
-								   &rpath_tlist,
-								   &dRightGroups);
+	lrel = recurse_set_operations(op->larg, root,
+								  op->colTypes, op->colCollations,
+								  false, 0,
+								  refnames_tlist,
+								  &lpath_tlist,
+								  &dLeftGroups);
+	lpath = lrel->cheapest_total_path;
+	rrel = recurse_set_operations(op->rarg, root,
+								  op->colTypes, op->colCollations,
+								  false, 1,
+								  refnames_tlist,
+								  &rpath_tlist,
+								  &dRightGroups);
+	rpath = rrel->cheapest_total_path;
 
 	/* Undo effects of forcing tuple_fraction to 0 */
 	root->tuple_fraction = save_fraction;
@@ -695,15 +718,17 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
+								 bms_union(lrel->relids, rrel->relids));
+	result_rel->reltarget = create_pathtarget(root, tlist);;
+
 	/*
 	 * Append the child results together.
 	 */
 	path = (Path *) create_append_path(result_rel, pathlist, NIL,
 									   NULL, 0, false, NIL, -1);
 
-	/* We have to manually jam the right tlist into the path; ick */
-	path->pathtarget = create_pathtarget(root, tlist);
-
 	/* Identify the grouping semantics */
 	groupList = generate_setop_grouplist(op, tlist);
 
@@ -769,10 +794,9 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 									  dNumGroups,
 									  dNumOutputRows);
 
-	if (pNumGroups)
-		*pNumGroups = dNumGroups;
-
-	return path;
+	result_rel->rows = path->rows;
+	add_path(result_rel, path);
+	return result_rel;
 }
 
 /*
@@ -897,8 +921,6 @@ make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
 															   groupList,
 															   tlist),
 								 -1.0);
-		/* We have to manually jam the right tlist into the path; ick */
-		path->pathtarget = create_pathtarget(root, tlist);
 		path = (Path *) create_upper_unique_path(root,
 												 result_rel,
 												 path,
@@ -909,6 +931,24 @@ make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
 	return path;
 }
 
+/*
+ * postprocess_setop_rel - perform steps required after adding paths
+ */
+static void
+postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel)
+{
+	/*
+	 * We don't currently worry about allowing FDWs to contribute paths to
+	 * this relation, but give extensions a chance.
+	 */
+	if (create_upper_paths_hook)
+		(*create_upper_paths_hook) (root, UPPERREL_SETOP,
+									NULL, rel);
+
+	/* Select cheapest path */
+	set_cheapest(rel);
+}
+
 /*
  * choose_hashed_setop - should we use hashing for a set operation?
  */
-- 
2.14.3 (Apple Git-98)

From 19a7ad8b89d9a1fc11c105343bde9e01df31a204 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 12:13:46 -0500
Subject: [PATCH 3/5] Rewrite recurse_union_children to iterate, rather than
 recurse.

Also, rename it to plan_union_chidren, so the old name wasn't
very descriptive.  This results in a small net reduction in code,
seems at least to me to be easier to understand, and saves
space on the process stack.
---
 src/backend/optimizer/prep/prepunion.c | 100 ++++++++++++++++-----------------
 1 file changed, 47 insertions(+), 53 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index b586f941a8..f387387289 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -78,10 +78,10 @@ static Path *generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 					   List *refnames_tlist,
 					   List **pTargetList,
 					   double *pNumGroups);
-static List *recurse_union_children(Node *setOp, PlannerInfo *root,
-					   SetOperationStmt *top_union,
-					   List *refnames_tlist,
-					   List **tlist_list);
+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);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
@@ -545,8 +545,6 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
 	double		save_fraction = root->tuple_fraction;
 	List	   *pathlist;
-	List	   *child_tlists1;
-	List	   *child_tlists2;
 	List	   *tlist_list;
 	List	   *tlist;
 	Path	   *path;
@@ -571,13 +569,7 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	pathlist = list_concat(recurse_union_children(op->larg, root,
-												  op, refnames_tlist,
-												  &child_tlists1),
-						   recurse_union_children(op->rarg, root,
-												  op, refnames_tlist,
-												  &child_tlists2));
-	tlist_list = list_concat(child_tlists1, child_tlists2);
+	pathlist = plan_union_children(root, op, refnames_tlist, &tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -797,56 +789,58 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
  * generate_union_path will force a fresh sort if the top level is a UNION.
  */
 static List *
-recurse_union_children(Node *setOp, PlannerInfo *root,
-					   SetOperationStmt *top_union,
-					   List *refnames_tlist,
-					   List **tlist_list)
+plan_union_children(PlannerInfo *root,
+					SetOperationStmt *top_union,
+					List *refnames_tlist,
+					List **tlist_list)
 {
-	List	   *result;
+	List	   *pending_rels = list_make1(top_union);
+	List	   *result = NIL;
 	List	   *child_tlist;
 
-	if (IsA(setOp, SetOperationStmt))
+	*tlist_list = NIL;
+
+	while (pending_rels != NIL)
 	{
-		SetOperationStmt *op = (SetOperationStmt *) setOp;
+		Node	   *setOp = linitial(pending_rels);
+
+		pending_rels = list_delete_first(pending_rels);
 
-		if (op->op == top_union->op &&
-			(op->all == top_union->all || op->all) &&
-			equal(op->colTypes, top_union->colTypes))
+		if (IsA(setOp, SetOperationStmt))
 		{
-			/* Same UNION, so fold children into parent's subpath list */
-			List	   *child_tlists1;
-			List	   *child_tlists2;
+			SetOperationStmt *op = (SetOperationStmt *) setOp;
 
-			result = list_concat(recurse_union_children(op->larg, root,
-														top_union,
-														refnames_tlist,
-														&child_tlists1),
-								 recurse_union_children(op->rarg, root,
-														top_union,
-														refnames_tlist,
-														&child_tlists2));
-			*tlist_list = list_concat(child_tlists1, child_tlists2);
-			return result;
+			if (op->op == top_union->op &&
+				(op->all == top_union->all || op->all) &&
+				equal(op->colTypes, top_union->colTypes))
+			{
+				/* Same UNION, so fold children into parent */
+				pending_rels = lcons(op->rarg, pending_rels);
+				pending_rels = lcons(op->larg, pending_rels);
+				continue;
+			}
 		}
+
+		/*
+		 * Not same, so plan this child separately.
+		 *
+		 * Note we disallow any resjunk columns in child results.  This is
+		 * necessary since the Append node that implements the union won't do
+		 * any projection, and upper levels will get confused if some of our
+		 * output tuples have junk and some don't.  This case only arises when
+		 * we have an EXCEPT or INTERSECT as child, else there won't be
+		 * resjunk anyway.
+		 */
+		result = lappend(result, recurse_set_operations(setOp, root,
+														top_union->colTypes,
+														top_union->colCollations,
+														false, -1,
+														refnames_tlist,
+														&child_tlist,
+														NULL));
+		*tlist_list = lappend(*tlist_list, child_tlist);
 	}
 
-	/*
-	 * Not same, so plan this child separately.
-	 *
-	 * Note we disallow any resjunk columns in child results.  This is
-	 * necessary since the Append node that implements the union won't do any
-	 * projection, and upper levels will get confused if some of our output
-	 * tuples have junk and some don't.  This case only arises when we have an
-	 * EXCEPT or INTERSECT as child, else there won't be resjunk anyway.
-	 */
-	result = list_make1(recurse_set_operations(setOp, root,
-											   top_union->colTypes,
-											   top_union->colCollations,
-											   false, -1,
-											   refnames_tlist,
-											   &child_tlist,
-											   NULL));
-	*tlist_list = list_make1(child_tlist);
 	return result;
 }
 
-- 
2.14.3 (Apple Git-98)

From 5e8b16bc7ef7043216ea6d48608973302b630870 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 11:53:07 -0500
Subject: [PATCH 2/5] Let Parallel Append over simple UNION ALL have partial
 subpaths.

A simple UNION ALL gets flattened into an appendrel of subquery
RTEs, but up until now it's been impossible for the appendrel to use
the partial paths for the subqueries, so we can implement the
appendrel as a Parallel Append but only one with non-partial paths
as children.

There are three separate obstacles to removing that limitation.
First, when planning a subquery, propagate any partial paths to the
final_rel so that they are potentially visible to outer query levels
(but not if they have initPlans attached, because that wouldn't be
safe).  Second, after planning a subquery, propagate any partial paths
for the final_rel to the subquery RTE in the outer query level in the
same way we do for non-partial paths.  Third, teach finalize_plan() to
account for the possibility that the fake parameter we use for rescan
signalling when the plan contains a Gather (Merge) node may be
propagated from an outer query level.

Patch by me, reviewed and tested by Amit Khandekar and Rajkumar
Raghuwanshi.  Test cases based on examples by Rajkumar Raghuwanshi.

Discussion: http://postgr.es/m/CA+Tgmoa6L9A1nNCk3aTDVZLZ4KkHDn1+tm7mFyFvP+uQPS7bAg@mail.gmail.com
---
 src/backend/optimizer/path/allpaths.c         | 22 +++++++++
 src/backend/optimizer/plan/planner.c          | 16 +++++++
 src/backend/optimizer/plan/subselect.c        | 17 ++++++-
 src/test/regress/expected/select_parallel.out | 65 +++++++++++++++++++++++++++
 src/test/regress/sql/select_parallel.sql      | 25 +++++++++++
 5 files changed, 143 insertions(+), 2 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 1c792a00eb..ea4e683abb 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2179,6 +2179,28 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 				 create_subqueryscan_path(root, rel, subpath,
 										  pathkeys, required_outer));
 	}
+
+	/* If consider_parallel is false, there should be no partial paths. */
+	Assert(sub_final_rel->consider_parallel ||
+		   sub_final_rel->partial_pathlist == NIL);
+
+	/* Same for partial paths. */
+	foreach(lc, sub_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,
+												  pathkeys, required_outer));
+	}
 }
 
 /*
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 14b7becf3e..91b32d4947 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -2194,6 +2194,22 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		add_path(final_rel, path);
 	}
 
+	/*
+	 * Generate partial paths for final_rel, too, if outer query levels might
+	 * be able to make use of them.
+	 */
+	if (final_rel->consider_parallel && root->query_level > 1 &&
+		!limit_needed(parse))
+	{
+		Assert(!parse->rowMarks && parse->commandType == CMD_SELECT);
+		foreach(lc, current_rel->partial_pathlist)
+		{
+			Path	   *partial_path = (Path *) lfirst(lc);
+
+			add_partial_path(final_rel, partial_path);
+		}
+	}
+
 	/*
 	 * If there is an FDW that's responsible for all baserels of the query,
 	 * let it consider adding ForeignPaths.
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 46367cba63..32bf1fd955 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -2202,6 +2202,13 @@ SS_charge_for_initplans(PlannerInfo *root, RelOptInfo *final_rel)
 		path->parallel_safe = false;
 	}
 
+	/*
+	 * Forget about any partial paths and clear consider_parallel, too;
+	 * they're not usable if we attached an initPlan.
+	 */
+	final_rel->partial_pathlist = NIL;
+	final_rel->consider_parallel = false;
+
 	/* We needn't do set_cheapest() here, caller will do it */
 }
 
@@ -2407,10 +2414,16 @@ finalize_plan(PlannerInfo *root, Plan *plan,
 			{
 				SubqueryScan *sscan = (SubqueryScan *) plan;
 				RelOptInfo *rel;
+				Bitmapset  *subquery_params;
 
-				/* We must run SS_finalize_plan on the subquery */
+				/* We must run finalize_plan on the subquery */
 				rel = find_base_rel(root, sscan->scan.scanrelid);
-				SS_finalize_plan(rel->subroot, sscan->subplan);
+				subquery_params = rel->subroot->outer_params;
+				if (gather_param >= 0)
+					subquery_params = bms_add_member(bms_copy(subquery_params),
+													 gather_param);
+				finalize_plan(rel->subroot, sscan->subplan, gather_param,
+							  subquery_params, NULL);
 
 				/* Now we can add its extParams to the parent's params */
 				context.paramids = bms_add_members(context.paramids,
diff --git a/src/test/regress/expected/select_parallel.out b/src/test/regress/expected/select_parallel.out
index 0a78261638..2fb16d1a15 100644
--- a/src/test/regress/expected/select_parallel.out
+++ b/src/test/regress/expected/select_parallel.out
@@ -890,4 +890,69 @@ select stringu1::int2 from tenk1 where unique1 = 1;
 ERROR:  invalid input syntax for integer: "BAAAAA"
 CONTEXT:  parallel worker
 ROLLBACK TO SAVEPOINT settings;
+-- test interaction with set-returning functions
+SAVEPOINT settings;
+-- multiple subqueries under a single Gather node
+-- must set parallel_setup_cost > 0 to discourage multiple Gather nodes
+SET LOCAL parallel_setup_cost = 10;
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Gather
+   Workers Planned: 4
+   ->  Parallel Append
+         ->  Parallel Seq Scan on tenk1
+               Filter: (fivethous = (tenthous + 1))
+         ->  Parallel Seq Scan on tenk1 tenk1_1
+               Filter: (fivethous = (tenthous + 1))
+(7 rows)
+
+ROLLBACK TO SAVEPOINT settings;
+-- can't use multiple subqueries under a single Gather node due to initPlans
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique1 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique2 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+ORDER BY 1;
+                             QUERY PLAN                             
+--------------------------------------------------------------------
+ Sort
+   Sort Key: tenk1.unique1
+   ->  Append
+         ->  Gather
+               Workers Planned: 4
+               Params Evaluated: $1
+               InitPlan 1 (returns $1)
+                 ->  Limit
+                       ->  Gather
+                             Workers Planned: 4
+                             ->  Parallel Seq Scan on tenk1 tenk1_2
+                                   Filter: (fivethous = 1)
+               ->  Parallel Seq Scan on tenk1
+                     Filter: (fivethous = $1)
+         ->  Gather
+               Workers Planned: 4
+               Params Evaluated: $3
+               InitPlan 2 (returns $3)
+                 ->  Limit
+                       ->  Gather
+                             Workers Planned: 4
+                             ->  Parallel Seq Scan on tenk1 tenk1_3
+                                   Filter: (fivethous = 1)
+               ->  Parallel Seq Scan on tenk1 tenk1_1
+                     Filter: (fivethous = $3)
+(25 rows)
+
+-- test interaction with SRFs
+SELECT * FROM information_schema.foreign_data_wrapper_options
+ORDER BY 1, 2, 3;
+ foreign_data_wrapper_catalog | foreign_data_wrapper_name | option_name | option_value 
+------------------------------+---------------------------+-------------+--------------
+(0 rows)
+
 rollback;
diff --git a/src/test/regress/sql/select_parallel.sql b/src/test/regress/sql/select_parallel.sql
index fa03aae0c0..ec817f2a4c 100644
--- a/src/test/regress/sql/select_parallel.sql
+++ b/src/test/regress/sql/select_parallel.sql
@@ -358,4 +358,29 @@ SET LOCAL force_parallel_mode = 1;
 select stringu1::int2 from tenk1 where unique1 = 1;
 ROLLBACK TO SAVEPOINT settings;
 
+-- test interaction with set-returning functions
+SAVEPOINT settings;
+
+-- multiple subqueries under a single Gather node
+-- must set parallel_setup_cost > 0 to discourage multiple Gather nodes
+SET LOCAL parallel_setup_cost = 10;
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1;
+ROLLBACK TO SAVEPOINT settings;
+
+-- can't use multiple subqueries under a single Gather node due to initPlans
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique1 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique2 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+ORDER BY 1;
+
+-- test interaction with SRFs
+SELECT * FROM information_schema.foreign_data_wrapper_options
+ORDER BY 1, 2, 3;
+
 rollback;
-- 
2.14.3 (Apple Git-98)

From f6b01233a9f02cae694220c86d0ca00297b278e5 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Wed, 7 Mar 2018 12:23:24 -0500
Subject: [PATCH 1/5] Correctly assess parallel-safety of tlists when SRFs are
 used.

Since commit 69f4b9c85f168ae006929eec44fc44d569e846b9, the existing
code was no longer assessing the parallel-safety of the real tlist
for each upper rel, but rather the first of possibly several tlists
created by split_pathtarget_at_srfs().  Repair.

Patch by me, per a report from Rajkumar Raghuwanshi.
---
 src/backend/optimizer/plan/planner.c | 52 ++++++++++++++++++++++++++++++------
 1 file changed, 44 insertions(+), 8 deletions(-)

diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index de1257d9c2..14b7becf3e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -137,6 +137,7 @@ static Size estimate_hashagg_tablesize(Path *path,
 static RelOptInfo *create_grouping_paths(PlannerInfo *root,
 					  RelOptInfo *input_rel,
 					  PathTarget *target,
+					  bool target_parallel_safe,
 					  const AggClauseCosts *agg_costs,
 					  grouping_sets_data *gd);
 static void consider_groupingsets_paths(PlannerInfo *root,
@@ -152,6 +153,7 @@ static RelOptInfo *create_window_paths(PlannerInfo *root,
 					RelOptInfo *input_rel,
 					PathTarget *input_target,
 					PathTarget *output_target,
+					bool output_target_parallel_safe,
 					List *tlist,
 					WindowFuncLists *wflists,
 					List *activeWindows);
@@ -168,6 +170,7 @@ static RelOptInfo *create_distinct_paths(PlannerInfo *root,
 static RelOptInfo *create_ordered_paths(PlannerInfo *root,
 					 RelOptInfo *input_rel,
 					 PathTarget *target,
+					 bool target_parallel_safe,
 					 double limit_tuples);
 static PathTarget *make_group_input_target(PlannerInfo *root,
 						PathTarget *final_target);
@@ -1583,6 +1586,7 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 	PathTarget *final_target;
 	List	   *final_targets;
 	List	   *final_targets_contain_srfs;
+	bool		final_target_parallel_safe;
 	RelOptInfo *current_rel;
 	RelOptInfo *final_rel;
 	ListCell   *lc;
@@ -1645,6 +1649,10 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		/* Also extract the PathTarget form of the setop result tlist */
 		final_target = current_rel->cheapest_total_path->pathtarget;
 
+		/* And check whether it's parallel safe */
+		final_target_parallel_safe =
+			is_parallel_safe(root, (Node *) final_target->exprs);
+
 		/* The setop result tlist couldn't contain any SRFs */
 		Assert(!parse->hasTargetSRFs);
 		final_targets = final_targets_contain_srfs = NIL;
@@ -1676,12 +1684,15 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		PathTarget *sort_input_target;
 		List	   *sort_input_targets;
 		List	   *sort_input_targets_contain_srfs;
+		bool		sort_input_target_parallel_safe;
 		PathTarget *grouping_target;
 		List	   *grouping_targets;
 		List	   *grouping_targets_contain_srfs;
+		bool		grouping_target_parallel_safe;
 		PathTarget *scanjoin_target;
 		List	   *scanjoin_targets;
 		List	   *scanjoin_targets_contain_srfs;
+		bool		scanjoin_target_parallel_safe;
 		bool		have_grouping;
 		AggClauseCosts agg_costs;
 		WindowFuncLists *wflists = NULL;
@@ -1805,6 +1816,8 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		 * that were obtained within query_planner().
 		 */
 		final_target = create_pathtarget(root, tlist);
+		final_target_parallel_safe =
+			is_parallel_safe(root, (Node *) final_target->exprs);
 
 		/*
 		 * If ORDER BY was given, consider whether we should use a post-sort
@@ -1812,11 +1825,18 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		 * so.
 		 */
 		if (parse->sortClause)
+		{
 			sort_input_target = make_sort_input_target(root,
 													   final_target,
 													   &have_postponed_srfs);
+			sort_input_target_parallel_safe =
+				is_parallel_safe(root, (Node *) sort_input_target->exprs);
+		}
 		else
+		{
 			sort_input_target = final_target;
+			sort_input_target_parallel_safe = final_target_parallel_safe;
+		}
 
 		/*
 		 * If we have window functions to deal with, the output from any
@@ -1824,11 +1844,18 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		 * otherwise, it should be sort_input_target.
 		 */
 		if (activeWindows)
+		{
 			grouping_target = make_window_input_target(root,
 													   final_target,
 													   activeWindows);
+			grouping_target_parallel_safe =
+				is_parallel_safe(root, (Node *) grouping_target->exprs);
+		}
 		else
+		{
 			grouping_target = sort_input_target;
+			grouping_target_parallel_safe = sort_input_target_parallel_safe;
+		}
 
 		/*
 		 * If we have grouping or aggregation to do, the topmost scan/join
@@ -1838,9 +1865,16 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		have_grouping = (parse->groupClause || parse->groupingSets ||
 						 parse->hasAggs || root->hasHavingQual);
 		if (have_grouping)
+		{
 			scanjoin_target = make_group_input_target(root, final_target);
+			scanjoin_target_parallel_safe =
+				is_parallel_safe(root, (Node *) grouping_target->exprs);
+		}
 		else
+		{
 			scanjoin_target = grouping_target;
+			scanjoin_target_parallel_safe = grouping_target_parallel_safe;
+		}
 
 		/*
 		 * If there are any SRFs in the targetlist, we must separate each of
@@ -1922,8 +1956,7 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		 * for partial paths.  But only parallel-safe expressions can be
 		 * computed by partial paths.
 		 */
-		if (current_rel->partial_pathlist &&
-			is_parallel_safe(root, (Node *) scanjoin_target->exprs))
+		if (current_rel->partial_pathlist && scanjoin_target_parallel_safe)
 		{
 			/* Apply the scan/join target to each partial path */
 			foreach(lc, current_rel->partial_pathlist)
@@ -1984,6 +2017,7 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 			current_rel = create_grouping_paths(root,
 												current_rel,
 												grouping_target,
+												grouping_target_parallel_safe,
 												&agg_costs,
 												gset_data);
 			/* Fix things up if grouping_target contains SRFs */
@@ -2003,6 +2037,7 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 											  current_rel,
 											  grouping_target,
 											  sort_input_target,
+											  sort_input_target_parallel_safe,
 											  tlist,
 											  wflists,
 											  activeWindows);
@@ -2036,6 +2071,7 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		current_rel = create_ordered_paths(root,
 										   current_rel,
 										   final_target,
+										   final_target_parallel_safe,
 										   have_postponed_srfs ? -1.0 :
 										   limit_tuples);
 		/* Fix things up if final_target contains SRFs */
@@ -3623,6 +3659,7 @@ static RelOptInfo *
 create_grouping_paths(PlannerInfo *root,
 					  RelOptInfo *input_rel,
 					  PathTarget *target,
+					  bool target_parallel_safe,
 					  const AggClauseCosts *agg_costs,
 					  grouping_sets_data *gd)
 {
@@ -3652,8 +3689,7 @@ create_grouping_paths(PlannerInfo *root,
 	 * target list and HAVING quals are parallel-safe.  The partially grouped
 	 * relation obeys the same rules.
 	 */
-	if (input_rel->consider_parallel &&
-		is_parallel_safe(root, (Node *) target->exprs) &&
+	if (input_rel->consider_parallel && target_parallel_safe &&
 		is_parallel_safe(root, (Node *) parse->havingQual))
 	{
 		grouped_rel->consider_parallel = true;
@@ -4230,6 +4266,7 @@ create_window_paths(PlannerInfo *root,
 					RelOptInfo *input_rel,
 					PathTarget *input_target,
 					PathTarget *output_target,
+					bool output_target_parallel_safe,
 					List *tlist,
 					WindowFuncLists *wflists,
 					List *activeWindows)
@@ -4245,8 +4282,7 @@ create_window_paths(PlannerInfo *root,
 	 * can't be parallel-safe, either.  Otherwise, we need to examine the
 	 * target list and active windows for non-parallel-safe constructs.
 	 */
-	if (input_rel->consider_parallel &&
-		is_parallel_safe(root, (Node *) output_target->exprs) &&
+	if (input_rel->consider_parallel && output_target_parallel_safe &&
 		is_parallel_safe(root, (Node *) activeWindows))
 		window_rel->consider_parallel = true;
 
@@ -4621,6 +4657,7 @@ static RelOptInfo *
 create_ordered_paths(PlannerInfo *root,
 					 RelOptInfo *input_rel,
 					 PathTarget *target,
+					 bool target_parallel_safe,
 					 double limit_tuples)
 {
 	Path	   *cheapest_input_path = input_rel->cheapest_total_path;
@@ -4635,8 +4672,7 @@ create_ordered_paths(PlannerInfo *root,
 	 * can't be parallel-safe, either.  Otherwise, it's parallel-safe if the
 	 * target list is parallel-safe.
 	 */
-	if (input_rel->consider_parallel &&
-		is_parallel_safe(root, (Node *) target->exprs))
+	if (input_rel->consider_parallel && target_parallel_safe)
 		ordered_rel->consider_parallel = true;
 
 	/*
-- 
2.14.3 (Apple Git-98)

From cf37a7afde5ff50bd950e2e172c0e9ddf730ee13 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Sat, 23 Dec 2017 10:56:07 -0800
Subject: [PATCH 4/4] Consider Parallel Append as a way to implement a union
 operation in a setop tree.

Patch by me, reviewed by Ashutosh Bapat.
---
 src/backend/optimizer/prep/prepunion.c | 93 +++++++++++++++++++++++++++++++++-
 1 file changed, 91 insertions(+), 2 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index e477a04f94..b80b9a95bc 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -298,12 +298,18 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		 */
 		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(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).
 		 */
-		final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
 		subpath = get_cheapest_fractional_path(final_rel,
 											   root->tuple_fraction);
 
@@ -320,6 +326,23 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 		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 (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,
+										 NIL, NULL);
+			add_partial_path(rel, partial_path);
+		}
+
 		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
 		 * grouping or aggregation, its output is probably mostly unique
@@ -552,6 +575,9 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	double		save_fraction = root->tuple_fraction;
 	ListCell   *lc;
 	List	   *pathlist = NIL;
+	List	   *partial_pathlist = NIL;
+	bool		partial_paths_valid = true;
+	bool		consider_parallel = true;
 	List	   *rellist;
 	List	   *tlist_list;
 	List	   *tlist;
@@ -591,18 +617,34 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
-	/* Build path list and relid set. */
+	/* Build path lists and relid set. */
 	foreach(lc, rellist)
 	{
 		RelOptInfo *rel = lfirst(lc);
 
 		pathlist = lappend(pathlist, rel->cheapest_total_path);
+
+		if (consider_parallel)
+		{
+			if (!rel->consider_parallel)
+			{
+				consider_parallel = false;
+				partial_paths_valid = false;
+			}
+			else if (rel->partial_pathlist == NIL)
+				partial_paths_valid = false;
+			else
+				partial_pathlist = lappend(partial_pathlist,
+										   linitial(rel->partial_pathlist));
+		}
+
 		relids = bms_union(relids, rel->relids);
 	}
 
 	/* Build result relation. */
 	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
 	result_rel->reltarget = create_pathtarget(root, tlist);
+	result_rel->consider_parallel = consider_parallel;
 
 	/*
 	 * Append the child results together.
@@ -626,6 +668,53 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 */
 	result_rel->rows = path->rows;
 
+	/*
+	 * Now consider doing the same thing using the partial paths plus Append
+	 * plus Gather.
+	 */
+	if (partial_paths_valid)
+	{
+		Path	   *ppath;
+		ListCell   *lc;
+		int			parallel_workers = 0;
+
+		/* Find the highest number of workers requested for any subpath. */
+		foreach(lc, partial_pathlist)
+		{
+			Path	   *path = lfirst(lc);
+
+			parallel_workers = Max(parallel_workers, path->parallel_workers);
+		}
+		Assert(parallel_workers > 0);
+
+		/*
+		 * If the use of parallel append is permitted, always request at least
+		 * log2(# of children) paths.  We assume it can be useful to have
+		 * extra workers in this case because they will be spread out across
+		 * the children.  The precise formula is just a guess; see
+		 * add_paths_to_append_rel.
+		 */
+		if (enable_parallel_append)
+		{
+			parallel_workers = Max(parallel_workers,
+								   fls(list_length(partial_pathlist)));
+			parallel_workers = Min(parallel_workers,
+								   max_parallel_workers_per_gather);
+		}
+		Assert(parallel_workers > 0);
+
+		ppath = (Path *)
+			create_append_path(result_rel, NIL, partial_pathlist,
+							   NULL, parallel_workers, enable_parallel_append,
+							   NIL /* XXX? Is this right? */ , -1);
+		ppath = (Path *)
+			create_gather_path(root, result_rel, ppath,
+							   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;
 
-- 
2.14.3 (Apple Git-98)

From 0dd95f93a9852882aa792424705acb8f5d22f579 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 15:42:51 -0500
Subject: [PATCH 3/4] Generate a separate upper relation for each stage of
 setop planning.

Commit 3fc6e2d7f5b652b417fa6937c34de2438d60fa9f made setop planning
stages return paths rather than plans, but all such paths were loosely
associated with a single RelOptInfo, and only the final path was added
to the RelOptInfo.  Even at the time, it was foreseen that this should
be changed, because there is otherwise no good way for a single stage
of setop planning to return multiple paths.  With this patch, each
stage of set operation planning now creates a separate RelOptInfo;
these are distinguished by using appropriate relid sets.  Note that
this patch does nothing whatsoever about actually returning multiple
paths for the same set operation; it just makes it possible for a
future patch to do so.

Along the way, adjust things so that create_upper_paths_hook is called
for each of these new RelOptInfos rather than just once, since that
might be useful to extensions using that hook.  It might be a good
to provide an FDW API here as well, but I didn't try to do that for
now.

Patch by me, reviewed by Ashutosh Bapat.
---
 src/backend/optimizer/prep/prepunion.c | 342 ++++++++++++++++++---------------
 1 file changed, 191 insertions(+), 151 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index f387387289..e477a04f94 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -60,30 +60,29 @@ typedef struct
 	AppendRelInfo **appinfos;
 } adjust_appendrel_attrs_context;
 
-static Path *recurse_set_operations(Node *setOp, PlannerInfo *root,
+static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List *colTypes, List *colCollations,
 					   bool junkOK,
 					   int flag, List *refnames_tlist,
 					   List **pTargetList,
 					   double *pNumGroups);
-static Path *generate_recursion_path(SetOperationStmt *setOp,
+static RelOptInfo *generate_recursion_path(SetOperationStmt *setOp,
 						PlannerInfo *root,
 						List *refnames_tlist,
 						List **pTargetList);
-static Path *generate_union_path(SetOperationStmt *op, PlannerInfo *root,
-					List *refnames_tlist,
-					List **pTargetList,
-					double *pNumGroups);
-static Path *generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
-					   List *refnames_tlist,
-					   List **pTargetList,
-					   double *pNumGroups);
+static RelOptInfo *generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
+					 List *refnames_tlist,
+					 List **pTargetList);
+static RelOptInfo *generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
+						List *refnames_tlist,
+						List **pTargetList);
 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);
+static void postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
 					Path *input_path,
 					double dNumGroups, double dNumOutputRows,
@@ -149,7 +148,6 @@ plan_set_operations(PlannerInfo *root)
 	RangeTblEntry *leftmostRTE;
 	Query	   *leftmostQuery;
 	RelOptInfo *setop_rel;
-	Path	   *path;
 	List	   *top_tlist;
 
 	Assert(topop);
@@ -181,57 +179,34 @@ plan_set_operations(PlannerInfo *root)
 	leftmostQuery = leftmostRTE->subquery;
 	Assert(leftmostQuery != NULL);
 
-	/*
-	 * We return our results in the (SETOP, NULL) upperrel.  For the moment,
-	 * this is also the parent rel of all Paths in the setop tree; we may well
-	 * change that in future.
-	 */
-	setop_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
-
-	/*
-	 * We don't currently worry about setting setop_rel's consider_parallel
-	 * flag, nor about allowing FDWs to contribute paths to it.
-	 */
-
 	/*
 	 * If the topmost node is a recursive union, it needs special processing.
 	 */
 	if (root->hasRecursion)
 	{
-		path = generate_recursion_path(topop, root,
-									   leftmostQuery->targetList,
-									   &top_tlist);
+		setop_rel = generate_recursion_path(topop, root,
+											leftmostQuery->targetList,
+											&top_tlist);
 	}
 	else
 	{
 		/*
 		 * Recurse on setOperations tree to generate paths for set ops. The
-		 * final output path should have just the column types shown as the
+		 * final output paths should have just the column types shown as the
 		 * output from the top-level node, plus possibly resjunk working
 		 * columns (we can rely on upper-level nodes to deal with that).
 		 */
-		path = recurse_set_operations((Node *) topop, root,
-									  topop->colTypes, topop->colCollations,
-									  true, -1,
-									  leftmostQuery->targetList,
-									  &top_tlist,
-									  NULL);
+		setop_rel = recurse_set_operations((Node *) topop, root,
+										   topop->colTypes, topop->colCollations,
+										   true, -1,
+										   leftmostQuery->targetList,
+										   &top_tlist,
+										   NULL);
 	}
 
 	/* Must return the built tlist into root->processed_tlist. */
 	root->processed_tlist = top_tlist;
 
-	/* Add only the final path to the SETOP upperrel. */
-	add_path(setop_rel, path);
-
-	/* Let extensions possibly add some more paths */
-	if (create_upper_paths_hook)
-		(*create_upper_paths_hook) (root, UPPERREL_SETOP,
-									NULL, setop_rel);
-
-	/* Select cheapest path */
-	set_cheapest(setop_rel);
-
 	return setop_rel;
 }
 
@@ -245,21 +220,21 @@ plan_set_operations(PlannerInfo *root)
  * flag: if >= 0, add a resjunk output column indicating value of flag
  * refnames_tlist: targetlist to take column names from
  *
- * Returns a path for the subtree, as well as these output parameters:
+ * Returns a RelOptInfo for the subtree, as well as these output parameters:
  * *pTargetList: receives the fully-fledged tlist for the subtree's top plan
  * *pNumGroups: if not NULL, we estimate the number of distinct groups
  *		in the result, and store it there
  *
  * The pTargetList output parameter is mostly redundant with the pathtarget
- * of the returned path, but for the moment we need it because much of 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.
+ * of the returned RelOptInfo, but for the moment we need it because much of
+ * the logic in this file depends on flag columns being marked resjunk.
+ * Pending a redesign of how that works, this is the easy way out.
  *
  * 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.
  */
-static Path *
+static RelOptInfo *
 recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List *colTypes, List *colCollations,
 					   bool junkOK,
@@ -267,6 +242,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List **pTargetList,
 					   double *pNumGroups)
 {
+	RelOptInfo *rel = NULL;		/* keep compiler quiet */
+
 	/* Guard against stack overflow due to overly complex setop nests */
 	check_stack_depth();
 
@@ -275,7 +252,6 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		RangeTblRef *rtr = (RangeTblRef *) setOp;
 		RangeTblEntry *rte = root->simple_rte_array[rtr->rtindex];
 		Query	   *subquery = rte->subquery;
-		RelOptInfo *rel;
 		PlannerInfo *subroot;
 		RelOptInfo *final_rel;
 		Path	   *subpath;
@@ -284,11 +260,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 		Assert(subquery != NULL);
 
-		/*
-		 * We need to build a RelOptInfo for each leaf subquery.  This isn't
-		 * used for much here, but it carries the subroot data structures
-		 * forward to setrefs.c processing.
-		 */
+		/* Build a RelOptInfo for this leaf subquery. */
 		rel = build_simple_rel(root, rtr->rtindex, NULL);
 
 		/* plan_params should not be in use in current query level */
@@ -307,6 +279,18 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		if (root->plan_params)
 			elog(ERROR, "unexpected outer reference in set operation subquery");
 
+		/* Figure out the appropriate target list for this subquery. */
+		tlist = generate_setop_tlist(colTypes, colCollations,
+									 flag,
+									 rtr->rtindex,
+									 true,
+									 subroot->processed_tlist,
+									 refnames_tlist);
+		rel->reltarget = create_pathtarget(root, tlist);
+
+		/* 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
@@ -334,22 +318,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		path = (Path *) create_subqueryscan_path(root, rel, subpath,
 												 NIL, NULL);
 
-		/*
-		 * Figure out the appropriate target list, and update the
-		 * SubqueryScanPath with the PathTarget form of that.
-		 */
-		tlist = generate_setop_tlist(colTypes, colCollations,
-									 flag,
-									 rtr->rtindex,
-									 true,
-									 subroot->processed_tlist,
-									 refnames_tlist);
-
-		path = apply_projection_to_path(root, rel, path,
-										create_pathtarget(root, tlist));
-
-		/* Return the fully-fledged tlist to caller, too */
-		*pTargetList = tlist;
+		add_path(rel, path);
 
 		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
@@ -378,25 +347,22 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 												  subpath->rows,
 												  NULL);
 		}
-
-		return (Path *) path;
 	}
 	else if (IsA(setOp, SetOperationStmt))
 	{
 		SetOperationStmt *op = (SetOperationStmt *) setOp;
-		Path	   *path;
 
 		/* UNIONs are much different from INTERSECT/EXCEPT */
 		if (op->op == SETOP_UNION)
-			path = generate_union_path(op, root,
-									   refnames_tlist,
-									   pTargetList,
-									   pNumGroups);
+			rel = generate_union_path(op, root,
+									  refnames_tlist,
+									  pTargetList);
 		else
-			path = generate_nonunion_path(op, root,
-										  refnames_tlist,
-										  pTargetList,
-										  pNumGroups);
+			rel = generate_nonunion_path(op, root,
+										 refnames_tlist,
+										 pTargetList);
+		if (pNumGroups)
+			*pNumGroups = rel->rows;
 
 		/*
 		 * If necessary, add a Result node to project the caller-requested
@@ -415,39 +381,70 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 			!tlist_same_datatypes(*pTargetList, colTypes, junkOK) ||
 			!tlist_same_collations(*pTargetList, colCollations, junkOK))
 		{
+			PathTarget *target;
+			ListCell   *lc;
+
 			*pTargetList = generate_setop_tlist(colTypes, colCollations,
 												flag,
 												0,
 												false,
 												*pTargetList,
 												refnames_tlist);
-			path = apply_projection_to_path(root,
-											path->parent,
-											path,
-											create_pathtarget(root,
-															  *pTargetList));
+			target = create_pathtarget(root, *pTargetList);
+
+			/* Apply projection to each path */
+			foreach(lc, rel->pathlist)
+			{
+				Path	   *subpath = (Path *) lfirst(lc);
+				Path	   *path;
+
+				Assert(subpath->param_info == NULL);
+				path = apply_projection_to_path(root, subpath->parent,
+												subpath, target);
+				/* If we had to add a Result, path is different from subpath */
+				if (path != subpath)
+					lfirst(lc) = path;
+			}
+
+			/* Apply projection to each partial path */
+			foreach(lc, rel->partial_pathlist)
+			{
+				Path	   *subpath = (Path *) lfirst(lc);
+				Path	   *path;
+
+				Assert(subpath->param_info == NULL);
+
+				/* avoid apply_projection_to_path, in case of multiple refs */
+				path = (Path *) create_projection_path(root, subpath->parent,
+													   subpath, target);
+				lfirst(lc) = path;
+			}
 		}
-		return path;
 	}
 	else
 	{
 		elog(ERROR, "unrecognized node type: %d",
 			 (int) nodeTag(setOp));
 		*pTargetList = NIL;
-		return NULL;			/* keep compiler quiet */
 	}
+
+	postprocess_setop_rel(root, rel);
+
+	return rel;
 }
 
 /*
- * Generate path for a recursive UNION node
+ * Generate paths for a recursive UNION node
  */
-static Path *
+static RelOptInfo *
 generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 						List *refnames_tlist,
 						List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	RelOptInfo *result_rel;
 	Path	   *path;
+	RelOptInfo *lrel,
+			   *rrel;
 	Path	   *lpath;
 	Path	   *rpath;
 	List	   *lpath_tlist;
@@ -466,20 +463,22 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	 * Unlike a regular UNION node, process the left and right inputs
 	 * separately without any intention of combining them into one Append.
 	 */
-	lpath = recurse_set_operations(setOp->larg, root,
-								   setOp->colTypes, setOp->colCollations,
-								   false, -1,
-								   refnames_tlist,
-								   &lpath_tlist,
-								   NULL);
+	lrel = recurse_set_operations(setOp->larg, root,
+								  setOp->colTypes, setOp->colCollations,
+								  false, -1,
+								  refnames_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;
-	rpath = recurse_set_operations(setOp->rarg, root,
-								   setOp->colTypes, setOp->colCollations,
-								   false, -1,
-								   refnames_tlist,
-								   &rpath_tlist,
-								   NULL);
+	rrel = recurse_set_operations(setOp->rarg, root,
+								  setOp->colTypes, setOp->colCollations,
+								  false, -1,
+								  refnames_tlist,
+								  &rpath_tlist,
+								  NULL);
+	rpath = rrel->cheapest_total_path;
 	root->non_recursive_path = NULL;
 
 	/*
@@ -491,6 +490,11 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
+								 bms_union(lrel->relids, rrel->relids));
+	result_rel->reltarget = create_pathtarget(root, tlist);
+
 	/*
 	 * If UNION, identify the grouping operators
 	 */
@@ -525,26 +529,30 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 											   result_rel,
 											   lpath,
 											   rpath,
-											   create_pathtarget(root, tlist),
+											   result_rel->reltarget,
 											   groupList,
 											   root->wt_param_id,
 											   dNumGroups);
 
-	return path;
+	add_path(result_rel, path);
+	postprocess_setop_rel(root, result_rel);
+	return result_rel;
 }
 
 /*
- * Generate path for a UNION or UNION ALL node
+ * Generate paths for a UNION or UNION ALL node
  */
-static Path *
-generate_union_path(SetOperationStmt *op, PlannerInfo *root,
-					List *refnames_tlist,
-					List **pTargetList,
-					double *pNumGroups)
+static RelOptInfo *
+generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
+					 List *refnames_tlist,
+					 List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	Relids		relids = NULL;
+	RelOptInfo *result_rel;
 	double		save_fraction = root->tuple_fraction;
-	List	   *pathlist;
+	ListCell   *lc;
+	List	   *pathlist = NIL;
+	List	   *rellist;
 	List	   *tlist_list;
 	List	   *tlist;
 	Path	   *path;
@@ -569,7 +577,7 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	pathlist = plan_union_children(root, op, refnames_tlist, &tlist_list);
+	rellist = plan_union_children(root, op, refnames_tlist, &tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -583,13 +591,24 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build path list and relid set. */
+	foreach(lc, rellist)
+	{
+		RelOptInfo *rel = lfirst(lc);
+
+		pathlist = lappend(pathlist, rel->cheapest_total_path);
+		relids = bms_union(relids, rel->relids);
+	}
+
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
+	result_rel->reltarget = create_pathtarget(root, tlist);
+
 	/*
 	 * Append the child results together.
 	 */
 	path = (Path *) create_append_path(result_rel, pathlist, NIL,
 									   NULL, 0, false, NIL, -1);
-	/* We have to manually jam the right tlist into the path; ick */
-	path->pathtarget = create_pathtarget(root, tlist);
 
 	/*
 	 * For UNION ALL, we just need the Append path.  For UNION, need to add
@@ -598,30 +617,32 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	if (!op->all)
 		path = make_union_unique(op, path, tlist, root);
 
+	add_path(result_rel, path);
+
 	/*
-	 * Estimate number of groups if caller wants it.  For now we just assume
-	 * the output is unique --- this is certainly true for the UNION case, and
-	 * we want worst-case estimates anyway.
+	 * 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.
 	 */
-	if (pNumGroups)
-		*pNumGroups = path->rows;
+	result_rel->rows = path->rows;
 
 	/* Undo effects of possibly forcing tuple_fraction to 0 */
 	root->tuple_fraction = save_fraction;
 
-	return path;
+	return result_rel;
 }
 
 /*
- * Generate path for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
+ * Generate paths for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
  */
-static Path *
-generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
-					   List *refnames_tlist,
-					   List **pTargetList,
-					   double *pNumGroups)
+static RelOptInfo *
+generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
+						List *refnames_tlist,
+						List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	RelOptInfo *result_rel;
+	RelOptInfo *lrel,
+			   *rrel;
 	double		save_fraction = root->tuple_fraction;
 	Path	   *lpath,
 			   *rpath,
@@ -646,18 +667,20 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 	root->tuple_fraction = 0.0;
 
 	/* Recurse on children, ensuring their outputs are marked */
-	lpath = recurse_set_operations(op->larg, root,
-								   op->colTypes, op->colCollations,
-								   false, 0,
-								   refnames_tlist,
-								   &lpath_tlist,
-								   &dLeftGroups);
-	rpath = recurse_set_operations(op->rarg, root,
-								   op->colTypes, op->colCollations,
-								   false, 1,
-								   refnames_tlist,
-								   &rpath_tlist,
-								   &dRightGroups);
+	lrel = recurse_set_operations(op->larg, root,
+								  op->colTypes, op->colCollations,
+								  false, 0,
+								  refnames_tlist,
+								  &lpath_tlist,
+								  &dLeftGroups);
+	lpath = lrel->cheapest_total_path;
+	rrel = recurse_set_operations(op->rarg, root,
+								  op->colTypes, op->colCollations,
+								  false, 1,
+								  refnames_tlist,
+								  &rpath_tlist,
+								  &dRightGroups);
+	rpath = rrel->cheapest_total_path;
 
 	/* Undo effects of forcing tuple_fraction to 0 */
 	root->tuple_fraction = save_fraction;
@@ -695,15 +718,17 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
+								 bms_union(lrel->relids, rrel->relids));
+	result_rel->reltarget = create_pathtarget(root, tlist);;
+
 	/*
 	 * Append the child results together.
 	 */
 	path = (Path *) create_append_path(result_rel, pathlist, NIL,
 									   NULL, 0, false, NIL, -1);
 
-	/* We have to manually jam the right tlist into the path; ick */
-	path->pathtarget = create_pathtarget(root, tlist);
-
 	/* Identify the grouping semantics */
 	groupList = generate_setop_grouplist(op, tlist);
 
@@ -769,10 +794,9 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 									  dNumGroups,
 									  dNumOutputRows);
 
-	if (pNumGroups)
-		*pNumGroups = dNumGroups;
-
-	return path;
+	result_rel->rows = path->rows;
+	add_path(result_rel, path);
+	return result_rel;
 }
 
 /*
@@ -897,8 +921,6 @@ make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
 															   groupList,
 															   tlist),
 								 -1.0);
-		/* We have to manually jam the right tlist into the path; ick */
-		path->pathtarget = create_pathtarget(root, tlist);
 		path = (Path *) create_upper_unique_path(root,
 												 result_rel,
 												 path,
@@ -909,6 +931,24 @@ make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
 	return path;
 }
 
+/*
+ * postprocess_setop_rel - perform steps required after adding paths
+ */
+static void
+postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel)
+{
+	/*
+	 * We don't currently worry about allowing FDWs to contribute paths to
+	 * this relation, but give extensions a chance.
+	 */
+	if (create_upper_paths_hook)
+		(*create_upper_paths_hook) (root, UPPERREL_SETOP,
+									NULL, rel);
+
+	/* Select cheapest path */
+	set_cheapest(rel);
+}
+
 /*
  * choose_hashed_setop - should we use hashing for a set operation?
  */
-- 
2.14.3 (Apple Git-98)

From 3604a7d0b00f65dc670e42fa0d7fc36633ef15ea Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 12:13:46 -0500
Subject: [PATCH 2/4] Rewrite recurse_union_children to iterate, rather than
 recurse.

Also, rename it to plan_union_chidren, so the old name wasn't
very descriptive.  This results in a small net reduction in code,
seems at least to me to be easier to understand, and saves
space on the process stack.

Patch by me, reviewed by Ashutosh Bapat.
---
 src/backend/optimizer/prep/prepunion.c | 100 ++++++++++++++++-----------------
 1 file changed, 47 insertions(+), 53 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index b586f941a8..f387387289 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -78,10 +78,10 @@ static Path *generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 					   List *refnames_tlist,
 					   List **pTargetList,
 					   double *pNumGroups);
-static List *recurse_union_children(Node *setOp, PlannerInfo *root,
-					   SetOperationStmt *top_union,
-					   List *refnames_tlist,
-					   List **tlist_list);
+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);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
@@ -545,8 +545,6 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
 	double		save_fraction = root->tuple_fraction;
 	List	   *pathlist;
-	List	   *child_tlists1;
-	List	   *child_tlists2;
 	List	   *tlist_list;
 	List	   *tlist;
 	Path	   *path;
@@ -571,13 +569,7 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	pathlist = list_concat(recurse_union_children(op->larg, root,
-												  op, refnames_tlist,
-												  &child_tlists1),
-						   recurse_union_children(op->rarg, root,
-												  op, refnames_tlist,
-												  &child_tlists2));
-	tlist_list = list_concat(child_tlists1, child_tlists2);
+	pathlist = plan_union_children(root, op, refnames_tlist, &tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -797,56 +789,58 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
  * generate_union_path will force a fresh sort if the top level is a UNION.
  */
 static List *
-recurse_union_children(Node *setOp, PlannerInfo *root,
-					   SetOperationStmt *top_union,
-					   List *refnames_tlist,
-					   List **tlist_list)
+plan_union_children(PlannerInfo *root,
+					SetOperationStmt *top_union,
+					List *refnames_tlist,
+					List **tlist_list)
 {
-	List	   *result;
+	List	   *pending_rels = list_make1(top_union);
+	List	   *result = NIL;
 	List	   *child_tlist;
 
-	if (IsA(setOp, SetOperationStmt))
+	*tlist_list = NIL;
+
+	while (pending_rels != NIL)
 	{
-		SetOperationStmt *op = (SetOperationStmt *) setOp;
+		Node	   *setOp = linitial(pending_rels);
+
+		pending_rels = list_delete_first(pending_rels);
 
-		if (op->op == top_union->op &&
-			(op->all == top_union->all || op->all) &&
-			equal(op->colTypes, top_union->colTypes))
+		if (IsA(setOp, SetOperationStmt))
 		{
-			/* Same UNION, so fold children into parent's subpath list */
-			List	   *child_tlists1;
-			List	   *child_tlists2;
+			SetOperationStmt *op = (SetOperationStmt *) setOp;
 
-			result = list_concat(recurse_union_children(op->larg, root,
-														top_union,
-														refnames_tlist,
-														&child_tlists1),
-								 recurse_union_children(op->rarg, root,
-														top_union,
-														refnames_tlist,
-														&child_tlists2));
-			*tlist_list = list_concat(child_tlists1, child_tlists2);
-			return result;
+			if (op->op == top_union->op &&
+				(op->all == top_union->all || op->all) &&
+				equal(op->colTypes, top_union->colTypes))
+			{
+				/* Same UNION, so fold children into parent */
+				pending_rels = lcons(op->rarg, pending_rels);
+				pending_rels = lcons(op->larg, pending_rels);
+				continue;
+			}
 		}
+
+		/*
+		 * Not same, so plan this child separately.
+		 *
+		 * Note we disallow any resjunk columns in child results.  This is
+		 * necessary since the Append node that implements the union won't do
+		 * any projection, and upper levels will get confused if some of our
+		 * output tuples have junk and some don't.  This case only arises when
+		 * we have an EXCEPT or INTERSECT as child, else there won't be
+		 * resjunk anyway.
+		 */
+		result = lappend(result, recurse_set_operations(setOp, root,
+														top_union->colTypes,
+														top_union->colCollations,
+														false, -1,
+														refnames_tlist,
+														&child_tlist,
+														NULL));
+		*tlist_list = lappend(*tlist_list, child_tlist);
 	}
 
-	/*
-	 * Not same, so plan this child separately.
-	 *
-	 * Note we disallow any resjunk columns in child results.  This is
-	 * necessary since the Append node that implements the union won't do any
-	 * projection, and upper levels will get confused if some of our output
-	 * tuples have junk and some don't.  This case only arises when we have an
-	 * EXCEPT or INTERSECT as child, else there won't be resjunk anyway.
-	 */
-	result = list_make1(recurse_set_operations(setOp, root,
-											   top_union->colTypes,
-											   top_union->colCollations,
-											   false, -1,
-											   refnames_tlist,
-											   &child_tlist,
-											   NULL));
-	*tlist_list = list_make1(child_tlist);
 	return result;
 }
 
-- 
2.14.3 (Apple Git-98)

From 2c8672d1ac8028894afbf1777072c35305b249e2 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 11:53:07 -0500
Subject: [PATCH 1/4] Let Parallel Append over simple UNION ALL have partial
 subpaths.

A simple UNION ALL gets flattened into an appendrel of subquery
RTEs, but up until now it's been impossible for the appendrel to use
the partial paths for the subqueries, so we can implement the
appendrel as a Parallel Append but only one with non-partial paths
as children.

There are three separate obstacles to removing that limitation.
First, when planning a subquery, propagate any partial paths to the
final_rel so that they are potentially visible to outer query levels
(but not if they have initPlans attached, because that wouldn't be
safe).  Second, after planning a subquery, propagate any partial paths
for the final_rel to the subquery RTE in the outer query level in the
same way we do for non-partial paths.  Third, teach finalize_plan() to
account for the possibility that the fake parameter we use for rescan
signalling when the plan contains a Gather (Merge) node may be
propagated from an outer query level.

Patch by me, reviewed and tested by Amit Khandekar and Rajkumar
Raghuwanshi.  Test cases based on examples by Rajkumar Raghuwanshi.

Discussion: http://postgr.es/m/CA+Tgmoa6L9A1nNCk3aTDVZLZ4KkHDn1+tm7mFyFvP+uQPS7bAg@mail.gmail.com
---
 src/backend/optimizer/path/allpaths.c         | 22 +++++++++
 src/backend/optimizer/plan/planner.c          | 16 +++++++
 src/backend/optimizer/plan/subselect.c        | 17 ++++++-
 src/test/regress/expected/select_parallel.out | 65 +++++++++++++++++++++++++++
 src/test/regress/sql/select_parallel.sql      | 25 +++++++++++
 5 files changed, 143 insertions(+), 2 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 1c792a00eb..ea4e683abb 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2179,6 +2179,28 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 				 create_subqueryscan_path(root, rel, subpath,
 										  pathkeys, required_outer));
 	}
+
+	/* If consider_parallel is false, there should be no partial paths. */
+	Assert(sub_final_rel->consider_parallel ||
+		   sub_final_rel->partial_pathlist == NIL);
+
+	/* Same for partial paths. */
+	foreach(lc, sub_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,
+												  pathkeys, required_outer));
+	}
 }
 
 /*
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 14b7becf3e..91b32d4947 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -2194,6 +2194,22 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 		add_path(final_rel, path);
 	}
 
+	/*
+	 * Generate partial paths for final_rel, too, if outer query levels might
+	 * be able to make use of them.
+	 */
+	if (final_rel->consider_parallel && root->query_level > 1 &&
+		!limit_needed(parse))
+	{
+		Assert(!parse->rowMarks && parse->commandType == CMD_SELECT);
+		foreach(lc, current_rel->partial_pathlist)
+		{
+			Path	   *partial_path = (Path *) lfirst(lc);
+
+			add_partial_path(final_rel, partial_path);
+		}
+	}
+
 	/*
 	 * If there is an FDW that's responsible for all baserels of the query,
 	 * let it consider adding ForeignPaths.
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 46367cba63..32bf1fd955 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -2202,6 +2202,13 @@ SS_charge_for_initplans(PlannerInfo *root, RelOptInfo *final_rel)
 		path->parallel_safe = false;
 	}
 
+	/*
+	 * Forget about any partial paths and clear consider_parallel, too;
+	 * they're not usable if we attached an initPlan.
+	 */
+	final_rel->partial_pathlist = NIL;
+	final_rel->consider_parallel = false;
+
 	/* We needn't do set_cheapest() here, caller will do it */
 }
 
@@ -2407,10 +2414,16 @@ finalize_plan(PlannerInfo *root, Plan *plan,
 			{
 				SubqueryScan *sscan = (SubqueryScan *) plan;
 				RelOptInfo *rel;
+				Bitmapset  *subquery_params;
 
-				/* We must run SS_finalize_plan on the subquery */
+				/* We must run finalize_plan on the subquery */
 				rel = find_base_rel(root, sscan->scan.scanrelid);
-				SS_finalize_plan(rel->subroot, sscan->subplan);
+				subquery_params = rel->subroot->outer_params;
+				if (gather_param >= 0)
+					subquery_params = bms_add_member(bms_copy(subquery_params),
+													 gather_param);
+				finalize_plan(rel->subroot, sscan->subplan, gather_param,
+							  subquery_params, NULL);
 
 				/* Now we can add its extParams to the parent's params */
 				context.paramids = bms_add_members(context.paramids,
diff --git a/src/test/regress/expected/select_parallel.out b/src/test/regress/expected/select_parallel.out
index 0a78261638..2fb16d1a15 100644
--- a/src/test/regress/expected/select_parallel.out
+++ b/src/test/regress/expected/select_parallel.out
@@ -890,4 +890,69 @@ select stringu1::int2 from tenk1 where unique1 = 1;
 ERROR:  invalid input syntax for integer: "BAAAAA"
 CONTEXT:  parallel worker
 ROLLBACK TO SAVEPOINT settings;
+-- test interaction with set-returning functions
+SAVEPOINT settings;
+-- multiple subqueries under a single Gather node
+-- must set parallel_setup_cost > 0 to discourage multiple Gather nodes
+SET LOCAL parallel_setup_cost = 10;
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Gather
+   Workers Planned: 4
+   ->  Parallel Append
+         ->  Parallel Seq Scan on tenk1
+               Filter: (fivethous = (tenthous + 1))
+         ->  Parallel Seq Scan on tenk1 tenk1_1
+               Filter: (fivethous = (tenthous + 1))
+(7 rows)
+
+ROLLBACK TO SAVEPOINT settings;
+-- can't use multiple subqueries under a single Gather node due to initPlans
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique1 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique2 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+ORDER BY 1;
+                             QUERY PLAN                             
+--------------------------------------------------------------------
+ Sort
+   Sort Key: tenk1.unique1
+   ->  Append
+         ->  Gather
+               Workers Planned: 4
+               Params Evaluated: $1
+               InitPlan 1 (returns $1)
+                 ->  Limit
+                       ->  Gather
+                             Workers Planned: 4
+                             ->  Parallel Seq Scan on tenk1 tenk1_2
+                                   Filter: (fivethous = 1)
+               ->  Parallel Seq Scan on tenk1
+                     Filter: (fivethous = $1)
+         ->  Gather
+               Workers Planned: 4
+               Params Evaluated: $3
+               InitPlan 2 (returns $3)
+                 ->  Limit
+                       ->  Gather
+                             Workers Planned: 4
+                             ->  Parallel Seq Scan on tenk1 tenk1_3
+                                   Filter: (fivethous = 1)
+               ->  Parallel Seq Scan on tenk1 tenk1_1
+                     Filter: (fivethous = $3)
+(25 rows)
+
+-- test interaction with SRFs
+SELECT * FROM information_schema.foreign_data_wrapper_options
+ORDER BY 1, 2, 3;
+ foreign_data_wrapper_catalog | foreign_data_wrapper_name | option_name | option_value 
+------------------------------+---------------------------+-------------+--------------
+(0 rows)
+
 rollback;
diff --git a/src/test/regress/sql/select_parallel.sql b/src/test/regress/sql/select_parallel.sql
index fa03aae0c0..ec817f2a4c 100644
--- a/src/test/regress/sql/select_parallel.sql
+++ b/src/test/regress/sql/select_parallel.sql
@@ -358,4 +358,29 @@ SET LOCAL force_parallel_mode = 1;
 select stringu1::int2 from tenk1 where unique1 = 1;
 ROLLBACK TO SAVEPOINT settings;
 
+-- test interaction with set-returning functions
+SAVEPOINT settings;
+
+-- multiple subqueries under a single Gather node
+-- must set parallel_setup_cost > 0 to discourage multiple Gather nodes
+SET LOCAL parallel_setup_cost = 10;
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1;
+ROLLBACK TO SAVEPOINT settings;
+
+-- can't use multiple subqueries under a single Gather node due to initPlans
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique1 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique2 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+ORDER BY 1;
+
+-- test interaction with SRFs
+SELECT * FROM information_schema.foreign_data_wrapper_options
+ORDER BY 1, 2, 3;
+
 rollback;
-- 
2.14.3 (Apple Git-98)

From 7e654c0ae30d867edea5a1a2ca8f7a17b05ed7c5 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 11:53:07 -0500
Subject: [PATCH 1/4] Let Parallel Append over simple UNION ALL have partial
 subpaths.

A simple UNION ALL gets flattened into an appendrel of subquery
RTEs, but up until now it's been impossible for the appendrel to use
the partial paths for the subqueries, so we can implement the
appendrel as a Parallel Append but only one with non-partial paths
as children.

There are three separate obstacles to removing that limitation.
First, when planning a subquery, propagate any partial paths to the
final_rel so that they are potentially visible to outer query levels
(but not if they have initPlans attached, because that wouldn't be
safe).  Second, after planning a subquery, propagate any partial paths
for the final_rel to the subquery RTE in the outer query level in the
same way we do for non-partial paths.  Third, teach finalize_plan() to
account for the possibility that the fake parameter we use for rescan
signalling when the plan contains a Gather (Merge) node may be
propagated from an outer query level.

Patch by me, reviewed and tested by Amit Khandekar and Rajkumar
Raghuwanshi.  Test cases based on examples by Rajkumar Raghuwanshi.

Discussion: http://postgr.es/m/CA+Tgmoa6L9A1nNCk3aTDVZLZ4KkHDn1+tm7mFyFvP+uQPS7bAg@mail.gmail.com
---
 src/backend/optimizer/path/allpaths.c         |   22 +++++++++
 src/backend/optimizer/plan/planner.c          |   16 ++++++
 src/backend/optimizer/plan/subselect.c        |   17 ++++++-
 src/test/regress/expected/select_parallel.out |   65 +++++++++++++++++++++++++
 src/test/regress/sql/select_parallel.sql      |   25 ++++++++++
 5 files changed, 143 insertions(+), 2 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 1c792a0..ea4e683 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2179,6 +2179,28 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 				 create_subqueryscan_path(root, rel, subpath,
 										  pathkeys, required_outer));
 	}
+
+	/* If consider_parallel is false, there should be no partial paths. */
+	Assert(sub_final_rel->consider_parallel ||
+		   sub_final_rel->partial_pathlist == NIL);
+
+	/* Same for partial paths. */
+	foreach(lc, sub_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,
+												  pathkeys, required_outer));
+	}
 }
 
 /*
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 24e6c46..66e7e7b 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -2195,6 +2195,22 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
 	}
 
 	/*
+	 * Generate partial paths for final_rel, too, if outer query levels might
+	 * be able to make use of them.
+	 */
+	if (final_rel->consider_parallel && root->query_level > 1 &&
+		!limit_needed(parse))
+	{
+		Assert(!parse->rowMarks && parse->commandType == CMD_SELECT);
+		foreach(lc, current_rel->partial_pathlist)
+		{
+			Path	   *partial_path = (Path *) lfirst(lc);
+
+			add_partial_path(final_rel, partial_path);
+		}
+	}
+
+	/*
 	 * If there is an FDW that's responsible for all baserels of the query,
 	 * let it consider adding ForeignPaths.
 	 */
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index dc86dd5..83008d7 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -2202,6 +2202,13 @@ SS_charge_for_initplans(PlannerInfo *root, RelOptInfo *final_rel)
 		path->parallel_safe = false;
 	}
 
+	/*
+	 * Forget about any partial paths and clear consider_parallel, too;
+	 * they're not usable if we attached an initPlan.
+	 */
+	final_rel->partial_pathlist = NIL;
+	final_rel->consider_parallel = false;
+
 	/* We needn't do set_cheapest() here, caller will do it */
 }
 
@@ -2407,10 +2414,16 @@ finalize_plan(PlannerInfo *root, Plan *plan,
 			{
 				SubqueryScan *sscan = (SubqueryScan *) plan;
 				RelOptInfo *rel;
+				Bitmapset  *subquery_params;
 
-				/* We must run SS_finalize_plan on the subquery */
+				/* We must run finalize_plan on the subquery */
 				rel = find_base_rel(root, sscan->scan.scanrelid);
-				SS_finalize_plan(rel->subroot, sscan->subplan);
+				subquery_params = rel->subroot->outer_params;
+				if (gather_param >= 0)
+					subquery_params = bms_add_member(bms_copy(subquery_params),
+													 gather_param);
+				finalize_plan(rel->subroot, sscan->subplan, gather_param,
+							  subquery_params, NULL);
 
 				/* Now we can add its extParams to the parent's params */
 				context.paramids = bms_add_members(context.paramids,
diff --git a/src/test/regress/expected/select_parallel.out b/src/test/regress/expected/select_parallel.out
index 0a78261..2fb16d1 100644
--- a/src/test/regress/expected/select_parallel.out
+++ b/src/test/regress/expected/select_parallel.out
@@ -890,4 +890,69 @@ select stringu1::int2 from tenk1 where unique1 = 1;
 ERROR:  invalid input syntax for integer: "BAAAAA"
 CONTEXT:  parallel worker
 ROLLBACK TO SAVEPOINT settings;
+-- test interaction with set-returning functions
+SAVEPOINT settings;
+-- multiple subqueries under a single Gather node
+-- must set parallel_setup_cost > 0 to discourage multiple Gather nodes
+SET LOCAL parallel_setup_cost = 10;
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Gather
+   Workers Planned: 4
+   ->  Parallel Append
+         ->  Parallel Seq Scan on tenk1
+               Filter: (fivethous = (tenthous + 1))
+         ->  Parallel Seq Scan on tenk1 tenk1_1
+               Filter: (fivethous = (tenthous + 1))
+(7 rows)
+
+ROLLBACK TO SAVEPOINT settings;
+-- can't use multiple subqueries under a single Gather node due to initPlans
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique1 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique2 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+ORDER BY 1;
+                             QUERY PLAN                             
+--------------------------------------------------------------------
+ Sort
+   Sort Key: tenk1.unique1
+   ->  Append
+         ->  Gather
+               Workers Planned: 4
+               Params Evaluated: $1
+               InitPlan 1 (returns $1)
+                 ->  Limit
+                       ->  Gather
+                             Workers Planned: 4
+                             ->  Parallel Seq Scan on tenk1 tenk1_2
+                                   Filter: (fivethous = 1)
+               ->  Parallel Seq Scan on tenk1
+                     Filter: (fivethous = $1)
+         ->  Gather
+               Workers Planned: 4
+               Params Evaluated: $3
+               InitPlan 2 (returns $3)
+                 ->  Limit
+                       ->  Gather
+                             Workers Planned: 4
+                             ->  Parallel Seq Scan on tenk1 tenk1_3
+                                   Filter: (fivethous = 1)
+               ->  Parallel Seq Scan on tenk1 tenk1_1
+                     Filter: (fivethous = $3)
+(25 rows)
+
+-- test interaction with SRFs
+SELECT * FROM information_schema.foreign_data_wrapper_options
+ORDER BY 1, 2, 3;
+ foreign_data_wrapper_catalog | foreign_data_wrapper_name | option_name | option_value 
+------------------------------+---------------------------+-------------+--------------
+(0 rows)
+
 rollback;
diff --git a/src/test/regress/sql/select_parallel.sql b/src/test/regress/sql/select_parallel.sql
index fa03aae..ec817f2 100644
--- a/src/test/regress/sql/select_parallel.sql
+++ b/src/test/regress/sql/select_parallel.sql
@@ -358,4 +358,29 @@ SET LOCAL force_parallel_mode = 1;
 select stringu1::int2 from tenk1 where unique1 = 1;
 ROLLBACK TO SAVEPOINT settings;
 
+-- test interaction with set-returning functions
+SAVEPOINT settings;
+
+-- multiple subqueries under a single Gather node
+-- must set parallel_setup_cost > 0 to discourage multiple Gather nodes
+SET LOCAL parallel_setup_cost = 10;
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous = tenthous + 1;
+ROLLBACK TO SAVEPOINT settings;
+
+-- can't use multiple subqueries under a single Gather node due to initPlans
+EXPLAIN (COSTS OFF)
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique1 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+UNION ALL
+SELECT unique1 FROM tenk1 WHERE fivethous =
+	(SELECT unique2 FROM tenk1 WHERE fivethous = 1 LIMIT 1)
+ORDER BY 1;
+
+-- test interaction with SRFs
+SELECT * FROM information_schema.foreign_data_wrapper_options
+ORDER BY 1, 2, 3;
+
 rollback;
-- 
1.7.9.5

From bac26e67c8732f805a1f5682773a8c5ef44f8a8c Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 12:13:46 -0500
Subject: [PATCH 2/4] Rewrite recurse_union_children to iterate, rather than
 recurse.

Also, rename it to plan_union_chidren, so the old name wasn't
very descriptive.  This results in a small net reduction in code,
seems at least to me to be easier to understand, and saves
space on the process stack.

Patch by me, reviewed by Ashutosh Bapat.
---
 src/backend/optimizer/prep/prepunion.c |  100 +++++++++++++++-----------------
 1 file changed, 47 insertions(+), 53 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index b586f94..f387387 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -78,10 +78,10 @@ static Path *generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 					   List *refnames_tlist,
 					   List **pTargetList,
 					   double *pNumGroups);
-static List *recurse_union_children(Node *setOp, PlannerInfo *root,
-					   SetOperationStmt *top_union,
-					   List *refnames_tlist,
-					   List **tlist_list);
+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);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
@@ -545,8 +545,6 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
 	double		save_fraction = root->tuple_fraction;
 	List	   *pathlist;
-	List	   *child_tlists1;
-	List	   *child_tlists2;
 	List	   *tlist_list;
 	List	   *tlist;
 	Path	   *path;
@@ -571,13 +569,7 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	pathlist = list_concat(recurse_union_children(op->larg, root,
-												  op, refnames_tlist,
-												  &child_tlists1),
-						   recurse_union_children(op->rarg, root,
-												  op, refnames_tlist,
-												  &child_tlists2));
-	tlist_list = list_concat(child_tlists1, child_tlists2);
+	pathlist = plan_union_children(root, op, refnames_tlist, &tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -797,56 +789,58 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
  * generate_union_path will force a fresh sort if the top level is a UNION.
  */
 static List *
-recurse_union_children(Node *setOp, PlannerInfo *root,
-					   SetOperationStmt *top_union,
-					   List *refnames_tlist,
-					   List **tlist_list)
+plan_union_children(PlannerInfo *root,
+					SetOperationStmt *top_union,
+					List *refnames_tlist,
+					List **tlist_list)
 {
-	List	   *result;
+	List	   *pending_rels = list_make1(top_union);
+	List	   *result = NIL;
 	List	   *child_tlist;
 
-	if (IsA(setOp, SetOperationStmt))
+	*tlist_list = NIL;
+
+	while (pending_rels != NIL)
 	{
-		SetOperationStmt *op = (SetOperationStmt *) setOp;
+		Node	   *setOp = linitial(pending_rels);
+
+		pending_rels = list_delete_first(pending_rels);
 
-		if (op->op == top_union->op &&
-			(op->all == top_union->all || op->all) &&
-			equal(op->colTypes, top_union->colTypes))
+		if (IsA(setOp, SetOperationStmt))
 		{
-			/* Same UNION, so fold children into parent's subpath list */
-			List	   *child_tlists1;
-			List	   *child_tlists2;
+			SetOperationStmt *op = (SetOperationStmt *) setOp;
 
-			result = list_concat(recurse_union_children(op->larg, root,
-														top_union,
-														refnames_tlist,
-														&child_tlists1),
-								 recurse_union_children(op->rarg, root,
-														top_union,
-														refnames_tlist,
-														&child_tlists2));
-			*tlist_list = list_concat(child_tlists1, child_tlists2);
-			return result;
+			if (op->op == top_union->op &&
+				(op->all == top_union->all || op->all) &&
+				equal(op->colTypes, top_union->colTypes))
+			{
+				/* Same UNION, so fold children into parent */
+				pending_rels = lcons(op->rarg, pending_rels);
+				pending_rels = lcons(op->larg, pending_rels);
+				continue;
+			}
 		}
+
+		/*
+		 * Not same, so plan this child separately.
+		 *
+		 * Note we disallow any resjunk columns in child results.  This is
+		 * necessary since the Append node that implements the union won't do
+		 * any projection, and upper levels will get confused if some of our
+		 * output tuples have junk and some don't.  This case only arises when
+		 * we have an EXCEPT or INTERSECT as child, else there won't be
+		 * resjunk anyway.
+		 */
+		result = lappend(result, recurse_set_operations(setOp, root,
+														top_union->colTypes,
+														top_union->colCollations,
+														false, -1,
+														refnames_tlist,
+														&child_tlist,
+														NULL));
+		*tlist_list = lappend(*tlist_list, child_tlist);
 	}
 
-	/*
-	 * Not same, so plan this child separately.
-	 *
-	 * Note we disallow any resjunk columns in child results.  This is
-	 * necessary since the Append node that implements the union won't do any
-	 * projection, and upper levels will get confused if some of our output
-	 * tuples have junk and some don't.  This case only arises when we have an
-	 * EXCEPT or INTERSECT as child, else there won't be resjunk anyway.
-	 */
-	result = list_make1(recurse_set_operations(setOp, root,
-											   top_union->colTypes,
-											   top_union->colCollations,
-											   false, -1,
-											   refnames_tlist,
-											   &child_tlist,
-											   NULL));
-	*tlist_list = list_make1(child_tlist);
 	return result;
 }
 
-- 
1.7.9.5

From f3e3f4b2a8b58c559c2759a99c71187ff3190353 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Fri, 23 Feb 2018 15:42:51 -0500
Subject: [PATCH 3/4] Generate a separate upper relation for each stage of
 setop planning.

Commit 3fc6e2d7f5b652b417fa6937c34de2438d60fa9f made setop planning
stages return paths rather than plans, but all such paths were loosely
associated with a single RelOptInfo, and only the final path was added
to the RelOptInfo.  Even at the time, it was foreseen that this should
be changed, because there is otherwise no good way for a single stage
of setop planning to return multiple paths.  With this patch, each
stage of set operation planning now creates a separate RelOptInfo;
these are distinguished by using appropriate relid sets.  Note that
this patch does nothing whatsoever about actually returning multiple
paths for the same set operation; it just makes it possible for a
future patch to do so.

Along the way, adjust things so that create_upper_paths_hook is called
for each of these new RelOptInfos rather than just once, since that
might be useful to extensions using that hook.  It might be a good
to provide an FDW API here as well, but I didn't try to do that for
now.

Patch by me, reviewed by Ashutosh Bapat.
---
 src/backend/optimizer/prep/prepunion.c |  340 ++++++++++++++++++--------------
 1 file changed, 190 insertions(+), 150 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index f387387..f087369 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -60,30 +60,29 @@ typedef struct
 	AppendRelInfo **appinfos;
 } adjust_appendrel_attrs_context;
 
-static Path *recurse_set_operations(Node *setOp, PlannerInfo *root,
+static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List *colTypes, List *colCollations,
 					   bool junkOK,
 					   int flag, List *refnames_tlist,
 					   List **pTargetList,
 					   double *pNumGroups);
-static Path *generate_recursion_path(SetOperationStmt *setOp,
+static RelOptInfo *generate_recursion_path(SetOperationStmt *setOp,
 						PlannerInfo *root,
 						List *refnames_tlist,
 						List **pTargetList);
-static Path *generate_union_path(SetOperationStmt *op, PlannerInfo *root,
-					List *refnames_tlist,
-					List **pTargetList,
-					double *pNumGroups);
-static Path *generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
-					   List *refnames_tlist,
-					   List **pTargetList,
-					   double *pNumGroups);
+static RelOptInfo *generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
+					 List *refnames_tlist,
+					 List **pTargetList);
+static RelOptInfo *generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
+						List *refnames_tlist,
+						List **pTargetList);
 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);
+static void postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel);
 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
 					Path *input_path,
 					double dNumGroups, double dNumOutputRows,
@@ -149,7 +148,6 @@ plan_set_operations(PlannerInfo *root)
 	RangeTblEntry *leftmostRTE;
 	Query	   *leftmostQuery;
 	RelOptInfo *setop_rel;
-	Path	   *path;
 	List	   *top_tlist;
 
 	Assert(topop);
@@ -182,56 +180,33 @@ plan_set_operations(PlannerInfo *root)
 	Assert(leftmostQuery != NULL);
 
 	/*
-	 * We return our results in the (SETOP, NULL) upperrel.  For the moment,
-	 * this is also the parent rel of all Paths in the setop tree; we may well
-	 * change that in future.
-	 */
-	setop_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
-
-	/*
-	 * We don't currently worry about setting setop_rel's consider_parallel
-	 * flag, nor about allowing FDWs to contribute paths to it.
-	 */
-
-	/*
 	 * If the topmost node is a recursive union, it needs special processing.
 	 */
 	if (root->hasRecursion)
 	{
-		path = generate_recursion_path(topop, root,
-									   leftmostQuery->targetList,
-									   &top_tlist);
+		setop_rel = generate_recursion_path(topop, root,
+											leftmostQuery->targetList,
+											&top_tlist);
 	}
 	else
 	{
 		/*
 		 * Recurse on setOperations tree to generate paths for set ops. The
-		 * final output path should have just the column types shown as the
+		 * final output paths should have just the column types shown as the
 		 * output from the top-level node, plus possibly resjunk working
 		 * columns (we can rely on upper-level nodes to deal with that).
 		 */
-		path = recurse_set_operations((Node *) topop, root,
-									  topop->colTypes, topop->colCollations,
-									  true, -1,
-									  leftmostQuery->targetList,
-									  &top_tlist,
-									  NULL);
+		setop_rel = recurse_set_operations((Node *) topop, root,
+										   topop->colTypes, topop->colCollations,
+										   true, -1,
+										   leftmostQuery->targetList,
+										   &top_tlist,
+										   NULL);
 	}
 
 	/* Must return the built tlist into root->processed_tlist. */
 	root->processed_tlist = top_tlist;
 
-	/* Add only the final path to the SETOP upperrel. */
-	add_path(setop_rel, path);
-
-	/* Let extensions possibly add some more paths */
-	if (create_upper_paths_hook)
-		(*create_upper_paths_hook) (root, UPPERREL_SETOP,
-									NULL, setop_rel);
-
-	/* Select cheapest path */
-	set_cheapest(setop_rel);
-
 	return setop_rel;
 }
 
@@ -245,21 +220,21 @@ plan_set_operations(PlannerInfo *root)
  * flag: if >= 0, add a resjunk output column indicating value of flag
  * refnames_tlist: targetlist to take column names from
  *
- * Returns a path for the subtree, as well as these output parameters:
+ * Returns a RelOptInfo for the subtree, as well as these output parameters:
  * *pTargetList: receives the fully-fledged tlist for the subtree's top plan
  * *pNumGroups: if not NULL, we estimate the number of distinct groups
  *		in the result, and store it there
  *
  * The pTargetList output parameter is mostly redundant with the pathtarget
- * of the returned path, but for the moment we need it because much of 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.
+ * of the returned RelOptInfo, but for the moment we need it because much of
+ * the logic in this file depends on flag columns being marked resjunk.
+ * Pending a redesign of how that works, this is the easy way out.
  *
  * 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.
  */
-static Path *
+static RelOptInfo *
 recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List *colTypes, List *colCollations,
 					   bool junkOK,
@@ -267,6 +242,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List **pTargetList,
 					   double *pNumGroups)
 {
+	RelOptInfo *rel = NULL;		/* keep compiler quiet */
+
 	/* Guard against stack overflow due to overly complex setop nests */
 	check_stack_depth();
 
@@ -275,7 +252,6 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		RangeTblRef *rtr = (RangeTblRef *) setOp;
 		RangeTblEntry *rte = root->simple_rte_array[rtr->rtindex];
 		Query	   *subquery = rte->subquery;
-		RelOptInfo *rel;
 		PlannerInfo *subroot;
 		RelOptInfo *final_rel;
 		Path	   *subpath;
@@ -284,11 +260,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 
 		Assert(subquery != NULL);
 
-		/*
-		 * We need to build a RelOptInfo for each leaf subquery.  This isn't
-		 * used for much here, but it carries the subroot data structures
-		 * forward to setrefs.c processing.
-		 */
+		/* Build a RelOptInfo for this leaf subquery. */
 		rel = build_simple_rel(root, rtr->rtindex, NULL);
 
 		/* plan_params should not be in use in current query level */
@@ -307,6 +279,18 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		if (root->plan_params)
 			elog(ERROR, "unexpected outer reference in set operation subquery");
 
+		/* Figure out the appropriate target list for this subquery. */
+		tlist = generate_setop_tlist(colTypes, colCollations,
+									 flag,
+									 rtr->rtindex,
+									 true,
+									 subroot->processed_tlist,
+									 refnames_tlist);
+		rel->reltarget = create_pathtarget(root, tlist);
+
+		/* 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
@@ -334,22 +318,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		path = (Path *) create_subqueryscan_path(root, rel, subpath,
 												 NIL, NULL);
 
-		/*
-		 * Figure out the appropriate target list, and update the
-		 * SubqueryScanPath with the PathTarget form of that.
-		 */
-		tlist = generate_setop_tlist(colTypes, colCollations,
-									 flag,
-									 rtr->rtindex,
-									 true,
-									 subroot->processed_tlist,
-									 refnames_tlist);
-
-		path = apply_projection_to_path(root, rel, path,
-										create_pathtarget(root, tlist));
-
-		/* Return the fully-fledged tlist to caller, too */
-		*pTargetList = tlist;
+		add_path(rel, path);
 
 		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
@@ -378,25 +347,22 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 												  subpath->rows,
 												  NULL);
 		}
-
-		return (Path *) path;
 	}
 	else if (IsA(setOp, SetOperationStmt))
 	{
 		SetOperationStmt *op = (SetOperationStmt *) setOp;
-		Path	   *path;
 
 		/* UNIONs are much different from INTERSECT/EXCEPT */
 		if (op->op == SETOP_UNION)
-			path = generate_union_path(op, root,
+			rel = generate_union_paths(op, root,
 									   refnames_tlist,
-									   pTargetList,
-									   pNumGroups);
+									   pTargetList);
 		else
-			path = generate_nonunion_path(op, root,
+			rel = generate_nonunion_paths(op, root,
 										  refnames_tlist,
-										  pTargetList,
-										  pNumGroups);
+										  pTargetList);
+		if (pNumGroups)
+			*pNumGroups = rel->rows;
 
 		/*
 		 * If necessary, add a Result node to project the caller-requested
@@ -415,39 +381,70 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 			!tlist_same_datatypes(*pTargetList, colTypes, junkOK) ||
 			!tlist_same_collations(*pTargetList, colCollations, junkOK))
 		{
+			PathTarget *target;
+			ListCell   *lc;
+
 			*pTargetList = generate_setop_tlist(colTypes, colCollations,
 												flag,
 												0,
 												false,
 												*pTargetList,
 												refnames_tlist);
-			path = apply_projection_to_path(root,
-											path->parent,
-											path,
-											create_pathtarget(root,
-															  *pTargetList));
+			target = create_pathtarget(root, *pTargetList);
+
+			/* Apply projection to each path */
+			foreach(lc, rel->pathlist)
+			{
+				Path	   *subpath = (Path *) lfirst(lc);
+				Path	   *path;
+
+				Assert(subpath->param_info == NULL);
+				path = apply_projection_to_path(root, subpath->parent,
+												subpath, target);
+				/* If we had to add a Result, path is different from subpath */
+				if (path != subpath)
+					lfirst(lc) = path;
+			}
+
+			/* Apply projection to each partial path */
+			foreach(lc, rel->partial_pathlist)
+			{
+				Path	   *subpath = (Path *) lfirst(lc);
+				Path	   *path;
+
+				Assert(subpath->param_info == NULL);
+
+				/* avoid apply_projection_to_path, in case of multiple refs */
+				path = (Path *) create_projection_path(root, subpath->parent,
+													   subpath, target);
+				lfirst(lc) = path;
+			}
 		}
-		return path;
 	}
 	else
 	{
 		elog(ERROR, "unrecognized node type: %d",
 			 (int) nodeTag(setOp));
 		*pTargetList = NIL;
-		return NULL;			/* keep compiler quiet */
 	}
+
+	postprocess_setop_rel(root, rel);
+
+	return rel;
 }
 
 /*
- * Generate path for a recursive UNION node
+ * Generate paths for a recursive UNION node
  */
-static Path *
+static RelOptInfo *
 generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 						List *refnames_tlist,
 						List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	RelOptInfo *result_rel;
 	Path	   *path;
+	RelOptInfo *lrel,
+			   *rrel;
 	Path	   *lpath;
 	Path	   *rpath;
 	List	   *lpath_tlist;
@@ -466,20 +463,22 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 	 * Unlike a regular UNION node, process the left and right inputs
 	 * separately without any intention of combining them into one Append.
 	 */
-	lpath = recurse_set_operations(setOp->larg, root,
-								   setOp->colTypes, setOp->colCollations,
-								   false, -1,
-								   refnames_tlist,
-								   &lpath_tlist,
-								   NULL);
+	lrel = recurse_set_operations(setOp->larg, root,
+								  setOp->colTypes, setOp->colCollations,
+								  false, -1,
+								  refnames_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;
-	rpath = recurse_set_operations(setOp->rarg, root,
-								   setOp->colTypes, setOp->colCollations,
-								   false, -1,
-								   refnames_tlist,
-								   &rpath_tlist,
-								   NULL);
+	rrel = recurse_set_operations(setOp->rarg, root,
+								  setOp->colTypes, setOp->colCollations,
+								  false, -1,
+								  refnames_tlist,
+								  &rpath_tlist,
+								  NULL);
+	rpath = rrel->cheapest_total_path;
 	root->non_recursive_path = NULL;
 
 	/*
@@ -491,6 +490,11 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
+								 bms_union(lrel->relids, rrel->relids));
+	result_rel->reltarget = create_pathtarget(root, tlist);
+
 	/*
 	 * If UNION, identify the grouping operators
 	 */
@@ -525,26 +529,30 @@ generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
 											   result_rel,
 											   lpath,
 											   rpath,
-											   create_pathtarget(root, tlist),
+											   result_rel->reltarget,
 											   groupList,
 											   root->wt_param_id,
 											   dNumGroups);
 
-	return path;
+	add_path(result_rel, path);
+	postprocess_setop_rel(root, result_rel);
+	return result_rel;
 }
 
 /*
- * Generate path for a UNION or UNION ALL node
+ * Generate paths for a UNION or UNION ALL node
  */
-static Path *
-generate_union_path(SetOperationStmt *op, PlannerInfo *root,
-					List *refnames_tlist,
-					List **pTargetList,
-					double *pNumGroups)
+static RelOptInfo *
+generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
+					 List *refnames_tlist,
+					 List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	Relids		relids = NULL;
+	RelOptInfo *result_rel;
 	double		save_fraction = root->tuple_fraction;
-	List	   *pathlist;
+	ListCell   *lc;
+	List	   *pathlist = NIL;
+	List	   *rellist;
 	List	   *tlist_list;
 	List	   *tlist;
 	Path	   *path;
@@ -569,7 +577,7 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	 * only one Append and unique-ification for the lot.  Recurse to find such
 	 * nodes and compute their children's paths.
 	 */
-	pathlist = plan_union_children(root, op, refnames_tlist, &tlist_list);
+	rellist = plan_union_children(root, op, refnames_tlist, &tlist_list);
 
 	/*
 	 * Generate tlist for Append plan node.
@@ -583,13 +591,24 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build path list and relid set. */
+	foreach(lc, rellist)
+	{
+		RelOptInfo *rel = lfirst(lc);
+
+		pathlist = lappend(pathlist, rel->cheapest_total_path);
+		relids = bms_union(relids, rel->relids);
+	}
+
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
+	result_rel->reltarget = create_pathtarget(root, tlist);
+
 	/*
 	 * Append the child results together.
 	 */
 	path = (Path *) create_append_path(result_rel, pathlist, NIL,
 									   NULL, 0, false, NIL, -1);
-	/* We have to manually jam the right tlist into the path; ick */
-	path->pathtarget = create_pathtarget(root, tlist);
 
 	/*
 	 * For UNION ALL, we just need the Append path.  For UNION, need to add
@@ -598,30 +617,32 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	if (!op->all)
 		path = make_union_unique(op, path, tlist, root);
 
+	add_path(result_rel, path);
+
 	/*
-	 * Estimate number of groups if caller wants it.  For now we just assume
-	 * the output is unique --- this is certainly true for the UNION case, and
-	 * we want worst-case estimates anyway.
+	 * 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.
 	 */
-	if (pNumGroups)
-		*pNumGroups = path->rows;
+	result_rel->rows = path->rows;
 
 	/* Undo effects of possibly forcing tuple_fraction to 0 */
 	root->tuple_fraction = save_fraction;
 
-	return path;
+	return result_rel;
 }
 
 /*
- * Generate path for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
+ * Generate paths for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
  */
-static Path *
-generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
-					   List *refnames_tlist,
-					   List **pTargetList,
-					   double *pNumGroups)
+static RelOptInfo *
+generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
+						List *refnames_tlist,
+						List **pTargetList)
 {
-	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+	RelOptInfo *result_rel;
+	RelOptInfo *lrel,
+			   *rrel;
 	double		save_fraction = root->tuple_fraction;
 	Path	   *lpath,
 			   *rpath,
@@ -646,18 +667,20 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 	root->tuple_fraction = 0.0;
 
 	/* Recurse on children, ensuring their outputs are marked */
-	lpath = recurse_set_operations(op->larg, root,
-								   op->colTypes, op->colCollations,
-								   false, 0,
-								   refnames_tlist,
-								   &lpath_tlist,
-								   &dLeftGroups);
-	rpath = recurse_set_operations(op->rarg, root,
-								   op->colTypes, op->colCollations,
-								   false, 1,
-								   refnames_tlist,
-								   &rpath_tlist,
-								   &dRightGroups);
+	lrel = recurse_set_operations(op->larg, root,
+								  op->colTypes, op->colCollations,
+								  false, 0,
+								  refnames_tlist,
+								  &lpath_tlist,
+								  &dLeftGroups);
+	lpath = lrel->cheapest_total_path;
+	rrel = recurse_set_operations(op->rarg, root,
+								  op->colTypes, op->colCollations,
+								  false, 1,
+								  refnames_tlist,
+								  &rpath_tlist,
+								  &dRightGroups);
+	rpath = rrel->cheapest_total_path;
 
 	/* Undo effects of forcing tuple_fraction to 0 */
 	root->tuple_fraction = save_fraction;
@@ -695,15 +718,17 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
+	/* Build result relation. */
+	result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
+								 bms_union(lrel->relids, rrel->relids));
+	result_rel->reltarget = create_pathtarget(root, tlist);;
+
 	/*
 	 * Append the child results together.
 	 */
 	path = (Path *) create_append_path(result_rel, pathlist, NIL,
 									   NULL, 0, false, NIL, -1);
 
-	/* We have to manually jam the right tlist into the path; ick */
-	path->pathtarget = create_pathtarget(root, tlist);
-
 	/* Identify the grouping semantics */
 	groupList = generate_setop_grouplist(op, tlist);
 
@@ -769,10 +794,9 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 									  dNumGroups,
 									  dNumOutputRows);
 
-	if (pNumGroups)
-		*pNumGroups = dNumGroups;
-
-	return path;
+	result_rel->rows = path->rows;
+	add_path(result_rel, path);
+	return result_rel;
 }
 
 /*
@@ -786,7 +810,7 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
  * collations have the same notion of equality.  It is valid from an
  * implementation standpoint because we don't care about the ordering of
  * a UNION child's result: UNION ALL results are always unordered, and
- * generate_union_path will force a fresh sort if the top level is a UNION.
+ * generate_union_paths will force a fresh sort if the top level is a UNION.
  */
 static List *
 plan_union_children(PlannerInfo *root,
@@ -897,8 +921,6 @@ make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
 															   groupList,
 															   tlist),
 								 -1.0);
-		/* We have to manually jam the right tlist into the path; ick */
-		path->pathtarget = create_pathtarget(root, tlist);
 		path = (Path *) create_upper_unique_path(root,
 												 result_rel,
 												 path,
@@ -910,6 +932,24 @@ make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
 }
 
 /*
+ * postprocess_setop_rel - perform steps required after adding paths
+ */
+static void
+postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel)
+{
+	/*
+	 * We don't currently worry about allowing FDWs to contribute paths to
+	 * this relation, but give extensions a chance.
+	 */
+	if (create_upper_paths_hook)
+		(*create_upper_paths_hook) (root, UPPERREL_SETOP,
+									NULL, rel);
+
+	/* Select cheapest path */
+	set_cheapest(rel);
+}
+
+/*
  * choose_hashed_setop - should we use hashing for a set operation?
  */
 static bool
-- 
1.7.9.5

From 7525f0baf1ea58544364c046d929d17a71abf84a Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Sat, 23 Dec 2017 10:56:07 -0800
Subject: [PATCH 4/4] Consider Parallel Append as a way to implement a union
 operation in a setop tree.

Patch by me, reviewed by Ashutosh Bapat.
---
 src/backend/optimizer/prep/prepunion.c |   93 +++++++++++++++++++++++++++++++-
 1 file changed, 91 insertions(+), 2 deletions(-)

diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index f087369..0114799 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -299,11 +299,17 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		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(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).
 		 */
-		final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
 		subpath = get_cheapest_fractional_path(final_rel,
 											   root->tuple_fraction);
 
@@ -321,6 +327,23 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		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 (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,
+										 NIL, NULL);
+			add_partial_path(rel, partial_path);
+		}
+
+		/*
 		 * Estimate number of groups if caller wants it.  If the subquery used
 		 * grouping or aggregation, its output is probably mostly unique
 		 * anyway; otherwise do statistical estimation.
@@ -552,6 +575,9 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	double		save_fraction = root->tuple_fraction;
 	ListCell   *lc;
 	List	   *pathlist = NIL;
+	List	   *partial_pathlist = NIL;
+	bool		partial_paths_valid = true;
+	bool		consider_parallel = true;
 	List	   *rellist;
 	List	   *tlist_list;
 	List	   *tlist;
@@ -591,18 +617,34 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 
 	*pTargetList = tlist;
 
-	/* Build path list and relid set. */
+	/* Build path lists and relid set. */
 	foreach(lc, rellist)
 	{
 		RelOptInfo *rel = lfirst(lc);
 
 		pathlist = lappend(pathlist, rel->cheapest_total_path);
+
+		if (consider_parallel)
+		{
+			if (!rel->consider_parallel)
+			{
+				consider_parallel = false;
+				partial_paths_valid = false;
+			}
+			else if (rel->partial_pathlist == NIL)
+				partial_paths_valid = false;
+			else
+				partial_pathlist = lappend(partial_pathlist,
+										   linitial(rel->partial_pathlist));
+		}
+
 		relids = bms_union(relids, rel->relids);
 	}
 
 	/* Build result relation. */
 	result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
 	result_rel->reltarget = create_pathtarget(root, tlist);
+	result_rel->consider_parallel = consider_parallel;
 
 	/*
 	 * Append the child results together.
@@ -626,6 +668,53 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	 */
 	result_rel->rows = path->rows;
 
+	/*
+	 * Now consider doing the same thing using the partial paths plus Append
+	 * plus Gather.
+	 */
+	if (partial_paths_valid)
+	{
+		Path	   *ppath;
+		ListCell   *lc;
+		int			parallel_workers = 0;
+
+		/* Find the highest number of workers requested for any subpath. */
+		foreach(lc, partial_pathlist)
+		{
+			Path	   *path = lfirst(lc);
+
+			parallel_workers = Max(parallel_workers, path->parallel_workers);
+		}
+		Assert(parallel_workers > 0);
+
+		/*
+		 * If the use of parallel append is permitted, always request at least
+		 * log2(# of children) paths.  We assume it can be useful to have
+		 * extra workers in this case because they will be spread out across
+		 * the children.  The precise formula is just a guess; see
+		 * add_paths_to_append_rel.
+		 */
+		if (enable_parallel_append)
+		{
+			parallel_workers = Max(parallel_workers,
+								   fls(list_length(partial_pathlist)));
+			parallel_workers = Min(parallel_workers,
+								   max_parallel_workers_per_gather);
+		}
+		Assert(parallel_workers > 0);
+
+		ppath = (Path *)
+			create_append_path(result_rel, NIL, partial_pathlist,
+							   NULL, parallel_workers, enable_parallel_append,
+							   NIL /* XXX? Is this right? */ , -1);
+		ppath = (Path *)
+			create_gather_path(root, result_rel, ppath,
+							   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;
 
-- 
1.7.9.5