allpaths.c

来自「PostgreSQL 8.1.4的源码 适用于Linux下的开源数据库系统」· C语言 代码 · 共 1,160 行 · 第 1/3 页

/*-------------------------------------------------------------------------
 *
 * allpaths.c
 *	  Routines to find possible search paths for processing a query
 *
 * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.137.2.3 2006/05/02 04:34:24 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "nodes/makefuncs.h"
#ifdef OPTIMIZER_DEBUG
#include "nodes/print.h"
#endif
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/geqo.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/plancat.h"
#include "optimizer/planner.h"
#include "optimizer/predtest.h"
#include "optimizer/prep.h"
#include "optimizer/var.h"
#include "parser/parsetree.h"
#include "parser/parse_clause.h"
#include "parser/parse_expr.h"
#include "rewrite/rewriteManip.h"


/* These parameters are set by GUC */
bool		constraint_exclusion = false;
bool		enable_geqo = false;	/* just in case GUC doesn't set it */
int			geqo_threshold;


static void set_base_rel_pathlists(PlannerInfo *root);
static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
					   RangeTblEntry *rte);
static void set_inherited_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
						   Index rti, RangeTblEntry *rte,
						   List *inheritlist);
static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
					  Index rti, RangeTblEntry *rte);
static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
					  RangeTblEntry *rte);
static RelOptInfo *make_one_rel_by_joins(PlannerInfo *root, int levels_needed,
					  List *initial_rels);
static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery,
						  bool *differentTypes);
static bool recurse_pushdown_safe(Node *setOp, Query *topquery,
					  bool *differentTypes);
static void compare_tlist_datatypes(List *tlist, List *colTypes,
						bool *differentTypes);
static bool qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
					  bool *differentTypes);
static void subquery_push_qual(Query *subquery,
				   RangeTblEntry *rte, Index rti, Node *qual);
static void recurse_push_qual(Node *setOp, Query *topquery,
				  RangeTblEntry *rte, Index rti, Node *qual);


/*
 * make_one_rel
 *	  Finds all possible access paths for executing a query, returning a
 *	  single rel that represents the join of all base rels in the query.
 */
RelOptInfo *
make_one_rel(PlannerInfo *root)
{
	RelOptInfo *rel;

	/*
	 * Generate access paths for the base rels.
	 */
	set_base_rel_pathlists(root);

	/*
	 * Generate access paths for the entire join tree.
	 */
	Assert(root->parse->jointree != NULL &&
		   IsA(root->parse->jointree, FromExpr));

	rel = make_fromexpr_rel(root, root->parse->jointree);

	/*
	 * The result should join all and only the query's base rels.
	 */
#ifdef USE_ASSERT_CHECKING
	{
		int			num_base_rels = 0;
		Index		rti;

		for (rti = 1; rti < root->base_rel_array_size; rti++)
		{
			RelOptInfo *brel = root->base_rel_array[rti];

			if (brel == NULL)
				continue;

			Assert(brel->relid == rti); /* sanity check on array */

			/* ignore RTEs that are "other rels" */
			if (brel->reloptkind != RELOPT_BASEREL)
				continue;

			Assert(bms_is_member(rti, rel->relids));
			num_base_rels++;
		}

		Assert(bms_num_members(rel->relids) == num_base_rels);
	}
#endif

	return rel;
}

/*
 * set_base_rel_pathlists
 *	  Finds all paths available for scanning each base-relation entry.
 *	  Sequential scan and any available indices are considered.
 *	  Each useful path is attached to its relation's 'pathlist' field.
 */
