Reimplementation of UNION/INTERSECT/EXCEPT. INTERSECT/EXCEPT now meet the

SQL92 semantics, including support for ALL option.  All three can be used
in subqueries and views.  DISTINCT and ORDER BY work now in views, too.
This rewrite fixes many problems with cross-datatype UNIONs and INSERT/SELECT
where the SELECT yields different datatypes than the INSERT needs.  I did
that by making UNION subqueries and SELECT in INSERT be treated like
subselects-in-FROM, thereby allowing an extra level of targetlist where the
datatype conversions can be inserted safely.
INITDB NEEDED!

11 files changed, 675 insertions, 338 deletions

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 8ab2aeec918..7e017a746f1 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.65 2000/09/29 18:21:31 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.66 2000/10/05 19:11:28 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -98,7 +98,8 @@ set_base_rel_pathlist(Query *root)
 			 */
 
 			/* Generate the plan for the subquery */
-			rel->subplan = planner(rte->subquery);
+			rel->subplan = subquery_planner(rte->subquery,
+											-1.0 /* default case */ );
 
 			/* Copy number of output rows from subplan */
 			rel->tuples = rel->subplan->plan_rows;
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index cc308b4fc96..eb005121cd5 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -10,7 +10,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.97 2000/09/29 18:21:33 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.98 2000/10/05 19:11:29 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -68,8 +68,6 @@ static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
 			   ScanDirection indexscandir);
 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
 			 List *tideval);
