indxpath.c

来自「PostgreSQL7.4.6 for Linux」· C语言 代码 · 共 2,156 行 · 第 1/5 页

	do
	{
		Oid			curClass = classes[0];
		FastList	clausegroup;
		List	   *item;

		FastListInit(&clausegroup);
		if (and_clause((Node *) orsubclause))
		{
			foreach(item, ((BoolExpr *) orsubclause)->args)
			{
				Expr	   *subsubclause = (Expr *) lfirst(item);

				if (match_clause_to_indexcol(rel, index,
											 indexcol, curClass,
											 subsubclause))
					FastConc(&clausegroup,
							 expand_indexqual_condition(subsubclause,
														curClass));
			}
		}
		else if (match_clause_to_indexcol(rel, index,
										  indexcol, curClass,
										  orsubclause))
			FastConc(&clausegroup,
					 expand_indexqual_condition(orsubclause,
												curClass));

		/*
		 * If we found no clauses for this indexkey in the OR subclause
		 * itself, try looking in the rel's top-level restriction list.
		 */
		if (FastListValue(&clausegroup) == NIL)
		{
			foreach(item, rel->baserestrictinfo)
			{
				RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);

				if (match_clause_to_indexcol(rel, index,
											 indexcol, curClass,
											 rinfo->clause))
					FastConc(&clausegroup,
							 expand_indexqual_condition(rinfo->clause,
														curClass));
			}
		}

		/*
		 * If still no clauses match this key, we're done; we don't want
		 * to look at keys to its right.
		 */
		if (FastListValue(&clausegroup) == NIL)
			break;

		FastConcFast(&quals, &clausegroup);

		indexcol++;
		classes++;

	} while (!DoneMatchingIndexKeys(classes));

	if (FastListValue(&quals) == NIL)
		elog(ERROR, "no matching OR clause");

	return FastListValue(&quals);
}


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


/*
 * group_clauses_by_indexkey
 *	  Find restriction clauses that can be used with an index.
 *
 * 'rel' is the node of the relation itself.
 * 'index' is a index on 'rel'.
 *
 * 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().)
 *
 * Note that in a multi-key index, we stop if we find a key that cannot be
 * used with any clause.  For example, given an index on (A,B,C), we might
 * return ((C1 C2) (C3 C4)) if we find that clauses C1 and C2 use column A,
 * clauses C3 and C4 use column B, and no clauses use column C.  But if
 * no clauses match B we will return ((C1 C2)), whether or not there are
 * clauses matching column C, because the executor couldn't use them anyway.
 * Therefore, there are no empty sublists in the result.
 */
static List *
group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index)
{
	FastList	clausegroup_list;
	List	   *restrictinfo_list = rel->baserestrictinfo;
	int			indexcol = 0;
	Oid		   *classes = index->classlist;

	if (restrictinfo_list == NIL)
		return NIL;

	FastListInit(&clausegroup_list);
	do
	{
		Oid			curClass = classes[0];
		FastList	clausegroup;
		List	   *i;

		FastListInit(&clausegroup);
		foreach(i, restrictinfo_list)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);

			if (match_clause_to_indexcol(rel,
										 index,
										 indexcol,
										 curClass,
										 rinfo->clause))
				FastAppend(&clausegroup, rinfo);
		}

		/*
		 * If no clauses match this key, we're done; we don't want to look
		 * at keys to its right.
		 */
		if (FastListValue(&clausegroup) == NIL)
			break;

		FastAppend(&clausegroup_list, FastListValue(&clausegroup));

		indexcol++;
		classes++;

	} while (!DoneMatchingIndexKeys(classes));

	return FastListValue(&clausegroup_list);
}

/*
 * group_clauses_by_indexkey_for_join
 *	  Generate a list of sublists of clauses that can be used with an index
 *	  to scan the inner side of a nestloop join.
 *
 * This is much like group_clauses_by_indexkey(), but we consider both
 * join and restriction clauses.  Any joinclause that uses only otherrels
 * in the specified outer_relids is fair game.	But there must be at least
 * one such joinclause in the final list, otherwise we return NIL indicating
 * that this index isn't interesting as an inner indexscan.  (A scan using
 * only restriction clauses shouldn't be created here, because a regular Path
 * will already have been generated for it.)
 */
