pathkeys.c

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

			retvallen++;
		}
	}

	return retval;
}

/*
 * build_join_pathkeys
 *	  Build the path keys for a join relation constructed by mergejoin or
 *	  nestloop join.  These keys should include all the path key vars of the
 *	  outer path (since the join will retain the ordering of the outer path)
 *	  plus any vars of the inner path that are equijoined to the outer vars.
 *
 *	  Per the discussion in backend/optimizer/README, equijoined inner vars
 *	  can be considered path keys of the result, just the same as the outer
 *	  vars they were joined with; furthermore, it doesn't matter what kind
 *	  of join algorithm is actually used.
 *
 * 'joinrel' is the join relation that paths are being formed for
 * 'outer_pathkeys' is the list of the current outer path's path keys
 *
 * Returns the list of new path keys.
 */
List *
build_join_pathkeys(Query *root,
					RelOptInfo *joinrel,
					List *outer_pathkeys)
{
	/*
	 * This used to be quite a complex bit of code, but now that all
	 * pathkey sublists start out life canonicalized, we don't have to do
	 * a darn thing here!  The inner-rel vars we used to need to add are
	 * *already* part of the outer pathkey!
	 *
	 * We do, however, need to truncate the pathkeys list, since it may
	 * contain pathkeys that were useful for forming this joinrel but are
	 * uninteresting to higher levels.
	 */
	return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
}

/****************************************************************************
 *		PATHKEYS AND SORT CLAUSES
 ****************************************************************************/

/*
 * make_pathkeys_for_sortclauses
 *		Generate a pathkeys list that represents the sort order specified
 *		by a list of SortClauses (GroupClauses will work too!)
 *
 * NB: the result is NOT in canonical form, but must be passed through
 * canonicalize_pathkeys() before it can be used for comparisons or
 * labeling relation sort orders.  (We do things this way because
 * grouping_planner needs to be able to construct requested pathkeys
 * before the pathkey equivalence sets have been created for the query.)
 *
 * 'sortclauses' is a list of SortClause or GroupClause nodes
 * 'tlist' is the targetlist to find the referenced tlist entries in
 */
List *
make_pathkeys_for_sortclauses(List *sortclauses,
							  List *tlist)
{
	List	   *pathkeys = NIL;
	List	   *i;

	foreach(i, sortclauses)
	{
		SortClause *sortcl = (SortClause *) lfirst(i);
		Node	   *sortkey;
		PathKeyItem *pathkey;

		sortkey = get_sortgroupclause_expr(sortcl, tlist);
		pathkey = makePathKeyItem(sortkey, sortcl->sortop, true);

		/*
		 * The pathkey becomes a one-element sublist, for now;
		 * canonicalize_pathkeys() might replace it with a longer sublist
		 * later.
		 */
		pathkeys = lappend(pathkeys, makeList1(pathkey));
	}
	return pathkeys;
}

/****************************************************************************
 *		PATHKEYS AND MERGECLAUSES
 ****************************************************************************/

/*
 * cache_mergeclause_pathkeys
 *		Make the cached pathkeys valid in a mergeclause restrictinfo.
 *
 * RestrictInfo contains fields in which we may cache the result
 * of looking up the canonical pathkeys for the left and right sides
 * of the mergeclause.	(Note that in normal cases they will be the
 * same, but not if the mergeclause appears above an OUTER JOIN.)
 * This is a worthwhile savings because these routines will be invoked
 * many times when dealing with a many-relation query.
 *
 * We have to be careful that the cached values are palloc'd in the same
 * context the RestrictInfo node itself is in.	This is not currently a
 * problem for normal planning, but it is an issue for GEQO planning.
 */
void
cache_mergeclause_pathkeys(Query *root, RestrictInfo *restrictinfo)
{
	Node	   *key;
	PathKeyItem *item;
	MemoryContext oldcontext;

	Assert(restrictinfo->mergejoinoperator != InvalidOid);

	if (restrictinfo->left_pathkey == NIL)
	{
		oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(restrictinfo));
		key = get_leftop(restrictinfo->clause);
		item = makePathKeyItem(key, restrictinfo->left_sortop, false);
		restrictinfo->left_pathkey = make_canonical_pathkey(root, item);
		MemoryContextSwitchTo(oldcontext);
	}
	if (restrictinfo->right_pathkey == NIL)
	{
		oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(restrictinfo));
		key = get_rightop(restrictinfo->clause);
		item = makePathKeyItem(key, restrictinfo->right_sortop, false);
		restrictinfo->right_pathkey = make_canonical_pathkey(root, item);
		MemoryContextSwitchTo(oldcontext);
	}
}

