indxpath.c

关系型数据库 Postgresql 6.5.2

 * An entry where test_op==0 means the implication cannot be determined, i.e.,
 * this test should always be considered false.
 */

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}
};


/*
 * clause_pred_clause_test
 *	  Use operator class info to check whether clause implies predicate.
 *
 *	  Does the "predicate inclusion test" for a "simple clause" predicate
 *	  for a single "simple clause" restriction.  Currently, this only handles
 *	  (binary boolean) operators that are in some btree operator class.
 *	  Eventually, rtree operators could also be handled by defining an
 *	  appropriate "RT_implic_table" array.
 */
static bool
clause_pred_clause_test(Expr *predicate, Node *clause)
{
	Var		   *pred_var,
			   *clause_var;
	Const	   *pred_const,
			   *clause_const;
	Oid			pred_op,
				clause_op,
				test_op;
	Oid			opclass_id;
	StrategyNumber pred_strategy,
				clause_strategy,
				test_strategy;
	Oper	   *test_oper;
	Expr	   *test_expr;
	bool		test_result,
				isNull;
	Relation	relation;
	HeapScanDesc scan;
	HeapTuple	tuple;
	ScanKeyData entry[3];
	Form_pg_amop aform;

	pred_var = (Var *) get_leftop(predicate);
	pred_const = (Const *) get_rightop(predicate);
	clause_var = (Var *) get_leftop((Expr *) clause);
	clause_const = (Const *) get_rightop((Expr *) clause);

	/* Check the basic form; for now, only allow the simplest case */
	if (!is_opclause(clause) ||
		!IsA(clause_var, Var) ||
		clause_const == NULL ||
		!IsA(clause_const, Const) ||
		!IsA(predicate->oper, Oper) ||
		!IsA(pred_var, Var) ||
		!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->varattno != pred_var->varattno)
		return false;

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


	/*
	 * 1. Find a "btree" strategy number for the pred_op
	 */
	ScanKeyEntryInitialize(&entry[0], 0,
						   Anum_pg_amop_amopid,
						   F_OIDEQ,
						   ObjectIdGetDatum(BTREE_AM_OID));

	ScanKeyEntryInitialize(&entry[1], 0,
						   Anum_pg_amop_amopopr,
						   F_OIDEQ,
						   ObjectIdGetDatum(pred_op));

	relation = heap_openr(AccessMethodOperatorRelationName);

	/*
	 * The following assumes that any given operator will only be in a
	 * single btree operator class.  This is true at least for all the
	 * pre-defined operator classes.  If it isn't true, then whichever
	 * operator class happens to be returned first for the given operator
	 * will be used to find the associated strategy numbers for the test.
	 * --Nels, Jan '93
	 */
	scan = heap_beginscan(relation, false, SnapshotNow, 2, entry);
	tuple = heap_getnext(scan, 0);
	if (!HeapTupleIsValid(tuple))
	{
		elog(DEBUG, "clause_pred_clause_test: unknown pred_op");
		return false;
	}
	aform = (Form_pg_amop) GETSTRUCT(tuple);

	/* Get the predicate operator's strategy number (1 to 5) */
	pred_strategy = (StrategyNumber) aform->amopstrategy;

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

	heap_endscan(scan);


	/*
	 * 2. From the same opclass, find a strategy num for the clause_op
	 */
	ScanKeyEntryInitialize(&entry[1], 0,
						   Anum_pg_amop_amopclaid,
						   F_OIDEQ,
						   ObjectIdGetDatum(opclass_id));

	ScanKeyEntryInitialize(&entry[2], 0,
						   Anum_pg_amop_amopopr,
						   F_OIDEQ,
						   ObjectIdGetDatum(clause_op));

	scan = heap_beginscan(relation, false, SnapshotNow, 3, entry);
	tuple = heap_getnext(scan, 0);
	if (!HeapTupleIsValid(tuple))
	{
		elog(DEBUG, "clause_pred_clause_test: unknown clause_op");
		return false;
	}
	aform = (Form_pg_amop) GETSTRUCT(tuple);

	/* Get the restriction clause operator's strategy number (1 to 5) */
	clause_strategy = (StrategyNumber) aform->amopstrategy;
	heap_endscan(scan);


	/*
	 * 3. 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 */


	/*
	 * 4. From the same opclass, find the operator for the test strategy
	 */

	ScanKeyEntryInitialize(&entry[2], 0,
						   Anum_pg_amop_amopstrategy,
						   F_INT2EQ,
						   Int16GetDatum(test_strategy));

	scan = heap_beginscan(relation, false, SnapshotNow, 3, entry);
	tuple = heap_getnext(scan, 0);
	if (!HeapTupleIsValid(tuple))
	{
		elog(DEBUG, "clause_pred_clause_test: unknown test_op");
		return false;
	}
	aform = (Form_pg_amop) GETSTRUCT(tuple);

	/* Get the test operator */
	test_op = aform->amopopr;
	heap_endscan(scan);


	/*
	 * 5. Evaluate the test
	 */
	test_oper = makeOper(test_op,		/* opno */
						 InvalidOid,	/* opid */
						 BOOLOID,		/* opresulttype */
						 0,		/* opsize */
						 NULL); /* op_fcache */
	replace_opid(test_oper);

	test_expr = make_opclause(test_oper,
							  copyObject(clause_const),
							  copyObject(pred_const));

#ifndef OMIT_PARTIAL_INDEX
	test_result = ExecEvalExpr((Node *) test_expr, NULL, &isNull, NULL);
#endif	 /* OMIT_PARTIAL_INDEX */
	if (isNull)
	{
		elog(DEBUG, "clause_pred_clause_test: null test result");
		return false;
	}
	return test_result;
}


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

