indxpath.c

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

	/* Set up a dummy BitmapAndPath */
	apath.path.type = T_BitmapAndPath;
	apath.path.parent = rel;
	apath.bitmapquals = paths;
	cost_bitmap_and_node(&apath, root);

	/* Now we can do cost_bitmap_heap_scan */
	cost_bitmap_heap_scan(&bpath, root, rel, (Path *) &apath, outer_rel);

	return bpath.total_cost;
}


/*
 * classify_index_clause_usage
 *		Construct a PathClauseUsage struct describing the WHERE clauses and
 *		index predicate clauses used by the given indexscan path.
 *		We consider two clauses the same if they are equal().
 *
 * At some point we might want to migrate this info into the Path data
 * structure proper, but for the moment it's only needed within
 * choose_bitmap_and().
 *
 * *clauselist is used and expanded as needed to identify all the distinct
 * clauses seen across successive calls.  Caller must initialize it to NIL
 * before first call of a set.
 */
static PathClauseUsage *
classify_index_clause_usage(Path *path, List **clauselist)
{
	PathClauseUsage *result;
	Bitmapset  *clauseids;
	ListCell   *lc;

	result = (PathClauseUsage *) palloc(sizeof(PathClauseUsage));
	result->path = path;

	/* Recursively find the quals and preds used by the path */
	result->quals = NIL;
	result->preds = NIL;
	find_indexpath_quals(path, &result->quals, &result->preds);

	/* Build up a bitmapset representing the quals and preds */
	clauseids = NULL;
	foreach(lc, result->quals)
	{
		Node	   *node = (Node *) lfirst(lc);

		clauseids = bms_add_member(clauseids,
								   find_list_position(node, clauselist));
	}
	foreach(lc, result->preds)
	{
		Node	   *node = (Node *) lfirst(lc);

		clauseids = bms_add_member(clauseids,
								   find_list_position(node, clauselist));
	}
	result->clauseids = clauseids;

	return result;
}


/*
 * find_indexpath_quals
 *
 * Given the Path structure for a plain or bitmap indexscan, extract lists
 * of all the indexquals and index predicate conditions used in the Path.
 * These are appended to the initial contents of *quals and *preds (hence
 * caller should initialize those to NIL).
 *
 * This is sort of a simplified version of make_restrictinfo_from_bitmapqual;
 * here, we are not trying to produce an accurate representation of the AND/OR
 * semantics of the Path, but just find out all the base conditions used.
 *
 * The result lists contain pointers to the expressions used in the Path,
 * but all the list cells are freshly built, so it's safe to destructively
 * modify the lists (eg, by concat'ing with other lists).
 */
static void
find_indexpath_quals(Path *bitmapqual, List **quals, List **preds)
{
	if (IsA(bitmapqual, BitmapAndPath))
	{
		BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
		ListCell   *l;

		foreach(l, apath->bitmapquals)
		{
			find_indexpath_quals((Path *) lfirst(l), quals, preds);
		}
	}
	else if (IsA(bitmapqual, BitmapOrPath))
	{
		BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
		ListCell   *l;

		foreach(l, opath->bitmapquals)
		{
			find_indexpath_quals((Path *) lfirst(l), quals, preds);
		}
	}
	else if (IsA(bitmapqual, IndexPath))
	{
		IndexPath  *ipath = (IndexPath *) bitmapqual;

		*quals = list_concat(*quals, get_actual_clauses(ipath->indexclauses));
		*preds = list_concat(*preds, list_copy(ipath->indexinfo->indpred));
	}
	else
		elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
}


/*
 * find_list_position
 *		Return the given node's position (counting from 0) in the given
 *		list of nodes.	If it's not equal() to any existing list member,
 *		add it at the end, and return that position.
 */
static int
find_list_position(Node *node, List **nodelist)
{
	int			i;
	ListCell   *lc;

	i = 0;
	foreach(lc, *nodelist)
	{
		Node	   *oldnode = (Node *) lfirst(lc);

		if (equal(node, oldnode))
			return i;
		i++;
	}

	*nodelist = lappend(*nodelist, node);

	return i;
}


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