/*
 * find_mergeclauses_for_pathkeys
 *	  This routine attempts to find a set of mergeclauses that can be
 *	  used with a specified ordering for one of the input relations.
 *	  If successful, it returns a list of mergeclauses.
 *
 * 'pathkeys' is a pathkeys list showing the ordering of an input path.
 *			It doesn't matter whether it is for the inner or outer path.
 * 'restrictinfos' is a list of mergejoinable restriction clauses for the
 *			join relation being formed.
 *
 * The result is NIL if no merge can be done, else a maximal list of
 * usable mergeclauses (represented as a list of their restrictinfo nodes).
 *
 * XXX Ideally we ought to be considering context, ie what path orderings
 * are available on the other side of the join, rather than just making
 * an arbitrary choice among the mergeclauses that will work for this side
 * of the join.
 */
List *
find_mergeclauses_for_pathkeys(Query *root,
							   List *pathkeys,
							   List *restrictinfos)
{
	List	   *mergeclauses = NIL;
	List	   *i;

	/* make sure we have pathkeys cached in the clauses */
	foreach(i, restrictinfos)
	{
		RestrictInfo *restrictinfo = lfirst(i);

		cache_mergeclause_pathkeys(root, restrictinfo);
	}

	foreach(i, pathkeys)
	{
		List	   *pathkey = lfirst(i);
		List	   *matched_restrictinfos = NIL;
		List	   *j;

		/*
		 * We can match a pathkey against either left or right side of any
		 * mergejoin clause.  (We examine both sides since we aren't told
		 * if the given pathkeys are for inner or outer input path; no
		 * confusion is possible.)	Furthermore, if there are multiple
		 * matching clauses, take them all.  In plain inner-join scenarios
		 * we expect only one match, because redundant-mergeclause
		 * elimination will have removed any redundant mergeclauses from
		 * the input list. However, in outer-join scenarios there might be
		 * multiple matches. An example is
		 *
		 * select * from a full join b on a.v1 = b.v1 and a.v2 = b.v2 and
		 * a.v1 = b.v2;
		 *
		 * Given the pathkeys ((a.v1), (a.v2)) it is okay to return all three
		 * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and
		 * indeed we *must* do so or we will be unable to form a valid
		 * plan.
		 */
		foreach(j, restrictinfos)
		{
			RestrictInfo *restrictinfo = lfirst(j);

			/*
			 * We can compare canonical pathkey sublists by simple pointer
			 * equality; see compare_pathkeys.
			 */
			if ((pathkey == restrictinfo->left_pathkey ||
				 pathkey == restrictinfo->right_pathkey) &&
				!ptrMember(restrictinfo, mergeclauses))
			{
				matched_restrictinfos = lappend(matched_restrictinfos,
												restrictinfo);
			}
		}

		/*
		 * If we didn't find a mergeclause, we're done --- any additional
		 * sort-key positions in the pathkeys are useless.	(But we can
		 * still mergejoin if we found at least one mergeclause.)
		 */
		if (matched_restrictinfos == NIL)
			break;

		/*
		 * If we did find usable mergeclause(s) for this sort-key
		 * position, add them to result list.
		 */
		mergeclauses = nconc(mergeclauses, matched_restrictinfos);
	}

	return mergeclauses;
}

/*
 * make_pathkeys_for_mergeclauses
 *	  Builds a pathkey list representing the explicit sort order that
 *	  must be applied to a path in order to make it usable for the
 *	  given mergeclauses.
 *
 * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
 *			that will be used in a merge join.
 * 'rel' is the relation the pathkeys will apply to (ie, either the inner
 *			or outer side of the proposed join rel).
 *
 * Returns a pathkeys list that can be applied to the indicated relation.
 *
 * Note that it is not this routine's job to decide whether sorting is
 * actually needed for a particular input path.  Assume a sort is necessary;
 * just make the keys, eh?
 */
