text: /*-------------------------------------------------------------------------
   *
   * prepunion.c
   *	  Routines to plan set-operation queries.  The filename is a leftover
   *	  from a time when only UNIONs were implemented.
   *
   * There are two code paths in the planner for set-operation queries.
   * If a subquery consists entirely of simple UNION ALL operations, it
   * is converted into an "append relation".  Otherwise, it is handled
   * by the general code in this module (plan_set_operations and its
   * subroutines).  There is some support code here for the append-relation
   * case, but most of the heavy lifting for that is done elsewhere,
   * notably in prepjointree.c and allpaths.c.
   *
   * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
   * Portions Copyright (c) 1994, Regents of the University of California
   *
   *
   * IDENTIFICATION
   *	  src/backend/optimizer/prep/prepunion.c
   *
   *-------------------------------------------------------------------------
   */
  #include "postgres.h"
  
  #include "access/htup_details.h"
  #include "access/sysattr.h"
  #include "catalog/partition.h"
  #include "catalog/pg_inherits.h"
  #include "catalog/pg_type.h"
  #include "miscadmin.h"
  #include "nodes/makefuncs.h"
  #include "nodes/nodeFuncs.h"
  #include "optimizer/cost.h"
  #include "optimizer/pathnode.h"
  #include "optimizer/paths.h"
  #include "optimizer/planmain.h"
  #include "optimizer/planner.h"
  #include "optimizer/prep.h"
  #include "optimizer/tlist.h"
  #include "parser/parse_coerce.h"
  #include "parser/parsetree.h"
  #include "utils/lsyscache.h"
  #include "utils/rel.h"
  #include "utils/selfuncs.h"
  #include "utils/syscache.h"
  
  
  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 RelOptInfo *generate_recursion_path(SetOperationStmt *setOp,
  										   PlannerInfo *root,
  										   List *refnames_tlist,
  										   List **pTargetList);
  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,
  								const char *construct);
  static List *generate_setop_tlist(List *colTypes, List *colCollations,
  								  int flag,
  								  Index varno,
  								  bool hack_constants,
  								  List *input_tlist,
  								  List *refnames_tlist);
  static List *generate_append_tlist(List *colTypes, List *colCollations,
  								   bool flag,
  								   List *input_tlists,
  								   List *refnames_tlist);
  static List *generate_setop_grouplist(SetOperationStmt *op, List *targetlist);
  
  
  /*
   * plan_set_operations
   *
   *	  Plans the queries for a tree of set operations (UNION/INTERSECT/EXCEPT)
   *
   * This routine only deals with the setOperations tree of the given query.
   * Any top-level ORDER BY requested in root->parse->sortClause will be handled
   * when we return to grouping_planner; likewise for LIMIT.
   *
   * What we return is an "upperrel" RelOptInfo containing at least one Path
   * that implements the set-operation tree.  In addition, root->processed_tlist
   * receives a targetlist representing the output of the topmost setop node.
   */
  RelOptInfo *
  plan_set_operations(PlannerInfo *root)
  {
  	Query	   *parse = root->parse;
  	SetOperationStmt *topop = castNode(SetOperationStmt, parse->setOperations);
  	Node	   *node;
  	RangeTblEntry *leftmostRTE;
  	Query	   *leftmostQuery;
  	RelOptInfo *setop_rel;
  	List	   *top_tlist;
  
  	Assert(topop);
  
  	/* check for unsupported stuff */
  	Assert(parse->jointree->fromlist == NIL);
  	Assert(parse->jointree->quals == NULL);
  	Assert(parse->groupClause == NIL);
  	Assert(parse->havingQual == NULL);
  	Assert(parse->windowClause == NIL);
  	Assert(parse->distinctClause == NIL);
  
  	/*
  	 * We'll need to build RelOptInfos for each of the leaf subqueries, which
  	 * are RTE_SUBQUERY rangetable entries in this Query.  Prepare the index
  	 * arrays for that.
  	 */
  	setup_simple_rel_arrays(root);
  
  	/*
  	 * Populate append_rel_array with each AppendRelInfo to allow direct
  	 * lookups by child relid.
  	 */
  	setup_append_rel_array(root);
  
  	/*
  	 * Find the leftmost component Query.  We need to use its column names for
  	 * all generated tlists (else SELECT INTO won't work right).
  	 */
  	node = topop->larg;
  	while (node && IsA(node, SetOperationStmt))
  		node = ((SetOperationStmt *) node)->larg;
  	Assert(node && IsA(node, RangeTblRef));
  	leftmostRTE = root->simple_rte_array[((RangeTblRef *) node)->rtindex];
  	leftmostQuery = leftmostRTE->subquery;
  	Assert(leftmostQuery != NULL);
  
  	/*
  	 * If the topmost node is a recursive union, it needs special processing.
  	 */
  	if (root->hasRecursion)
  	{
  		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 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).
  		 */
  		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;
  
  	return setop_rel;
  }
  
  /*
   * recurse_set_operations
   *	  Recursively handle one step in a tree of set operations
   *
   * colTypes: OID list of set-op's result column datatypes
   * colCollations: OID list of set-op's result column collations
   * junkOK: if true, child resjunk columns may be left in the result
   * flag: if >= 0, add a resjunk output column indicating value of flag
   * refnames_tlist: targetlist to take column names from
   *
   * 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 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 RelOptInfo *
  recurse_set_operations(Node *setOp, PlannerInfo *root,
  					   List *colTypes, List *colCollations,
  					   bool junkOK,
  					   int flag, List *refnames_tlist,
  					   List **pTargetList,
  					   double *pNumGroups)
  {
  	RelOptInfo *rel = NULL;		/* keep compiler quiet */
  
  	/* Guard against stack overflow due to overly complex setop nests */
  	check_stack_depth();
  
  	if (IsA(setOp, RangeTblRef))
  	{
  		RangeTblRef *rtr = (RangeTblRef *) setOp;
  		RangeTblEntry *rte = root->simple_rte_array[rtr->rtindex];
  		Query	   *subquery = rte->subquery;
  		PlannerInfo *subroot;
  		RelOptInfo *final_rel;
  		Path	   *subpath;
  		Path	   *path;
  		List	   *tlist;
  
  		Assert(subquery != NULL);
  
  		/* 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 */
  		Assert(root->plan_params == NIL);
  
  		/* Generate a subroot and Paths for the subquery */
  		subroot = rel->subroot = subquery_planner(root->glob, subquery,
  												  root,
  												  false,
  												  root->tuple_fraction);
  
  		/*
  		 * It should not be possible for the primitive query to contain any
  		 * cross-references to other primitive queries in the setop tree.
  		 */
  		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
  		 * cost_subqueryscan is not happy.
  		 */
  		set_subquery_size_estimates(root, rel);
  
  		/*
  		 * Since we may want to add a partial path to this relation, we must
  		 * set its consider_parallel flag correctly.
  		 */
  		final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
  		rel->consider_parallel = final_rel->consider_parallel;
  
  		/*
  		 * For the moment, we consider only a single Path for the subquery.
  		 * This should change soon (make it look more like
  		 * set_subquery_pathlist).
  		 */
  		subpath = get_cheapest_fractional_path(final_rel,
  											   root->tuple_fraction);
  
  		/*
  		 * Stick a SubqueryScanPath atop that.
  		 *
  		 * We don't bother to determine the subquery's output ordering since
  		 * it won't be reflected in the set-op result anyhow; so just label
  		 * the SubqueryScanPath with nil pathkeys.  (XXX that should change
  		 * soon too, likely.)
  		 */
  		path = (Path *) create_subqueryscan_path(root, rel, subpath,
  												 NIL, NULL);
  
  		add_path(rel, path);
  
  		/*
  		 * If we have a partial path for the child relation, we can use that
  		 * to build a partial path for this relation.  But there's no point in
  		 * considering any path but the cheapest.
  		 */
  		if (rel->consider_parallel && bms_is_empty(rel->lateral_relids) &&
  			final_rel->partial_pathlist != NIL)
  		{
  			Path	   *partial_subpath;
  			Path	   *partial_path;
  
  			partial_subpath = linitial(final_rel->partial_pathlist);
  			partial_path = (Path *)
  				create_subqueryscan_path(root, rel, partial_subpath,
  										 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.
  		 *
  		 * XXX you don't really want to know about this: we do the estimation
  		 * using the subquery's original targetlist expressions, not the
  		 * subroot->processed_tlist which might seem more appropriate.  The
  		 * reason is that if the subquery is itself a setop, it may return a
  		 * processed_tlist containing "varno 0" Vars generated by
  		 * generate_append_tlist, and those would confuse estimate_num_groups
  		 * mightily.  We ought to get rid of the "varno 0" hack, but that
  		 * requires a redesign of the parsetree representation of setops, so
  		 * that there can be an RTE corresponding to each setop's output.
  		 */
  		if (pNumGroups)
  		{
  			if (subquery->groupClause || subquery->groupingSets ||
  				subquery->distinctClause ||
  				subroot->hasHavingQual || subquery->hasAggs)
  				*pNumGroups = subpath->rows;
  			else
  				*pNumGroups = estimate_num_groups(subroot,
  												  get_tlist_exprs(subquery->targetList, false),
  												  subpath->rows,
  												  NULL);
  		}
  	}
  	else if (IsA(setOp, SetOperationStmt))
  	{
  		SetOperationStmt *op = (SetOperationStmt *) setOp;
  
  		/* UNIONs are much different from INTERSECT/EXCEPT */
  		if (op->op == SETOP_UNION)
  			rel = generate_union_paths(op, root,
  									   refnames_tlist,
  									   pTargetList);
  		else
  			rel = generate_nonunion_paths(op, root,
  										  refnames_tlist,
  										  pTargetList);
  		if (pNumGroups)
  			*pNumGroups = rel->rows;
  
  		/*
  		 * If necessary, add a Result node to project the caller-requested
  		 * output columns.
  		 *
  		 * XXX you don't really want to know about this: setrefs.c will apply
  		 * fix_upper_expr() to the Result node's tlist. This would fail if the
  		 * Vars generated by generate_setop_tlist() were not exactly equal()
  		 * to the corresponding tlist entries of the subplan. However, since
  		 * the subplan was generated by generate_union_plan() or
  		 * generate_nonunion_plan(), and hence its tlist was generated by
  		 * generate_append_tlist(), this will work.  We just tell
  		 * generate_setop_tlist() to use varno 0.
  		 */
  		if (flag >= 0 ||
  			!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);
  			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;
  			}
  		}
  	}
  	else
  	{
  		elog(ERROR, "unrecognized node type: %d",
  			 (int) nodeTag(setOp));
  		*pTargetList = NIL;
  	}
  
  	postprocess_setop_rel(root, rel);
  
  	return rel;
  }
  
  /*
   * Generate paths for a recursive UNION node
   */
  static RelOptInfo *
  generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
  						List *refnames_tlist,
  						List **pTargetList)
  {
  	RelOptInfo *result_rel;
  	Path	   *path;
  	RelOptInfo *lrel,
  			   *rrel;
  	Path	   *lpath;
  	Path	   *rpath;
  	List	   *lpath_tlist;
  	List	   *rpath_tlist;
  	List	   *tlist;
  	List	   *groupList;
  	double		dNumGroups;
  
  	/* Parser should have rejected other cases */
  	if (setOp->op != SETOP_UNION)
  		elog(ERROR, "only UNION queries can be recursive");
  	/* Worktable ID should be assigned */
  	Assert(root->wt_param_id >= 0);
  
  	/*
  	 * Unlike a regular UNION node, process the left and right inputs
  	 * separately without any intention of combining them into one Append.
  	 */
  	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;
  	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;
  
  	/*
  	 * Generate tlist for RecursiveUnion path node --- same as in Append cases
  	 */
  	tlist = generate_append_tlist(setOp->colTypes, setOp->colCollations, false,
  								  list_make2(lpath_tlist, rpath_tlist),
  								  refnames_tlist);
  
  	*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
  	 */
  	if (setOp->all)
  	{
  		groupList = NIL;
  		dNumGroups = 0;
  	}
  	else
  	{
  		/* Identify the grouping semantics */
  		groupList = generate_setop_grouplist(setOp, tlist);
  
  		/* We only support hashing here */
  		if (!grouping_is_hashable(groupList))
  			ereport(ERROR,
  					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
  					 errmsg("could not implement recursive UNION"),
  					 errdetail("All column datatypes must be hashable.")));
  
  		/*
  		 * For the moment, take the number of distinct groups as equal to the
  		 * total input size, ie, the worst case.
  		 */
  		dNumGroups = lpath->rows + rpath->rows * 10;
  	}
  
  	/*
  	 * And make the path node.
  	 */
  	path = (Path *) create_recursiveunion_path(root,
  											   result_rel,
  											   lpath,
  											   rpath,
  											   result_rel->reltarget,
  											   groupList,
  											   root->wt_param_id,
  											   dNumGroups);
  
  	add_path(result_rel, path);
  	postprocess_setop_rel(root, result_rel);
  	return result_rel;
  }
  
  /*
   * Generate paths for a UNION or UNION ALL node
   */
  static RelOptInfo *
  generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
  					 List *refnames_tlist,
  					 List **pTargetList)
  {
  	Relids		relids = NULL;
  	RelOptInfo *result_rel;
  	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;
  	Path	   *path;
  
  	/*
  	 * If plain UNION, tell children to fetch all tuples.
  	 *
  	 * Note: in UNION ALL, we pass the top-level tuple_fraction unmodified to
  	 * each arm of the UNION ALL.  One could make a case for reducing the
  	 * tuple fraction for later arms (discounting by the expected size of the
  	 * earlier arms' results) but it seems not worth the trouble. The normal
  	 * case where tuple_fraction isn't already zero is a LIMIT at top level,
  	 * and passing it down as-is is usually enough to get the desired result
  	 * of preferring fast-start plans.
  	 */
  	if (!op->all)
  		root->tuple_fraction = 0.0;
  
  	/*
  	 * If any of my children are identical UNION nodes (same op, all-flag, and
  	 * colTypes) then they can be merged into this node so that we generate
  	 * only one Append and unique-ification for the lot.  Recurse to find such
  	 * nodes and compute their children's paths.
  	 */
  	rellist = plan_union_children(root, op, refnames_tlist, &tlist_list);
  
  	/*
  	 * Generate tlist for Append plan node.
  	 *
  	 * The tlist for an Append plan isn't important as far as the Append is
  	 * concerned, but we must make it look real anyway for the benefit of the
  	 * next plan level up.
  	 */
  	tlist = generate_append_tlist(op->colTypes, op->colCollations, false,
  								  tlist_list, refnames_tlist);
  
  	*pTargetList = tlist;
  
  	/* 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.
  	 */
  	path = (Path *) create_append_path(root, result_rel, pathlist, NIL,
  									   NIL, NULL, 0, false, NIL, -1);
  
  	/*
  	 * For UNION ALL, we just need the Append path.  For UNION, need to add
  	 * node(s) to remove duplicates.
  	 */
  	if (!op->all)
  		path = make_union_unique(op, path, tlist, root);
  
  	add_path(result_rel, path);
  
  	/*
  	 * Estimate number of groups.  For now we just assume the output is unique
  	 * --- this is certainly true for the UNION case, and we want worst-case
  	 * estimates anyway.
  	 */
  	result_rel->rows = path->rows;
  
  	/*
  	 * 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(root, result_rel, NIL, partial_pathlist,
  							   NIL, NULL,
  							   parallel_workers, enable_parallel_append,
  							   NIL, -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;
  
  	return result_rel;
  }
  
  /*
   * Generate paths for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
   */
  static RelOptInfo *
  generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
  						List *refnames_tlist,
  						List **pTargetList)
  {
  	RelOptInfo *result_rel;
  	RelOptInfo *lrel,
  			   *rrel;
  	double		save_fraction = root->tuple_fraction;
  	Path	   *lpath,
  			   *rpath,
  			   *path;
  	List	   *lpath_tlist,
  			   *rpath_tlist,
  			   *tlist_list,
  			   *tlist,
  			   *groupList,
  			   *pathlist;
  	double		dLeftGroups,
  				dRightGroups,
  				dNumGroups,
  				dNumOutputRows;
  	bool		use_hash;
  	SetOpCmd	cmd;
  	int			firstFlag;
  
  	/*
  	 * Tell children to fetch all tuples.
  	 */
  	root->tuple_fraction = 0.0;
  
  	/* Recurse on children, ensuring their outputs are marked */
  	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;
  
  	/*
  	 * For EXCEPT, we must put the left input first.  For INTERSECT, either
  	 * order should give the same results, and we prefer to put the smaller
  	 * input first in order to minimize the size of the hash table in the
  	 * hashing case.  "Smaller" means the one with the fewer groups.
  	 */
  	if (op->op == SETOP_EXCEPT || dLeftGroups <= dRightGroups)
  	{
  		pathlist = list_make2(lpath, rpath);
  		tlist_list = list_make2(lpath_tlist, rpath_tlist);
  		firstFlag = 0;
  	}
  	else
  	{
  		pathlist = list_make2(rpath, lpath);
  		tlist_list = list_make2(rpath_tlist, lpath_tlist);
  		firstFlag = 1;
  	}
  
  	/*
  	 * Generate tlist for Append plan node.
  	 *
  	 * The tlist for an Append plan isn't important as far as the Append is
  	 * concerned, but we must make it look real anyway for the benefit of the
  	 * next plan level up.  In fact, it has to be real enough that the flag
  	 * column is shown as a variable not a constant, else setrefs.c will get
  	 * confused.
  	 */
  	tlist = generate_append_tlist(op->colTypes, op->colCollations, true,
  								  tlist_list, refnames_tlist);
  
  	*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(root, result_rel, pathlist, NIL,
  									   NIL, NULL, 0, false, NIL, -1);
  
  	/* Identify the grouping semantics */
  	groupList = generate_setop_grouplist(op, tlist);
  
  	/*
  	 * Estimate number of distinct groups that we'll need hashtable entries
  	 * for; this is the size of the left-hand input for EXCEPT, or the smaller
  	 * input for INTERSECT.  Also estimate the number of eventual output rows.
  	 * In non-ALL cases, we estimate each group produces one output row; in
  	 * ALL cases use the relevant relation size.  These are worst-case
  	 * estimates, of course, but we need to be conservative.
  	 */
  	if (op->op == SETOP_EXCEPT)
  	{
  		dNumGroups = dLeftGroups;
  		dNumOutputRows = op->all ? lpath->rows : dNumGroups;
  	}
  	else
  	{
  		dNumGroups = Min(dLeftGroups, dRightGroups);
  		dNumOutputRows = op->all ? Min(lpath->rows, rpath->rows) : dNumGroups;
  	}
  
  	/*
  	 * Decide whether to hash or sort, and add a sort node if needed.
  	 */
  	use_hash = choose_hashed_setop(root, groupList, path,
  								   dNumGroups, dNumOutputRows,
  								   (op->op == SETOP_INTERSECT) ? "INTERSECT" : "EXCEPT");
  
  	if (groupList && !use_hash)
  		path = (Path *) create_sort_path(root,
  										 result_rel,
  										 path,
  										 make_pathkeys_for_sortclauses(root,
  																	   groupList,
  																	   tlist),
  										 -1.0);
  
  	/*
  	 * Finally, add a SetOp path node to generate the correct output.
  	 */
  	switch (op->op)
  	{
  		case SETOP_INTERSECT:
  			cmd = op->all ? SETOPCMD_INTERSECT_ALL : SETOPCMD_INTERSECT;
  			break;
  		case SETOP_EXCEPT:
  			cmd = op->all ? SETOPCMD_EXCEPT_ALL : SETOPCMD_EXCEPT;
  			break;
  		default:
  			elog(ERROR, "unrecognized set op: %d", (int) op->op);
  			cmd = SETOPCMD_INTERSECT;	/* keep compiler quiet */
  			break;
  	}
  	path = (Path *) create_setop_path(root,
  									  result_rel,
  									  path,
  									  cmd,
  									  use_hash ? SETOP_HASHED : SETOP_SORTED,
  									  groupList,
  									  list_length(op->colTypes) + 1,
  									  use_hash ? firstFlag : -1,
  									  dNumGroups,
  									  dNumOutputRows);
  
  	result_rel->rows = path->rows;
  	add_path(result_rel, path);
  	return result_rel;
  }
  
  /*
   * Pull up children of a UNION node that are identically-propertied UNIONs.
   *
   * NOTE: we can also pull a UNION ALL up into a UNION, since the distinct
   * output rows will be lost anyway.
   *
   * NOTE: currently, we ignore collations while determining if a child has
   * the same properties.  This is semantically sound only so long as all
   * 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_paths will force a fresh sort if the top level is a UNION.
   */
  static List *
  plan_union_children(PlannerInfo *root,
  					SetOperationStmt *top_union,
  					List *refnames_tlist,
  					List **tlist_list)
  {
  	List	   *pending_rels = list_make1(top_union);
  	List	   *result = NIL;
  	List	   *child_tlist;
  
  	*tlist_list = NIL;
  
  	while (pending_rels != NIL)
  	{
  		Node	   *setOp = linitial(pending_rels);
  
  		pending_rels = list_delete_first(pending_rels);
  
  		if (IsA(setOp, SetOperationStmt))
  		{
  			SetOperationStmt *op = (SetOperationStmt *) setOp;
  
  			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);
  	}
  
  	return result;
  }
  
  /*
   * Add nodes to the given path tree to unique-ify the result of a UNION.
   */
  static Path *
  make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
  				  PlannerInfo *root)
  {
  	RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
  	List	   *groupList;
  	double		dNumGroups;
  
  	/* Identify the grouping semantics */
  	groupList = generate_setop_grouplist(op, tlist);
  
  	/*
  	 * XXX for the moment, take the number of distinct groups as equal to the
  	 * total input size, ie, the worst case.  This is too conservative, but we
  	 * don't want to risk having the hashtable overrun memory; also, it's not
  	 * clear how to get a decent estimate of the true size.  One should note
  	 * as well the propensity of novices to write UNION rather than UNION ALL
  	 * even when they don't expect any duplicates...
  	 */
  	dNumGroups = path->rows;
  
  	/* Decide whether to hash or sort */
  	if (choose_hashed_setop(root, groupList, path,
  							dNumGroups, dNumGroups,
  							"UNION"))
  	{
  		/* Hashed aggregate plan --- no sort needed */
  		path = (Path *) create_agg_path(root,
  										result_rel,
  										path,
  										create_pathtarget(root, tlist),
  										AGG_HASHED,
  										AGGSPLIT_SIMPLE,
  										groupList,
  										NIL,
  										NULL,
  										dNumGroups);
  	}
  	else
  	{
  		/* Sort and Unique */
  		if (groupList)
  			path = (Path *)
  				create_sort_path(root,
  								 result_rel,
  								 path,
  								 make_pathkeys_for_sortclauses(root,
  															   groupList,
  															   tlist),
  								 -1.0);
  		path = (Path *) create_upper_unique_path(root,
  												 result_rel,
  												 path,
  												 list_length(path->pathkeys),
  												 dNumGroups);
  	}
  
  	return path;
  }
  
  /*
   * postprocess_setop_rel - perform steps required after adding paths
   */
  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, NULL);
  
  	/* Select cheapest path */
  	set_cheapest(rel);
  }
  
  /*
   * choose_hashed_setop - should we use hashing for a set operation?
   */
  static bool
  choose_hashed_setop(PlannerInfo *root, List *groupClauses,
  					Path *input_path,
  					double dNumGroups, double dNumOutputRows,
  					const char *construct)
  {
  	int			numGroupCols = list_length(groupClauses);
  	bool		can_sort;
  	bool		can_hash;
  	Size		hashentrysize;
  	Path		hashed_p;
  	Path		sorted_p;
  	double		tuple_fraction;
  
  	/* Check whether the operators support sorting or hashing */
  	can_sort = grouping_is_sortable(groupClauses);
  	can_hash = grouping_is_hashable(groupClauses);
  	if (can_hash && can_sort)
  	{
  		/* we have a meaningful choice to make, continue ... */
  	}
  	else if (can_hash)
  		return true;
  	else if (can_sort)
  		return false;
  	else
  		ereport(ERROR,
  				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
  		/* translator: %s is UNION, INTERSECT, or EXCEPT */
  				 errmsg("could not implement %s", construct),
  				 errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
  
  	/* Prefer sorting when enable_hashagg is off */
  	if (!enable_hashagg)
  		return false;
  
  	/*
  	 * Don't do it if it doesn't look like the hashtable will fit into
  	 * work_mem.
  	 */
  	hashentrysize = MAXALIGN(input_path->pathtarget->width) + MAXALIGN(SizeofMinimalTupleHeader);
  
  	if (hashentrysize * dNumGroups > work_mem * 1024L)
  		return false;
  
  	/*
  	 * See if the estimated cost is no more than doing it the other way.
  	 *
  	 * We need to consider input_plan + hashagg versus input_plan + sort +
  	 * group.  Note that the actual result plan might involve a SetOp or
  	 * Unique node, not Agg or Group, but the cost estimates for Agg and Group
  	 * should be close enough for our purposes here.
  	 *
  	 * These path variables are dummies that just hold cost fields; we don't
  	 * make actual Paths for these steps.
  	 */
  	cost_agg(&hashed_p, root, AGG_HASHED, NULL,
  			 numGroupCols, dNumGroups,
  			 NIL,
  			 input_path->startup_cost, input_path->total_cost,
  			 input_path->rows);
  
  	/*
  	 * Now for the sorted case.  Note that the input is *always* unsorted,
  	 * since it was made by appending unrelated sub-relations together.
  	 */
  	sorted_p.startup_cost = input_path->startup_cost;
  	sorted_p.total_cost = input_path->total_cost;
  	/* XXX cost_sort doesn't actually look at pathkeys, so just pass NIL */
  	cost_sort(&sorted_p, root, NIL, sorted_p.total_cost,
  			  input_path->rows, input_path->pathtarget->width,
  			  0.0, work_mem, -1.0);
  	cost_group(&sorted_p, root, numGroupCols, dNumGroups,
  			   NIL,
  			   sorted_p.startup_cost, sorted_p.total_cost,
  			   input_path->rows);
  
  	/*
  	 * Now make the decision using the top-level tuple fraction.  First we
  	 * have to convert an absolute count (LIMIT) into fractional form.
  	 */
  	tuple_fraction = root->tuple_fraction;
  	if (tuple_fraction >= 1.0)
  		tuple_fraction /= dNumOutputRows;
  
  	if (compare_fractional_path_costs(&hashed_p, &sorted_p,
  									  tuple_fraction) < 0)
  	{
  		/* Hashed is cheaper, so use it */
  		return true;
  	}
  	return false;
  }
  
  /*
   * Generate targetlist for a set-operation plan node
   *
   * colTypes: OID list of set-op's result column datatypes
   * colCollations: OID list of set-op's result column collations
   * flag: -1 if no flag column needed, 0 or 1 to create a const flag column
   * varno: varno to use in generated Vars
   * hack_constants: true to copy up constants (see comments in code)
   * input_tlist: targetlist of this node's input node
   * refnames_tlist: targetlist to take column names from
   */
  static List *
  generate_setop_tlist(List *colTypes, List *colCollations,
  					 int flag,
  					 Index varno,
  					 bool hack_constants,
  					 List *input_tlist,
  					 List *refnames_tlist)
  {
  	List	   *tlist = NIL;
  	int			resno = 1;
  	ListCell   *ctlc,
  			   *cclc,
  			   *itlc,
  			   *rtlc;
  	TargetEntry *tle;
  	Node	   *expr;
  
  	forfour(ctlc, colTypes, cclc, colCollations,
  			itlc, input_tlist, rtlc, refnames_tlist)
  	{
  		Oid			colType = lfirst_oid(ctlc);
  		Oid			colColl = lfirst_oid(cclc);
  		TargetEntry *inputtle = (TargetEntry *) lfirst(itlc);
  		TargetEntry *reftle = (TargetEntry *) lfirst(rtlc);
  
  		Assert(inputtle->resno == resno);
  		Assert(reftle->resno == resno);
  		Assert(!inputtle->resjunk);
  		Assert(!reftle->resjunk);
  
  		/*
  		 * Generate columns referencing input columns and having appropriate
  		 * data types and column names.  Insert datatype coercions where
  		 * necessary.
  		 *
  		 * HACK: constants in the input's targetlist are copied up as-is
  		 * rather than being referenced as subquery outputs.  This is mainly
  		 * to ensure that when we try to coerce them to the output column's
  		 * datatype, the right things happen for UNKNOWN constants.  But do
  		 * this only at the first level of subquery-scan plans; we don't want
  		 * phony constants appearing in the output tlists of upper-level
  		 * nodes!
  		 */
  		if (hack_constants && inputtle->expr && IsA(inputtle->expr, Const))
  			expr = (Node *) inputtle->expr;
  		else
  			expr = (Node *) makeVar(varno,
  									inputtle->resno,
  									exprType((Node *) inputtle->expr),
  									exprTypmod((Node *) inputtle->expr),
  									exprCollation((Node *) inputtle->expr),
  									0);
  
  		if (exprType(expr) != colType)
  		{
  			/*
  			 * Note: it's not really cool to be applying coerce_to_common_type
  			 * here; one notable point is that assign_expr_collations never
  			 * gets run on any generated nodes.  For the moment that's not a
  			 * problem because we force the correct exposed collation below.
  			 * It would likely be best to make the parser generate the correct
  			 * output tlist for every set-op to begin with, though.
  			 */
  			expr = coerce_to_common_type(NULL,	/* no UNKNOWNs here */
  										 expr,
  										 colType,
  										 "UNION/INTERSECT/EXCEPT");
  		}
  
  		/*
  		 * Ensure the tlist entry's exposed collation matches the set-op. This
  		 * is necessary because plan_set_operations() reports the result
  		 * ordering as a list of SortGroupClauses, which don't carry collation
  		 * themselves but just refer to tlist entries.  If we don't show the
  		 * right collation then planner.c might do the wrong thing in
  		 * higher-level queries.
  		 *
  		 * Note we use RelabelType, not CollateExpr, since this expression
  		 * will reach the executor without any further processing.
  		 */
  		if (exprCollation(expr) != colColl)
  		{
  			expr = (Node *) makeRelabelType((Expr *) expr,
  											exprType(expr),
  											exprTypmod(expr),
  											colColl,
  											COERCE_IMPLICIT_CAST);
  		}
  
  		tle = makeTargetEntry((Expr *) expr,
  							  (AttrNumber) resno++,
  							  pstrdup(reftle->resname),
  							  false);
  
  		/*
  		 * By convention, all non-resjunk columns in a setop tree have
  		 * ressortgroupref equal to their resno.  In some cases the ref isn't
  		 * needed, but this is a cleaner way than modifying the tlist later.
  		 */
  		tle->ressortgroupref = tle->resno;
  
  		tlist = lappend(tlist, tle);
  	}
  
  	if (flag >= 0)
  	{
  		/* Add a resjunk flag column */
  		/* flag value is the given constant */
  		expr = (Node *) makeConst(INT4OID,
  								  -1,
  								  InvalidOid,
  								  sizeof(int32),
  								  Int32GetDatum(flag),
  								  false,
  								  true);
  		tle = makeTargetEntry((Expr *) expr,
  							  (AttrNumber) resno++,
  							  pstrdup("flag"),
  							  true);
  		tlist = lappend(tlist, tle);
  	}
  
  	return tlist;
  }
  
  /*
   * Generate targetlist for a set-operation Append node
   *
   * colTypes: OID list of set-op's result column datatypes
   * colCollations: OID list of set-op's result column collations
   * flag: true to create a flag column copied up from subplans
   * input_tlists: list of tlists for sub-plans of the Append
   * refnames_tlist: targetlist to take column names from
   *
   * The entries in the Append's targetlist should always be simple Vars;
   * we just have to make sure they have the right datatypes/typmods/collations.
   * The Vars are always generated with varno 0.
   *
   * XXX a problem with the varno-zero approach is that set_pathtarget_cost_width
   * cannot figure out a realistic width for the tlist we make here.  But we
   * ought to refactor this code to produce a PathTarget directly, anyway.
   */
  static List *
  generate_append_tlist(List *colTypes, List *colCollations,
  					  bool flag,
  					  List *input_tlists,
  					  List *refnames_tlist)
  {
  	List	   *tlist = NIL;
  	int			resno = 1;
  	ListCell   *curColType;
  	ListCell   *curColCollation;
  	ListCell   *ref_tl_item;
  	int			colindex;
  	TargetEntry *tle;
  	Node	   *expr;
  	ListCell   *tlistl;
  	int32	   *colTypmods;
  
  	/*
  	 * First extract typmods to use.
  	 *
  	 * If the inputs all agree on type and typmod of a particular column, use
  	 * that typmod; else use -1.
  	 */
  	colTypmods = (int32 *) palloc(list_length(colTypes) * sizeof(int32));
  
  	foreach(tlistl, input_tlists)
  	{
  		List	   *subtlist = (List *) lfirst(tlistl);
  		ListCell   *subtlistl;
  
  		curColType = list_head(colTypes);
  		colindex = 0;
  		foreach(subtlistl, subtlist)
  		{
  			TargetEntry *subtle = (TargetEntry *) lfirst(subtlistl);
  
  			if (subtle->resjunk)
  				continue;
  			Assert(curColType != NULL);
  			if (exprType((Node *) subtle->expr) == lfirst_oid(curColType))
  			{
  				/* If first subplan, copy the typmod; else compare */
  				int32		subtypmod = exprTypmod((Node *) subtle->expr);
  
  				if (tlistl == list_head(input_tlists))
  					colTypmods[colindex] = subtypmod;
  				else if (subtypmod != colTypmods[colindex])
  					colTypmods[colindex] = -1;
  			}
  			else
  			{
  				/* types disagree, so force typmod to -1 */
  				colTypmods[colindex] = -1;
  			}
  			curColType = lnext(curColType);
  			colindex++;
  		}
  		Assert(curColType == NULL);
  	}
  
  	/*
  	 * Now we can build the tlist for the Append.
  	 */
  	colindex = 0;
  	forthree(curColType, colTypes, curColCollation, colCollations,
  			 ref_tl_item, refnames_tlist)
  	{
  		Oid			colType = lfirst_oid(curColType);
  		int32		colTypmod = colTypmods[colindex++];
  		Oid			colColl = lfirst_oid(curColCollation);
  		TargetEntry *reftle = (TargetEntry *) lfirst(ref_tl_item);
  
  		Assert(reftle->resno == resno);
  		Assert(!reftle->resjunk);
  		expr = (Node *) makeVar(0,
  								resno,
  								colType,
  								colTypmod,
  								colColl,
  								0);
  		tle = makeTargetEntry((Expr *) expr,
  							  (AttrNumber) resno++,
  							  pstrdup(reftle->resname),
  							  false);
  
  		/*
  		 * By convention, all non-resjunk columns in a setop tree have
  		 * ressortgroupref equal to their resno.  In some cases the ref isn't
  		 * needed, but this is a cleaner way than modifying the tlist later.
  		 */
  		tle->ressortgroupref = tle->resno;
  
  		tlist = lappend(tlist, tle);
  	}
  
  	if (flag)
  	{
  		/* Add a resjunk flag column */
  		/* flag value is shown as copied up from subplan */
  		expr = (Node *) makeVar(0,
  								resno,
  								INT4OID,
  								-1,
  								InvalidOid,
  								0);
  		tle = makeTargetEntry((Expr *) expr,
  							  (AttrNumber) resno++,
  							  pstrdup("flag"),
  							  true);
  		tlist = lappend(tlist, tle);
  	}
  
  	pfree(colTypmods);
  
  	return tlist;
  }
  
  /*
   * generate_setop_grouplist
   *		Build a SortGroupClause list defining the sort/grouping properties
   *		of the setop's output columns.
   *
   * Parse analysis already determined the properties and built a suitable
   * list, except that the entries do not have sortgrouprefs set because
   * the parser output representation doesn't include a tlist for each
   * setop.  So what we need to do here is copy that list and install
   * proper sortgrouprefs into it (copying those from the targetlist).
   */
  static List *
  generate_setop_grouplist(SetOperationStmt *op, List *targetlist)
  {
  	List	   *grouplist = copyObject(op->groupClauses);
  	ListCell   *lg;
  	ListCell   *lt;
  
  	lg = list_head(grouplist);
  	foreach(lt, targetlist)
  	{
  		TargetEntry *tle = (TargetEntry *) lfirst(lt);
  		SortGroupClause *sgc;
  
  		if (tle->resjunk)
  		{
  			/* resjunk columns should not have sortgrouprefs */
  			Assert(tle->ressortgroupref == 0);
  			continue;			/* ignore resjunk columns */
  		}
  
  		/* non-resjunk columns should have sortgroupref = resno */
  		Assert(tle->ressortgroupref == tle->resno);
  
  		/* non-resjunk columns should have grouping clauses */
  		Assert(lg != NULL);
  		sgc = (SortGroupClause *) lfirst(lg);
  		lg = lnext(lg);
  		Assert(sgc->tleSortGroupRef == 0);
  
  		sgc->tleSortGroupRef = tle->ressortgroupref;
  	}
  	Assert(lg == NULL);
  	return grouplist;
  }
  