planner.c

来自「PostgreSQL7.4.6 for Linux」· C语言 代码 · 共 1,553 行 · 第 1/4 页

/*-------------------------------------------------------------------------
 *
 * planner.c
 *	  The query optimizer external interface.
 *
 * 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/plan/planner.c,v 1.161.2.2 2004/05/11 02:21:55 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include <limits.h>

#include "catalog/pg_operator.h"
#include "catalog/pg_type.h"
#include "executor/executor.h"
#include "miscadmin.h"
#include "nodes/makefuncs.h"
#ifdef OPTIMIZER_DEBUG
#include "nodes/print.h"
#endif
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "optimizer/planner.h"
#include "optimizer/prep.h"
#include "optimizer/subselect.h"
#include "optimizer/tlist.h"
#include "optimizer/var.h"
#include "parser/analyze.h"
#include "parser/parsetree.h"
#include "parser/parse_expr.h"
#include "parser/parse_oper.h"
#include "utils/selfuncs.h"
#include "utils/syscache.h"


/* Expression kind codes for preprocess_expression */
#define EXPRKIND_QUAL	0
#define EXPRKIND_TARGET 1
#define EXPRKIND_RTFUNC 2
#define EXPRKIND_LIMIT	3
#define EXPRKIND_ININFO 4


static Node *preprocess_expression(Query *parse, Node *expr, int kind);
static void preprocess_qual_conditions(Query *parse, Node *jtnode);
static Plan *inheritance_planner(Query *parse, List *inheritlist);
static Plan *grouping_planner(Query *parse, double tuple_fraction);
static bool hash_safe_grouping(Query *parse);
static List *make_subplanTargetList(Query *parse, List *tlist,
					   AttrNumber **groupColIdx, bool *need_tlist_eval);
static void locate_grouping_columns(Query *parse,
						List *tlist,
						List *sub_tlist,
						AttrNumber *groupColIdx);
static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);


/*****************************************************************************
 *
 *	   Query optimizer entry point
 *
 *****************************************************************************/
Plan *
planner(Query *parse, bool isCursor, int cursorOptions)
{
	double		tuple_fraction;
	Plan	   *result_plan;
	Index		save_PlannerQueryLevel;
	List	   *save_PlannerParamList;

	/*
	 * The planner can be called recursively (an example is when
	 * eval_const_expressions tries to pre-evaluate an SQL function). So,
	 * these global state variables must be saved and restored.
	 *
	 * 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_PlannerParamList = PlannerParamList;

	/* Initialize state for handling outer-level references and params */
	PlannerQueryLevel = 0;		/* will be 1 in top-level subquery_planner */
	PlannerParamList = NIL;

	/* Determine what fraction of the plan is likely to be scanned */
	if (isCursor)
	{
		/*
		 * We have no real idea how many tuples the user will ultimately
		 * FETCH from a cursor, but it seems a good bet that he doesn't
		 * want 'em all.  Optimize for 10% retrieval (you gotta better
		 * number?	Should this be a SETtable parameter?)
		 */
		tuple_fraction = 0.10;
	}
	else
	{
		/* Default assumption is we need all the tuples */
		tuple_fraction = 0.0;
	}

	/* primary planning entry point (may recurse for subqueries) */
	result_plan = subquery_planner(parse, tuple_fraction);

	Assert(PlannerQueryLevel == 0);

	/*
	 * If creating a plan for a scrollable cursor, make sure it can run
	 * backwards on demand.  Add a Material node at the top at need.
	 */
	if (isCursor && (cursorOptions & CURSOR_OPT_SCROLL))
	{
		if (!ExecSupportsBackwardScan(result_plan))
			result_plan = materialize_finished_plan(result_plan);
	}

	/* executor wants to know total number of Params used overall */
	result_plan->nParamExec = length(PlannerParamList);

	/* final cleanup of the plan */
	set_plan_references(result_plan, parse->rtable);

	/* restore state for outer planner, if any */
	PlannerQueryLevel = save_PlannerQueryLevel;
	PlannerParamList = save_PlannerParamList;

	return result_plan;
}


