indxpath.c

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

		 * If we didn't find a member of the index's opfamily, see whether it
		 * is a "special" indexable operator.
		 */
		if (plain_op &&
			match_special_index_operator(clause, opfamily, true))
			return true;
		return false;
	}

	if (plain_op &&
		match_index_to_operand(rightop, indexcol, index) &&
		bms_is_subset(left_relids, outer_relids) &&
		!contain_volatile_functions(leftop))
	{
		if (is_indexable_operator(expr_op, opfamily, false))
			return true;

		/*
		 * If we didn't find a member of the index's opfamily, see whether it
		 * is a "special" indexable operator.
		 */
		if (match_special_index_operator(clause, opfamily, false))
			return true;
		return false;
	}

	return false;
}

/*
 * is_indexable_operator
 *	  Does the operator match the specified index opfamily?
 *
 * If the indexkey is on the right, what we actually want to know
 * is whether the operator has a commutator operator that matches
 * the opfamily.
 */
static bool
is_indexable_operator(Oid expr_op, Oid opfamily, bool indexkey_on_left)
{
	/* Get the commuted operator if necessary */
	if (!indexkey_on_left)
	{
		expr_op = get_commutator(expr_op);
		if (expr_op == InvalidOid)
			return false;
	}

	/* OK if the (commuted) operator is a member of the index's opfamily */
	return op_in_opfamily(expr_op, opfamily);
}

/*
 * match_rowcompare_to_indexcol()
 *	  Handles the RowCompareExpr case for match_clause_to_indexcol(),
 *	  which see for comments.
 */
static bool
match_rowcompare_to_indexcol(IndexOptInfo *index,
							 int indexcol,
							 Oid opfamily,
							 RowCompareExpr *clause,
							 Relids outer_relids)
{
	Node	   *leftop,
			   *rightop;
	Oid			expr_op;

	/* Forget it if we're not dealing with a btree index */
	if (index->relam != BTREE_AM_OID)
		return false;

	/*
	 * We could do the matching on the basis of insisting that the opfamily
	 * shown in the RowCompareExpr be the same as the index column's opfamily,
	 * but that could fail in the presence of reverse-sort opfamilies: it'd be
	 * a matter of chance whether RowCompareExpr had picked the forward or
	 * reverse-sort family.  So look only at the operator, and match if it is
	 * a member of the index's opfamily (after commutation, if the indexkey is
	 * on the right).  We'll worry later about whether any additional
	 * operators are matchable to the index.
	 */
	leftop = (Node *) linitial(clause->largs);
	rightop = (Node *) linitial(clause->rargs);
	expr_op = linitial_oid(clause->opnos);

	/*
	 * These syntactic tests are the same as in match_clause_to_indexcol()
	 */
	if (match_index_to_operand(leftop, indexcol, index) &&
		bms_is_subset(pull_varnos(rightop), outer_relids) &&
		!contain_volatile_functions(rightop))
	{
		/* OK, indexkey is on left */
	}
	else if (match_index_to_operand(rightop, indexcol, index) &&
			 bms_is_subset(pull_varnos(leftop), outer_relids) &&
			 !contain_volatile_functions(leftop))
	{
		/* indexkey is on right, so commute the operator */
		expr_op = get_commutator(expr_op);
		if (expr_op == InvalidOid)
			return false;
	}
	else
		return false;

	/* We're good if the operator is the right type of opfamily member */
	switch (get_op_opfamily_strategy(expr_op, opfamily))
	{
		case BTLessStrategyNumber:
		case BTLessEqualStrategyNumber:
		case BTGreaterEqualStrategyNumber:
		case BTGreaterStrategyNumber:
			return true;
	}

	return false;
}


/****************************************************************************
 *				----  ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS	----
 ****************************************************************************/

/*
 * check_partial_indexes
 *		Check each partial index of the relation, and mark it predOK or not
 *		depending on whether the predicate is satisfied for this query.
 */
