indxpath.c

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

/*
 * indexable_outerrelids
 *	  Finds all other relids that participate in any indexable join clause
 *	  for the specified index.	Returns a set of relids.
 *
 * 'rel' is the relation for which 'index' is defined
 */
static Relids
indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index)
{
	Relids		outer_relids = NULL;
	List	   *i;

	foreach(i, rel->joininfo)
	{
		JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
		bool		match_found = false;
		List	   *j;

		/*
		 * Examine each joinclause in the JoinInfo node's list to see if
		 * it matches any key of the index.  If so, add the JoinInfo's
		 * otherrels to the result.  We can skip examining other
		 * joinclauses in the same list as soon as we find a match (since
		 * by definition they all have the same otherrels).
		 */
		foreach(j, joininfo->jinfo_restrictinfo)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
			Expr	   *clause = rinfo->clause;
			int			indexcol = 0;
			Oid		   *classes = index->classlist;

			do
			{
				Oid			curClass = classes[0];

				if (match_join_clause_to_indexcol(rel,
												  index,
												  indexcol,
												  curClass,
												  clause))
				{
					match_found = true;
					break;
				}

				indexcol++;
				classes++;

			} while (!DoneMatchingIndexKeys(classes));

			if (match_found)
				break;
		}

		if (match_found)
		{
			outer_relids = bms_add_members(outer_relids,
										   joininfo->unjoined_relids);
		}
	}

	return outer_relids;
}

/*
 * best_inner_indexscan
 *	  Finds the best available inner indexscan for a nestloop join
 *	  with the given rel on the inside and the given outer_relids outside.
 *	  May return NULL if there are no possible inner indexscans.
 *
 * We ignore ordering considerations (since a nestloop's inner scan's order
 * is uninteresting).  Also, we consider only total cost when deciding which
 * of two possible paths is better --- this assumes that all indexpaths have
 * negligible startup cost.  (True today, but someday we might have to think
 * harder.)  Therefore, there is only one dimension of comparison and so it's
 * sufficient to return a single "best" path.
 */
