indxpath.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * indxpath.c
 *	  Routines to determine which indices are usable for scanning a
 *	  given relation
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.57.2.1 1999/09/14 20:26:02 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */
#include <math.h>

#include "postgres.h"

#include "access/attnum.h"
#include "access/heapam.h"
#include "access/nbtree.h"
#include "catalog/catname.h"
#include "catalog/pg_amop.h"
#include "catalog/pg_type.h"
#include "executor/executor.h"
#include "fmgr.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/pg_list.h"
#include "nodes/relation.h"
#include "optimizer/clauses.h"
#include "optimizer/restrictinfo.h"
#include "optimizer/cost.h"
#include "optimizer/internal.h"
#include "optimizer/keys.h"
#include "optimizer/ordering.h"
#include "optimizer/paths.h"
#include "optimizer/plancat.h"
#include "optimizer/pathnode.h"
#include "optimizer/xfunc.h"
#include "parser/parsetree.h"	/* for getrelid() */
#include "parser/parse_expr.h"	/* for exprType() */
#include "parser/parse_oper.h"	/* for oprid() and oper() */
#include "parser/parse_coerce.h"/* for IS_BINARY_COMPATIBLE() */
#include "utils/lsyscache.h"


static void match_index_orclauses(RelOptInfo *rel, RelOptInfo *index, int indexkey,
					  int xclass, List *restrictinfo_list);
static bool match_index_to_operand(int indexkey, Expr *operand,
					   RelOptInfo *rel, RelOptInfo *index);
static List *match_index_orclause(RelOptInfo *rel, RelOptInfo *index, int indexkey,
			 int xclass, List *or_clauses, List *other_matching_indices);
static List *group_clauses_by_indexkey(RelOptInfo *rel, RelOptInfo *index,
				  int *indexkeys, Oid *classes, List *restrictinfo_list);
static List *group_clauses_by_ikey_for_joins(RelOptInfo *rel, RelOptInfo *index,
								int *indexkeys, Oid *classes, List *join_cinfo_list, List *restr_cinfo_list);
static RestrictInfo *match_clause_to_indexkey(RelOptInfo *rel, RelOptInfo *index, int indexkey,
					  int xclass, RestrictInfo *restrictInfo, bool join);
static bool pred_test(List *predicate_list, List *restrictinfo_list,
		  List *joininfo_list);
static bool one_pred_test(Expr *predicate, List *restrictinfo_list);
static bool one_pred_clause_expr_test(Expr *predicate, Node *clause);
static bool one_pred_clause_test(Expr *predicate, Node *clause);
static bool clause_pred_clause_test(Expr *predicate, Node *clause);
static List *indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index,
					  List *joininfo_list, List *restrictinfo_list);
static List *index_innerjoin(Query *root, RelOptInfo *rel,
				List *clausegroup_list, RelOptInfo *index);
static List *create_index_path_group(Query *root, RelOptInfo *rel, RelOptInfo *index,
						List *clausegroup_list, bool join);
static List *add_index_paths(List *indexpaths, List *new_indexpaths);
static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index);


/* find_index_paths()
 *	  Finds all possible index paths by determining which indices in the
 *	  list 'indices' are usable.
 *
 *	  To be usable, an index must match against either a set of
 *	  restriction clauses or join clauses.
 *
 *	  Note that the current implementation requires that there exist
 *	  matching clauses for every key in the index (i.e., no partial
 *	  matches are allowed).
 *
 *	  If an index can't be used with restriction clauses, but its keys
 *	  match those of the result sort order (according to information stored
 *	  within 'sortkeys'), then the index is also considered.
 *
 * 'rel' is the relation entry to which these index paths correspond
 * 'indices' is a list of possible index paths
 * 'restrictinfo_list' is a list of restriction restrictinfo nodes for 'rel'
 * 'joininfo_list' is a list of joininfo nodes for 'rel'
 * 'sortkeys' is a node describing the result sort order (from
 *		(find_sortkeys))
 *
 * Returns a list of index nodes.
 *
 */
