indxpath.c

PostgreSQL 8.1.4的源码 适用于Linux下的开源数据库系统

	 * promising combination of bitmap index paths.
	 */
	if (bitindexpaths != NIL)
	{
		Path	   *bitmapqual;
		BitmapHeapPath *bpath;

		bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
		bpath = create_bitmap_heap_path(root, rel, bitmapqual, true);
		indexpaths = lappend(indexpaths, bpath);
	}

	/*
	 * Now choose the cheapest member of indexpaths.
	 */
	cheapest = NULL;
	foreach(l, indexpaths)
	{
		Path	   *path = (Path *) lfirst(l);

		if (cheapest == NULL ||
			compare_path_costs(path, cheapest, TOTAL_COST) < 0)
			cheapest = path;
	}

	/* Cache the result --- whether positive or negative */
	info = makeNode(InnerIndexscanInfo);
	info->other_relids = outer_relids;
	info->isouterjoin = isouterjoin;
	info->best_innerpath = cheapest;
	rel->index_inner_paths = lcons(info, rel->index_inner_paths);

	MemoryContextSwitchTo(oldcontext);

	return cheapest;
}

/*
 * find_clauses_for_join
 *	  Generate a list of clauses that are potentially useful for
 *	  scanning rel as the inner side of a nestloop join.
 *
 * 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 there isn't any potential win here.
 */
static List *
find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
					  Relids outer_relids, bool isouterjoin)
{
	List	   *clause_list = NIL;
	Relids		join_relids;
	ListCell   *l;

	/* Look for joinclauses that are usable with given outer_relids */
	join_relids = bms_union(rel->relids, outer_relids);

	foreach(l, rel->joininfo)
	{
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

		/* Can't use pushed-down join clauses in outer join */
		if (isouterjoin && rinfo->is_pushed_down)
			continue;
		if (!bms_is_subset(rinfo->required_relids, join_relids))
			continue;

		clause_list = lappend(clause_list, rinfo);
	}

	bms_free(join_relids);

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

	/*
	 * We can also use any plain restriction clauses for the rel.  We put
	 * these at the front of the clause list for the convenience of
	 * remove_redundant_join_clauses, which can never remove non-join clauses
	 * and hence won't be able to get rid of a non-join clause if it appears
	 * after a join clause it is redundant with.
	 */
	clause_list = list_concat(list_copy(rel->baserestrictinfo), clause_list);

	/*
	 * We may now have clauses that are known redundant.  Get rid of 'em.
	 */
	if (list_length(clause_list) > 1)
	{
		clause_list = remove_redundant_join_clauses(root,
													clause_list,
													isouterjoin);
	}

	return clause_list;
}

/****************************************************************************
 *				----  ROUTINES TO HANDLE PATHKEYS  ----
 ****************************************************************************/

/*
 * match_variant_ordering
 *		Try to match an index's ordering to the query's requested ordering
 *
 * This is used when the index is ordered but a naive comparison fails to
 * match its ordering (pathkeys) to root->query_pathkeys.  It may be that
 * we need to scan the index backwards.  Also, a less naive comparison can
 * help for both forward and backward indexscans.  Columns of the index
 * that have an equality restriction clause can be ignored in the match;
 * that is, an index on (x,y) can be considered to match the ordering of
 *		... WHERE x = 42 ORDER BY y;
 *
 * Note: it would be possible to similarly ignore useless ORDER BY items;
 * that is, an index on just y could be considered to match the ordering of
 *		... WHERE x = 42 ORDER BY x, y;
 * But proving that this is safe would require finding a btree opclass
 * containing both the = operator and the < or > operator in the ORDER BY
 * item.  That's significantly more expensive than what we do here, since
 * we'd have to look at restriction clauses unrelated to the current index
 * and search for opclasses without any hint from the index.  The practical
 * use-cases seem to be mostly covered by ignoring index columns, so that's
 * all we do for now.
 *
 * Inputs:
 * 'index' is the index of interest.
 * 'restrictclauses' is the list of sublists of restriction clauses
 *		matching the columns of the index (NIL if none)
 *
 * If able to match the requested query pathkeys, returns either
 * ForwardScanDirection or BackwardScanDirection to indicate the proper index
 * scan direction.	If no match, returns NoMovementScanDirection.
 */