/*--------------------
 * subquery_planner
 *	  Invokes the planner on a subquery.  We recurse to here for each
 *	  sub-SELECT found in the query tree.
 *
 * parse is the querytree produced by the parser & rewriter.
 * tuple_fraction is the fraction of tuples we expect will be retrieved.
 * tuple_fraction is interpreted as explained for grouping_planner, below.
 *
 * Basically, this routine does the stuff that should only be done once
 * per Query object.  It then calls grouping_planner.  At one time,
 * grouping_planner could be invoked recursively on the same Query object;
 * that's not currently true, but we keep the separation between the two
 * routines anyway, in case we need it again someday.
 *
 * subquery_planner will be called recursively to handle sub-Query nodes
 * found within the query's expressions and rangetable.
 *
 * Returns a query plan.
 *--------------------
 */
Plan *
subquery_planner(Query *parse, double tuple_fraction)
{
	List	   *saved_initplan = PlannerInitPlan;
	int			saved_planid = PlannerPlanId;
	bool		hasOuterJoins;
	Plan	   *plan;
	List	   *newHaving;
	List	   *lst;

	/* Set up for a new level of subquery */
	PlannerQueryLevel++;
	PlannerInitPlan = NIL;

	/*
	 * Look for IN clauses at the top level of WHERE, and transform them
	 * into joins.	Note that this step only handles IN clauses originally
	 * at top level of WHERE; if we pull up any subqueries in the next
	 * step, their INs are processed just before pulling them up.
	 */
	parse->in_info_list = NIL;
	if (parse->hasSubLinks)
		parse->jointree->quals = pull_up_IN_clauses(parse,
												 parse->jointree->quals);

	/*
	 * Check to see if any subqueries in the rangetable can be merged into
	 * this query.
	 */
	parse->jointree = (FromExpr *)
		pull_up_subqueries(parse, (Node *) parse->jointree, false);

	/*
	 * Detect whether any rangetable entries are RTE_JOIN kind; if not, we
	 * can avoid the expense of doing flatten_join_alias_vars().  Also
	 * check for outer joins --- if none, we can skip
	 * reduce_outer_joins(). This must be done after we have done
	 * pull_up_subqueries, of course.
	 */
	parse->hasJoinRTEs = false;
	hasOuterJoins = false;
	foreach(lst, parse->rtable)
	{
		RangeTblEntry *rte = (RangeTblEntry *) lfirst(lst);

		if (rte->rtekind == RTE_JOIN)
		{
			parse->hasJoinRTEs = true;
			if (IS_OUTER_JOIN(rte->jointype))
			{
				hasOuterJoins = true;
				/* Can quit scanning once we find an outer join */
				break;
			}
		}
	}

	/*
	 * Do expression preprocessing on targetlist and quals.
	 */
	parse->targetList = (List *)
		preprocess_expression(parse, (Node *) parse->targetList,
							  EXPRKIND_TARGET);

	preprocess_qual_conditions(parse, (Node *) parse->jointree);

	parse->havingQual = preprocess_expression(parse, parse->havingQual,
											  EXPRKIND_QUAL);

	parse->limitOffset = preprocess_expression(parse, parse->limitOffset,
											   EXPRKIND_LIMIT);
	parse->limitCount = preprocess_expression(parse, parse->limitCount,
											  EXPRKIND_LIMIT);

	parse->in_info_list = (List *)
		preprocess_expression(parse, (Node *) parse->in_info_list,
							  EXPRKIND_ININFO);

	/* Also need to preprocess expressions for function RTEs */
	foreach(lst, parse->rtable)
	{
		RangeTblEntry *rte = (RangeTblEntry *) lfirst(lst);

		if (rte->rtekind == RTE_FUNCTION)
			rte->funcexpr = preprocess_expression(parse, rte->funcexpr,
												  EXPRKIND_RTFUNC);
	}

	/*
	 * A HAVING clause without aggregates is equivalent to a WHERE clause
	 * (except it can only refer to grouped fields).  Transfer any
	 * agg-free clauses of the HAVING qual into WHERE.	This may seem like
	 * wasting cycles to cater to stupidly-written queries, but there are
	 * other reasons for doing it.	Firstly, if the query contains no aggs
	 * at all, then we aren't going to generate an Agg plan node, and so
	 * there'll be no place to execute HAVING conditions; without this
	 * transfer, we'd lose the HAVING condition entirely, which is wrong.
	 * Secondly, when we push down a qual condition into a sub-query, it's
	 * easiest to push the qual into HAVING always, in case it contains
	 * aggs, and then let this code sort it out.
	 *
	 * Note that both havingQual and parse->jointree->quals are in
	 * implicitly-ANDed-list form at this point, even though they are
	 * declared as Node *.
	 */
	newHaving = NIL;
	foreach(lst, (List *) parse->havingQual)
	{
		Node	   *havingclause = (Node *) lfirst(lst);

		if (contain_agg_clause(havingclause))
			newHaving = lappend(newHaving, havingclause);
		else
			parse->jointree->quals = (Node *)
				lappend((List *) parse->jointree->quals, havingclause);
	}
	parse->havingQual = (Node *) newHaving;

	/*
	 * If we have any outer joins, try to reduce them to plain inner
	 * joins. This step is most easily done after we've done expression
	 * preprocessing.
	 */
	if (hasOuterJoins)
		reduce_outer_joins(parse);

	/*
	 * See if we can simplify the jointree; opportunities for this may
	 * come from having pulled up subqueries, or from flattening explicit
	 * JOIN syntax.  We must do this after flattening JOIN alias
	 * variables, since eliminating explicit JOIN nodes from the jointree
	 * will cause get_relids_for_join() to fail.  But it should happen
	 * after reduce_outer_joins, anyway.
	 */
	parse->jointree = (FromExpr *)
		simplify_jointree(parse, (Node *) parse->jointree);

	/*
	 * Do the main planning.  If we have an inherited target relation,
	 * that needs special processing, else go straight to
	 * grouping_planner.
	 */
	if (parse->resultRelation &&
		(lst = expand_inherited_rtentry(parse, parse->resultRelation,
										false)) != NIL)
		plan = inheritance_planner(parse, lst);
	else
		plan = grouping_planner(parse, tuple_fraction);

	/*
	 * If any subplans were generated, or if we're inside a subplan, build
	 * initPlan list and extParam/allParam sets for plan nodes.
	 */
	if (PlannerPlanId != saved_planid || PlannerQueryLevel > 1)
	{
		Cost		initplan_cost = 0;

		/* Prepare extParam/allParam sets for all nodes in tree */
		SS_finalize_plan(plan, parse->rtable);

		/*
		 * SS_finalize_plan doesn't handle initPlans, so we have to
		 * manually attach them to the topmost plan node, and add their
		 * extParams to the topmost node's, too.
		 *
		 * We also add the total_cost of each initPlan to the startup cost of
		 * the top node.  This is a conservative overestimate, since in
		 * fact each initPlan might be executed later than plan startup,
		 * or even not at all.
		 */
		plan->initPlan = PlannerInitPlan;

		foreach(lst, plan->initPlan)
		{
			SubPlan    *initplan = (SubPlan *) lfirst(lst);

			plan->extParam = bms_add_members(plan->extParam,
											 initplan->plan->extParam);
			/* allParam must include all members of extParam */
			plan->allParam = bms_add_members(plan->allParam,
											 plan->extParam);
			initplan_cost += initplan->plan->total_cost;
		}

		plan->startup_cost += initplan_cost;
		plan->total_cost += initplan_cost;
	}

	/* Return to outer subquery context */
	PlannerQueryLevel--;
	PlannerInitPlan = saved_initplan;
	/* we do NOT restore PlannerPlanId; that's not an oversight! */

	return plan;
}

/*
 * preprocess_expression
 *		Do subquery_planner's preprocessing work for an expression,
 *		which can be a targetlist, a WHERE clause (including JOIN/ON
 *		conditions), or a HAVING clause.
 */
static Node *
preprocess_expression(Query *parse, Node *expr, int kind)
{
	/*
	 * If the query has any join RTEs, replace join alias variables with
	 * base-relation variables. We must do this before sublink processing,
	 * else sublinks expanded out from join aliases wouldn't get
	 * processed.
	 */
	if (parse->hasJoinRTEs)
		expr = flatten_join_alias_vars(parse, expr);

	/*
	 * Simplify constant expressions.
	 *
	 * Note that at this point quals have not yet been converted to
	 * implicit-AND form, so we can apply eval_const_expressions directly.
	 */
	expr = eval_const_expressions(expr);