List *
make_pathkeys_for_mergeclauses(Query *root,
							   List *mergeclauses,
							   RelOptInfo *rel)
{
	List	   *pathkeys = NIL;
	List	   *i;

	foreach(i, mergeclauses)
	{
		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
		List	   *pathkey;

		cache_mergeclause_pathkeys(root, restrictinfo);

		if (bms_is_subset(restrictinfo->left_relids, rel->relids))
		{
			/* Rel is left side of mergeclause */
			pathkey = restrictinfo->left_pathkey;
		}
		else if (bms_is_subset(restrictinfo->right_relids, rel->relids))
		{
			/* Rel is right side of mergeclause */
			pathkey = restrictinfo->right_pathkey;
		}
		else
		{
			elog(ERROR, "could not identify which side of mergeclause to use");
			pathkey = NIL;		/* keep compiler quiet */
		}

		/*
		 * When we are given multiple merge clauses, it's possible that
		 * some clauses refer to the same vars as earlier clauses. There's
		 * no reason for us to specify sort keys like (A,B,A) when (A,B)
		 * will do --- and adding redundant sort keys makes add_path think
		 * that this sort order is different from ones that are really the
		 * same, so don't do it.  Since we now have a canonicalized
		 * pathkey, a simple ptrMember test is sufficient to detect
		 * redundant keys.
		 */
		if (!ptrMember(pathkey, pathkeys))
			pathkeys = lappend(pathkeys, pathkey);
	}

	return pathkeys;
}

/****************************************************************************
 *		PATHKEY USEFULNESS CHECKS
 *
 * We only want to remember as many of the pathkeys of a path as have some
 * potential use, either for subsequent mergejoins or for meeting the query's
 * requested output ordering.  This ensures that add_path() won't consider
 * a path to have a usefully different ordering unless it really is useful.
 * These routines check for usefulness of given pathkeys.
 ****************************************************************************/

/*
 * pathkeys_useful_for_merging
 *		Count the number of pathkeys that may be useful for mergejoins
 *		above the given relation (by looking at its joininfo lists).
 *
 * We consider a pathkey potentially useful if it corresponds to the merge
 * ordering of either side of any joinclause for the rel.  This might be
 * overoptimistic, since joinclauses that appear in different join lists
 * might never be usable at the same time, but trying to be exact is likely
 * to be more trouble than it's worth.
 */
int
pathkeys_useful_for_merging(Query *root, RelOptInfo *rel, List *pathkeys)
{
	int			useful = 0;
	List	   *i;

	foreach(i, pathkeys)
	{
		List	   *pathkey = lfirst(i);
		bool		matched = false;
		List	   *j;

		foreach(j, rel->joininfo)
		{
			JoinInfo   *joininfo = (JoinInfo *) lfirst(j);
			List	   *k;

			foreach(k, joininfo->jinfo_restrictinfo)
			{
				RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(k);

				if (restrictinfo->mergejoinoperator == InvalidOid)
					continue;
				cache_mergeclause_pathkeys(root, restrictinfo);

				/*
				 * We can compare canonical pathkey sublists by simple
				 * pointer equality; see compare_pathkeys.
				 */
				if (pathkey == restrictinfo->left_pathkey ||
					pathkey == restrictinfo->right_pathkey)
				{
					matched = true;
					break;
				}
			}

			if (matched)
				break;
		}

		/*
		 * If we didn't find a mergeclause, we're done --- any additional
		 * sort-key positions in the pathkeys are useless.	(But we can
		 * still mergejoin if we found at least one mergeclause.)
		 */
		if (matched)
			useful++;
		else
			break;
	}

	return useful;
}

/*
 * pathkeys_useful_for_ordering
 *		Count the number of pathkeys that are useful for meeting the
 *		query's requested output ordering.
 *
 * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
 * no good to order by just the first key(s) of the requested ordering.
 * So the result is always either 0 or length(root->query_pathkeys).
 */
int
pathkeys_useful_for_ordering(Query *root, List *pathkeys)
{
	if (root->query_pathkeys == NIL)
		return 0;				/* no special ordering requested */

	if (pathkeys == NIL)
		return 0;				/* unordered path */

	if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
	{
		/* It's useful ... or at least the first N keys are */
		return length(root->query_pathkeys);
	}

	return 0;					/* path ordering not useful */
}

/*
 * truncate_useless_pathkeys
 *		Shorten the given pathkey list to just the useful pathkeys.
 */
List *
truncate_useless_pathkeys(Query *root,
						  RelOptInfo *rel,
						  List *pathkeys)
{
	int			nuseful;
	int			nuseful2;

	nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
	nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
	if (nuseful2 > nuseful)
		nuseful = nuseful2;

	/*
	 * Note: not safe to modify input list destructively, but we can avoid
	 * copying the list if we're not actually going to change it
	 */
	if (nuseful == length(pathkeys))
		return pathkeys;
	else
		return ltruncate(nuseful, listCopy(pathkeys));
}