/*
 * indexable_joinclauses
 *	  Finds all groups of join clauses from among 'joininfo_list' that can
 *	  be used in conjunction with 'index'.
 *
 *	  The first clause in the group is marked as having the other relation
 *	  in the join clause as its outer join relation.
 *
 * Returns a list of these clause groups.
 *
 *	  Added: restrictinfo_list - list of restriction RestrictInfos. It's to
 *		support multi-column indices in joins and for cases
 *		when a key is in both join & restriction clauses. - vadim 03/18/97
 *
 */
static List *
indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index,
					  List *joininfo_list, List *restrictinfo_list)
{
	JoinInfo   *joininfo = (JoinInfo *) NULL;
	List	   *cg_list = NIL;
	List	   *i = NIL;
	List	   *clausegroups = NIL;

	foreach(i, joininfo_list)
	{
		joininfo = (JoinInfo *) lfirst(i);

		if (joininfo->jinfo_restrictinfo == NIL)
			continue;
		clausegroups = group_clauses_by_ikey_for_joins(rel,
													   index,
													   index->indexkeys,
													   index->classlist,
											joininfo->jinfo_restrictinfo,
													   restrictinfo_list);

		if (clausegroups != NIL)
		{
			List	   *clauses = lfirst(clausegroups);

			((RestrictInfo *) lfirst(clauses))->restrictinfojoinid = joininfo->unjoined_relids;
		}
		cg_list = nconc(cg_list, clausegroups);
	}
	return cg_list;
}

/****************************************************************************
 *				----  PATH CREATION UTILITIES  ----
 ****************************************************************************/

/*
 * extract_restrict_clauses -
 *	  the list of clause info contains join clauses and restriction clauses.
 *	  This routine returns the restriction clauses only.
 */
#ifdef NOT_USED
static List *
extract_restrict_clauses(List *clausegroup)
{
	List	   *restrict_cls = NIL;
	List	   *l;

	foreach(l, clausegroup)
	{
		RestrictInfo *cinfo = lfirst(l);

		if (!is_joinable((Node *) cinfo->clause))
			restrict_cls = lappend(restrict_cls, cinfo);
	}
	return restrict_cls;
}

#endif

/*
 * index_innerjoin
 *	  Creates index path nodes corresponding to paths to be used as inner
 *	  relations in nestloop joins.
 *
 * 'clausegroup-list' is a list of list of restrictinfo nodes which can use
 * 'index' on their inner relation.
 *
 * Returns a list of index pathnodes.
 *
 */