static void
set_base_rel_pathlists(PlannerInfo *root)
{
	Index		rti;

	/*
	 * Note: because we call expand_inherited_rtentry inside the loop, it's
	 * quite possible for the base_rel_array to be enlarged while the loop
	 * runs.  Hence don't try to optimize the loop.
	 */
	for (rti = 1; rti < root->base_rel_array_size; rti++)
	{
		RelOptInfo *rel = root->base_rel_array[rti];
		RangeTblEntry *rte;
		List	   *inheritlist;

		/* there may be empty slots corresponding to non-baserel RTEs */
		if (rel == NULL)
			continue;

		Assert(rel->relid == rti);		/* sanity check on array */

		/* ignore RTEs that are "other rels" */
		if (rel->reloptkind != RELOPT_BASEREL)
			continue;

		rte = rt_fetch(rti, root->parse->rtable);

		if (rel->rtekind == RTE_SUBQUERY)
		{
			/* Subquery --- generate a separate plan for it */
			set_subquery_pathlist(root, rel, rti, rte);
		}
		else if (rel->rtekind == RTE_FUNCTION)
		{
			/* RangeFunction --- generate a separate plan for it */
			set_function_pathlist(root, rel, rte);
		}
		else if ((inheritlist = expand_inherited_rtentry(root, rti)) != NIL)
		{
			/* Relation is root of an inheritance tree, process specially */
			set_inherited_rel_pathlist(root, rel, rti, rte, inheritlist);
		}
		else
		{
			/* Plain relation */
			set_plain_rel_pathlist(root, rel, rte);
		}

#ifdef OPTIMIZER_DEBUG
		debug_print_rel(root, rel);
#endif
	}
}

/*
 * set_plain_rel_pathlist
 *	  Build access paths for a plain relation (no subquery, no inheritance)
 */
static void
set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
{
	/* Mark rel with estimated output rows, width, etc */
	set_baserel_size_estimates(root, rel);

	/* Test any partial indexes of rel for applicability */
	check_partial_indexes(root, rel);

	/*
	 * Check to see if we can extract any restriction conditions from join
	 * quals that are OR-of-AND structures.  If so, add them to the rel's
	 * restriction list, and recompute the size estimates.
	 */
	if (create_or_index_quals(root, rel))
		set_baserel_size_estimates(root, rel);

	/*
	 * Generate paths and add them to the rel's pathlist.
	 *
	 * Note: add_path() will discard any paths that are dominated by another
	 * available path, keeping only those paths that are superior along at
	 * least one dimension of cost or sortedness.
	 */

	/* Consider sequential scan */
	add_path(rel, create_seqscan_path(root, rel));

	/* Consider index scans */
	create_index_paths(root, rel);

	/* Consider TID scans */
	create_tidscan_paths(root, rel);

	/* Now find the cheapest of the paths for this rel */
	set_cheapest(rel);
}

/*
 * set_inherited_rel_pathlist
 *	  Build access paths for a inheritance tree rooted at rel
 *
 * inheritlist is a list of RT indexes of all tables in the inheritance tree,
 * including a duplicate of the parent itself.	Note we will not come here
 * unless there's at least one child in addition to the parent.
 *
 * NOTE: the passed-in rel and RTE will henceforth represent the appended
 * result of the whole inheritance tree.  The members of inheritlist represent
 * the individual tables --- in particular, the inheritlist member that is a
 * duplicate of the parent RTE represents the parent table alone.
 * We will generate plans to scan the individual tables that refer to
 * the inheritlist RTEs, whereas Vars elsewhere in the plan tree that
 * refer to the original RTE are taken to refer to the append output.
 * In particular, this means we have separate RelOptInfos for the parent
 * table and for the append output, which is a good thing because they're
 * not the same size.
 */