/*
 * group_clauses_by_indexkey
 *	  Find restriction clauses that can be used with an index.
 *
 * Returns a list of sublists of RestrictInfo nodes for clauses that can be
 * used with this index.  Each sublist contains clauses that can be used
 * with one index key (in no particular order); the top list is ordered by
 * index key.  (This is depended on by expand_indexqual_conditions().)
 *
 * We can use clauses from either the current clauses or outer_clauses lists,
 * but *found_clause is set TRUE only if we used at least one clause from
 * the "current clauses" list.	See find_usable_indexes() for motivation.
 *
 * outer_relids determines what Vars will be allowed on the other side
 * of a possible index qual; see match_clause_to_indexcol().
 *
 * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used.
 * When it's SAOP_REQUIRE, *found_clause is set TRUE only if we used at least
 * one ScalarArrayOpExpr from the current clauses list.
 *
 * If the index has amoptionalkey = false, we give up and return NIL when
 * there are no restriction clauses matching the first index key.  Otherwise,
 * we return NIL if there are no restriction clauses matching any index key.
 * A non-NIL result will have one (possibly empty) sublist for each index key.
 *
 * Example: given an index on (A,B,C), we would return ((C1 C2) () (C3 C4))
 * if we find that clauses C1 and C2 use column A, clauses C3 and C4 use
 * column C, and no clauses use column B.
 *
 * Note: in some circumstances we may find the same RestrictInfos coming
 * from multiple places.  Defend against redundant outputs by using
 * list_append_unique_ptr (pointer equality should be good enough).
 */
List *
group_clauses_by_indexkey(IndexOptInfo *index,
						  List *clauses, List *outer_clauses,
						  Relids outer_relids,
						  SaOpControl saop_control,
						  bool *found_clause)
{
	List	   *clausegroup_list = NIL;
	bool		found_outer_clause = false;
	int			indexcol = 0;
	Oid		   *families = index->opfamily;

	*found_clause = false;		/* default result */

	if (clauses == NIL && outer_clauses == NIL)
		return NIL;				/* cannot succeed */

	do
	{
		Oid			curFamily = families[0];
		List	   *clausegroup = NIL;
		ListCell   *l;

		/* check the current clauses */
		foreach(l, clauses)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

			Assert(IsA(rinfo, RestrictInfo));
			if (match_clause_to_indexcol(index,
										 indexcol,
										 curFamily,
										 rinfo,
										 outer_relids,
										 saop_control))
			{
				clausegroup = list_append_unique_ptr(clausegroup, rinfo);
				if (saop_control != SAOP_REQUIRE ||
					IsA(rinfo->clause, ScalarArrayOpExpr))
					*found_clause = true;
			}
		}

		/* check the outer clauses */
		foreach(l, outer_clauses)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

			Assert(IsA(rinfo, RestrictInfo));
			if (match_clause_to_indexcol(index,
										 indexcol,
										 curFamily,
										 rinfo,
										 outer_relids,
										 saop_control))
			{
				clausegroup = list_append_unique_ptr(clausegroup, rinfo);
				found_outer_clause = true;
			}
		}

		/*
		 * If no clauses match this key, check for amoptionalkey restriction.
		 */
		if (clausegroup == NIL && !index->amoptionalkey && indexcol == 0)
			return NIL;

		clausegroup_list = lappend(clausegroup_list, clausegroup);

		indexcol++;
		families++;

	} while (!DoneMatchingIndexKeys(families));

	if (!*found_clause && !found_outer_clause)
		return NIL;				/* no indexable clauses anywhere */

	return clausegroup_list;
}