static List *
index_innerjoin(Query *root, RelOptInfo *rel, List *clausegroup_list,
				RelOptInfo *index)
{
	List	   *clausegroup = NIL;
	List	   *cg_list = NIL;
	List	   *i = NIL;
	IndexPath  *pathnode = (IndexPath *) NULL;
	Cost		temp_selec;
	float		temp_pages;

	foreach(i, clausegroup_list)
	{
		List	   *attnos,
				   *values,
				   *flags;

		clausegroup = lfirst(i);
		pathnode = makeNode(IndexPath);

		get_joinvars(lfirsti(rel->relids), clausegroup,
					 &attnos, &values, &flags);
		index_selectivity(lfirsti(index->relids),
						  index->classlist,
						  get_opnos(clausegroup),
						  getrelid(lfirsti(rel->relids),
								   root->rtable),
						  attnos,
						  values,
						  flags,
						  length(clausegroup),
						  &temp_pages,
						  &temp_selec);

		pathnode->path.pathtype = T_IndexScan;
		pathnode->path.parent = rel;
		pathnode->path.pathorder = makeNode(PathOrder);
		pathnode->path.pathorder->ordtype = SORTOP_ORDER;
		pathnode->path.pathorder->ord.sortop = index->ordering;
		pathnode->path.pathkeys = NIL;

		pathnode->indexid = index->relids;
		pathnode->indexkeys = index->indexkeys;
		pathnode->indexqual = clausegroup;

		pathnode->path.joinid = ((RestrictInfo *) lfirst(clausegroup))->restrictinfojoinid;

		pathnode->path.path_cost = cost_index((Oid) lfirsti(index->relids),
											  (int) temp_pages,
											  temp_selec,
											  rel->pages,
											  rel->tuples,
											  index->pages,
											  index->tuples,
											  true);

		/*
		 * copy restrictinfo list into path for expensive function
		 * processing -- JMH, 7/7/92
		 */
		pathnode->path.loc_restrictinfo = set_difference(copyObject((Node *) rel->restrictinfo),
														 clausegroup);

#ifdef NOT_USED					/* fix xfunc */
		/* add in cost for expensive functions!  -- JMH, 7/7/92 */
		if (XfuncMode != XFUNC_OFF)
			((Path *) pathnode)->path_cost += xfunc_get_path_cost((Path *) pathnode);
#endif
		cg_list = lappend(cg_list, pathnode);
	}
	return cg_list;
}

/*
 * create_index_path_group
 *	  Creates a list of index path nodes for each group of clauses
 *	  (restriction or join) that can be used in conjunction with an index.
 *
 * 'rel' is the relation for which 'index' is defined
 * 'clausegroup-list' is the list of clause groups (lists of restrictinfo
 *				nodes) grouped by mergejoinorder
 * 'join' is a flag indicating whether or not the clauses are join
 *				clauses
 *
 * Returns a list of new index path nodes.
 *
 */
static List *
create_index_path_group(Query *root,
						RelOptInfo *rel,
						RelOptInfo *index,
						List *clausegroup_list,
						bool join)
{
	List	   *clausegroup = NIL;
	List	   *ip_list = NIL;
	List	   *i = NIL;
	List	   *j = NIL;
	IndexPath  *temp_path;

	foreach(i, clausegroup_list)
	{
		RestrictInfo *restrictinfo;
		bool		temp = true;

		clausegroup = lfirst(i);

		foreach(j, clausegroup)
		{
			restrictinfo = (RestrictInfo *) lfirst(j);
			if (!(is_joinable((Node *) restrictinfo->clause) &&
				  equal_path_merge_ordering(index->ordering,
										  restrictinfo->mergejoinorder)))
				temp = false;
		}

		if (!join || temp)
		{						/* restriction, ordering scan */
			temp_path = create_index_path(root, rel, index, clausegroup, join);
			ip_list = lappend(ip_list, temp_path);
		}
	}
	return ip_list;
}

static List *
add_index_paths(List *indexpaths, List *new_indexpaths)
{
	return nconc(indexpaths, new_indexpaths);
}

static bool
function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index)
{
	Oid			heapRelid = (Oid) lfirsti(rel->relids);
	Func	   *function;
	List	   *funcargs;
	int		   *indexKeys = index->indexkeys;
	List	   *arg;
	int			i;

	/*
	 * sanity check, make sure we know what we're dealing with here.
	 */
	if (funcOpnd == NULL ||
		nodeTag(funcOpnd) != T_Expr || funcOpnd->opType != FUNC_EXPR ||
		funcOpnd->oper == NULL || indexKeys == NULL)
		return false;

	function = (Func *) funcOpnd->oper;
	funcargs = funcOpnd->args;

	if (function->funcid != index->indproc)
		return false;

	/*
	 * Check that the arguments correspond to the same arguments used to
	 * create the functional index.  To do this we must check that 1.
	 * refer to the right relatiion. 2. the args have the right attr.
	 * numbers in the right order.
	 *
	 *
	 * Check all args refer to the correct relation (i.e. the one with the
	 * functional index defined on it (rel).  To do this we can simply
	 * compare range table entry numbers, they must be the same.
	 */
	foreach(arg, funcargs)
	{
		if (heapRelid != ((Var *) lfirst(arg))->varno)
			return false;
	}

	/*
	 * check attr numbers and order.
	 */
	i = 0;
	foreach(arg, funcargs)
	{

		if (indexKeys[i] == 0)
			return false;

		if (((Var *) lfirst(arg))->varattno != indexKeys[i])
			return false;

		i++;
	}

	return true;
}