static List *
group_clauses_by_indexkey_for_join(Query *root,
								   RelOptInfo *rel, IndexOptInfo *index,
								   Relids outer_relids,
								   JoinType jointype, bool isouterjoin)
{
	FastList	clausegroup_list;
	bool		jfound = false;
	int			indexcol = 0;
	Oid		   *classes = index->classlist;

	FastListInit(&clausegroup_list);
	do
	{
		Oid			curClass = classes[0];
		FastList	clausegroup;
		List	   *i;

		FastListInit(&clausegroup);

		/* Look for joinclauses that are usable with given outer_relids */
		foreach(i, rel->joininfo)
		{
			JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
			List	   *j;

			if (!bms_is_subset(joininfo->unjoined_relids, outer_relids))
				continue;

			foreach(j, joininfo->jinfo_restrictinfo)
			{
				RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);

				/* Can't use pushed-down clauses in outer join */
				if (isouterjoin && rinfo->ispusheddown)
					continue;

				if (match_join_clause_to_indexcol(rel,
												  index,
												  indexcol,
												  curClass,
												  rinfo->clause))
				{
					FastAppend(&clausegroup, rinfo);
					jfound = true;
				}
			}
		}

		/*
		 * If we found join clauses in more than one joininfo list, we may
		 * now have clauses that are known redundant.  Get rid of 'em.
		 * (There is no point in looking at restriction clauses, because
		 * remove_redundant_join_clauses will never think they are
		 * redundant, so we do this before adding restriction clauses to
		 * the clause group.)
		 */
		if (FastListValue(&clausegroup) != NIL)
		{
			List	   *nl;

			nl = remove_redundant_join_clauses(root,
											 FastListValue(&clausegroup),
											   jointype);
			FastListFromList(&clausegroup, nl);
		}

		/* We can also use plain restriction clauses for the rel */
		foreach(i, rel->baserestrictinfo)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);

			/* Can't use pushed-down clauses in outer join */
			if (isouterjoin && rinfo->ispusheddown)
				continue;

			if (match_clause_to_indexcol(rel,
										 index,
										 indexcol,
										 curClass,
										 rinfo->clause))
				FastAppend(&clausegroup, rinfo);
		}

		/*
		 * If no clauses match this key, we're done; we don't want to look
		 * at keys to its right.
		 */
		if (FastListValue(&clausegroup) == NIL)
			break;

		FastAppend(&clausegroup_list, FastListValue(&clausegroup));

		indexcol++;
		classes++;

	} while (!DoneMatchingIndexKeys(classes));

	/* if no join clause was matched then forget it, per comments above */
	if (!jfound)
		return NIL;

	return FastListValue(&clausegroup_list);
}


/*
 * match_clause_to_indexcol()
 *	  Determines whether a restriction clause matches a column of an index.
 *
 *	  To match, 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 class as the index
 *		   operator for this column, or is a "special" operator as recognized
 *		   by match_special_index_operator().
 *
 *	  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.
 *
 * 'rel' is the relation of interest.
 * 'index' is an index on 'rel'.
 * 'indexcol' is a column number of 'index' (counting from 0).
 * 'opclass' is the corresponding operator class.
 * 'clause' is the clause to be tested.
 *
 * 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(RelOptInfo *rel,
						 IndexOptInfo *index,
						 int indexcol,
						 Oid opclass,
						 Expr *clause)
{
	Node	   *leftop,
			   *rightop;

	/* Clause must be a binary opclause. */
	if (!is_opclause(clause))
		return false;
	leftop = get_leftop(clause);
	rightop = get_rightop(clause);
	if (!leftop || !rightop)
		return false;

	/*
	 * Check for clauses of the form: (indexkey operator constant) or
	 * (constant operator indexkey). Anything that is a "pseudo constant"
	 * expression will do.
	 */
	if (match_index_to_operand(leftop, indexcol, rel, index) &&
		is_pseudo_constant_clause(rightop))
	{
		if (is_indexable_operator(clause, opclass, true))
			return true;

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

	if (match_index_to_operand(rightop, indexcol, rel, index) &&
		is_pseudo_constant_clause(leftop))
	{
		if (is_indexable_operator(clause, opclass, false))
			return true;

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

	return false;
}

/*
 * match_join_clause_to_indexcol()
 *	  Determines whether a join clause matches a column of an index.
 *
 *	  To match, the clause:
 *
 *	  (1)  must be in the form (indexkey op others) or (others op indexkey),
 *		   where others is an expression involving only vars of the other
 *		   relation(s); and
 *	  (2)  must contain an operator which is in the same class as the index
 *		   operator for this column, or is a "special" operator as recognized
 *		   by match_special_index_operator().
 *
 *	  As above, we must be able to commute the clause to put the indexkey
 *	  on the left.
 *
 *	  Note that we already know that the clause as a whole uses vars from
 *	  the interesting set of relations.  But we need to defend against
 *	  expressions like (a.f1 OP (b.f2 OP a.f3)); that's not processable by
 *	  an indexscan nestloop join, whereas (a.f1 OP (b.f2 OP c.f3)) is.
 *
 * 'rel' is the relation of interest.
 * 'index' is an index on 'rel'.
 * 'indexcol' is a column number of 'index' (counting from 0).
 * 'opclass' is the corresponding operator class.
 * 'clause' is the clause to be tested.
 *
 * 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_join_clause_to_indexcol(RelOptInfo *rel,
							  IndexOptInfo *index,
							  int indexcol,
							  Oid opclass,
							  Expr *clause)
{
	Node	   *leftop,
			   *rightop;

	/* Clause must be a binary opclause. */
	if (!is_opclause(clause))
		return false;
	leftop = get_leftop(clause);
	rightop = get_rightop(clause);
	if (!leftop || !rightop)
		return false;

	/*
	 * Check for an indexqual that could be handled by a nestloop join. We
	 * need the index key to be compared against an expression that uses
	 * none of the indexed relation's vars and contains no volatile
	 * functions.
	 */
	if (match_index_to_operand(leftop, indexcol, rel, index))
	{
		Relids		othervarnos = pull_varnos(rightop);
		bool		isIndexable;

		isIndexable =
			!bms_overlap(rel->relids, othervarnos) &&
			!contain_volatile_functions(rightop) &&
			is_indexable_operator(clause, opclass, true);
		bms_free(othervarnos);
		return isIndexable;
	}

	if (match_index_to_operand(rightop, indexcol, rel, index))
	{
		Relids		othervarnos = pull_varnos(leftop);
		bool		isIndexable;

		isIndexable =
			!bms_overlap(rel->relids, othervarnos) &&
			!contain_volatile_functions(leftop) &&
			is_indexable_operator(clause, opclass, false);
		bms_free(othervarnos);
		return isIndexable;
	}

	return false;
}

/*
 * indexable_operator