indxpath.c

来自「postgresql8.3.4源码,开源数据库」· C语言 代码 · 共 2,070 行 · 第 1/5 页

/*-------------------------------------------------------------------------
 *
 * indxpath.c
 *	  Routines to determine which indexes are usable for scanning a
 *	  given relation, and create Paths accordingly.
 *
 * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.227.2.1 2008/09/12 14:56:19 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <math.h>

#include "access/skey.h"
#include "catalog/pg_am.h"
#include "catalog/pg_operator.h"
#include "catalog/pg_opfamily.h"
#include "catalog/pg_type.h"
#include "nodes/makefuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/predtest.h"
#include "optimizer/restrictinfo.h"
#include "optimizer/var.h"
#include "utils/builtins.h"
#include "utils/lsyscache.h"
#include "utils/pg_locale.h"
#include "utils/selfuncs.h"


/*
 * DoneMatchingIndexKeys() - MACRO
 */
#define DoneMatchingIndexKeys(families) (families[0] == InvalidOid)

#define IsBooleanOpfamily(opfamily) \
	((opfamily) == BOOL_BTREE_FAM_OID || (opfamily) == BOOL_HASH_FAM_OID)


/* Per-path data used within choose_bitmap_and() */
typedef struct
{
	Path	   *path;			/* IndexPath, BitmapAndPath, or BitmapOrPath */
	List	   *quals;			/* the WHERE clauses it uses */
	List	   *preds;			/* predicates of its partial index(es) */
	Bitmapset  *clauseids;		/* quals+preds represented as a bitmapset */
} PathClauseUsage;


static List *find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
					List *clauses, List *outer_clauses,
					bool istoplevel, RelOptInfo *outer_rel,
					SaOpControl saop_control);
static List *find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
				List *clauses, List *outer_clauses,
				bool istoplevel, RelOptInfo *outer_rel);
static Path *choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
				  List *paths, RelOptInfo *outer_rel);
static int	path_usage_comparator(const void *a, const void *b);
static Cost bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
					 Path *ipath, RelOptInfo *outer_rel);
static Cost bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
					List *paths, RelOptInfo *outer_rel);
static PathClauseUsage *classify_index_clause_usage(Path *path,
							List **clauselist);
static void find_indexpath_quals(Path *bitmapqual, List **quals, List **preds);
static int	find_list_position(Node *node, List **nodelist);
static bool match_clause_to_indexcol(IndexOptInfo *index,
						 int indexcol, Oid opfamily,
						 RestrictInfo *rinfo,
						 Relids outer_relids,
						 SaOpControl saop_control);
static bool is_indexable_operator(Oid expr_op, Oid opfamily,
					  bool indexkey_on_left);
static bool match_rowcompare_to_indexcol(IndexOptInfo *index,
							 int indexcol,
							 Oid opfamily,
							 RowCompareExpr *clause,
							 Relids outer_relids);
static Relids indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel);
static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
				  Relids outer_relids);
static List *find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
					  Relids outer_relids, bool isouterjoin);
static bool match_boolean_index_clause(Node *clause, int indexcol,
						   IndexOptInfo *index);
static bool match_special_index_operator(Expr *clause, Oid opfamily,
							 bool indexkey_on_left);
static Expr *expand_boolean_index_clause(Node *clause, int indexcol,
							IndexOptInfo *index);
static List *expand_indexqual_opclause(RestrictInfo *rinfo, Oid opfamily);
static RestrictInfo *expand_indexqual_rowcompare(RestrictInfo *rinfo,
							IndexOptInfo *index,
							int indexcol);
static List *prefix_quals(Node *leftop, Oid opfamily,
			 Const *prefix, Pattern_Prefix_Status pstatus);
static List *network_prefix_quals(Node *leftop, Oid expr_op, Oid opfamily,
					 Datum rightop);
static Datum string_to_datum(const char *str, Oid datatype);
static Const *string_to_const(const char *str, Oid datatype);


/*
 * create_index_paths()
 *	  Generate all interesting index paths for the given relation.
 *	  Candidate paths are added to the rel's pathlist (using add_path).
 *
 * To be considered for an index scan, an index must match one or more
 * restriction clauses or join clauses from the query's qual condition,
 * or match the query's ORDER BY condition, or have a predicate that
 * matches the query's qual condition.
 *
 * There are two basic kinds of index scans.  A "plain" index scan uses
 * only restriction clauses (possibly none at all) in its indexqual,
 * so it can be applied in any context.  An "innerjoin" index scan uses
 * join clauses (plus restriction clauses, if available) in its indexqual.
 * Therefore it can only be used as the inner relation of a nestloop
 * join against an outer rel that includes all the other rels mentioned
 * in its join clauses.  In that context, values for the other rels'
 * attributes are available and fixed during any one scan of the indexpath.
 *
 * An IndexPath is generated and submitted to add_path() for each plain index
 * scan this routine deems potentially interesting for the current query.
 *
 * We also determine the set of other relids that participate in join
 * clauses that could be used with each index.	The actually best innerjoin
 * path will be generated for each outer relation later on, but knowing the
 * set of potential otherrels allows us to identify equivalent outer relations
 * and avoid repeated computation.
 *
 * 'rel' is the relation for which we want to generate index paths
 *
 * Note: check_partial_indexes() must have been run previously for this rel.
 */
