planner.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * planner.c
 *	  The query optimizer external interface.
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.57.2.1 1999/08/02 06:27:02 scrappy Exp $
 *
 *-------------------------------------------------------------------------
 */
#include <sys/types.h>

#include "postgres.h"

#include "access/genam.h"
#include "access/heapam.h"
#include "catalog/pg_type.h"
#include "executor/executor.h"
#include "nodes/makefuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/internal.h"
#include "optimizer/planmain.h"
#include "optimizer/planner.h"
#include "optimizer/prep.h"
#include "optimizer/subselect.h"
#include "optimizer/tlist.h"
#include "optimizer/var.h"
#include "parser/parse_expr.h"
#include "parser/parse_oper.h"
#include "utils/builtins.h"
#include "utils/lsyscache.h"
#include "utils/syscache.h"

static List *make_subplanTargetList(Query *parse, List *tlist,
					   AttrNumber **groupColIdx);
static Plan *make_groupplan(List *group_tlist, bool tuplePerGroup,
			   List *groupClause, AttrNumber *grpColIdx,
			   Plan *subplan);
static bool need_sortplan(List *sortcls, Plan *plan);
static Plan *make_sortplan(List *tlist, List *sortcls, Plan *plannode);

/*****************************************************************************
 *
 *	   Query optimizer entry point
 *
 *****************************************************************************/
Plan *
planner(Query *parse)
{
	Plan	   *result_plan;

	/* Initialize state for subselects */
	PlannerQueryLevel = 1;
	PlannerInitPlan = NULL;
	PlannerParamVar = NULL;
	PlannerPlanId = 0;

	transformKeySetQuery(parse);
	result_plan = union_planner(parse);

	Assert(PlannerQueryLevel == 1);
	if (PlannerPlanId > 0)
	{
		result_plan->initPlan = PlannerInitPlan;
		(void) SS_finalize_plan(result_plan);
	}
	result_plan->nParamExec = length(PlannerParamVar);

	return result_plan;
}

/*
 * union_planner
 *
 *	  Invokes the planner on union queries if there are any left,
 *	  recursing if necessary to get them all, then processes normal plans.
 *
 * Returns a query plan.
 *
 */