static ScanDirection
match_variant_ordering(PlannerInfo *root,
					   IndexOptInfo *index,
					   List *restrictclauses)
{
	List	   *ignorables;

	/*
	 * Forget the whole thing if not a btree index; our check for ignorable
	 * columns assumes we are dealing with btree opclasses.  (It'd be possible
	 * to factor out just the try for backwards indexscan, but considering
	 * that we presently have no orderable indexes except btrees anyway, it's
	 * hardly worth contorting this code for that case.)
	 *
	 * Note: if you remove this, you probably need to put in a check on
	 * amoptionalkey to prevent possible clauseless scan on an index that
	 * won't cope.
	 */
	if (index->relam != BTREE_AM_OID)
		return NoMovementScanDirection;

	/*
	 * Figure out which index columns can be optionally ignored because they
	 * have an equality constraint.  This is the same set for either forward
	 * or backward scan, so we do it just once.
	 */
	ignorables = identify_ignorable_ordering_cols(root, index,
												  restrictclauses);

	/*
	 * Try to match to forward scan, then backward scan.  However, we can skip
	 * the forward-scan case if there are no ignorable columns, because
	 * find_usable_indexes() would have found the match already.
	 */
	if (ignorables &&
		match_index_to_query_keys(root, index, ForwardScanDirection,
								  ignorables))
		return ForwardScanDirection;

	if (match_index_to_query_keys(root, index, BackwardScanDirection,
								  ignorables))
		return BackwardScanDirection;

	return NoMovementScanDirection;
}

/*
 * identify_ignorable_ordering_cols
 *		Determine which index columns can be ignored for ordering purposes
 *
 * Returns an integer List of column numbers (1-based) of ignorable
 * columns.  The ignorable columns are those that have equality constraints
 * against pseudoconstants.
 */
static List *
identify_ignorable_ordering_cols(PlannerInfo *root,
								 IndexOptInfo *index,
								 List *restrictclauses)
{
	List	   *result = NIL;
	int			indexcol = 0;	/* note this is 0-based */
	ListCell   *l;

	/* restrictclauses is either NIL or has a sublist per column */
	foreach(l, restrictclauses)
	{
		List	   *sublist = (List *) lfirst(l);
		Oid			opclass = index->classlist[indexcol];
		ListCell   *l2;

		foreach(l2, sublist)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l2);
			OpExpr	   *clause = (OpExpr *) rinfo->clause;
			Oid			clause_op;
			int			op_strategy;
			bool		varonleft;
			bool		ispc;

			/* We know this clause passed match_clause_to_indexcol */

			/* First check for boolean-index cases. */
			if (IsBooleanOpclass(opclass))
			{
				if (match_boolean_index_clause((Node *) clause, indexcol,
											   index))
				{
					/*
					 * The clause means either col = TRUE or col = FALSE; we
					 * do not care which, it's an equality constraint either
					 * way.
					 */
					result = lappend_int(result, indexcol + 1);
					break;
				}
			}

			/* Else clause must be a binary opclause. */
			Assert(IsA(clause, OpExpr));

			/* Determine left/right sides and check the operator */
			clause_op = clause->opno;
			if (match_index_to_operand(linitial(clause->args), indexcol,
									   index))
			{
				/* clause_op is correct */
				varonleft = true;
			}
			else
			{
				Assert(match_index_to_operand(lsecond(clause->args), indexcol,
											  index));
				/* Must flip operator to get the opclass member */
				clause_op = get_commutator(clause_op);
				varonleft = false;
			}
			if (!OidIsValid(clause_op))
				continue;		/* ignore non match, per next comment */
			op_strategy = get_op_opclass_strategy(clause_op, opclass);

			/*
			 * You might expect to see Assert(op_strategy != 0) here, but you
			 * won't: the clause might contain a special indexable operator
			 * rather than an ordinary opclass member.	Currently none of the
			 * special operators are very likely to expand to an equality
			 * operator; we do not bother to check, but just assume no match.
			 */
			if (op_strategy != BTEqualStrategyNumber)
				continue;

			/* Now check that other side is pseudoconstant */
			if (varonleft)
				ispc = is_pseudo_constant_clause_relids(lsecond(clause->args),
														rinfo->right_relids);
			else
				ispc = is_pseudo_constant_clause_relids(linitial(clause->args),
														rinfo->left_relids);
			if (ispc)
			{
				result = lappend_int(result, indexcol + 1);
				break;
			}
		}
		indexcol++;
	}
	return result;
}