void
create_index_paths(PlannerInfo *root, RelOptInfo *rel)
{
	List	   *indexpaths;
	List	   *bitindexpaths;
	ListCell   *l;

	/* Skip the whole mess if no indexes */
	if (rel->indexlist == NIL)
	{
		rel->index_outer_relids = NULL;
		return;
	}

	/*
	 * Examine join clauses to see which ones are potentially usable with
	 * indexes of this rel, and generate the set of all other relids that
	 * participate in such join clauses.  We'll use this set later to
	 * recognize outer rels that are equivalent for joining purposes.
	 */
	rel->index_outer_relids = indexable_outerrelids(root, rel);

	/*
	 * Find all the index paths that are directly usable for this relation
	 * (ie, are valid without considering OR or JOIN clauses).
	 */
	indexpaths = find_usable_indexes(root, rel,
									 rel->baserestrictinfo, NIL,
									 true, NULL, SAOP_FORBID);

	/*
	 * We can submit them all to add_path.	(This generates access paths for
	 * plain IndexScan plans.)	However, for the next step we will only want
	 * the ones that have some selectivity; we must discard anything that was
	 * generated solely for ordering purposes.
	 */
	bitindexpaths = NIL;
	foreach(l, indexpaths)
	{
		IndexPath  *ipath = (IndexPath *) lfirst(l);

		add_path(rel, (Path *) ipath);

		if (ipath->indexselectivity < 1.0 &&
			!ScanDirectionIsBackward(ipath->indexscandir))
			bitindexpaths = lappend(bitindexpaths, ipath);
	}

	/*
	 * Generate BitmapOrPaths for any suitable OR-clauses present in the
	 * restriction list.  Add these to bitindexpaths.
	 */
	indexpaths = generate_bitmap_or_paths(root, rel,
										  rel->baserestrictinfo, NIL,
										  NULL);
	bitindexpaths = list_concat(bitindexpaths, indexpaths);

	/*
	 * Likewise, generate paths using ScalarArrayOpExpr clauses; these can't
	 * be simple indexscans but they can be used in bitmap scans.
	 */
	indexpaths = find_saop_paths(root, rel,
								 rel->baserestrictinfo, NIL,
								 true, NULL);
	bitindexpaths = list_concat(bitindexpaths, indexpaths);

	/*
	 * If we found anything usable, generate a BitmapHeapPath for the most
	 * promising combination of bitmap index paths.
	 */
	if (bitindexpaths != NIL)
	{
		Path	   *bitmapqual;
		BitmapHeapPath *bpath;

		bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, NULL);
		bpath = create_bitmap_heap_path(root, rel, bitmapqual, NULL);
		add_path(rel, (Path *) bpath);
	}
}


/*----------
 * find_usable_indexes
 *	  Given a list of restriction clauses, find all the potentially usable
 *	  indexes for the given relation, and return a list of IndexPaths.
 *
 * The caller actually supplies two lists of restriction clauses: some
 * "current" ones and some "outer" ones.  Both lists can be used freely
 * to match keys of the index, but an index must use at least one of the
 * "current" clauses to be considered usable.  The motivation for this is
 * examples like
 *		WHERE (x = 42) AND (... OR (y = 52 AND z = 77) OR ....)
 * While we are considering the y/z subclause of the OR, we can use "x = 42"
 * as one of the available index conditions; but we shouldn't match the
 * subclause to any index on x alone, because such a Path would already have
 * been generated at the upper level.  So we could use an index on x,y,z
 * or an index on x,y for the OR subclause, but not an index on just x.
 * When dealing with a partial index, a match of the index predicate to
 * one of the "current" clauses also makes the index usable.
 *
 * If istoplevel is true (indicating we are considering the top level of a
 * rel's restriction clauses), we will include indexes in the result that
 * have an interesting sort order, even if they have no matching restriction
 * clauses.
 *
 * 'rel' is the relation for which we want to generate index paths
 * 'clauses' is the current list of clauses (RestrictInfo nodes)
 * 'outer_clauses' is the list of additional upper-level clauses
 * 'istoplevel' is true if clauses are the rel's top-level restriction list
 *		(outer_clauses must be NIL when this is true)
 * 'outer_rel' is the outer side of the join if forming an inner indexscan
 *		(so some of the given clauses are join clauses); NULL if not
 * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used
 *
 * Note: check_partial_indexes() must have been run previously.
 *----------
 */
