planner.c

PostgreSQL 8.1.4的源码 适用于Linux下的开源数据库系统

		return NULL;

	/*
	 * 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 (root->hasJoinRTEs)
		expr = flatten_join_alias_vars(root, expr);

	/*
	 * Simplify constant expressions.
	 *
	 * Note: this also flattens nested AND and OR expressions into N-argument
	 * form.  All processing of a qual expression after this point must be
	 * careful to maintain AND/OR flatness --- that is, do not generate a tree
	 * with AND directly under AND, nor OR directly under OR.
	 *
	 * Because this is a relatively expensive process, we skip it when the
	 * query is trivial, such as "SELECT 2+2;" or "INSERT ... VALUES()". The
	 * expression will only be evaluated once anyway, so no point in
	 * pre-simplifying; we can't execute it any faster than the executor can,
	 * and we will waste cycles copying the tree.  Notice however that we
	 * still must do it for quals (to get AND/OR flatness); and if we are in a
	 * subquery we should not assume it will be done only once.
	 */
	if (root->parse->jointree->fromlist != NIL ||
		kind == EXPRKIND_QUAL ||
		PlannerQueryLevel > 1)
		expr = eval_const_expressions(expr);

	/*
	 * If it's a qual or havingQual, canonicalize it.
	 */
	if (kind == EXPRKIND_QUAL)
	{
		expr = (Node *) canonicalize_qual((Expr *) expr);

#ifdef OPTIMIZER_DEBUG
		printf("After canonicalize_qual()\n");
		pprint(expr);
#endif
	}

	/* Expand SubLinks to SubPlans */
	if (root->parse->hasSubLinks)
		expr = SS_process_sublinks(expr, (kind == EXPRKIND_QUAL));

	/*
	 * XXX do not insert anything here unless you have grokked the comments in
	 * SS_replace_correlation_vars ...
	 */

	/* Replace uplevel vars with Param nodes */
	if (PlannerQueryLevel > 1)
		expr = SS_replace_correlation_vars(expr);

	/*
	 * If it's a qual or havingQual, convert it to implicit-AND format. (We
	 * don't want to do this before eval_const_expressions, since the latter
	 * would be unable to simplify a top-level AND correctly. Also,
	 * SS_process_sublinks expects explicit-AND format.)
	 */
	if (kind == EXPRKIND_QUAL)
		expr = (Node *) make_ands_implicit((Expr *) expr);

	return expr;
}

/*
 * preprocess_qual_conditions
 *		Recursively scan the query's jointree and do subquery_planner's
 *		preprocessing work on each qual condition found therein.
 */