Path *
best_inner_indexscan(Query *root, RelOptInfo *rel,
					 Relids outer_relids, JoinType jointype)
{
	Path	   *cheapest = NULL;
	bool		isouterjoin;
	List	   *ilist;
	List	   *jlist;
	InnerIndexscanInfo *info;
	MemoryContext oldcontext;

	/*
	 * Nestloop only supports inner, left, and IN joins.
	 */
	switch (jointype)
	{
		case JOIN_INNER:
		case JOIN_IN:
		case JOIN_UNIQUE_OUTER:
			isouterjoin = false;
			break;
		case JOIN_LEFT:
			isouterjoin = true;
			break;
		default:
			return NULL;
	}

	/*
	 * If there are no indexable joinclauses for this rel, exit quickly.
	 */
	if (bms_is_empty(rel->index_outer_relids))
		return NULL;

	/*
	 * Otherwise, we have to do path selection in the memory context of
	 * the given rel, so that any created path can be safely attached to
	 * the rel's cache of best inner paths.  (This is not currently an
	 * issue for normal planning, but it is an issue for GEQO planning.)
	 */
	oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));

	/*
	 * Intersect the given outer_relids with index_outer_relids to find
	 * the set of outer relids actually relevant for this index. If there
	 * are none, again we can fail immediately.
	 */
	outer_relids = bms_intersect(rel->index_outer_relids, outer_relids);
	if (bms_is_empty(outer_relids))
	{
		bms_free(outer_relids);
		MemoryContextSwitchTo(oldcontext);
		return NULL;
	}

	/*
	 * Look to see if we already computed the result for this set of
	 * relevant outerrels.	(We include the isouterjoin status in the
	 * cache lookup key for safety.  In practice I suspect this is not
	 * necessary because it should always be the same for a given
	 * innerrel.)
	 */
	foreach(jlist, rel->index_inner_paths)
	{
		info = (InnerIndexscanInfo *) lfirst(jlist);
		if (bms_equal(info->other_relids, outer_relids) &&
			info->isouterjoin == isouterjoin)
		{
			bms_free(outer_relids);
			MemoryContextSwitchTo(oldcontext);
			return info->best_innerpath;
		}
	}

	/*
	 * For each index of the rel, find the best path; then choose the best
	 * overall.  We cache the per-index results as well as the overall
	 * result.	(This is useful because different indexes may have
	 * different relevant outerrel sets, so different overall outerrel
	 * sets might still map to the same computation for a given index.)
	 */
	foreach(ilist, rel->indexlist)
	{
		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
		Relids		index_outer_relids;
		Path	   *path = NULL;

		/* identify set of relevant outer relids for this index */
		index_outer_relids = bms_intersect(index->outer_relids, outer_relids);
		/* skip if none */
		if (bms_is_empty(index_outer_relids))
		{
			bms_free(index_outer_relids);
			continue;
		}

		/*
		 * Look to see if we already computed the result for this index.
		 */
		foreach(jlist, index->inner_paths)
		{
			info = (InnerIndexscanInfo *) lfirst(jlist);
			if (bms_equal(info->other_relids, index_outer_relids) &&
				info->isouterjoin == isouterjoin)
			{
				path = info->best_innerpath;
				bms_free(index_outer_relids);	/* not needed anymore */
				break;
			}
		}

		if (jlist == NIL)		/* failed to find a match? */
		{
			List	   *clausegroups;

			/* find useful clauses for this index and outerjoin set */
			clausegroups = group_clauses_by_indexkey_for_join(root,
															  rel,
															  index,
													  index_outer_relids,
															  jointype,
															isouterjoin);
			if (clausegroups)
			{
				/* make the path */
				path = make_innerjoin_index_path(root, rel, index,
												 clausegroups);
			}

			/* Cache the result --- whether positive or negative */
			info = makeNode(InnerIndexscanInfo);
			info->other_relids = index_outer_relids;
			info->isouterjoin = isouterjoin;
			info->best_innerpath = path;
			index->inner_paths = lcons(info, index->inner_paths);
		}

		if (path != NULL &&
			(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;
}

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

/*
 * make_innerjoin_index_path
 *	  Create an index path node for a path to be used as an inner
 *	  relation in a nestloop join.
 *
 * 'rel' is the relation for which 'index' is defined
 * 'clausegroups' is a list of lists of RestrictInfos that can use 'index'
 */
static Path *
make_innerjoin_index_path(Query *root,
						  RelOptInfo *rel, IndexOptInfo *index,
						  List *clausegroups)
{
	IndexPath  *pathnode = makeNode(IndexPath);
	List	   *indexquals,
			   *allclauses,
			   *l;

	/* XXX perhaps this code should be merged with create_index_path? */

	pathnode->path.pathtype = T_IndexScan;
	pathnode->path.parent = rel;

	/*
	 * There's no point in marking the path with any pathkeys, since it
	 * will only ever be used as the inner path of a nestloop, and so its
	 * ordering does not matter.
	 */
	pathnode->path.pathkeys = NIL;

	/* Convert RestrictInfo nodes to indexquals the executor can handle */
	indexquals = expand_indexqual_conditions(index, clausegroups);

	/*
	 * Also make a flattened list of the RestrictInfo nodes; createplan.c
	 * will need this later.  We assume here that we can destructively
	 * modify the passed-in clausegroups list structure.
	 */
	allclauses = NIL;
	foreach(l, clausegroups)
	{
		/* nconc okay here since same clause couldn't be in two sublists */
		allclauses = nconc(allclauses, (List *) lfirst(l));
	}

	/*
	 * Note that we are making a pathnode for a single-scan indexscan;
	 * therefore, indexinfo and indexqual should be single-element lists.
	 */
	pathnode->indexinfo = makeList1(index);
	pathnode->indexqual = makeList1(indexquals);
	pathnode->indexjoinclauses = makeList1(allclauses);

	/* We don't actually care what order the index scans in ... */
	pathnode->indexscandir = NoMovementScanDirection;

	/*
	 * We must compute the estimated number of output rows for the
	 * indexscan.  This is less than rel->rows because of the additional
	 * selectivity of the join clauses.  Since clausegroups may contain
	 * both restriction and join clauses, we have to do a set union to get
	 * the full set of clauses that must be considered to compute the
	 * correct selectivity.  (Without the union operation, we might have
	 * some restriction clauses appearing twice, which'd mislead
	 * restrictlist_selectivity into double-counting their selectivity.
	 * However, since RestrictInfo nodes aren't copied when linking them
	 * into different lists, it should be sufficient to use pointer
	 * comparison to remove duplicates.)
	 *
	 * Always assume the join type is JOIN_INNER; even if some of the join
	 * clauses come from other contexts, that's not our problem.
	 */
	allclauses = set_ptrUnion(rel->baserestrictinfo, allclauses);
	pathnode->rows = rel->tuples *
		restrictlist_selectivity(root,
								 allclauses,
								 rel->relid,
								 JOIN_INNER);
	/* Like costsize.c, force estimate to be at least one row */
	if (pathnode->rows < 1.0)
		pathnode->rows = 1.0;

	cost_index(&pathnode->path, root, rel, index, indexquals, true);

	return (Path *) pathnode;
}

/****************************************************************************
 *				----  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)
 * rel: the parent relation
 * index: the index of interest
 */
static bool
match_index_to_operand(Node *operand,
					   int indexcol,
					   RelOptInfo *rel,
					   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) &&
			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.)
		 */
		List	   *indexprs;
		int			i;
		Node	   *indexkey;

		indexprs = index->indexprs;
		for (i = 0; i < indexcol; i++)
		{
			if (index->indexkeys[i] == 0)
			{
				if (indexprs == NIL)
					elog(ERROR, "wrong number of index expressions");
				indexprs = lnext(indexprs);
			}
		}
		if (indexprs == NIL)
			elog(ERROR, "wrong number of index expressions");
		indexkey = (Node *) lfirst(indexprs);

		/*
		 * Does it match the operand?  Again, strip any relabeling.
		 */
		if (indexkey && IsA(indexkey, RelabelType))
			indexkey = (Node *) ((RelabelType *) indexkey)->arg;

		if (equal(indexkey, operand))
			return true;
	}

	return false;
}

/****************************************************************************
 *			----  ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS  ----
 ****************************************************************************/

/*----------
 * These routines handle special optimization of operators that can be
 * used with index scans even though they are not known to the executor's
 * indexscan machinery.  The key idea is that these operators allow us
 * to derive approximate indexscan qual clauses, such that any tuples
 * that pass the operator clause itself must also satisfy the simpler
 * indexscan condition(s).	Then we can use the indexscan machinery
 * to avoid scanning as much of the table as we'd otherwise have to,
 * while applying the original operator as a qpqual condition to ensure
 * we deliver only the tuples we want.	(In essence, we're using a regular
 * index as if it were a lossy index.)
 *
 * An example of what we're doing is
 *			textfield LIKE 'abc%'
 * from which we can generate the indexscanable conditions
 *			textfield >= 'abc' AND textfield < 'abd'
 * which allow efficient scanning of an index on textfield.
 * (In reality, character set and collation issues make the transformation
 * from LIKE to indexscan limits rather harder than one might think ...
 * but that's the basic idea.)
 *
 * Two routines are provided here, match_special_index_operator() and