static List *
find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
					List *clauses, List *outer_clauses,
					bool istoplevel, RelOptInfo *outer_rel,
					SaOpControl saop_control)
{
	Relids		outer_relids = outer_rel ? outer_rel->relids : NULL;
	bool		possibly_useful_pathkeys = has_useful_pathkeys(root, rel);
	List	   *result = NIL;
	List	   *all_clauses = NIL;		/* not computed till needed */
	ListCell   *ilist;

	foreach(ilist, rel->indexlist)
	{
		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
		IndexPath  *ipath;
		List	   *restrictclauses;
		List	   *index_pathkeys;
		List	   *useful_pathkeys;
		bool		useful_predicate;
		bool		found_clause;
		bool		index_is_ordered;

		/*
		 * Ignore partial indexes that do not match the query.	If a partial
		 * index is marked predOK then we know it's OK; otherwise, if we are
		 * at top level we know it's not OK (since predOK is exactly whether
		 * its predicate could be proven from the toplevel clauses).
		 * Otherwise, we have to test whether the added clauses are sufficient
		 * to imply the predicate.	If so, we could use the index in the
		 * current context.
		 *
		 * We set useful_predicate to true iff the predicate was proven using
		 * the current set of clauses.	This is needed to prevent matching a
		 * predOK index to an arm of an OR, which would be a legal but
		 * pointlessly inefficient plan.  (A better plan will be generated by
		 * just scanning the predOK index alone, no OR.)
		 */
		useful_predicate = false;
		if (index->indpred != NIL)
		{
			if (index->predOK)
			{
				if (istoplevel)
				{
					/* we know predicate was proven from these clauses */
					useful_predicate = true;
				}
			}
			else
			{
				if (istoplevel)
					continue;	/* no point in trying to prove it */

				/* Form all_clauses if not done already */
				if (all_clauses == NIL)
					all_clauses = list_concat(list_copy(clauses),
											  outer_clauses);

				if (!predicate_implied_by(index->indpred, all_clauses))
					continue;	/* can't use it at all */

				if (!predicate_implied_by(index->indpred, outer_clauses))
					useful_predicate = true;
			}
		}

		/*
		 * 1. Match the index against the available restriction clauses.
		 * found_clause is set true only if at least one of the current
		 * clauses was used (and, if saop_control is SAOP_REQUIRE, it has to
		 * have been a ScalarArrayOpExpr clause).
		 */
		restrictclauses = group_clauses_by_indexkey(index,
													clauses,
													outer_clauses,
													outer_relids,
													saop_control,
													&found_clause);

		/*
		 * Not all index AMs support scans with no restriction clauses. We
		 * can't generate a scan over an index with amoptionalkey = false
		 * unless there's at least one restriction clause.
		 */
		if (restrictclauses == NIL && !index->amoptionalkey)
			continue;

		/*
		 * 2. Compute pathkeys describing index's ordering, if any, then see
		 * how many of them are actually useful for this query.  This is not
		 * relevant unless we are at top level.
		 */
		index_is_ordered = OidIsValid(index->fwdsortop[0]);
		if (index_is_ordered && possibly_useful_pathkeys &&
			istoplevel && outer_rel == NULL)
		{
			index_pathkeys = build_index_pathkeys(root, index,
												  ForwardScanDirection);
			useful_pathkeys = truncate_useless_pathkeys(root, rel,
														index_pathkeys);
		}
		else
			useful_pathkeys = NIL;

		/*
		 * 3. Generate an indexscan path if there are relevant restriction
		 * clauses in the current clauses, OR the index ordering is
		 * potentially useful for later merging or final output ordering, OR
		 * the index has a predicate that was proven by the current clauses.
		 */
		if (found_clause || useful_pathkeys != NIL || useful_predicate)
		{
			ipath = create_index_path(root, index,
									  restrictclauses,
									  useful_pathkeys,
									  index_is_ordered ?
									  ForwardScanDirection :
									  NoMovementScanDirection,
									  outer_rel);
			result = lappend(result, ipath);
		}

		/*
		 * 4. If the index is ordered, a backwards scan might be interesting.
		 * Again, this is only interesting at top level.
		 */
		if (index_is_ordered && possibly_useful_pathkeys &&
			istoplevel && outer_rel == NULL)
		{
			index_pathkeys = build_index_pathkeys(root, index,
												  BackwardScanDirection);
			useful_pathkeys = truncate_useless_pathkeys(root, rel,
														index_pathkeys);
			if (useful_pathkeys != NIL)
			{
				ipath = create_index_path(root, index,
										  restrictclauses,
										  useful_pathkeys,
										  BackwardScanDirection,
										  outer_rel);
				result = lappend(result, ipath);
			}
		}
	}

	return result;
}


/*
 * find_saop_paths
 *		Find all the potential indexpaths that make use of ScalarArrayOpExpr
 *		clauses.  The executor only supports these in bitmap scans, not