indxpath.c

关系型数据库 Postgresql 6.5.2

													  temp,
													  true);
			if (!matched_clause)
				continue;

			tempgroup = lappend(tempgroup, matched_clause);
			jfound = true;
		}
		foreach(curCinfo, restr_cinfo_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)
	{

		/*
		 * if no one join clause was matched then there ain't clauses for
		 * joins at all.
		 */
		if (!jfound)
		{
			freeList(clausegroup);
			return NIL;
		}
		return lcons(clausegroup, NIL);
	}
	return NIL;
}

/*
 * IndexScanableClause ()  MACRO
 *
 * Generalize condition on which we match a clause with an index.
 * Now we can match with functional indices.
 */
#define IndexScanableOperand(opnd, indkeys, rel, index) \
	((index->indproc == InvalidOid) ? \
		match_indexkey_operand(indkeys, opnd, rel) : \
		function_index_operand((Expr*)opnd,rel,index))

/*
 * There was
 *		equal_indexkey_var(indkeys,opnd) : \
 * above, and now
 *		match_indexkey_operand(indkeys, opnd, rel) : \
 * - vadim 01/22/97
 */

/* match_clause_to_indexkey()
 *	  Finds the first of a relation's available restriction clauses that
 *	  matches a key of an index.
 *
 *	  To match, the clause must:
 *	  (1) be in the form (op var const) if the clause is a single-
 *				relation clause, and
 *	  (2) contain an operator which is in the same class as the index
 *				operator for this key.
 *
 *	  If the clause being matched is a join clause, then 'join' is t.
 *
 * Returns a single restrictinfo node corresponding to the matching
 * clause.
 *
 * NOTE:  returns nil if clause is an or_clause.
 *
 */