void
check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
{
	List	   *restrictinfo_list = rel->baserestrictinfo;
	ListCell   *ilist;

	foreach(ilist, rel->indexlist)
	{
		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);

		if (index->indpred == NIL)
			continue;			/* ignore non-partial indexes */

		index->predOK = predicate_implied_by(index->indpred,
											 restrictinfo_list);
	}
}

/****************************************************************************
 *				----  ROUTINES TO CHECK JOIN CLAUSES  ----
 ****************************************************************************/

/*
 * indexable_outerrelids
 *	  Finds all other relids that participate in any indexable join clause
 *	  for the specified table.	Returns a set of relids.
 */
static Relids
indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel)
{
	Relids		outer_relids = NULL;
	bool		is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
	ListCell   *lc1;

	/*
	 * Examine each joinclause in the joininfo list to see if it matches any
	 * key of any index.  If so, add the clause's other rels to the result.
	 */
	foreach(lc1, rel->joininfo)
	{
		RestrictInfo *joininfo = (RestrictInfo *) lfirst(lc1);
		Relids		other_rels;

		other_rels = bms_difference(joininfo->required_relids, rel->relids);
		if (matches_any_index(joininfo, rel, other_rels))
			outer_relids = bms_join(outer_relids, other_rels);
		else
			bms_free(other_rels);
	}

	/*
	 * We also have to look through the query's EquivalenceClasses to see if
	 * any of them could generate indexable join conditions for this rel.
	 */
	if (rel->has_eclass_joins)
	{
		foreach(lc1, root->eq_classes)
		{
			EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
			Relids		other_rels = NULL;
			bool		found_index = false;
			ListCell   *lc2;

			/*
			 * Won't generate joinclauses if const or single-member (the
			 * latter test covers the volatile case too)
			 */
			if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
				continue;

			/*
			 * Note we don't test ec_broken; if we did, we'd need a separate
			 * code path to look through ec_sources.  Checking the members
			 * anyway is OK as a possibly-overoptimistic heuristic.
			 */

			/*
			 * No point in searching if rel not mentioned in eclass (but we
			 * can't tell that for a child rel).
			 */
			if (!is_child_rel &&
				!bms_is_subset(rel->relids, cur_ec->ec_relids))
				continue;

			/*
			 * Scan members, looking for both an index match and join
			 * candidates
			 */
			foreach(lc2, cur_ec->ec_members)
			{
				EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);

				/* Join candidate? */
				if (!cur_em->em_is_child &&
					!bms_overlap(cur_em->em_relids, rel->relids))
				{
					other_rels = bms_add_members(other_rels,
												 cur_em->em_relids);
					continue;
				}

				/* Check for index match (only need one) */
				if (!found_index &&
					bms_equal(cur_em->em_relids, rel->relids) &&
					eclass_matches_any_index(cur_ec, cur_em, rel))
					found_index = true;
			}

			if (found_index)
				outer_relids = bms_join(outer_relids, other_rels);
			else
				bms_free(other_rels);
		}
	}

	return outer_relids;
}

/*
 * matches_any_index
 *	  Workhorse for indexable_outerrelids: see if a joinclause can be
 *	  matched to any index of the given rel.
 */