-static SubqueryScan *make_subqueryscan(List *qptlist, List *qpqual,
-									   Index scanrelid, Plan *subplan);
 static NestLoop *make_nestloop(List *tlist,
 							   List *joinclauses, List *otherclauses,
 							   Plan *lefttree, Plan *righttree,
@@ -86,7 +84,6 @@ static MergeJoin *make_mergejoin(List *tlist,
 								 Plan *lefttree, Plan *righttree,
 								 JoinType jointype);
 static void copy_path_costsize(Plan *dest, Path *src);
-static void copy_plan_costsize(Plan *dest, Plan *src);
 
 /*
  * create_plan
@@ -1109,7 +1106,7 @@ copy_path_costsize(Plan *dest, Path *src)
  * but it helps produce more reasonable-looking EXPLAIN output.
  * (Some callers alter the info after copying it.)
  */
-static void
+void
 copy_plan_costsize(Plan *dest, Plan *src)
 {
 	if (src)
@@ -1206,7 +1203,7 @@ make_tidscan(List *qptlist,
 	return node;
 }
 
-static SubqueryScan *
+SubqueryScan *
 make_subqueryscan(List *qptlist,
 				  List *qpqual,
 				  Index scanrelid,
@@ -1593,6 +1590,67 @@ make_unique(List *tlist, Plan *lefttree, List *distinctList)
 	return node;
 }
 
+/*
+ * distinctList is a list of SortClauses, identifying the targetlist items
+ * that should be considered by the SetOp filter.
+ */
+
+SetOp *
+make_setop(SetOpCmd cmd, List *tlist, Plan *lefttree,
+		   List *distinctList, AttrNumber flagColIdx)
+{
+	SetOp	   *node = makeNode(SetOp);
+	Plan	   *plan = &node->plan;
+	int			numCols = length(distinctList);
+	int			keyno = 0;
+	AttrNumber *dupColIdx;
+	List	   *slitem;
+
+	copy_plan_costsize(plan, lefttree);
+
+	/*
+	 * Charge one cpu_operator_cost per comparison per input tuple. We
+	 * assume all columns get compared at most of the tuples.
+	 */
+	plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
+
+	/*
+	 * As for Group, we make the unsupported assumption that there will be
+	 * 10% as many tuples out as in.
+	 */
+	plan->plan_rows *= 0.1;
+	if (plan->plan_rows < 1)
+		plan->plan_rows = 1;
+
+	plan->state = (EState *) NULL;
+	plan->targetlist = tlist;
+	plan->qual = NIL;
+	plan->lefttree = lefttree;
+	plan->righttree = NULL;
+
+	/*
+	 * convert SortClause list into array of attr indexes, as wanted by
+	 * exec
+	 */
+	Assert(numCols > 0);
+	dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
+
+	foreach(slitem, distinctList)
+	{
+		SortClause *sortcl = (SortClause *) lfirst(slitem);
+		TargetEntry *tle = get_sortgroupclause_tle(sortcl, tlist);
+
+		dupColIdx[keyno++] = tle->resdom->resno;
+	}
+
+	node->cmd = cmd;
+	node->numCols = numCols;
+	node->dupColIdx = dupColIdx;
+	node->flagColIdx = flagColIdx;
+
+	return node;
+}
+
 Result *
 make_result(List *tlist,
 			Node *resconstantqual,
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 29cfccfef7b..a9747b32799 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -14,7 +14,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.60 2000/09/29 18:21:33 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.61 2000/10/05 19:11:29 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -174,8 +174,6 @@ subplanner(Query *root,
 	List	   *brel;
 	RelOptInfo *final_rel;
 	Plan	   *resultplan;
-	MemoryContext mycontext;
-	MemoryContext oldcxt;
 	Path	   *cheapestpath;
 	Path	   *presortedpath;
 
@@ -228,24 +226,6 @@ subplanner(Query *root,
 	root->query_pathkeys = canonicalize_pathkeys(root, root->query_pathkeys);
 
 	/*
-	 * We might allocate quite a lot of storage during planning (due to
-	 * constructing lots of Paths), but all of it can be reclaimed after
-	 * we generate the finished Plan tree.  Work in a temporary context
-	 * to let that happen.  We make the context a child of
-	 * TransactionCommandContext so it will be freed if error abort.
-	 *
-	 * Note: beware of trying to move this up to the start of this routine.
-	 * Some of the data structures built above --- notably the pathkey
-	 * equivalence sets --- will still be needed after this routine exits.
-	 */
-	mycontext = AllocSetContextCreate(TransactionCommandContext,
-									  "Planner",
-									  ALLOCSET_DEFAULT_MINSIZE,
-									  ALLOCSET_DEFAULT_INITSIZE,
-									  ALLOCSET_DEFAULT_MAXSIZE);
-	oldcxt = MemoryContextSwitchTo(mycontext);
-
-	/*
 	 * Ready to do the primary planning.
 	 */
 	final_rel = make_one_rel(root);
@@ -355,25 +335,5 @@ subplanner(Query *root,
 
 plan_built:
 
-	/*
-	 * Must copy the completed plan tree and its pathkeys out of temporary
-	 * context.  We also have to copy the rtable in case it contains any
-	 * subqueries.  (If it does, they'll have been modified during the
-	 * recursive invocation of planner.c, and hence will contain substructure
-	 * allocated in my temporary context...)
-	 */
-	MemoryContextSwitchTo(oldcxt);
-
-	resultplan = copyObject(resultplan);
-
-	root->query_pathkeys = copyObject(root->query_pathkeys);
-
-	root->rtable = copyObject(root->rtable);
-
-	/*
-	 * Now we can release the Path storage.
-	 */
-	MemoryContextDelete(mycontext);
-
 	return resultplan;
 }
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 937628121b3..d73ca9a34ac 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.91 2000/09/29 18:21:33 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.92 2000/10/05 19:11:29 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -48,7 +48,6 @@ static List *make_subplanTargetList(Query *parse, List *tlist,
 static Plan *make_groupplan(List *group_tlist, bool tuplePerGroup,
 			   List *groupClause, AttrNumber *grpColIdx,
 			   bool is_presorted, Plan *subplan);
-static Plan *make_sortplan(List *tlist, Plan *plannode, List *sortcls);
 
 /*****************************************************************************
  *
@@ -60,43 +59,32 @@ planner(Query *parse)
 {
 	Plan	   *result_plan;
 	Index		save_PlannerQueryLevel;
-	List	   *save_PlannerInitPlan;
 	List	   *save_PlannerParamVar;
-	int			save_PlannerPlanId;
 
 	/*
-	 * The outer planner can be called recursively, for example to process
-	 * a subquery in the rangetable.  (A less obvious example occurs when
-	 * eval_const_expressions tries to simplify an SQL function.)
-	 * So, global state variables must be saved and restored.
+	 * The planner can be called recursively (an example is when
+	 * eval_const_expressions tries to simplify an SQL function).
+	 * So, these global state variables must be saved and restored.
 	 *
-	 * (Perhaps these should be moved into the Query structure instead?)
+	 * These vars cannot be moved into the Query structure since their
+	 * whole purpose is communication across multiple sub-Queries.
+	 *
+	 * Note we do NOT save and restore PlannerPlanId: it exists to assign
+	 * unique IDs to SubPlan nodes, and we want those IDs to be unique
+	 * for the life of a backend.  Also, PlannerInitPlan is saved/restored
+	 * in subquery_planner, not here.
 	 */
 	save_PlannerQueryLevel = PlannerQueryLevel;
-	save_PlannerInitPlan = PlannerInitPlan;
 	save_PlannerParamVar = PlannerParamVar;
-	save_PlannerPlanId = PlannerPlanId;
 
-	/* Initialize state for subselects */
-	PlannerQueryLevel = 1;
-	PlannerInitPlan = NULL;
-	PlannerParamVar = NULL;
-	PlannerPlanId = 0;
+	/* Initialize state for handling outer-level references and params */
+	PlannerQueryLevel = 0;		/* will be 1 in top-level subquery_planner */
+	PlannerParamVar = NIL;
 
-	/* this should go away sometime soon */
-	transformKeySetQuery(parse);
-
-	/* primary planning entry point (may recurse for sublinks) */
+	/* primary planning entry point (may recurse for subqueries) */
 	result_plan = subquery_planner(parse, -1.0 /* default case */ );
 
-	Assert(PlannerQueryLevel == 1);
-
-	/* if top-level query had subqueries, do housekeeping for them */
-	if (PlannerPlanId > 0)
-	{
-		(void) SS_finalize_plan(result_plan);
-		result_plan->initPlan = PlannerInitPlan;
-	}
+	Assert(PlannerQueryLevel == 0);
 
 	/* executor wants to know total number of Params used overall */
 	result_plan->nParamExec = length(PlannerParamVar);
@@ -106,9 +94,7 @@ planner(Query *parse)
 
 	/* restore state for outer planner, if any */
 	PlannerQueryLevel = save_PlannerQueryLevel;
-	PlannerInitPlan = save_PlannerInitPlan;
 	PlannerParamVar = save_PlannerParamVar;
-	PlannerPlanId = save_PlannerPlanId;
 
 	return result_plan;
 }
@@ -125,14 +111,9 @@ planner(Query *parse)
  *
  * Basically, this routine does the stuff that should only be done once
  * per Query object.  It then calls union_planner, which may be called
- * recursively on the same Query node in order to handle UNIONs and/or
- * inheritance.  subquery_planner is called recursively from subselect.c
- * to handle sub-Query nodes found within the query's expressions.
- *
- * prepunion.c uses an unholy combination of calling union_planner when
- * recursing on the primary Query node, or subquery_planner when recursing
- * on a UNION'd Query node that hasn't previously been seen by
- * subquery_planner.  That whole chunk of code needs rewritten from scratch.
+ * recursively on the same Query node in order to handle inheritance.
+ * subquery_planner will be called recursively to handle sub-Query nodes
+ * found within the query's expressions and rangetable.
  *
  * Returns a query plan.
  *--------------------
@@ -140,6 +121,20 @@ planner(Query *parse)
 Plan *
 subquery_planner(Query *parse, double tuple_fraction)
 {
+	List	   *saved_initplan = PlannerInitPlan;
+	int			saved_planid = PlannerPlanId;
+	Plan	   *plan;
+	List	   *lst;
+
+	/* Set up for a new level of subquery */
+	PlannerQueryLevel++;
+	PlannerInitPlan = NIL;
+
+#ifdef ENABLE_KEY_SET_QUERY
+	/* this should go away sometime soon */
+	transformKeySetQuery(parse);
+#endif
+
 	/*
 	 * Check to see if any subqueries in the rangetable can be merged into
 	 * this query.
@@ -179,9 +174,9 @@ subquery_planner(Query *parse, double tuple_fraction)
 											  EXPRKIND_HAVING);
 
 	/*
-	 * Do the main planning (potentially recursive)
+	 * Do the main planning (potentially recursive for inheritance)
 	 */
-	return union_planner(parse, tuple_fraction);
+	plan = union_planner(parse, tuple_fraction);
 
 	/*
 	 * XXX should any more of union_planner's activity be moved here?
@@ -190,6 +185,35 @@ subquery_planner(Query *parse, double tuple_fraction)
 	 * but I suspect it would pay off in simplicity and avoidance of
 	 * wasted cycles.
 	 */
+
+	/*
+	 * If any subplans were generated, or if we're inside a subplan,
+	 * build subPlan, extParam and locParam lists for plan nodes.
+	 */
+	if (PlannerPlanId != saved_planid || PlannerQueryLevel > 1)
+	{
+		(void) SS_finalize_plan(plan);
+		/*
+		 * At the moment, SS_finalize_plan doesn't handle initPlans
+		 * and so we assign them to the topmost plan node.
+		 */
+		plan->initPlan = PlannerInitPlan;
+		/* Must add the initPlans' extParams to the topmost node's, too */
+		foreach(lst, plan->initPlan)
+		{
+			SubPlan *subplan = (SubPlan *) lfirst(lst);
+
+			plan->extParam = set_unioni(plan->extParam,
+										subplan->plan->extParam);
+		}
+	}
+
+	/* Return to outer subquery context */
+	PlannerQueryLevel--;
+	PlannerInitPlan = saved_initplan;
+	/* we do NOT restore PlannerPlanId; that's not an oversight! */
+
+	return plan;
 }
 
 /*
@@ -320,9 +344,10 @@ is_simple_subquery(Query *subquery)
 	if (subquery->limitOffset || subquery->limitCount)
 		elog(ERROR, "LIMIT is not supported in subselects");
 	/*
-	 * Can't currently pull up a union query.  Maybe after querytree redesign.
+	 * Can't currently pull up a query with setops.
+	 * Maybe after querytree redesign...
 	 */
-	if (subquery->unionClause)
+	if (subquery->setOperations)
 		return false;
 	/*
 	 * Can't pull up a subquery involving grouping, aggregation, or sorting.
@@ -573,7 +598,7 @@ preprocess_qual_conditions(Query *parse, Node *jtnode)
 
 /*--------------------
  * union_planner
- *	  Invokes the planner on union-type queries (both regular UNIONs and
+ *	  Invokes the planner on union-type queries (both set operations and
  *	  appends produced by inheritance), recursing if necessary to get them
  *	  all, then processes normal plans.
  *
@@ -606,24 +631,31 @@ union_planner(Query *parse,
 	Index		rt_index;
 	List	   *inheritors;
 
-	if (parse->unionClause)
+	if (parse->setOperations)
 	{
-		result_plan = plan_union_queries(parse);
-		/* XXX do we need to do this? bjm 12/19/97 */
-		tlist = preprocess_targetlist(tlist,
-									  parse->commandType,
-									  parse->resultRelation,
-									  parse->rtable);
+		/*
+		 * Construct the plan for set operations.  The result will
+		 * not need any work except perhaps a top-level sort.
+		 */
+		result_plan = plan_set_operations(parse);
+
+		/*
+		 * We should not need to call preprocess_targetlist, since we must
+		 * be in a SELECT query node.
+		 */
+		Assert(parse->commandType == CMD_SELECT);
 
 		/*
 		 * We leave current_pathkeys NIL indicating we do not know sort
-		 * order.  This is correct for the appended-together subplan
-		 * results, even if the subplans themselves produced sorted results.
+		 * order.  This is correct when the top set operation is UNION ALL,
+		 * since the appended-together results are unsorted even if the
+		 * subplans were sorted.  For other set operations we could be
+		 * smarter --- future improvement!
 		 */
 
 		/*
 		 * Calculate pathkeys that represent grouping/ordering
-		 * requirements
+		 * requirements (grouping should always be null, but...)
 		 */
 		group_pathkeys = make_pathkeys_for_sortclauses(parse->groupClause,
 													   tlist);
@@ -886,7 +918,7 @@ union_planner(Query *parse,
 				tuple_fraction = 0.25;
 		}
 
-		/* Generate the (sub) plan */
+		/* Generate the basic plan for this Query */
 		result_plan = query_planner(parse,
 									sub_tlist,
 									tuple_fraction);
@@ -1176,7 +1208,7 @@ make_groupplan(List *group_tlist,
  * make_sortplan
  *	  Add a Sort node to implement an explicit ORDER BY clause.
  */
-static Plan *
+Plan *
 make_sortplan(List *tlist, Plan *plannode, List *sortcls)
 {
 	List	   *sort_tlist;
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index ad1b47aaeb6..14c9dad3ef3 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/setrefs.c,v 1.66 2000/09/29 18:21:33 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/setrefs.c,v 1.67 2000/10/05 19:11:29 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -103,9 +103,15 @@ set_plan_references(Plan *plan)
 			fix_expr_references(plan, (Node *) plan->qual);
 			break;
 		case T_SubqueryScan:
+			/*
+			 * We do not do set_uppernode_references() here, because
+			 * a SubqueryScan will always have been created with correct
+			 * references to its subplan's outputs to begin with.
+			 */
 			fix_expr_references(plan, (Node *) plan->targetlist);
 			fix_expr_references(plan, (Node *) plan->qual);
-			/* No need to recurse into the subplan, it's fixed already */
+			/* Recurse into subplan too */
+			set_plan_references(((SubqueryScan *) plan)->subplan);
 			break;
 		case T_NestLoop:
 			set_join_references((Join *) plan);
@@ -132,6 +138,7 @@ set_plan_references(Plan *plan)
 		case T_Material:
 		case T_Sort:
 		case T_Unique:
+		case T_SetOp:
 		case T_Hash:
 
 			/*
@@ -170,6 +177,7 @@ set_plan_references(Plan *plan)
 			 * Append, like Sort et al, doesn't actually evaluate its
 			 * targetlist or quals, and we haven't bothered to give it
 			 * its own tlist copy.  So, don't fix targetlist/qual.
+			 * But do recurse into subplans.
 			 */
 			foreach(pl, ((Append *) plan)->appendplans)
 				set_plan_references((Plan *) lfirst(pl));
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 182d1384aa1..03e38371df5 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.42 2000/09/29 18:21:33 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.43 2000/10/05 19:11:29 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -29,7 +29,8 @@
 Index		PlannerQueryLevel;	/* level of current query */
 List	   *PlannerInitPlan;	/* init subplans for current query */
 List	   *PlannerParamVar;	/* to get Var from Param->paramid */
-int			PlannerPlanId;		/* to assign unique ID to subquery plans */
+
+int			PlannerPlanId = 0;	/* to assign unique ID to subquery plans */
 
 /*--------------------
  * PlannerParamVar is a list of Var nodes, wherein the n'th entry
@@ -81,7 +82,7 @@ replace_var(Var *var)
 
 	/*
 	 * If there's already a PlannerParamVar entry for this same Var, just
-	 * use it.	NOTE: in situations involving UNION or inheritance, it is
+	 * use it.	NOTE: in sufficiently complex querytrees, it is
 	 * possible for the same varno/varlevel to refer to different RTEs in
 	 * different parts of the parsetree, so that different fields might
 	 * end up sharing the same Param number.  As long as we check the
@@ -128,11 +129,6 @@ make_subplan(SubLink *slink)
 	Plan	   *plan;
 	List	   *lst;
 	Node	   *result;
-	List	   *saved_ip = PlannerInitPlan;
-
-	PlannerInitPlan = NULL;
-
-	PlannerQueryLevel++;		/* we become child */
 
 	/*
 	 * Check to see if this node was already processed; if so we have
@@ -181,45 +177,30 @@ make_subplan(SubLink *slink)
 	else
 		tuple_fraction = -1.0;	/* default behavior */
 
-	node->plan = plan = subquery_planner(subquery, tuple_fraction);
-
 	/*
-	 * Assign subPlan, extParam and locParam to plan nodes. At the moment,
-	 * SS_finalize_plan doesn't handle initPlan-s and so we assign them to
-	 * the topmost plan node and take care about its extParam too.
+	 * Generate the plan for the subquery.
 	 */
-	(void) SS_finalize_plan(plan);
-	plan->initPlan = PlannerInitPlan;
-
-	/* Create extParam list as union of InitPlan-s' lists */
-	foreach(lst, PlannerInitPlan)
-	{
-		List	   *lp;
-
-		foreach(lp, ((SubPlan *) lfirst(lst))->plan->extParam)
-		{
-			if (!intMember(lfirsti(lp), plan->extParam))
-				plan->extParam = lappendi(plan->extParam, lfirsti(lp));
-		}
-	}
+	node->plan = plan = subquery_planner(subquery, tuple_fraction);
 
-	/* and now we are parent again */
-	PlannerInitPlan = saved_ip;
-	PlannerQueryLevel--;
+	node->plan_id = PlannerPlanId++; /* Assign unique ID to this SubPlan */
 
-	node->plan_id = PlannerPlanId++;
 	node->rtable = subquery->rtable;
 	node->sublink = slink;
+
 	slink->subselect = NULL;	/* cool ?! see error check above! */
 
-	/* make parParam list of params coming from current query level */
+	/*
+	 * Make parParam list of params that current query level will pass
+	 * to this child plan.
+	 */
 	foreach(lst, plan->extParam)
 	{
-		Var		   *var = nth(lfirsti(lst), PlannerParamVar);
+		int			paramid = lfirsti(lst);
+		Var		   *var = nth(paramid, PlannerParamVar);
 
 		/* note varlevelsup is absolute level number */
 		if (var->varlevelsup == PlannerQueryLevel)
-			node->parParam = lappendi(node->parParam, lfirsti(lst));
+			node->parParam = lappendi(node->parParam, paramid);
 	}
 
 	/*
@@ -625,6 +606,11 @@ SS_finalize_plan(Plan *plan)
 								 SS_finalize_plan((Plan *) lfirst(lst)));
 			break;
 
+		case T_SubqueryScan:
+			results.paramids = set_unioni(results.paramids,
+						SS_finalize_plan(((SubqueryScan *) plan)->subplan));
+			break;
+
 		case T_IndexScan:
 			finalize_primnode((Node *) ((IndexScan *) plan)->indxqual,
 							  &results);
@@ -667,10 +653,10 @@ SS_finalize_plan(Plan *plan)
 
 		case T_Agg:
 		case T_SeqScan:
-		case T_SubqueryScan:
 		case T_Material:
 		case T_Sort:
 		case T_Unique:
+		case T_SetOp:
 		case T_Group:
 			break;
 
@@ -689,17 +675,18 @@ SS_finalize_plan(Plan *plan)
 
 	foreach(lst, results.paramids)
 	{
-		Var		   *var = nth(lfirsti(lst), PlannerParamVar);
+		int			paramid = lfirsti(lst);
+		Var		   *var = nth(paramid, PlannerParamVar);
 
 		/* note varlevelsup is absolute level number */
 		if (var->varlevelsup < PlannerQueryLevel)
-			extParam = lappendi(extParam, lfirsti(lst));
+			extParam = lappendi(extParam, paramid);
 		else if (var->varlevelsup > PlannerQueryLevel)
 			elog(ERROR, "SS_finalize_plan: plan shouldn't reference subplan's variable");
 		else
 		{
 			Assert(var->varno == 0 && var->varattno == 0);
-			locParam = lappendi(locParam, lfirsti(lst));
+			locParam = lappendi(locParam, paramid);
 		}
 	}
 
diff --git a/src/backend/optimizer/prep/prepkeyset.c b/src/backend/optimizer/prep/prepkeyset.c
index 60166289a59..764697636c7 100644
--- a/src/backend/optimizer/prep/prepkeyset.c
+++ b/src/backend/optimizer/prep/prepkeyset.c
@@ -20,6 +20,8 @@
 
 bool		_use_keyset_query_optimizer = FALSE;
 
+#ifdef ENABLE_KEY_SET_QUERY
+
 static int	inspectOpNode(Expr *expr);
 static int	inspectAndNode(Expr *expr);
 static int	inspectOrNode(Expr *expr);
@@ -213,3 +215,5 @@ inspectOpNode(Expr *expr)
 	secondExpr = lsecond(expr->args);
 	return (firstExpr && secondExpr && nodeTag(firstExpr) == T_Var && nodeTag(secondExpr) == T_Const);
 }
+
+#endif /* ENABLE_KEY_SET_QUERY */
diff --git a/src/backend/optimizer/prep/preptlist.c b/src/backend/optimizer/prep/preptlist.c
index e3b9803d0ab..822c0c79f05 100644
--- a/src/backend/optimizer/prep/preptlist.c
+++ b/src/backend/optimizer/prep/preptlist.c
@@ -15,7 +15,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/prep/preptlist.c,v 1.38 2000/08/08 15:41:48 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/prep/preptlist.c,v 1.39 2000/10/05 19:11:30 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -49,6 +49,17 @@ preprocess_targetlist(List *tlist,
 					  Index result_relation,
 					  List *range_table)
 {
+	/*
+	 * Sanity check: if there is a result relation, it'd better be a
+	 * real relation not a subquery.  Else parser or rewriter messed up.
+	 */
+	if (result_relation)
+	{
+		RangeTblEntry *rte = rt_fetch(result_relation, range_table);
+
+		if (rte->subquery != NULL || rte->relid == InvalidOid)
+			elog(ERROR, "preprocess_targetlist: subquery cannot be result relation");
+	}
 
 	/*
 	 * for heap_formtuple to work, the targetlist must match the exact
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index d3df8863270..0c91631563d 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -1,27 +1,32 @@
 /*-------------------------------------------------------------------------
  *
  * prepunion.c
- *	  Routines to plan inheritance, union, and version queries
+ *	  Routines to plan set-operation and inheritance queries.  The filename
+ *	  is a leftover from a time when only UNIONs were handled.
  *
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.53 2000/09/29 18:21:34 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.54 2000/10/05 19:11:30 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
-#include <sys/types.h>
-
 #include "postgres.h"
 
+#include <sys/types.h>
+
+#include "catalog/pg_type.h"
+#include "nodes/makefuncs.h"
 #include "optimizer/clauses.h"
 #include "optimizer/plancat.h"
+#include "optimizer/planmain.h"
 #include "optimizer/planner.h"
 #include "optimizer/prep.h"
 #include "optimizer/tlist.h"
 #include "parser/parse_clause.h"
+#include "parser/parse_coerce.h"
 #include "parser/parsetree.h"
 #include "utils/lsyscache.h"
 
@@ -33,221 +38,398 @@ typedef struct
 	Oid			new_relid;
 } fix_parsetree_attnums_context;
 
+static Plan *recurse_set_operations(Node *setOp, Query *parse,
+									List *colTypes, int flag,
+									List *refnames_tlist);
+static Plan *generate_union_plan(SetOperationStmt *op, Query *parse,
+								 List *refnames_tlist);
+static Plan *generate_nonunion_plan(SetOperationStmt *op, Query *parse,
+									List *refnames_tlist);
+static List *recurse_union_children(Node *setOp, Query *parse,
+									SetOperationStmt *top_union,
+									List *refnames_tlist);
+static List *generate_setop_tlist(List *colTypes, int flag,
+								  List *input_tlist,
+								  List *refnames_tlist);
+static bool tlist_same_datatypes(List *tlist, List *colTypes);
 static void fix_parsetree_attnums(Index rt_index, Oid old_relid,
 					  Oid new_relid, Query *parsetree);
 static bool fix_parsetree_attnums_walker(Node *node,
 							 fix_parsetree_attnums_context *context);
 static RangeTblEntry *new_rangetable_entry(Oid new_relid,
 					 RangeTblEntry *old_entry);
-static Append *make_append(List *appendplans, List *unionrtables,
-			Index rt_index,
-			List *inheritrtable, List *tlist);
+static Append *make_append(List *appendplans, Index rt_index,
+						   List *inheritrtable, List *tlist);
 
 
 /*
- * plan_union_queries
+ * plan_set_operations
  *
- *	  Plans the queries for a given UNION.
+ *	  Plans the queries for a tree of set operations (UNION/INTERSECT/EXCEPT)
  *
- * Returns an Append plan that combines the results of the unioned queries.
- * Note that Append output is correct for UNION ALL, but caller still needs
- * to take care of sort/unique processing if it's a plain UNION.  We set or
- * clear the Query's fields so that the right things will happen back in
- * union_planner.  (This control structure is an unholy mess...)
+ * This routine only deals with the setOperations tree of the given query.
+ * Any top-level ORDER BY requested in parse->sortClause will be added on
+ * back in union_planner.
  */
 Plan *
-plan_union_queries(Query *parse)
+plan_set_operations(Query *parse)
 {
-	List	   *union_plans = NIL,
-			   *ulist,
-			   *union_all_queries,
-			   *union_rts,
-			   *last_union = NIL,
-			   *hold_sortClause = parse->sortClause;
-	bool		union_all_found = false,
-				union_found = false,
-				last_union_all_flag = false;
-
-	/*------------------------------------------------------------------
-	 *
-	 * Do we need to split up our unions because we have UNION and UNION
-	 * ALL?
-	 *
-	 * We are checking for the case of: SELECT 1 UNION SELECT 2 UNION SELECT
-	 * 3 UNION ALL SELECT 4 UNION ALL SELECT 5
-	 *
-	 * where we have to do a DISTINCT on the output of the first three
-	 * queries, then add the rest.	If they have used UNION and UNION ALL,
-	 * we grab all queries up to the last UNION query, make them their own
-	 * UNION with the owner as the first query in the list.  Then, we take
-	 * the remaining queries, which is UNION ALL, and add them to the list
-	 * of union queries.
-	 *
-	 * So the above query becomes:
-	 *
-	 *	Append Node
-	 *	{
-	 *		Sort and Unique
-	 *		{
-	 *			Append Node
-	 *			{
-	 *				SELECT 1		This is really a sub-UNION.
-	 *				unionClause		We run a DISTINCT on these.
-	 *				{
-	 *					SELECT 2
-	 *					SELECT 3
-	 *				}
-	 *			}
-	 *		}
-	 *		SELECT 4
-	 *		SELECT 5
-	 *	}
-	 *
-	 *---------------------------------------------------------------------
+	SetOperationStmt *topop = (SetOperationStmt *) parse->setOperations;
+	Node	   *node;
+	Query	   *leftmostQuery;
+
+	Assert(topop && IsA(topop, SetOperationStmt));
+
+	/*
+	 * 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));
+	leftmostQuery = rt_fetch(((RangeTblRef *) node)->rtindex,
+							 parse->rtable)->subquery;
+	Assert(leftmostQuery != NULL);
 
-	foreach(ulist, parse->unionClause)
+	/*
+	 * Recurse on setOperations tree to generate plans for set ops.
+	 * The final output plan should have just the column types shown
+	 * as the output from the top-level node.
+	 */
+	return recurse_set_operations((Node *) topop, parse,
+								  topop->colTypes, -1,
+								  leftmostQuery->targetList);
+}
+
+/*
+ * recurse_set_operations
+ *	  Recursively handle one step in a tree of set operations
+ *
+ * colTypes: integer list of type OIDs of expected output columns
+ * flag: if >= 0, add a resjunk output column indicating value of flag
+ * refnames_tlist: targetlist to take column names from
+ */
+static Plan *
+recurse_set_operations(Node *setOp, Query *parse,
+					   List *colTypes, int flag,
+					   List *refnames_tlist)
+{
+	if (IsA(setOp, RangeTblRef))
 	{
-		Query	   *union_query = lfirst(ulist);
+		RangeTblRef *rtr = (RangeTblRef *) setOp;
+		RangeTblEntry *rte = rt_fetch(rtr->rtindex, parse->rtable);
+		Query  *subquery = rte->subquery;
+		Plan   *subplan,
+			   *plan;
 
-		if (union_query->unionall)
-			union_all_found = true;
-		else
-		{
-			union_found = true;
-			last_union = ulist;
-		}
-		last_union_all_flag = union_query->unionall;
+		Assert(subquery != NULL);
+		/*
+		 * Generate plan for primitive subquery
+		 */
+		subplan = subquery_planner(subquery,
+								   -1.0 /* default case */ );
+		/*
+		 * Add a SubqueryScan with the caller-requested targetlist
+		 */
+		plan = (Plan *)
+			make_subqueryscan(generate_setop_tlist(colTypes, flag,
+												   subplan->targetlist,
+												   refnames_tlist),
+							  NIL,
+							  rtr->rtindex,
+							  subplan);
+		copy_plan_costsize(plan, subplan);
+		return plan;
 	}
-
-	/* Is this a simple one */
-	if (!union_all_found ||
-		!union_found ||
-	/* A trailing UNION negates the effect of earlier UNION ALLs */
-		!last_union_all_flag)
+	else if (IsA(setOp, SetOperationStmt))
 	{
-		List	   *hold_unionClause = parse->unionClause;
-		double		tuple_fraction = -1.0;		/* default processing */
-
-		/* we will do sorting later, so don't do it now */
-		if (!union_all_found ||
-			!last_union_all_flag)
-		{
-			parse->sortClause = NIL;
-			parse->distinctClause = NIL;
-
-			/*
-			 * force lower-level planning to assume that all tuples will
-			 * be retrieved, even if it sees a LIMIT in the query node.
-			 */
-			tuple_fraction = 0.0;
-		}
-
-		parse->unionClause = NIL;		/* prevent recursion */
-		union_plans = lcons(union_planner(parse, tuple_fraction), NIL);
-		union_rts = lcons(parse->rtable, NIL);
+		SetOperationStmt *op = (SetOperationStmt *) setOp;
+		Plan   *plan;
 
-		foreach(ulist, hold_unionClause)
+		/* UNIONs are much different from INTERSECT/EXCEPT */
+		if (op->op == SETOP_UNION)
+			plan = generate_union_plan(op, parse, refnames_tlist);
+		else
+			plan = generate_nonunion_plan(op, parse, refnames_tlist);
+		/*
+		 * 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
+		 * replace_vars_with_subplan_refs() to the Result node's tlist.
+		 * This would fail if the input plan's non-resjunk tlist entries were
+		 * not all simple Vars equal() to the referencing Vars generated by
+		 * generate_setop_tlist().  However, since the input plan was
+		 * generated by generate_union_plan() or generate_nonunion_plan(),
+		 * the referencing Vars will equal the tlist entries they reference.
+		 * Ugly but I don't feel like making that code more general right now.
+		 */
+		if (flag >= 0 || ! tlist_same_datatypes(plan->targetlist, colTypes))
 		{
-			Query	   *union_query = lfirst(ulist);
-
-			/*
-			 * use subquery_planner here because the union'd queries have
-			 * not been preprocessed yet.  My goodness this is messy...
-			 */
-			union_plans = lappend(union_plans,
-								  subquery_planner(union_query,
-												   tuple_fraction));
-			union_rts = lappend(union_rts, union_query->rtable);
+			plan = (Plan *)
+				make_result(generate_setop_tlist(colTypes, flag,
+												 plan->targetlist,
+												 refnames_tlist),
+							NULL,
+							plan);
 		}
+		return plan;
 	}
 	else
 	{
+		elog(ERROR, "recurse_set_operations: unexpected node %d",
+			 (int) nodeTag(setOp));
+		return NULL;			/* keep compiler quiet */
+	}
+}
 
-		/*
-		 * We have mixed unions and non-unions
-		 *
-		 * We need to restructure this to put the UNIONs on their own so we
-		 * can do a DISTINCT.
-		 */
+/*
+ * Generate plan for a UNION or UNION ALL node
+ */
+static Plan *
+generate_union_plan(SetOperationStmt *op, Query *parse,
+					List *refnames_tlist)
+{
+	List   *planlist;
+	Plan   *plan;
+
+	/*
+	 * 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 Sort for the lot.  Recurse to find
+	 * such nodes and compute their children's plans.
+	 */
+	planlist = nconc(recurse_union_children(op->larg, parse,
+											op, refnames_tlist),
+					 recurse_union_children(op->rarg, parse,
+											op, refnames_tlist));
+	/*
+	 * Append the child results together.
+	 *
+	 * 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.
+	 */
+	plan = (Plan *)
+		make_append(planlist,
+					0,
+					NIL,
+					generate_setop_tlist(op->colTypes, -1,
+									((Plan *) lfirst(planlist))->targetlist,
+									refnames_tlist));
+	/*
+	 * For UNION ALL, we just need the Append plan.  For UNION,
+	 * need to add Sort and Unique nodes to produce unique output.
+	 */
+	if (! op->all)
+	{
+		List   *tlist,
+			   *sortList;
 
-		/* save off everthing past the last UNION */
-		union_all_queries = lnext(last_union);
+		tlist = new_unsorted_tlist(plan->targetlist);
+		sortList = addAllTargetsToSortList(NIL, tlist);
+		plan = make_sortplan(tlist, plan, sortList);
+		plan = (Plan *) make_unique(tlist, plan, copyObject(sortList));
+	}
+	return plan;
+}
 
-		/* clip off the list to remove the trailing UNION ALLs */
-		lnext(last_union) = NIL;
+/*
+ * Generate plan for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
+ */
+static Plan *
+generate_nonunion_plan(SetOperationStmt *op, Query *parse,
+					   List *refnames_tlist)
+{
+	Plan   *lplan,
+		   *rplan,
+		   *plan;
+	List   *tlist,
+		   *sortList;
+	SetOpCmd cmd;
+
+	/* Recurse on children, ensuring their outputs are marked */
+	lplan = recurse_set_operations(op->larg, parse,
+								   op->colTypes, 0,
+								   refnames_tlist);
+	rplan = recurse_set_operations(op->rarg, parse,
+								   op->colTypes, 1,
+								   refnames_tlist);
+	/*
+	 * Append the child results together.
+	 *
+	 * 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.
+	 */
+	plan = (Plan *)
+		make_append(makeList2(lplan, rplan),
+					0,
+					NIL,
+					generate_setop_tlist(op->colTypes, 0,
+										 lplan->targetlist,
+										 refnames_tlist));
+	/*
+	 * Sort the child results, then add a SetOp plan node to
+	 * generate the correct output.
+	 */
+	tlist = new_unsorted_tlist(plan->targetlist);
+	sortList = addAllTargetsToSortList(NIL, tlist);
+	plan = make_sortplan(tlist, plan, sortList);
+	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, "generate_nonunion_plan: bogus operation code");
+			cmd = SETOPCMD_INTERSECT; /* keep compiler quiet */
+			break;
+	}
+	plan = (Plan *) make_setop(cmd, tlist, plan, sortList,
+							   length(op->colTypes)+1);
+	return plan;
+}
 
-		/*
-		 * Recursion, but UNION only. The last one is a UNION, so it will
-		 * not come here in recursion.
-		 *
-		 * XXX is it OK to pass default -1 to union_planner in this path, or
-		 * should we force a tuple_fraction value?
-		 */
-		union_plans = lcons(union_planner(parse, -1.0), NIL);
-		union_rts = lcons(parse->rtable, NIL);
+/*
+ * 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.
+ */
+static List *
+recurse_union_children(Node *setOp, Query *parse,
+					   SetOperationStmt *top_union,
+					   List *refnames_tlist)
+{
+	if (IsA(setOp, SetOperationStmt))
+	{
+		SetOperationStmt *op = (SetOperationStmt *) setOp;
 
-		/* Append the remaining UNION ALLs */
-		foreach(ulist, union_all_queries)
+		if (op->op == top_union->op &&
+			(op->all == top_union->all || op->all) &&
+			equali(op->colTypes, top_union->colTypes))
 		{
-			Query	   *union_all_query = lfirst(ulist);
-
-			/*
-			 * use subquery_planner here because the union'd queries have
-			 * not been preprocessed yet.  My goodness this is messy...
-			 */
-			union_plans = lappend(union_plans,
-								subquery_planner(union_all_query, -1.0));
-			union_rts = lappend(union_rts, union_all_query->rtable);
+			/* Same UNION, so fold children into parent's subplan list */
+			return nconc(recurse_union_children(op->larg, parse,
+												top_union, refnames_tlist),
+						 recurse_union_children(op->rarg, parse,
+												top_union, refnames_tlist));
 		}
 	}
+	/* Not same, so plan this child separately */
+	return makeList1(recurse_set_operations(setOp, parse,
+											top_union->colTypes, -1,
+											refnames_tlist));
+}
 
-	/* We have already split UNION and UNION ALL and we made it consistent */
-	if (!last_union_all_flag)
-	{
+/*
+ * Generate targetlist for a set-operation plan node
+ */
+static List *
+generate_setop_tlist(List *colTypes, int flag,
+					 List *input_tlist,
+					 List *refnames_tlist)
+{
+	List	   *tlist = NIL;
+	int			resno = 1;
+	List	   *i;
+	Resdom	   *resdom;
+	Node	   *expr;
 
+	foreach(i, colTypes)
+	{
+		Oid		colType = (Oid) lfirsti(i);
+		TargetEntry *inputtle = (TargetEntry *) lfirst(input_tlist);
+		TargetEntry *reftle = (TargetEntry *) lfirst(refnames_tlist);
+
+		Assert(inputtle->resdom->resno == resno);
+		Assert(reftle->resdom->resno == resno);
+		Assert(!inputtle->resdom->resjunk);
+		Assert(!reftle->resdom->resjunk);
 		/*
-		 * Need SELECT DISTINCT behavior to implement UNION. Put back the
-		 * held sortClause, add any missing columns to the sort clause,
-		 * and set distinctClause properly.
+		 * 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.
 		 */
-		List	   *slitem;
-
-		parse->sortClause = addAllTargetsToSortList(hold_sortClause,
-													parse->targetList);
-		parse->distinctClause = NIL;
-		foreach(slitem, parse->sortClause)
-		{
-			SortClause *scl = (SortClause *) lfirst(slitem);
-			TargetEntry *tle = get_sortgroupclause_tle(scl, parse->targetList);
-
-			if (!tle->resdom->resjunk)
-				parse->distinctClause = lappend(parse->distinctClause,
-												copyObject(scl));
-		}
+		resdom = makeResdom((AttrNumber) resno++,
+							colType,
+							-1,
+							pstrdup(reftle->resdom->resname),
+							false);
+		if (inputtle->expr && IsA(inputtle->expr, Const))
+			expr = inputtle->expr;
+		else
+			expr = (Node *) makeVar(0,
+									inputtle->resdom->resno,
+									inputtle->resdom->restype,
+									inputtle->resdom->restypmod,
+									0);
+		expr = coerce_to_common_type(NULL,
+									 expr,
+									 colType,
+									 "UNION/INTERSECT/EXCEPT");
+		tlist = lappend(tlist, makeTargetEntry(resdom, expr));
+		input_tlist = lnext(input_tlist);
+		refnames_tlist = lnext(refnames_tlist);
 	}
-	else
+
+	if (flag >= 0)
 	{
-		/* needed so we don't take SELECT DISTINCT from the first query */
-		parse->distinctClause = NIL;
+		/* Add a resjunk column yielding specified flag value */
+		resdom = makeResdom((AttrNumber) resno++,
+							INT4OID,
+							-1,
+							pstrdup("flag"),
+							true);
+		expr = (Node *) makeConst(INT4OID,
+								  sizeof(int4),
+								  Int32GetDatum(flag),
+								  false,
+								  true,
+								  false,
+								  false);
+		tlist = lappend(tlist, makeTargetEntry(resdom, expr));
 	}
 
-	/*
-	 * Make sure we don't try to apply the first query's grouping stuff to
-	 * the Append node, either.  Basically we don't want union_planner to
-	 * do anything when we return control, except add the top sort/unique
-	 * nodes for DISTINCT processing if this wasn't UNION ALL, or the top
-	 * sort node if it was UNION ALL with a user-provided sort clause.
-	 */
-	parse->groupClause = NULL;
-	parse->havingQual = NULL;
-	parse->hasAggs = false;
+	return tlist;
+}
 
-	return (Plan *) make_append(union_plans,
-								union_rts,
-								0,
-								NIL,
-								parse->targetList);
+/*
+ * Does tlist have same datatypes as requested colTypes?
+ *
+ * Resjunk columns are ignored.
+ */
+static bool
+tlist_same_datatypes(List *tlist, List *colTypes)
+{
+	List	   *i;
+
+	foreach(i, tlist)
+	{
+		TargetEntry *tle = (TargetEntry *) lfirst(i);
+
+		if (!tle->resdom->resjunk)
+		{
+			if (colTypes == NIL)
+				return false;
+			if (tle->resdom->restype != (Oid) lfirsti(colTypes))
+				return false;
+			colTypes = lnext(colTypes);
+		}
+	}
+	if (colTypes != NIL)
+		return false;
+	return true;
 }
 
 
@@ -372,7 +554,6 @@ plan_inherit_queries(Query *root, List *tlist,
 
 	/* Construct the finished Append plan. */
 	return (Plan *) make_append(union_plans,
-								NIL,
 								rt_index,
 								union_rtentries,
 								((Plan *) lfirst(union_plans))->targetlist);
@@ -530,7 +711,8 @@ fix_parsetree_attnums(Index rt_index,
 
 	query_tree_walker(parsetree,
 					  fix_parsetree_attnums_walker,
-					  (void *) &context);
+					  (void *) &context,
+					  true);
 }
 
 /*
@@ -570,7 +752,8 @@ fix_parsetree_attnums_walker(Node *node,
 		context->sublevels_up++;
 		result = query_tree_walker((Query *) node,
 								   fix_parsetree_attnums_walker,
-								   (void *) context);
+								   (void *) context,
+								   true);
 		context->sublevels_up--;
 		return result;
 	}
@@ -580,7 +763,6 @@ fix_parsetree_attnums_walker(Node *node,
 
 static Append *
 make_append(List *appendplans,
-			List *unionrtables,
 			Index rt_index,
 			List *inheritrtable,
 			List *tlist)
@@ -589,7 +771,6 @@ make_append(List *appendplans,
 	List	   *subnode;
 
 	node->appendplans = appendplans;
-	node->unionrtables = unionrtables;
 	node->inheritrelid = rt_index;
 	node->inheritrtable = inheritrtable;
 	node->plan.startup_cost = 0;
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 06c67daebfc..f52ec6d2d87 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.76 2000/09/29 18:21:23 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.77 2000/10/05 19:11:32 tgl Exp $
  *
  * HISTORY
  *	  AUTHOR			DATE			MAJOR EVENT
@@ -1636,8 +1636,8 @@ simplify_op_or_func(Expr *expr, List *args)
  * so that a scan of a target list can be handled without additional code.
  * (But only the "expr" part of a TargetEntry is examined, unless the walker
  * chooses to process TargetEntry nodes specially.)  Also, RangeTblRef,
- * FromExpr, and JoinExpr nodes are handled, so that qual expressions in a
- * jointree can be processed without additional code.
+ * FromExpr, JoinExpr, and SetOperationStmt nodes are handled, so that query
+ * jointrees and setOperation trees can be processed without additional code.
  *
  * expression_tree_walker will handle SubLink and SubPlan nodes by recursing
  * normally into the "lefthand" arguments (which belong to the outer plan).
@@ -1654,7 +1654,8 @@ simplify_op_or_func(Expr *expr, List *args)
  *		if (IsA(node, Query))
  *		{
  *			adjust context for subquery;
- *			result = query_tree_walker((Query *) node, my_walker, context);
+ *			result = query_tree_walker((Query *) node, my_walker, context,
+ *									   true); // to visit subquery RTEs too
  *			restore context if needed;
  *			return result;
  *		}
@@ -1827,6 +1828,16 @@ expression_tree_walker(Node *node,
 				 */
 			}
 			break;
+		case T_SetOperationStmt:
+			{
+				SetOperationStmt *setop = (SetOperationStmt *) node;
+
+				if (walker(setop->larg, context))
+					return true;
+				if (walker(setop->rarg, context))
+					return true;
+			}
+			break;
 		default:
 			elog(ERROR, "expression_tree_walker: Unexpected node type %d",
 				 nodeTag(node));
@@ -1843,11 +1854,17 @@ expression_tree_walker(Node *node,
  * for starting a walk at top level of a Query regardless of whether the
  * walker intends to descend into subqueries.  It is also useful for
  * descending into subqueries within a walker.
+ *
+ * If visitQueryRTEs is true, the walker will also be called on sub-Query
+ * nodes present in subquery rangetable entries of the given Query.  This
+ * is optional since some callers handle those sub-queries separately,
+ * or don't really want to see subqueries anyway.
  */
 bool
 query_tree_walker(Query *query,
 				  bool (*walker) (),
-				  void *context)
+				  void *context,
+				  bool visitQueryRTEs)
 {
 	Assert(query != NULL && IsA(query, Query));
 
@@ -1855,11 +1872,23 @@ query_tree_walker(Query *query,
 		return true;
 	if (walker((Node *) query->jointree, context))
 		return true;
+	if (walker(query->setOperations, context))
+		return true;
 	if (walker(query->havingQual, context))
 		return true;
-	/*
-	 * XXX for subselect-in-FROM, may need to examine rtable as well?
-	 */
+	if (visitQueryRTEs)
+	{
+		List   *rt;
+
+		foreach(rt, query->rtable)
+		{
+			RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt);
+
+			if (rte->subquery)
+				if (walker(rte->subquery, context))
+					return true;
+		}
+	}
 	return false;
 }
 
@@ -2158,6 +2187,17 @@ expression_tree_mutator(Node *node,
 				return (Node *) newnode;
 			}
 			break;
+		case T_SetOperationStmt:
+			{
+				SetOperationStmt *setop = (SetOperationStmt *) node;
+				SetOperationStmt *newnode;
+
+				FLATCOPY(newnode, setop, SetOperationStmt);
+				MUTATE(newnode->larg, setop->larg, Node *);
+				MUTATE(newnode->rarg, setop->rarg, Node *);
+				return (Node *) newnode;
+			}
+			break;
 		default:
 			elog(ERROR, "expression_tree_mutator: Unexpected node type %d",
 				 nodeTag(node));
@@ -2166,3 +2206,58 @@ expression_tree_mutator(Node *node,
 	/* can't get here, but keep compiler happy */
 	return NULL;
 }
+
+
+/*
+ * query_tree_mutator --- initiate modification of a Query's expressions
+ *
+ * This routine exists just to reduce the number of places that need to know
+ * where all the expression subtrees of a Query are.  Note it can be used
+ * for starting a walk at top level of a Query regardless of whether the
+ * mutator intends to descend into subqueries.  It is also useful for
+ * descending into subqueries within a mutator.
+ *
+ * The specified Query node is modified-in-place; do a FLATCOPY() beforehand
+ * if you don't want to change the original.  All substructure is safely
+ * copied, however.
+ *
+ * If visitQueryRTEs is true, the mutator will also be called on sub-Query
+ * nodes present in subquery rangetable entries of the given Query.  This
+ * is optional since some callers handle those sub-queries separately,
+ * or don't really want to see subqueries anyway.
+ */
+void
+query_tree_mutator(Query *query,
+				   Node *(*mutator) (),
+				   void *context,
+				   bool visitQueryRTEs)
+{
+	Assert(query != NULL && IsA(query, Query));
+
+	MUTATE(query->targetList, query->targetList, List *);
+	MUTATE(query->jointree, query->jointree, FromExpr *);
+	MUTATE(query->setOperations, query->setOperations, Node *);
+	MUTATE(query->havingQual, query->havingQual, Node *);
+	if (visitQueryRTEs)
+	{
+		List   *newrt = NIL;
+		List   *rt;
+
+		foreach(rt, query->rtable)
+		{
+			RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt);
+
+			if (rte->subquery)
+			{
+				RangeTblEntry *newrte;
+
+				FLATCOPY(newrte, rte, RangeTblEntry);
+				CHECKFLATCOPY(newrte->subquery, rte->subquery, Query);
+				MUTATE(newrte->subquery, newrte->subquery, Query *);
+				rte = newrte;
+			}
+			newrt = lappend(newrt, rte);
+		}
+		query->rtable = newrt;
+	}
+}
diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c
index ec9f9dafd0b..a18db71ec55 100644
--- a/src/backend/optimizer/util/var.c
+++ b/src/backend/optimizer/util/var.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/var.c,v 1.27 2000/09/12 21:06:59 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/var.c,v 1.28 2000/10/05 19:11:32 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -67,7 +67,7 @@ pull_varnos(Node *node)
 	 */
 	if (node && IsA(node, Query))
 		query_tree_walker((Query *) node, pull_varnos_walker,
-						  (void *) &context);
+						  (void *) &context, true);
 	else
 		pull_varnos_walker(node, &context);
 
@@ -108,12 +108,12 @@ pull_varnos_walker(Node *node, pull_varnos_context *context)
 	}
 	if (IsA(node, Query))
 	{
-		/* Recurse into not-yet-planned subquery */
+		/* Recurse into RTE subquery or not-yet-planned sublink subquery */
 		bool		result;
 
 		context->sublevels_up++;
 		result = query_tree_walker((Query *) node, pull_varnos_walker,
-								   (void *) context);
+								   (void *) context, true);
 		context->sublevels_up--;
 		return result;
 	}