/*
 * match_index_to_query_keys
 *		Check a single scan direction for "intelligent" match to query keys
 *
 * 'index' is the index of interest.
 * 'indexscandir' is the scan direction to consider
 * 'ignorables' is an integer list of indexes of ignorable index columns
 *
 * Returns TRUE on successful match (ie, the query_pathkeys can be considered
 * to match this index).
 */
static bool
match_index_to_query_keys(PlannerInfo *root,
						  IndexOptInfo *index,
						  ScanDirection indexscandir,
						  List *ignorables)
{
	List	   *index_pathkeys;
	ListCell   *index_cell;
	int			index_col;
	ListCell   *r;

	/* Get the pathkeys that exactly describe the index */
	index_pathkeys = build_index_pathkeys(root, index, indexscandir, false);

	/*
	 * Can we match to the query's requested pathkeys?  The inner loop skips
	 * over ignorable index columns while trying to match.
	 */
	index_cell = list_head(index_pathkeys);
	index_col = 0;

	foreach(r, root->query_pathkeys)
	{
		List	   *rsubkey = (List *) lfirst(r);

		for (;;)
		{
			List	   *isubkey;

			if (index_cell == NULL)
				return false;
			isubkey = (List *) lfirst(index_cell);
			index_cell = lnext(index_cell);
			index_col++;		/* index_col is now 1-based */

			/*
			 * Since we are dealing with canonicalized pathkeys, pointer
			 * comparison is sufficient to determine a match.
			 */
			if (rsubkey == isubkey)
				break;			/* matched current query pathkey */

			if (!list_member_int(ignorables, index_col))
				return false;	/* definite failure to match */
			/* otherwise loop around and try to match to next index col */
		}
	}

	return true;
}

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

/*
 * flatten_clausegroups_list
 *	  Given a list of lists of RestrictInfos, flatten it to a list
 *	  of RestrictInfos.
 *
 * This is used to flatten out the result of group_clauses_by_indexkey()
 * to produce an indexclauses list.  The original list structure mustn't
 * be altered, but it's OK to share copies of the underlying RestrictInfos.
 */
List *
flatten_clausegroups_list(List *clausegroups)
{
	List	   *allclauses = NIL;
	ListCell   *l;

	foreach(l, clausegroups)
		allclauses = list_concat(allclauses, list_copy((List *) lfirst(l)));
	return allclauses;
}


/****************************************************************************
 *				----  ROUTINES TO CHECK OPERANDS  ----
 ****************************************************************************/

/*
 * match_index_to_operand()
 *	  Generalized test for a match between an index's key
 *	  and the operand on one side of a restriction or join clause.
 *
 * operand: the nodetree to be compared to the index
 * indexcol: the column number of the index (counting from 0)
 * index: the index of interest
 */
bool
match_index_to_operand(Node *operand,
					   int indexcol,
					   IndexOptInfo *index)
{
	int			indkey;

	/*
	 * Ignore any RelabelType node above the operand.	This is needed to be
	 * able to apply indexscanning in binary-compatible-operator cases. Note:
	 * we can assume there is at most one RelabelType node;
	 * eval_const_expressions() will have simplified if more than one.
	 */
	if (operand && IsA(operand, RelabelType))
		operand = (Node *) ((RelabelType *) operand)->arg;

	indkey = index->indexkeys[indexcol];
	if (indkey != 0)
	{
		/*
		 * Simple index column; operand must be a matching Var.
		 */
		if (operand && IsA(operand, Var) &&
			index->rel->relid == ((Var *) operand)->varno &&
			indkey == ((Var *) operand)->varattno)
			return true;
	}
	else
	{
		/*
		 * Index expression; find the correct expression.  (This search could
		 * be avoided, at the cost of complicating all the callers of this
		 * routine; doesn't seem worth it.)
		 */
		ListCell   *indexpr_item;
		int			i;
		Node	   *indexkey;

		indexpr_item = list_head(index->indexprs);
		for (i = 0; i < indexcol; i++)