/*
 * match_clause_to_indexcol()
 *	  Determines whether a restriction clause matches a column of an index.
 *
 *	  To match a normal index, the clause:
 *
 *	  (1)  must be in the form (indexkey op const) or (const op indexkey);
 *		   and
 *	  (2)  must contain an operator which is in the same family as the index
 *		   operator for this column, or is a "special" operator as recognized
 *		   by match_special_index_operator().
 *
 *	  Our definition of "const" is pretty liberal: we allow Vars belonging
 *	  to the caller-specified outer_relids relations (which had better not
 *	  include the relation whose index is being tested).  outer_relids should
 *	  be NULL when checking simple restriction clauses, and the outer side
 *	  of the join when building a join inner scan.	Other than that, the
 *	  only thing we don't like is volatile functions.
 *
 *	  Note: in most cases we already know that the clause as a whole uses
 *	  vars from the interesting set of relations.  The reason for the
 *	  outer_relids test is to reject clauses like (a.f1 OP (b.f2 OP a.f3));
 *	  that's not processable by an indexscan nestloop join on A, whereas
 *	  (a.f1 OP (b.f2 OP c.f3)) is.
 *
 *	  Presently, the executor can only deal with indexquals that have the
 *	  indexkey on the left, so we can only use clauses that have the indexkey
 *	  on the right if we can commute the clause to put the key on the left.
 *	  We do not actually do the commuting here, but we check whether a
 *	  suitable commutator operator is available.
 *
 *	  It is also possible to match RowCompareExpr clauses to indexes (but
 *	  currently, only btree indexes handle this).  In this routine we will
 *	  report a match if the first column of the row comparison matches the
 *	  target index column.	This is sufficient to guarantee that some index
 *	  condition can be constructed from the RowCompareExpr --- whether the
 *	  remaining columns match the index too is considered in
 *	  expand_indexqual_rowcompare().
 *
 *	  It is also possible to match ScalarArrayOpExpr clauses to indexes, when
 *	  the clause is of the form "indexkey op ANY (arrayconst)".  Since the
 *	  executor can only handle these in the context of bitmap index scans,
 *	  our caller specifies whether to allow these or not.
 *
 *	  For boolean indexes, it is also possible to match the clause directly
 *	  to the indexkey; or perhaps the clause is (NOT indexkey).
 *
 * 'index' is the index of interest.
 * 'indexcol' is a column number of 'index' (counting from 0).
 * 'opfamily' is the corresponding operator family.
 * 'rinfo' is the clause to be tested (as a RestrictInfo node).
 * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used.
 *
 * Returns true if the clause can be used with this index key.
 *
 * NOTE:  returns false if clause is an OR or AND clause; it is the
 * responsibility of higher-level routines to cope with those.
 */
static bool
match_clause_to_indexcol(IndexOptInfo *index,
						 int indexcol,
						 Oid opfamily,
						 RestrictInfo *rinfo,
						 Relids outer_relids,
						 SaOpControl saop_control)
{
	Expr	   *clause = rinfo->clause;
	Node	   *leftop,
			   *rightop;
	Relids		left_relids;
	Relids		right_relids;
	Oid			expr_op;
	bool		plain_op;

	/*
	 * Never match pseudoconstants to indexes.	(Normally this could not
	 * happen anyway, since a pseudoconstant clause couldn't contain a Var,
	 * but what if someone builds an expression index on a constant? It's not
	 * totally unreasonable to do so with a partial index, either.)
	 */
	if (rinfo->pseudoconstant)
		return false;

	/* First check for boolean-index cases. */
	if (IsBooleanOpfamily(opfamily))
	{
		if (match_boolean_index_clause((Node *) clause, indexcol, index))
			return true;
	}

	/*
	 * Clause must be a binary opclause, or possibly a ScalarArrayOpExpr
	 * (which is always binary, by definition).  Or it could be a
	 * RowCompareExpr, which we pass off to match_rowcompare_to_indexcol().
	 * Or, if the index supports it, we can handle IS NULL clauses.
	 */
	if (is_opclause(clause))
	{
		leftop = get_leftop(clause);
		rightop = get_rightop(clause);
		if (!leftop || !rightop)
			return false;
		left_relids = rinfo->left_relids;
		right_relids = rinfo->right_relids;
		expr_op = ((OpExpr *) clause)->opno;
		plain_op = true;
	}
	else if (saop_control != SAOP_FORBID &&
			 clause && IsA(clause, ScalarArrayOpExpr))
	{
		ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;

		/* We only accept ANY clauses, not ALL */
		if (!saop->useOr)
			return false;
		leftop = (Node *) linitial(saop->args);
		rightop = (Node *) lsecond(saop->args);
		left_relids = NULL;		/* not actually needed */
		right_relids = pull_varnos(rightop);
		expr_op = saop->opno;
		plain_op = false;
	}
	else if (clause && IsA(clause, RowCompareExpr))
	{
		return match_rowcompare_to_indexcol(index, indexcol, opfamily,
											(RowCompareExpr *) clause,
											outer_relids);
	}
	else if (index->amsearchnulls && IsA(clause, NullTest))
	{
		NullTest   *nt = (NullTest *) clause;

		if (nt->nulltesttype == IS_NULL &&
			match_index_to_operand((Node *) nt->arg, indexcol, index))
			return true;
		return false;
	}
	else
		return false;

	/*
	 * Check for clauses of the form: (indexkey operator constant) or
	 * (constant operator indexkey).  See above notes about const-ness.
	 */
	if (match_index_to_operand(leftop, indexcol, index) &&
		bms_is_subset(right_relids, outer_relids) &&
		!contain_volatile_functions(rightop))
	{
		if (is_indexable_operator(expr_op, opfamily, true))
			return true;

		/*