static void
set_inherited_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
						   Index rti, RangeTblEntry *rte,
						   List *inheritlist)
{
	int			parentRTindex = rti;
	Oid			parentOID = rte->relid;
	List	   *subpaths = NIL;
	ListCell   *il;

	/*
	 * XXX for now, can't handle inherited expansion of FOR UPDATE/SHARE; can
	 * we do better?
	 */
	if (list_member_int(root->parse->rowMarks, parentRTindex))
		ereport(ERROR,
				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
				 errmsg("SELECT FOR UPDATE/SHARE is not supported for inheritance queries")));

	/*
	 * We might have looked up indexes for the parent rel, but they're
	 * really not relevant to the appendrel.  Reset the pointer to avoid
	 * any confusion.
	 */
	rel->indexlist = NIL;

	/*
	 * Initialize to compute size estimates for whole inheritance tree
	 */
	rel->rows = 0;
	rel->width = 0;

	/*
	 * Generate access paths for each table in the tree (parent AND children),
	 * and pick the cheapest path for each table.
	 */
	foreach(il, inheritlist)
	{
		int			childRTindex = lfirst_int(il);
		RangeTblEntry *childrte;
		Oid			childOID;
		RelOptInfo *childrel;
		ListCell   *parentvars;
		ListCell   *childvars;

		childrte = rt_fetch(childRTindex, root->parse->rtable);
		childOID = childrte->relid;

		/*
		 * Make a RelOptInfo for the child so we can do planning. Mark it as
		 * an "other rel" since it will not be part of the main join tree.
		 */
		childrel = build_other_rel(root, childRTindex);

		/*
		 * Copy the parent's targetlist and restriction quals to the child,
		 * with attribute-number adjustment as needed.	We don't bother to
		 * copy the join quals, since we can't do any joining of the
		 * individual tables.  Also, we just zap attr_needed rather than
		 * trying to adjust it; it won't be looked at in the child.
		 */
		childrel->reltargetlist = (List *)
			adjust_inherited_attrs((Node *) rel->reltargetlist,
								   parentRTindex,
								   parentOID,
								   childRTindex,
								   childOID);
		childrel->attr_needed = NULL;
		childrel->baserestrictinfo = (List *)
			adjust_inherited_attrs((Node *) rel->baserestrictinfo,
								   parentRTindex,
								   parentOID,
								   childRTindex,
								   childOID);

		/*
		 * If we can prove we don't need to scan this child via constraint
		 * exclusion, just ignore it.  (We have to have converted the
		 * baserestrictinfo Vars before we can make the test.)
		 */
		if (constraint_exclusion)
		{
			List	   *constraint_pred;

			constraint_pred = get_relation_constraints(childOID, childrel);

			/*
			 * We do not currently enforce that CHECK constraints contain only
			 * immutable functions, so it's necessary to check here. We
			 * daren't draw conclusions from plan-time evaluation of
			 * non-immutable functions.
			 */
			if (!contain_mutable_functions((Node *) constraint_pred))
			{
				/*
				 * The constraints are effectively ANDed together, so we can
				 * just try to refute the entire collection at once.  This may
				 * allow us to make proofs that would fail if we took them
				 * individually.
				 */
				if (predicate_refuted_by(constraint_pred,
										 childrel->baserestrictinfo))
					continue;
			}
		}

		/*
		 * Compute the child's access paths, and save the cheapest.
		 */
		set_plain_rel_pathlist(root, childrel, childrte);

		subpaths = lappend(subpaths, childrel->cheapest_total_path);

		/*
		 * Propagate size information from the child back to the parent. For
		 * simplicity, we use the largest widths from any child as the parent
		 * estimates.
		 */
		rel->rows += childrel->rows;
		if (childrel->width > rel->width)
			rel->width = childrel->width;

		forboth(parentvars, rel->reltargetlist,
				childvars, childrel->reltargetlist)
		{
			Var		   *parentvar = (Var *) lfirst(parentvars);
			Var		   *childvar = (Var *) lfirst(childvars);

			if (IsA(parentvar, Var) &&IsA(childvar, Var))
			{
				int			pndx = parentvar->varattno - rel->min_attr;
				int			cndx = childvar->varattno - childrel->min_attr;

				if (childrel->attr_widths[cndx] > rel->attr_widths[pndx])
					rel->attr_widths[pndx] = childrel->attr_widths[cndx];
			}
		}
	}

	/*
	 * Finally, build Append path and install it as the only access path for