static RestrictInfo *
match_clause_to_indexkey(RelOptInfo *rel,
						 RelOptInfo *index,
						 int indexkey,
						 int xclass,
						 RestrictInfo *restrictInfo,
						 bool join)
{
	Expr	   *clause = restrictInfo->clause;
	Var		   *leftop,
			   *rightop;
	Oid			join_op = InvalidOid;
	Oid			restrict_op = InvalidOid;
	bool		isIndexable = false;

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

	/*
	 * If this is not a join clause, check for clauses of the form:
	 * (operator var/func constant) and (operator constant var/func)
	 */
	if (!join)
	{

		/*
		 * Check for standard s-argable clause
		 */
		if ((rightop && IsA(rightop, Const)) ||
			(rightop && IsA(rightop, Param)))
		{
			restrict_op = ((Oper *) ((Expr *) clause)->oper)->opno;

			isIndexable = (op_class(restrict_op, xclass, index->relam) &&
						   IndexScanableOperand(leftop,
												indexkey,
												rel,
												index));

#ifndef IGNORE_BINARY_COMPATIBLE_INDICES

			/*
			 * Didn't find an index? Then maybe we can find another
			 * binary-compatible index instead... thomas 1998-08-14
			 */
			if (!isIndexable)
			{
				Oid			ltype;
				Oid			rtype;

				ltype = exprType((Node *) leftop);
				rtype = exprType((Node *) rightop);

				/*
				 * make sure we have two different binary-compatible
				 * types...
				 */
				if ((ltype != rtype)
					&& IS_BINARY_COMPATIBLE(ltype, rtype))
				{
					char	   *opname;
					Operator	newop;

					opname = get_opname(restrict_op);
					if (opname != NULL)
						newop = oper(opname, ltype, ltype, TRUE);
					else
						newop = NULL;

					/* actually have a different operator to try? */
					if (HeapTupleIsValid(newop) && (oprid(newop) != restrict_op))
					{
						restrict_op = oprid(newop);

						isIndexable = (op_class(restrict_op, xclass, index->relam) &&
									   IndexScanableOperand(leftop,
															indexkey,
															rel,
															index));

						if (isIndexable)
							((Oper *) ((Expr *) clause)->oper)->opno = restrict_op;
					}
				}
			}
#endif
		}

		/*
		 * Must try to commute the clause to standard s-arg format.
		 */
		else if ((leftop && IsA(leftop, Const)) ||
				 (leftop && IsA(leftop, Param)))
		{
			restrict_op = get_commutator(((Oper *) ((Expr *) clause)->oper)->opno);

			isIndexable = ((restrict_op != InvalidOid) &&
						   op_class(restrict_op, xclass, index->relam) &&
						   IndexScanableOperand(rightop,
												indexkey, rel, index));

#ifndef IGNORE_BINARY_COMPATIBLE_INDICES
			if (!isIndexable)
			{
				Oid			ltype;
				Oid			rtype;

				ltype = exprType((Node *) leftop);
				rtype = exprType((Node *) rightop);

				if ((ltype != rtype)
					&& IS_BINARY_COMPATIBLE(ltype, rtype))
				{
					char	   *opname;
					Operator	newop;

					restrict_op = ((Oper *) ((Expr *) clause)->oper)->opno;

					opname = get_opname(restrict_op);
					if (opname != NULL)
						newop = oper(opname, rtype, rtype, TRUE);
					else
						newop = NULL;

					if (HeapTupleIsValid(newop) && (oprid(newop) != restrict_op))
					{
						restrict_op = get_commutator(oprid(newop));

						isIndexable = ((restrict_op != InvalidOid) &&
						   op_class(restrict_op, xclass, index->relam) &&
									   IndexScanableOperand(rightop,
															indexkey,
															rel,
															index));

						if (isIndexable)
							((Oper *) ((Expr *) clause)->oper)->opno = oprid(newop);
					}
				}
			}
#endif

			if (isIndexable)
			{

				/*
				 * In place list modification. (op const var/func) -> (op
				 * var/func const)
				 */
				CommuteClause((Node *) clause);
			}
		}
	}

	/*
	 * Check for an indexable scan on one of the join relations. clause is
	 * of the form (operator var/func var/func)
	 */
	else
	{
		if (rightop
		&& match_index_to_operand(indexkey, (Expr *) rightop, rel, index))
		{
			join_op = get_commutator(((Oper *) ((Expr *) clause)->oper)->opno);

		}
		else if (leftop
				 && match_index_to_operand(indexkey,
										   (Expr *) leftop, rel, index))
			join_op = ((Oper *) ((Expr *) clause)->oper)->opno;

		if (join_op && op_class(join_op, xclass, index->relam) &&
			is_joinable((Node *) clause))
		{
			isIndexable = true;

			/*
			 * If we're using the operand's commutator we must commute the
			 * clause.
			 */
			if (join_op != ((Oper *) ((Expr *) clause)->oper)->opno)
				CommuteClause((Node *) clause);
		}
	}

	if (isIndexable)
		return restrictInfo;

	return NULL;
}

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

/*
 * pred_test
 *	  Does the "predicate inclusion test" for partial indexes.
 *
 *	  Recursively checks whether the clauses in restrictinfo_list imply
 *	  that the given predicate is true.
 *
 *	  This routine (together with the routines it calls) iterates over
 *	  ANDs in the predicate first, then reduces the qualification
 *	  clauses down to their constituent terms, and iterates over ORs
 *	  in the predicate last.  This order is important to make the test
 *	  succeed whenever possible (assuming the predicate has been
 *	  successfully cnfify()-ed). --Nels, Jan '93
 */
static bool
pred_test(List *predicate_list, List *restrictinfo_list, List *joininfo_list)
{
	List	   *pred,
			   *items,
			   *item;

	/*
	 * Note: if Postgres tried to optimize queries by forming equivalence
	 * classes over equi-joined attributes (i.e., if it recognized that a
	 * qualification such as "where a.b=c.d and a.b=5" could make use of
	 * an index on c.d), then we could use that equivalence class info
	 * here with joininfo_list to do more complete tests for the usability
	 * of a partial index.	For now, the test only uses restriction
	 * clauses (those in restrictinfo_list). --Nels, Dec '92
	 */

	if (predicate_list == NULL)
		return true;			/* no predicate: the index is usable */
	if (restrictinfo_list == NULL)
		return false;			/* no restriction clauses: the test must
								 * fail */

	foreach(pred, predicate_list)
	{

		/*
		 * if any clause is not implied, the whole predicate is not
		 * implied
		 */
		if (and_clause(lfirst(pred)))
		{
			items = ((Expr *) lfirst(pred))->args;
			foreach(item, items)
			{
				if (!one_pred_test(lfirst(item), restrictinfo_list))
					return false;
			}
		}
		else if (!one_pred_test(lfirst(pred), restrictinfo_list))
			return false;
	}
	return true;
}