Plan *
union_planner(Query *parse)
{
	List	   *tlist = parse->targetList;
	List	   *rangetable = parse->rtable;
	Plan	   *result_plan = (Plan *) NULL;
	AttrNumber *groupColIdx = NULL;
	Index		rt_index;

	if (parse->unionClause)
	{
		result_plan = (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);
	}
	else if ((rt_index = first_inherit_rt_entry(rangetable)) != -1)
	{
		List	   *sub_tlist;

		/*
		 * Generate appropriate target list for subplan; may be different
		 * from tlist if grouping or aggregation is needed.
		 */
		sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx);

		/*
		 * Recursively plan the subqueries needed for inheritance
		 */
		result_plan = (Plan *) plan_inherit_queries(parse, sub_tlist,
													rt_index);

		/*
		 * Fix up outer target list.  NOTE: unlike the case for non-inherited
		 * query, we pass the unfixed tlist to subplans, which do their own
		 * fixing.  But we still want to fix the outer target list afterwards.
		 * I *think* this is correct --- doing the fix before recursing is
		 * definitely wrong, because preprocess_targetlist() will do the
		 * wrong thing if invoked twice on the same list. Maybe that is a bug?
		 * tgl 6/6/99
		 */
		tlist = preprocess_targetlist(tlist,
									  parse->commandType,
									  parse->resultRelation,
									  parse->rtable);

		if (parse->rowMark != NULL)
			elog(ERROR, "SELECT FOR UPDATE is not supported for inherit queries");
	}
	else
	{
		List	   *sub_tlist;

		/* Preprocess targetlist in case we are inside an INSERT/UPDATE. */
		tlist = preprocess_targetlist(tlist,
									  parse->commandType,
									  parse->resultRelation,
									  parse->rtable);

		/*
		 * Add row-mark targets for UPDATE (should this be done in
		 * preprocess_targetlist?)
		 */
		if (parse->rowMark != NULL)
		{
			List	   *l;

			foreach(l, parse->rowMark)
			{
				RowMark    *rowmark = (RowMark *) lfirst(l);
				TargetEntry *ctid;
				Resdom	   *resdom;
				Var		   *var;
				char	   *resname;

				if (!(rowmark->info & ROW_MARK_FOR_UPDATE))
					continue;

				resname = (char *) palloc(32);
				sprintf(resname, "ctid%u", rowmark->rti);
				resdom = makeResdom(length(tlist) + 1,
									TIDOID,
									-1,
									resname,
									0,
									0,
									true);

				var = makeVar(rowmark->rti, -1, TIDOID,
							  -1, 0, rowmark->rti, -1);

				ctid = makeTargetEntry(resdom, (Node *) var);
				tlist = lappend(tlist, ctid);
			}
		}

		/*
		 * Generate appropriate target list for subplan; may be different
		 * from tlist if grouping or aggregation is needed.
		 */
		sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx);

		/* Generate the (sub) plan */
		result_plan = query_planner(parse,
									parse->commandType,
									sub_tlist,
									(List *) parse->qual);
	}

	/* query_planner returns NULL if it thinks plan is bogus */
	if (! result_plan)
		elog(ERROR, "union_planner: failed to create plan");

	/*
	 * If we have a GROUP BY clause, insert a group node (with the
	 * appropriate sort node.)
	 */
	if (parse->groupClause)
	{
		bool		tuplePerGroup;
		List	   *group_tlist;

		/*
		 * Decide whether how many tuples per group the Group node needs
		 * to return. (Needs only one tuple per group if no aggregate is
		 * present. Otherwise, need every tuple from the group to do the
		 * aggregation.)  Note tuplePerGroup is named backwards :-(
		 */
		tuplePerGroup = parse->hasAggs;

		/*
		 * If there are aggregates then the Group node should just return
		 * the same (simplified) tlist as the subplan, which we indicate
		 * to make_groupplan by passing NIL.  If there are no aggregates
		 * then the Group node had better compute the final tlist.
		 */
		group_tlist = parse->hasAggs ? NIL : tlist;

		result_plan = make_groupplan(group_tlist,
									 tuplePerGroup,
									 parse->groupClause,
									 groupColIdx,
									 result_plan);
	}

	/*
	 * If we have a HAVING clause, do the necessary things with it.
	 */
	if (parse->havingQual)
	{
		/* convert the havingQual to conjunctive normal form (cnf) */
		parse->havingQual = (Node *) cnfify((Expr *) parse->havingQual, true);

		if (parse->hasSubLinks)
		{
			/*
			 * There may be a subselect in the havingQual, so we have to
			 * process it using the same function as for a subselect in
			 * 'where'
			 */
			parse->havingQual = SS_process_sublinks(parse->havingQual);

			/*
			 * Check for ungrouped variables passed to subplans. (Probably
			 * this should be done for the targetlist as well???)
			 */
			check_having_for_ungrouped_vars(parse->havingQual,
											parse->groupClause,
											parse->targetList);
		}

		/* Calculate the opfids from the opnos */
		parse->havingQual = (Node *) fix_opids((List *) parse->havingQual);
	}

	/*
	 * If aggregate is present, insert the agg node
	 */
	if (parse->hasAggs)
	{
		result_plan = (Plan *) make_agg(tlist, result_plan);

		/* HAVING clause, if any, becomes qual of the Agg node */
		result_plan->qual = (List *) parse->havingQual;

		/*
		 * Update vars to refer to subplan result tuples, find Aggrefs,
		 * make sure there is an Aggref in every HAVING clause.
		 */
		if (!set_agg_tlist_references((Agg *) result_plan))
			elog(ERROR, "SELECT/HAVING requires aggregates to be valid");

		/*
		 * Check that we actually found some aggregates, else executor
		 * will die unpleasantly.  (This defends against possible bugs in
		 * parser or rewrite that might cause hasAggs to be incorrectly
		 * set 'true'. It's not easy to recover here, since we've already
		 * made decisions assuming there will be an Agg node.)
		 */
		if (((Agg *) result_plan)->aggs == NIL)
			elog(ERROR, "union_planner: query is marked hasAggs, but I don't see any");
	}

	/*
	 * For now, before we hand back the plan, check to see if there is a
	 * user-specified sort that needs to be done.  Eventually, this will
	 * be moved into the guts of the planner s.t. user specified sorts
	 * will be considered as part of the planning process. Since we can
	 * only make use of user-specified sorts in special cases, we can do
	 * the optimization step later.
	 */

	if (parse->uniqueFlag)
	{
		Plan	   *sortplan = make_sortplan(tlist, parse->sortClause, result_plan);

		return ((Plan *) make_unique(tlist, sortplan, parse->uniqueFlag));
	}
	else
	{
		if (parse->sortClause && need_sortplan(parse->sortClause, result_plan))
			return (make_sortplan(tlist, parse->sortClause, result_plan));
		else
			return ((Plan *) result_plan);
	}

}