static void
preprocess_qual_conditions(PlannerInfo *root, Node *jtnode)
{
	if (jtnode == NULL)
		return;
	if (IsA(jtnode, RangeTblRef))
	{
		/* nothing to do here */
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;

		foreach(l, f->fromlist)
			preprocess_qual_conditions(root, lfirst(l));

		f->quals = preprocess_expression(root, f->quals, EXPRKIND_QUAL);
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;

		preprocess_qual_conditions(root, j->larg);
		preprocess_qual_conditions(root, j->rarg);

		j->quals = preprocess_expression(root, j->quals, EXPRKIND_QUAL);
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
}

/*--------------------
 * inheritance_planner
 *	  Generate a plan in the case where the result relation is an
 *	  inheritance set.
 *
 * We have to handle this case differently from cases where a source
 * relation is an inheritance set.	Source inheritance is expanded at
 * the bottom of the plan tree (see allpaths.c), but target inheritance
 * has to be expanded at the top.  The reason is that for UPDATE, each
 * target relation needs a different targetlist matching its own column
 * set.  (This is not so critical for DELETE, but for simplicity we treat
 * inherited DELETE the same way.)	Fortunately, the UPDATE/DELETE target
 * can never be the nullable side of an outer join, so it's OK to generate
 * the plan this way.
 *
 * inheritlist is an integer list of RT indexes for the result relation set.
 *
 * Returns a query plan.
 *--------------------
 */
static Plan *
inheritance_planner(PlannerInfo *root, List *inheritlist)
{
	Query	   *parse = root->parse;
	int			parentRTindex = parse->resultRelation;
	Oid			parentOID = getrelid(parentRTindex, parse->rtable);
	int			mainrtlength = list_length(parse->rtable);
	List	   *subplans = NIL;
	List	   *tlist = NIL;
	ListCell   *l;

	foreach(l, inheritlist)
	{
		int			childRTindex = lfirst_int(l);
		Oid			childOID = getrelid(childRTindex, parse->rtable);
		PlannerInfo subroot;
		Plan	   *subplan;

		/*
		 * Generate modified query with this rel as target.  We have to be
		 * prepared to translate varnos in in_info_list as well as in the
		 * Query proper.
		 */
		memcpy(&subroot, root, sizeof(PlannerInfo));
		subroot.parse = (Query *)
			adjust_inherited_attrs((Node *) parse,
								   parentRTindex, parentOID,
								   childRTindex, childOID);
		subroot.in_info_list = (List *)
			adjust_inherited_attrs((Node *) root->in_info_list,
								   parentRTindex, parentOID,
								   childRTindex, childOID);

		/* Generate plan */
		subplan = grouping_planner(&subroot, 0.0 /* retrieve all tuples */ );

		subplans = lappend(subplans, subplan);

		/*
		 * XXX my goodness this next bit is ugly.  Really need to think about
		 * ways to rein in planner's habit of scribbling on its input.
		 *
		 * Planning of the subquery might have modified the rangetable, either
		 * by addition of RTEs due to expansion of inherited source tables, or
		 * by changes of the Query structures inside subquery RTEs.  We have
		 * to ensure that this gets propagated back to the master copy.
		 * However, if we aren't done planning yet, we also need to ensure
		 * that subsequent calls to grouping_planner have virgin sub-Queries
		 * to work from.  So, if we are at the last list entry, just copy the
		 * subquery rangetable back to the master copy; if we are not, then
		 * extend the master copy by adding whatever the subquery added.  (We
		 * assume these added entries will go untouched by the future
		 * grouping_planner calls.	We are also effectively assuming that
		 * sub-Queries will get planned identically each time, or at least
		 * that the impacts on their rangetables will be the same each time.
		 * Did I say this is ugly?)
		 */
		if (lnext(l) == NULL)
			parse->rtable = subroot.parse->rtable;
		else
		{
			int			subrtlength = list_length(subroot.parse->rtable);

			if (subrtlength > mainrtlength)
			{
				List	   *subrt;

				subrt = list_copy_tail(subroot.parse->rtable, mainrtlength);
				parse->rtable = list_concat(parse->rtable, subrt);
				mainrtlength = subrtlength;
			}
		}

		/* Save preprocessed tlist from first rel for use in Append */
		if (tlist == NIL)
			tlist = subplan->targetlist;
	}

	/* Save the target-relations list for the executor, too */
	parse->resultRelations = inheritlist;

	/* Mark result as unordered (probably unnecessary) */
	root->query_pathkeys = NIL;

	return (Plan *) make_append(subplans, true, tlist);
}

/*--------------------
 * grouping_planner
 *	  Perform planning steps related to grouping, aggregation, etc.
 *	  This primarily means adding top-level processing to the basic
 *	  query plan produced by query_planner.
 *
 * tuple_fraction is the fraction of tuples we expect will be retrieved
 *
 * tuple_fraction is interpreted as follows:
 *	  0: expect all tuples to be retrieved (normal case)
 *	  0 < tuple_fraction < 1: expect the given fraction of tuples available
 *		from the plan to be retrieved
 *	  tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
 *		expected to be retrieved (ie, a LIMIT specification)
 *
 * Returns a query plan.  Also, root->query_pathkeys is returned as the
 * actual output ordering of the plan (in pathkey format).
 *--------------------
 */
static Plan *
grouping_planner(PlannerInfo *root, double tuple_fraction)
{
	Query	   *parse = root->parse;
	List	   *tlist = parse->targetList;
	int			offset_est = 0;
	int			count_est = 0;
	Plan	   *result_plan;
	List	   *current_pathkeys;
	List	   *sort_pathkeys;
	double		dNumGroups = 0;

	/* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
	if (parse->limitCount || parse->limitOffset)
		tuple_fraction = preprocess_limit(root, tuple_fraction,
										  &offset_est, &count_est);

	if (parse->setOperations)
	{
		List	   *set_sortclauses;

		/*
		 * If there's a top-level ORDER BY, assume we have to fetch all the
		 * tuples.	This might seem too simplistic given all the hackery below
		 * to possibly avoid the sort ... but a nonzero tuple_fraction is only
		 * of use to plan_set_operations() when the setop is UNION ALL, and
		 * the result of UNION ALL is always unsorted.
		 */
		if (parse->sortClause)
			tuple_fraction = 0.0;

		/*
		 * Construct the plan for set operations.  The result will not need
		 * any work except perhaps a top-level sort and/or LIMIT.
		 */
		result_plan = plan_set_operations(root, tuple_fraction,
										  &set_sortclauses);

		/*
		 * Calculate pathkeys representing the sort order (if any) of the set
		 * operation's result.  We have to do this before overwriting the sort
		 * key information...
		 */
		current_pathkeys = make_pathkeys_for_sortclauses(set_sortclauses,
													result_plan->targetlist);
		current_pathkeys = canonicalize_pathkeys(root, current_pathkeys);

		/*
		 * We should not need to call preprocess_targetlist, since we must be
		 * in a SELECT query node.	Instead, use the targetlist returned by
		 * plan_set_operations (since this tells whether it returned any
		 * resjunk columns!), and transfer any sort key information from the
		 * original tlist.
		 */
		Assert(parse->commandType == CMD_SELECT);

		tlist = postprocess_setop_tlist(result_plan->targetlist, tlist);

		/*
		 * Can't handle FOR UPDATE/SHARE here (parser should have checked
		 * already, but let's make sure).
		 */
		if (parse->rowMarks)
			ereport(ERROR,
					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					 errmsg("SELECT FOR UPDATE/SHARE is not allowed with UNION/INTERSECT/EXCEPT")));

		/*
		 * Calculate pathkeys that represent result ordering requirements
		 */
		sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause,
													  tlist);
		sort_pathkeys = canonicalize_pathkeys(root, sort_pathkeys);
	}
	else
	{
		/* No set operations, do regular planning */
		List	   *sub_tlist;
		List	   *group_pathkeys;
		AttrNumber *groupColIdx = NULL;
		bool		need_tlist_eval = true;
		QualCost	tlist_cost;
		Path	   *cheapest_path;
		Path	   *sorted_path;
		Path	   *best_path;
		long		numGroups = 0;
		AggClauseCounts agg_counts;
		int			numGroupCols = list_length(parse->groupClause);
		bool		use_hashed_grouping = false;

		MemSet(&agg_counts, 0, sizeof(AggClauseCounts));

		/* Preprocess targetlist */
		tlist = preprocess_targetlist(root, tlist);

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

		/*
		 * Calculate pathkeys that represent grouping/ordering requirements.
		 * Stash them in PlannerInfo so that query_planner can canonicalize
		 * them.
		 */
		root->group_pathkeys =
			make_pathkeys_for_sortclauses(parse->groupClause, tlist);
		root->sort_pathkeys =
			make_pathkeys_for_sortclauses(parse->sortClause, tlist);

		/*
		 * Will need actual number of aggregates for estimating costs.
		 *
		 * Note: we do not attempt to detect duplicate aggregates here; a
		 * somewhat-overestimated count is okay for our present purposes.
		 *
		 * Note: think not that we can turn off hasAggs if we find no aggs. It
		 * is possible for constant-expression simplification to remove all
		 * explicit references to aggs, but we still have to follow the
		 * aggregate semantics (eg, producing only one output row).
		 */
		if (parse->hasAggs)
		{
			count_agg_clauses((Node *) tlist, &agg_counts);
			count_agg_clauses(parse->havingQual, &agg_counts);
		}

		/*
		 * Figure out whether we need a sorted result from query_planner.
		 *
		 * If we have a GROUP BY clause, then we want a result sorted properly
		 * for grouping.  Otherwise, if there is an ORDER BY clause, we want
		 * to sort by the ORDER BY clause.	(Note: if we have both, and ORDER
		 * BY is a superset of GROUP BY, it would be tempting to request sort
		 * by ORDER BY --- but that might just leave us failing to exploit an
		 * available sort order at all. Needs more thought...)
		 */
		if (parse->groupClause)
			root->query_pathkeys = root->group_pathkeys;
		else if (parse->sortClause)
			root->query_pathkeys = root->sort_pathkeys;
		else
			root->query_pathkeys = NIL;

		/*
		 * Generate the best unsorted and presorted paths for this Query (but
		 * note there may not be any presorted path).  query_planner will also
		 * estimate the number of groups in the query, and canonicalize all
		 * the pathkeys.
		 */
		query_planner(root, sub_tlist, tuple_fraction,
					  &cheapest_path, &sorted_path, &dNumGroups);

		group_pathkeys = root->group_pathkeys;
		sort_pathkeys = root->sort_pathkeys;

		/*
		 * If grouping, decide whether we want to use hashed grouping.
		 */
		if (parse->groupClause)
		{
			use_hashed_grouping =
				choose_hashed_grouping(root, tuple_fraction,
									   cheapest_path, sorted_path,
									   dNumGroups, &agg_counts);

			/* Also convert # groups to long int --- but 'ware overflow! */
			numGroups = (long) Min(dNumGroups, (double) LONG_MAX);
		}

		/*
		 * Select the best path.  If we are doing hashed grouping, we will
		 * always read all the input tuples, so use the cheapest-total path.
		 * Otherwise, trust query_planner's decision about which to use.
		 */