/*
 * one_pred_test
 *	  Does the "predicate inclusion test" for one conjunct of a predicate
 *	  expression.
 */
static bool
one_pred_test(Expr *predicate, List *restrictinfo_list)
{
	RestrictInfo *restrictinfo;
	List	   *item;

	Assert(predicate != NULL);
	foreach(item, restrictinfo_list)
	{
		restrictinfo = (RestrictInfo *) lfirst(item);
		/* if any clause implies the predicate, return true */
		if (one_pred_clause_expr_test(predicate, (Node *) restrictinfo->clause))
			return true;
	}
	return false;
}


/*
 * one_pred_clause_expr_test
 *	  Does the "predicate inclusion test" for a general restriction-clause
 *	  expression.
 */
static bool
one_pred_clause_expr_test(Expr *predicate, Node *clause)
{
	List	   *items,
			   *item;

	if (is_opclause(clause))
		return one_pred_clause_test(predicate, clause);
	else if (or_clause(clause))
	{
		items = ((Expr *) clause)->args;
		foreach(item, items)
		{
			/* if any OR item doesn't imply the predicate, clause doesn't */
			if (!one_pred_clause_expr_test(predicate, lfirst(item)))
				return false;
		}
		return true;
	}
	else if (and_clause(clause))
	{
		items = ((Expr *) clause)->args;
		foreach(item, items)
		{

			/*
			 * if any AND item implies the predicate, the whole clause
			 * does
			 */
			if (one_pred_clause_expr_test(predicate, lfirst(item)))
				return true;
		}
		return false;
	}
	else
	{
		/* unknown clause type never implies the predicate */
		return false;
	}
}


/*
 * one_pred_clause_test
 *	  Does the "predicate inclusion test" for one conjunct of a predicate
 *	  expression for a simple restriction clause.
 */
static bool
one_pred_clause_test(Expr *predicate, Node *clause)
{
	List	   *items,
			   *item;

	if (is_opclause((Node *) predicate))
		return clause_pred_clause_test(predicate, clause);
	else if (or_clause((Node *) predicate))
	{
		items = predicate->args;
		foreach(item, items)
		{
			/* if any item is implied, the whole predicate is implied */
			if (one_pred_clause_test(lfirst(item), clause))
				return true;
		}
		return false;
	}
	else if (and_clause((Node *) predicate))
	{
		items = predicate->args;
		foreach(item, items)
		{

			/*
			 * if any item is not implied, the whole predicate is not
			 * implied
			 */
			if (!one_pred_clause_test(lfirst(item), clause))
				return false;
		}
		return true;
	}
	else
	{
		elog(DEBUG, "Unsupported predicate type, index will not be used");
		return false;
	}
}


/*
 * Define an "operator implication table" for btree operators ("strategies").
 * The "strategy numbers" are:	(1) <	(2) <=	 (3) =	 (4) >=   (5) >
 *
 * The interpretation of:
 *
 *		test_op = BT_implic_table[given_op-1][target_op-1]
 *
 * where test_op, given_op and target_op are strategy numbers (from 1 to 5)
 * of btree operators, is as follows:
 *
 *	 If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
 *	 want to determine whether "ATTR target_op CONST2" must also be true, then
 *	 you can use "CONST1 test_op CONST2" as a test.  If this test returns true,
 *	 then the target expression must be true; if the test returns false, then
 *	 the target expression may be false.
 *