/*---------------
 * make_subplanTargetList
 *	  Generate appropriate target lists when grouping is required.
 *
 * When union_planner inserts Aggregate and/or Group/Sort plan nodes above
 * the result of query_planner, we typically need to pass a different
 * target list to query_planner than the outer plan nodes should have.
 * This routine generates the correct target list for the subplan, and
 * if necessary modifies the target list for the inserted nodes as well.
 *
 * The initial target list passed from the parser already contains entries
 * for all ORDER BY and GROUP BY expressions, but it will not have entries
 * for variables used only in HAVING clauses; so we need to add those
 * variables to the subplan target list.  Also, if we are doing either
 * grouping or aggregation, we flatten all expressions except GROUP BY items
 * into their component variables; the other expressions will be computed by
 * the inserted nodes rather than by the subplan.  For example,
 * given a query like
 *		SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
 * we want to pass this targetlist to the subplan:
 *		a+b,c,d
 * where the a+b target will be used by the Sort/Group steps, and the
 * c and d targets will be needed to compute the aggregate results.
 *
 * 'parse' is the query being processed.
 * 'tlist' is the query's target list.  CAUTION: list elements may be
 * modified by this routine!
 * 'groupColIdx' receives an array of column numbers for the GROUP BY
 * expressions (if there are any) in the subplan's target list.
 *
 * The result is the targetlist to be passed to the subplan.  Also,
 * the parent tlist is modified so that any nontrivial targetlist items that
 * exactly match GROUP BY items are replaced by simple Var nodes referencing
 * those outputs of the subplan.  This avoids redundant recalculations in
 * cases like
 *		SELECT a+1, ... GROUP BY a+1
 * Note, however, that other varnodes in the parent's targetlist (and
 * havingQual, if any) will still need to be updated to refer to outputs
 * of the subplan.	This routine is quite large enough already, so we do
 * that later.
 *---------------
 */
