indxpath.c

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

 *	  Does a binary opclause contain an operator matching the index opclass?
 *
 * If the indexkey is on the right, what we actually want to know
 * is whether the operator has a commutator operator that matches
 * the index's opclass.
 *
 * Returns the OID of the matching operator, or InvalidOid if no match.
 * (Formerly, this routine might return a binary-compatible operator
 * rather than the original one, but that kluge is history.)
 */
static Oid
indexable_operator(Expr *clause, Oid opclass, bool indexkey_on_left)
{
	Oid			expr_op = ((OpExpr *) clause)->opno;
	Oid			commuted_op;

	/* Get the commuted operator if necessary */
	if (indexkey_on_left)
		commuted_op = expr_op;
	else
		commuted_op = get_commutator(expr_op);
	if (commuted_op == InvalidOid)
		return InvalidOid;

	/* OK if the (commuted) operator is a member of the index's opclass */
	if (op_in_opclass(commuted_op, opclass))
		return expr_op;

	return InvalidOid;
}

/****************************************************************************
 *				----  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 converted
 *	  to CNF format). --Nels, Jan '93
 */
static bool
pred_test(List *predicate_list, List *restrictinfo_list, List *joininfo_list)
{
	List	   *pred;

	/*
	 * 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
	 *
	 * XXX as of 7.1, equivalence class info *is* available.  Consider
	 * improving this code as foreseen by Nels.
	 */

	if (predicate_list == NIL)
		return true;			/* no predicate: the index is usable */
	if (restrictinfo_list == NIL)
		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.  Note we assume that any sub-ANDs have been flattened
		 * when the predicate was fed through canonicalize_qual().
		 */
		if (!pred_test_restrict_list(lfirst(pred), restrictinfo_list))
			return false;
	}
	return true;
}


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

	foreach(item, restrictinfo_list)
	{
		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(item);

		/* if any clause implies the predicate, return true */
		if (pred_test_recurse_clause(predicate,
									 (Node *) restrictinfo->clause))
			return true;
	}
	return false;
}


/*
 * pred_test_recurse_clause
 *	  Does the "predicate inclusion test" for a general restriction-clause
 *	  expression.  Here we recursively deal with the possibility that the
 *	  restriction clause is itself an AND or OR structure.
 */
static bool
pred_test_recurse_clause(Expr *predicate, Node *clause)
{
	List	   *items,
			   *item;

	Assert(clause != NULL);
	if (or_clause(clause))
	{
		items = ((BoolExpr *) clause)->args;
		foreach(item, items)
		{
			/* if any OR item doesn't imply the predicate, clause doesn't */
			if (!pred_test_recurse_clause(predicate, lfirst(item)))
				return false;
		}
		return true;
	}
	else if (and_clause(clause))
	{
		items = ((BoolExpr *) clause)->args;
		foreach(item, items)
		{
			/*
			 * if any AND item implies the predicate, the whole clause
			 * does
			 */
			if (pred_test_recurse_clause(predicate, lfirst(item)))
				return true;
		}
		return false;
	}
	else
		return pred_test_recurse_pred(predicate, clause);
}


/*
 * pred_test_recurse_pred
 *	  Does the "predicate inclusion test" for one conjunct of a predicate
 *	  expression for a simple restriction clause.  Here we recursively deal
 *	  with the possibility that the predicate conjunct is itself an AND or
 *	  OR structure.
 */
static bool
pred_test_recurse_pred(Expr *predicate, Node *clause)
{
	List	   *items,
			   *item;

	Assert(predicate != NULL);
	if (or_clause((Node *) predicate))
	{
		items = ((BoolExpr *) predicate)->args;
		foreach(item, items)
		{
			/* if any item is implied, the whole predicate is implied */
			if (pred_test_recurse_pred(lfirst(item), clause))
				return true;
		}
		return false;
	}
	else if (and_clause((Node *) predicate))
	{
		items = ((BoolExpr *) predicate)->args;
		foreach(item, items)
		{
			/*
			 * if any item is not implied, the whole predicate is not
			 * implied
			 */
			if (!pred_test_recurse_pred(lfirst(item), clause))
				return false;
		}
		return true;
	}
	else
		return pred_test_simple_clause(predicate, clause);
}


/*
 * 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.
 *
 * An entry where test_op==0 means the implication cannot be determined, i.e.,
 * this test should always be considered false.
 */

static const StrategyNumber
			BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = {
	{2, 2, 0, 0, 0},
	{1, 2, 0, 0, 0},
	{1, 2, 3, 4, 5},
	{0, 0, 0, 4, 5},
	{0, 0, 0, 4, 4}
};


/*
 * pred_test_simple_clause
 *	  Does the "predicate inclusion test" for a "simple clause" predicate
 *	  and a "simple clause" restriction.
 *
 *	  We have two strategies for determining whether one simple clause
 *	  implies another.	A simple and general way is to see if they are
 *	  equal(); this works for any kind of expression.  (Actually, there
 *	  is an implied assumption that the functions in the expression are
 *	  immutable, ie dependent only on their input arguments --- but this
 *	  was checked for the predicate by CheckPredicate().)
 *
 *	  Our other way works only for (binary boolean) operators that are
 *	  in some btree operator class.  We use the above operator implication
 *	  table to be able to derive implications between nonidentical clauses.
 *
 *	  Eventually, rtree operators could also be handled by defining an
 *	  appropriate "RT_implic_table" array.
 */