List *
create_index_paths(Query *root,
				   RelOptInfo *rel,
				   List *indices,
				   List *restrictinfo_list,
				   List *joininfo_list)
{
	List	   *scanclausegroups = NIL;
	List	   *scanpaths = NIL;
	RelOptInfo *index = (RelOptInfo *) NULL;
	List	   *joinclausegroups = NIL;
	List	   *joinpaths = NIL;
	List	   *retval = NIL;
	List	   *ilist;

	foreach(ilist, indices)
	{
		index = (RelOptInfo *) lfirst(ilist);

		/*
		 * If this is a partial index, return if it fails the predicate
		 * test
		 */
		if (index->indpred != NIL)
			if (!pred_test(index->indpred, restrictinfo_list, joininfo_list))
				continue;

		/*
		 * 1. Try matching the index against subclauses of an 'or' clause.
		 * The fields of the restrictinfo nodes are marked with lists of
		 * the matching indices.  No path are actually created.  We
		 * currently only look to match the first key.	We don't find
		 * multi-key index cases where an AND matches the first key, and
		 * the OR matches the second key.
		 */
		match_index_orclauses(rel,
							  index,
							  index->indexkeys[0],
							  index->classlist[0],
							  restrictinfo_list);

		/*
		 * 2. If the keys of this index match any of the available
		 * restriction clauses, then create pathnodes corresponding to
		 * each group of usable clauses.
		 */
		scanclausegroups = group_clauses_by_indexkey(rel,
													 index,
													 index->indexkeys,
													 index->classlist,
													 restrictinfo_list);

		scanpaths = NIL;
		if (scanclausegroups != NIL)
			scanpaths = create_index_path_group(root,
												rel,
												index,
												scanclausegroups,
												false);

		/*
		 * 3. If this index can be used with any join clause, then create
		 * pathnodes for each group of usable clauses.	An index can be
		 * used with a join clause if its ordering is useful for a
		 * mergejoin, or if the index can possibly be used for scanning
		 * the inner relation of a nestloop join.
		 */
		joinclausegroups = indexable_joinclauses(rel, index, joininfo_list, restrictinfo_list);
		joinpaths = NIL;

		if (joinclausegroups != NIL)
		{
			joinpaths = create_index_path_group(root, rel,
												index,
												joinclausegroups,
												true);
			rel->innerjoin = nconc(rel->innerjoin,
								   index_innerjoin(root, rel,
											   joinclausegroups, index));
		}

		/*
		 * Some sanity checks to make sure that the indexpath is valid.
		 */
		if (joinpaths != NULL)
			retval = add_index_paths(joinpaths, retval);
		if (scanpaths != NULL)
			retval = add_index_paths(scanpaths, retval);
	}

	return retval;

}


/****************************************************************************
 *		----  ROUTINES TO MATCH 'OR' CLAUSES  ----
 ****************************************************************************/


/*
 * match_index_orclauses
 *	  Attempt to match an index against subclauses within 'or' clauses.
 *	  If the index does match, then the clause is marked with information
 *	  about the index.
 *
 *	  Essentially, this adds 'index' to the list of indices in the
 *	  RestrictInfo field of each of the clauses which it matches.
 *
 * 'rel' is the node of the relation on which the index is defined.
 * 'index' is the index node.
 * 'indexkey' is the (single) key of the index
 * 'class' is the class of the operator corresponding to 'indexkey'.
 * 'restrictinfo_list' is the list of available restriction clauses.
 *
 * Returns nothing.
 *
 */
static void
match_index_orclauses(RelOptInfo *rel,
					  RelOptInfo *index,
					  int indexkey,
					  int xclass,
					  List *restrictinfo_list)
{
	RestrictInfo *restrictinfo = (RestrictInfo *) NULL;
	List	   *i = NIL;

	foreach(i, restrictinfo_list)
	{
		restrictinfo = (RestrictInfo *) lfirst(i);
		if (valid_or_clause(restrictinfo))
		{

			/*
			 * Mark the 'or' clause with a list of indices which match
			 * each of its subclauses.	The list is generated by adding
			 * 'index' to the existing list where appropriate.
			 */
			restrictinfo->indexids = match_index_orclause(rel, index, indexkey,
														  xclass,
											  restrictinfo->clause->args,
												 restrictinfo->indexids);
		}
	}
}

/* match_index_to_operand()
 *	  Generalize test for a match between an existing index's key
 *	  and the operand on the rhs of a restriction clause.  Now check
 *	  for functional indices as well.
 */
static bool
match_index_to_operand(int indexkey,
					   Expr *operand,
					   RelOptInfo *rel,
					   RelOptInfo *index)
{
	bool		result;

	/*
	 * Normal index.
	 */
	if (index->indproc == InvalidOid)
	{
		result = match_indexkey_operand(indexkey, (Var *) operand, rel);
		return result;
	}

	/*
	 * functional index check
	 */
	result = function_index_operand(operand, rel, index);
	return result;
}

/*
 * match_index_orclause
 *	  Attempts to match an index against the subclauses of an 'or' clause.
 *
 *	  A match means that:
 *	  (1) the operator within the subclause can be used with one
 *				of the index's operator classes, and
 *	  (2) there is a usable key that matches the variable within a
 *				searchable clause.
 *
 * 'or_clauses' are the remaining subclauses within the 'or' clause
 * 'other_matching_indices' is the list of information on other indices
 *		that have already been matched to subclauses within this
 *		particular 'or' clause (i.e., a list previously generated by
 *		this routine)
 *
 * Returns a list of the form ((a b c) (d e f) nil (g h) ...) where
 * a,b,c are nodes of indices that match the first subclause in
 * 'or-clauses', d,e,f match the second subclause, no indices
 * match the third, g,h match the fourth, etc.
 */