static List *
make_subplanTargetList(Query *parse,
					   List *tlist,
					   AttrNumber **groupColIdx)
{
	List	   *sub_tlist;
	List	   *prnt_tlist;
	List	   *sl,
			   *gl;
	List	   *glc = NIL;
	List	   *extravars = NIL;
	int			numCols;
	AttrNumber *grpColIdx = NULL;
	int			next_resno = 1;

	*groupColIdx = NULL;

	/*
	 * If we're not grouping or aggregating, nothing to do here;
	 * query_planner should receive the unmodified target list.
	 */
	if (!parse->hasAggs && !parse->groupClause && !parse->havingQual)
		return tlist;

	/*
	 * If grouping, make a working copy of groupClause list (which we use
	 * just to verify that we found all the groupClause items in tlist).
	 * Also allocate space to remember where the group columns are in the
	 * subplan tlist.
	 */
	numCols = length(parse->groupClause);
	if (numCols > 0)
	{
		glc = listCopy(parse->groupClause);
		grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
		*groupColIdx = grpColIdx;
	}

	sub_tlist = new_unsorted_tlist(tlist);		/* make a modifiable copy */

	/*
	 * Step 1: build grpColIdx by finding targetlist items that match
	 * GroupBy entries.  If there are aggregates, remove non-GroupBy items
	 * from sub_tlist, and reset its resnos accordingly.  When we leave an
	 * expression in the subplan tlist, modify the parent tlist to copy
	 * the value from the subplan output rather than re-evaluating it.
	 */
	prnt_tlist = tlist;			/* scans parent tlist in sync with sl */
	foreach(sl, sub_tlist)
	{
		TargetEntry *te = (TargetEntry *) lfirst(sl);
		TargetEntry *parentte = (TargetEntry *) lfirst(prnt_tlist);
		Resdom	   *resdom = te->resdom;
		bool		keepInSubPlan = true;
		bool		foundGroupClause = false;
		int			keyno = 0;

		foreach(gl, parse->groupClause)
		{
			GroupClause *grpcl = (GroupClause *) lfirst(gl);

			keyno++;			/* sort key # for this GroupClause */
			if (grpcl->tleGroupref == resdom->resgroupref)
			{
				/* Found a matching groupclause; record info for sorting */
				foundGroupClause = true;
				resdom->reskey = keyno;
				resdom->reskeyop = get_opcode(grpcl->grpOpoid);
				grpColIdx[keyno - 1] = next_resno;

				/*
				 * Remove groupclause from our list of unmatched
				 * groupclauses. NB: this depends on having used a shallow
				 * listCopy() above.
				 */
				glc = lremove((void *) grpcl, glc);
				break;
			}
		}

		if (!foundGroupClause)
		{

			/*
			 * Non-GroupBy entry: remove it from subplan if there are
			 * aggregates in query - it will be evaluated by Aggregate
			 * plan. But do not remove simple-Var entries; we'd just have
			 * to add them back anyway, and we risk confusing
			 * INSERT/UPDATE.
			 */
			if (parse->hasAggs && !IsA(te->expr, Var))
				keepInSubPlan = false;
		}

		if (keepInSubPlan)
		{
			/* Assign new sequential resnos to subplan tlist items */
			resdom->resno = next_resno++;
			if (!IsA(parentte->expr, Var))
			{

				/*
				 * Since the item is being computed in the subplan, we can
				 * just make a Var node to reference it in the outer plan,
				 * rather than recomputing it there. Note we use varnoold
				 * = -1 as a flag to let replace_vars_with_subplan_refs
				 * know it needn't change this Var node. If it's only a
				 * Var anyway, we leave it alone for now;
				 * replace_vars_with_subplan_refs will fix it later.
				 */
				parentte->expr = (Node *) makeVar(1, resdom->resno,
												  resdom->restype,
												  resdom->restypmod,
												  0, -1, resdom->resno);
			}
		}
		else
		{

			/*
			 * Remove this tlist item from the subplan, but remember the
			 * vars it needs.  The outer tlist item probably needs
			 * changes, but that will happen later.
			 */
			sub_tlist = lremove(te, sub_tlist);
			extravars = nconc(extravars, pull_var_clause(te->expr));
		}

		prnt_tlist = lnext(prnt_tlist);
	}

	/* We should have found all the GROUP BY clauses in the tlist. */
	if (length(glc) != 0)
		elog(ERROR, "make_subplanTargetList: GROUP BY attribute not found in target list");

	/*
	 * Add subplan targets for any variables needed by removed tlist
	 * entries that aren't otherwise mentioned in the subplan target list.
	 * We'll also need targets for any variables seen only in HAVING.
	 */