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!

1 files changed, 362 insertions, 181 deletions

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;