static List *
match_index_orclause(RelOptInfo *rel,
					 RelOptInfo *index,
					 int indexkey,
					 int xclass,
					 List *or_clauses,
					 List *other_matching_indices)
{
	Node	   *clause = NULL;
	List	   *matching_indices = other_matching_indices;
	List	   *index_list = NIL;
	List	   *clist;

	/* first time through, we create index list */
	if (!other_matching_indices)
	{
		foreach(clist, or_clauses)
			matching_indices = lcons(NIL, matching_indices);
	}
	else
		matching_indices = other_matching_indices;

	index_list = matching_indices;

	foreach(clist, or_clauses)
	{
		clause = lfirst(clist);

		if (is_opclause(clause))
		{
			Expr	   *left = (Expr *) get_leftop((Expr *) clause);
			Expr	   *right = (Expr *) get_rightop((Expr *) clause);

			if (left && right &&
				op_class(((Oper *) ((Expr *) clause)->oper)->opno,
						 xclass, index->relam) &&
				((IsA(right, Const) &&
				  match_index_to_operand(indexkey, left, rel, index)) ||
				 (IsA(left, Const) &&
				  match_index_to_operand(indexkey, right, rel, index))))
				lfirst(matching_indices) = lcons(index,
											   lfirst(matching_indices));
		}

		matching_indices = lnext(matching_indices);
	}

	return index_list;
}

/****************************************************************************
 *				----  ROUTINES TO CHECK RESTRICTIONS  ----
 ****************************************************************************/


/*
 * DoneMatchingIndexKeys() - MACRO
 *
 * Determine whether we should continue matching index keys in a clause.
 * Depends on if there are more to match or if this is a functional index.
 * In the latter case we stop after the first match since the there can
 * be only key (i.e. the function's return value) and the attributes in
 * keys list represent the arguments to the function.  -mer 3 Oct. 1991
 */
#define DoneMatchingIndexKeys(indexkeys, index) \
		(indexkeys[0] == 0 || \
		 (index->indproc != InvalidOid))

/*
 * group_clauses_by_indexkey
 *	  Determines whether there are clauses which will match each and every
 *	  one of the remaining keys of an index.
 *
 * 'rel' is the node of the relation corresponding to the index.
 * 'indexkeys' are the remaining index keys to be matched.
 * 'classes' are the classes of the index operators on those keys.
 * 'clauses' is either:
 *		(1) the list of available restriction clauses on a single
 *				relation, or
 *		(2) a list of join clauses between 'rel' and a fixed set of
 *				relations,
 *		depending on the value of 'join'.
 *
 *		NOTE: it works now for restriction clauses only. - vadim 03/18/97
 *
 * Returns all possible groups of clauses that will match (given that
 * one or more clauses can match any of the remaining keys).
 * E.g., if you have clauses A, B, and C, ((A B) (A C)) might be
 * returned for an index with 2 keys.
 *
 */
static List *
group_clauses_by_indexkey(RelOptInfo *rel,
						  RelOptInfo *index,
						  int *indexkeys,
						  Oid *classes,
						  List *restrictinfo_list)
{
	List	   *curCinfo = NIL;
	RestrictInfo *matched_clause = (RestrictInfo *) NULL;
	List	   *clausegroup = NIL;
	int			curIndxKey;
	Oid			curClass;

	if (restrictinfo_list == NIL || indexkeys[0] == 0)
		return NIL;

	do
	{
		List	   *tempgroup = NIL;

		curIndxKey = indexkeys[0];
		curClass = classes[0];

		foreach(curCinfo, restrictinfo_list)
		{
			RestrictInfo *temp = (RestrictInfo *) lfirst(curCinfo);

			matched_clause = match_clause_to_indexkey(rel,
													  index,
													  curIndxKey,
													  curClass,
													  temp,
													  false);
			if (!matched_clause)
				continue;

			tempgroup = lappend(tempgroup, matched_clause);
		}
		if (tempgroup == NIL)
			break;

		clausegroup = nconc(clausegroup, tempgroup);

		indexkeys++;
		classes++;

	} while (!DoneMatchingIndexKeys(indexkeys, index));

	/* clausegroup holds all matched clauses ordered by indexkeys */

	if (clausegroup != NIL)
		return lcons(clausegroup, NIL);
	return NIL;
}

/*
 * group_clauses_by_ikey_for_joins
 *	  special edition of group_clauses_by_indexkey - will
 *	  match join & restriction clauses. See comment in indexable_joinclauses.
 *		- vadim 03/18/97
 *
 */
static List *
group_clauses_by_ikey_for_joins(RelOptInfo *rel,
								RelOptInfo *index,
								int *indexkeys,
								Oid *classes,
								List *join_cinfo_list,
								List *restr_cinfo_list)
{
	List	   *curCinfo = NIL;
	RestrictInfo *matched_clause = (RestrictInfo *) NULL;
	List	   *clausegroup = NIL;
	int			curIndxKey;
	Oid			curClass;
	bool		jfound = false;

	if (join_cinfo_list == NIL || indexkeys[0] == 0)
		return NIL;

	do
	{
		List	   *tempgroup = NIL;

		curIndxKey = indexkeys[0];
		curClass = classes[0];

		foreach(curCinfo, join_cinfo_list)
		{
			RestrictInfo *temp = (RestrictInfo *) lfirst(curCinfo);

			matched_clause = match_clause_to_indexkey(rel,
													  index,
													  curIndxKey,
													  curClass,