prepunion.c

PostgreSQL7.4.6 for Linux

/*-------------------------------------------------------------------------
 *
 * prepunion.c
 *	  Routines to plan set-operation queries.  The filename is a leftover
 *	  from a time when only UNIONs were implemented.
 *
 * There is also some code here to support planning of queries that use
 * inheritance (SELECT FROM foo*).	This no longer has much connection
 * to the processing of UNION queries, but it's still here.
 *
 *
 * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.104 2003/08/11 23:04:49 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.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"


typedef struct
{
	Index		old_rt_index;
	Index		new_rt_index;
	Oid			old_relid;
	Oid			new_relid;
} adjust_inherited_attrs_context;

static Plan *recurse_set_operations(Node *setOp, Query *parse,
					   List *colTypes, bool junkOK,
					   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,
					 bool hack_constants,
					 List *input_tlist,
					 List *refnames_tlist);
static List *generate_append_tlist(List *colTypes, bool flag,
					  List *input_plans,
					  List *refnames_tlist);
static bool tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK);
static Node *adjust_inherited_attrs_mutator(Node *node,
							   adjust_inherited_attrs_context *context);
static Relids adjust_relid_set(Relids relids, Index oldrelid, Index newrelid);
static List *adjust_inherited_tlist(List *tlist, Oid old_relid, Oid new_relid);


/*
 * 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 parse->sortClause will be added
 * when we return to grouping_planner.
 */
Plan *
plan_set_operations(Query *parse)
{
	SetOperationStmt *topop = (SetOperationStmt *) parse->setOperations;
	Node	   *node;
	Query	   *leftmostQuery;

	Assert(topop && IsA(topop, SetOperationStmt));

	/* check for unsupported stuff */
	Assert(parse->utilityStmt == NULL);
	Assert(parse->jointree->fromlist == NIL);
	Assert(parse->jointree->quals == NULL);
	Assert(parse->groupClause == NIL);
	Assert(parse->havingQual == NULL);
	Assert(parse->distinctClause == NIL);

	/*
	 * 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);

	/*
	 * 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, plus possibly a resjunk working
	 * column (we can rely on upper-level nodes to deal with that).
	 */
	return recurse_set_operations((Node *) topop, parse,
								  topop->colTypes, true, -1,
								  leftmostQuery->targetList);
}

/*
 * recurse_set_operations
 *	  Recursively handle one step in a tree of set operations
 *
 * colTypes: list of type OIDs of expected output columns
 * 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
 */
static Plan *
recurse_set_operations(Node *setOp, Query *parse,
					   List *colTypes, bool junkOK,
					   int flag, List *refnames_tlist)
{
	if (IsA(setOp, RangeTblRef))
	{
		RangeTblRef *rtr = (RangeTblRef *) setOp;
		RangeTblEntry *rte = rt_fetch(rtr->rtindex, parse->rtable);
		Query	   *subquery = rte->subquery;
		Plan	   *subplan,
				   *plan;

		Assert(subquery != NULL);

		/*
		 * Generate plan for primitive subquery
		 */
		subplan = subquery_planner(subquery, 0.0 /* default case */ );

		/*
		 * Add a SubqueryScan with the caller-requested targetlist
		 */
		plan = (Plan *)
			make_subqueryscan(generate_setop_tlist(colTypes, flag, true,
												   subplan->targetlist,
												   refnames_tlist),
							  NIL,
							  rtr->rtindex,
							  subplan);
		return plan;
	}
	else if (IsA(setOp, SetOperationStmt))
	{
		SetOperationStmt *op = (SetOperationStmt *) setOp;
		Plan	   *plan;

		/* 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 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.
		 */
		if (flag >= 0 ||
			!tlist_same_datatypes(plan->targetlist, colTypes, junkOK))
		{
			plan = (Plan *)
				make_result(generate_setop_tlist(colTypes, flag, false,
												 plan->targetlist,
												 refnames_tlist),
							NULL,
							plan);
		}
		return plan;
	}
	else
	{
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(setOp));
		return NULL;			/* keep compiler quiet */
	}
}

/*
 * Generate plan for a UNION or UNION ALL node
 */
static Plan *
generate_union_plan(SetOperationStmt *op, Query *parse,
					List *refnames_tlist)
{
	List	   *planlist;
	List	   *tlist;
	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));

	/*
	 * 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, false,
								  planlist, refnames_tlist);

	/*
	 * Append the child results together.
	 */
	plan = (Plan *) make_append(planlist, false, 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	   *sortList;

		tlist = copyObject(tlist);
		sortList = addAllTargetsToSortList(NULL, NIL, tlist, false);
		plan = (Plan *) make_sort_from_sortclauses(parse, tlist,
												   plan, sortList);
		plan = (Plan *) make_unique(tlist, plan, sortList);
	}
	return plan;
}

/*
 * 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,
			   *planlist;
	SetOpCmd	cmd;

	/* Recurse on children, ensuring their outputs are marked */
	lplan = recurse_set_operations(op->larg, parse,
								   op->colTypes, false, 0,
								   refnames_tlist);
	rplan = recurse_set_operations(op->rarg, parse,
								   op->colTypes, false, 1,
								   refnames_tlist);
	planlist = makeList2(lplan, rplan);

	/*
	 * 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, true,
								  planlist, refnames_tlist);

	/*
	 * Append the child results together.
	 */
	plan = (Plan *) make_append(planlist, false, tlist);

	/*
	 * Sort the child results, then add a SetOp plan node to generate the
	 * correct output.
	 */
	tlist = copyObject(tlist);
	sortList = addAllTargetsToSortList(NULL, NIL, tlist, false);
	plan = (Plan *) make_sort_from_sortclauses(parse, 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, "unrecognized set op: %d",
				 (int) op->op);
			cmd = SETOPCMD_INTERSECT;	/* keep compiler quiet */
			break;
	}
	plan = (Plan *) make_setop(cmd, tlist, plan, sortList,
							   length(op->colTypes) + 1);
	return plan;
}

/*
 * 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;

		if (op->op == top_union->op &&
			(op->all == top_union->all || op->all) &&
			equalo(op->colTypes, top_union->colTypes))
		{
			/* 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.