static bool
pred_test_simple_clause(Expr *predicate, Node *clause)
{
	Var		   *pred_var,
			   *clause_var;
	Const	   *pred_const,
			   *clause_const;
	Oid			pred_op,
				clause_op,
				test_op;
	Oid			opclass_id = InvalidOid;
	bool		found = false;
	StrategyNumber pred_strategy = 0,
				clause_strategy = 0,
				test_strategy;
	Expr	   *test_expr;
	ExprState  *test_exprstate;
	Datum		test_result;
	bool		isNull;
	CatCList   *catlist;
	int			i;
	EState	   *estate;
	MemoryContext oldcontext;

	/* First try the equal() test */
	if (equal((Node *) predicate, clause))
		return true;

	/*
	 * Can't do anything more unless they are both binary opclauses with a
	 * Var on the left and a Const on the right.  (XXX someday try to
	 * commute Const/Var cases?)
	 */
	if (!is_opclause(predicate))
		return false;
	pred_var = (Var *) get_leftop(predicate);
	pred_const = (Const *) get_rightop(predicate);

	if (!is_opclause(clause))
		return false;
	clause_var = (Var *) get_leftop((Expr *) clause);
	clause_const = (Const *) get_rightop((Expr *) clause);

	if (!IsA(clause_var, Var) ||
		clause_const == NULL ||
		!IsA(clause_const, Const) ||
		!IsA(pred_var, Var) ||
		pred_const == NULL ||
		!IsA(pred_const, Const))
		return false;

	/*
	 * The implication can't be determined unless the predicate and the
	 * clause refer to the same attribute.
	 */
	if (clause_var->varno != pred_var->varno ||
		clause_var->varattno != pred_var->varattno)
		return false;

	/* Get the operators for the two clauses we're comparing */
	pred_op = ((OpExpr *) predicate)->opno;
	clause_op = ((OpExpr *) clause)->opno;

	/*
	 * 1. Find "btree" strategy numbers for the pred_op and clause_op.
	 *
	 * We must find a btree opclass that contains both operators, else the
	 * implication can't be determined.  If there are multiple such
	 * opclasses, assume we can use any one to determine the logical
	 * relationship of the two operators and the correct corresponding
	 * test operator.  This should work for any logically consistent
	 * opclasses.
	 */
	catlist = SearchSysCacheList(AMOPOPID, 1,
								 ObjectIdGetDatum(pred_op),
								 0, 0, 0);

	for (i = 0; i < catlist->n_members; i++)
	{
		HeapTuple	pred_tuple = &catlist->members[i]->tuple;
		Form_pg_amop pred_form = (Form_pg_amop) GETSTRUCT(pred_tuple);
		HeapTuple	clause_tuple;

		if (!opclass_is_btree(pred_form->amopclaid))
			continue;

		/* Get the predicate operator's btree strategy number */
		pred_strategy = (StrategyNumber) pred_form->amopstrategy;
		Assert(pred_strategy >= 1 && pred_strategy <= 5);

		/*
		 * Remember which operator class this strategy number came from
		 */
		opclass_id = pred_form->amopclaid;

		/*
		 * From the same opclass, find a strategy num for the clause_op,
		 * if possible
		 */
		clause_tuple = SearchSysCache(AMOPOPID,
									  ObjectIdGetDatum(clause_op),
									  ObjectIdGetDatum(opclass_id),
									  0, 0);
		if (HeapTupleIsValid(clause_tuple))
		{
			Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);

			/* Get the restriction clause operator's strategy number */
			clause_strategy = (StrategyNumber) clause_form->amopstrategy;
			Assert(clause_strategy >= 1 && clause_strategy <= 5);

			ReleaseSysCache(clause_tuple);
			found = true;
			break;
		}
	}

	ReleaseSysCacheList(catlist);

	if (!found)
	{
		/* couldn't find a btree opclass to interpret the operators */
		return false;
	}

	/*
	 * 2. Look up the "test" strategy number in the implication table
	 */
	test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
	if (test_strategy == 0)
		return false;			/* the implication cannot be determined */

	/*
	 * 3. From the same opclass, find the operator for the test strategy
	 */
	test_op = get_opclass_member(opclass_id, test_strategy);
	if (!OidIsValid(test_op))
	{
		/* This should not fail, else pg_amop entry is missing */
		elog(ERROR, "missing pg_amop entry for opclass %u strategy %d",
			 opclass_id, test_strategy);
	}

	/*
	 * 4. Evaluate the test.  For this we need an EState.
	 */
	estate = CreateExecutorState();

	/* We can use the estate's working context to avoid memory leaks. */
	oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);

	/* Build expression tree */
	test_expr = make_opclause(test_op,
							  BOOLOID,
							  false,
							  (Expr *) clause_const,
							  (Expr *) pred_const);

	/* Prepare it for execution */
	test_exprstate = ExecPrepareExpr(test_expr, estate);

	/* And execute it. */
	test_result = ExecEvalExprSwitchContext(test_exprstate,
										  GetPerTupleExprContext(estate),
											&isNull, NULL);

	/* Get back to outer memory context */
	MemoryContextSwitchTo(oldcontext);

	/* Release all the junk we just created */
	FreeExecutorState(estate);

	if (isNull)
	{
		/* Treat a null result as false ... but it's a tad fishy ... */
		elog(DEBUG2, "null predicate test result");
		return false;
	}
	return DatumGetBool(test_result);
}


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