static bool
matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel, Relids outer_relids)
{
	ListCell   *l;

	Assert(IsA(rinfo, RestrictInfo));

	if (restriction_is_or_clause(rinfo))
	{
		foreach(l, ((BoolExpr *) rinfo->orclause)->args)
		{
			Node	   *orarg = (Node *) lfirst(l);

			/* OR arguments should be ANDs or sub-RestrictInfos */
			if (and_clause(orarg))
			{
				ListCell   *j;

				/* Recurse to examine AND items and sub-ORs */
				foreach(j, ((BoolExpr *) orarg)->args)
				{
					RestrictInfo *arinfo = (RestrictInfo *) lfirst(j);

					if (matches_any_index(arinfo, rel, outer_relids))
						return true;
				}
			}
			else
			{
				/* Recurse to examine simple clause */
				Assert(IsA(orarg, RestrictInfo));
				Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
				if (matches_any_index((RestrictInfo *) orarg, rel,
									  outer_relids))
					return true;
			}
		}

		return false;
	}

	/* Normal case for a simple restriction clause */
	foreach(l, rel->indexlist)
	{
		IndexOptInfo *index = (IndexOptInfo *) lfirst(l);
		int			indexcol = 0;
		Oid		   *families = index->opfamily;

		do
		{
			Oid			curFamily = families[0];

			if (match_clause_to_indexcol(index,
										 indexcol,
										 curFamily,
										 rinfo,
										 outer_relids,
										 SAOP_ALLOW))
				return true;

			indexcol++;
			families++;
		} while (!DoneMatchingIndexKeys(families));
	}

	return false;
}

/*
 * eclass_matches_any_index
 *	  Workhorse for indexable_outerrelids: see if an EquivalenceClass member
 *	  can be matched to any index column of the given rel.
 *
 * This is also exported for use by find_eclass_clauses_for_index_join.
 */
bool
eclass_matches_any_index(EquivalenceClass *ec, EquivalenceMember *em,
						 RelOptInfo *rel)
{
	ListCell   *l;

	foreach(l, rel->indexlist)
	{
		IndexOptInfo *index = (IndexOptInfo *) lfirst(l);
		int			indexcol = 0;
		Oid		   *families = index->opfamily;

		do
		{
			Oid			curFamily = families[0];

			/*
			 * If it's a btree index, we can reject it if its opfamily isn't
			 * compatible with the EC, since no clause generated from the
			 * EC could be used with the index.  For non-btree indexes,
			 * we can't easily tell whether clauses generated from the EC
			 * could be used with the index, so only check for expression
			 * match.  This might mean we return "true" for a useless index,
			 * but that will just cause some wasted planner cycles; it's
			 * better than ignoring useful indexes.
			 */
			if ((index->relam != BTREE_AM_OID ||
				 list_member_oid(ec->ec_opfamilies, curFamily)) &&
				match_index_to_operand((Node *) em->em_expr, indexcol, index))
				return true;

			indexcol++;
			families++;
		} while (!DoneMatchingIndexKeys(families));
	}

	return false;
}


/*
 * best_inner_indexscan
 *	  Finds the best available inner indexscans for a nestloop join
 *	  with the given rel on the inside and the given outer_rel outside.
 *
 * *cheapest_startup gets the path with least startup cost
 * *cheapest_total gets the path with least total cost (often the same path)
 * Both are set to NULL if there are no possible inner indexscans.
 *
 * We ignore ordering considerations, since a nestloop's inner scan's order
 * is uninteresting.  Hence startup cost and total cost are the only figures
 * of merit to consider.
 *
 * Note: create_index_paths() must have been run previously for this rel,
 * else the results will always be NULL.
 */
void
best_inner_indexscan(PlannerInfo *root, RelOptInfo *rel,
					 RelOptInfo *outer_rel, JoinType jointype,
					 Path **cheapest_startup, Path **cheapest_total)
{
	Relids		outer_relids;
	bool		isouterjoin;
	List	   *clause_list;
	List	   *indexpaths;
	List	   *bitindexpaths;
	ListCell   *l;
	InnerIndexscanInfo *info;
	MemoryContext oldcontext;

	/* Initialize results for failure returns */
	*cheapest_startup = *cheapest_total = NULL;

	/*
	 * Nestloop only supports inner, left, and IN joins.
	 */
	switch (jointype)
	{
		case JOIN_INNER:
		case JOIN_IN:
		case JOIN_UNIQUE_OUTER:
			isouterjoin = false;
			break;
		case JOIN_LEFT:
			isouterjoin = true;
			break;