pathkeys.c

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

/*-------------------------------------------------------------------------
 *
 * pathkeys.c
 *	  Utilities for matching and building path keys
 *
 * See src/backend/optimizer/README for a great deal of information about
 * the nature and use of path keys.
 *
 *
 * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.53.4.1 2003/12/03 17:45:36 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "nodes/makefuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "optimizer/tlist.h"
#include "optimizer/var.h"
#include "parser/parsetree.h"
#include "parser/parse_expr.h"
#include "parser/parse_func.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"


static PathKeyItem *makePathKeyItem(Node *key, Oid sortop, bool checkType);
static List *make_canonical_pathkey(Query *root, PathKeyItem *item);
static Var *find_indexkey_var(Query *root, RelOptInfo *rel,
				  AttrNumber varattno);


/*
 * makePathKeyItem
 *		create a PathKeyItem node
 */
static PathKeyItem *
makePathKeyItem(Node *key, Oid sortop, bool checkType)
{
	PathKeyItem *item = makeNode(PathKeyItem);

	/*
	 * Some callers pass expressions that are not necessarily of the same
	 * type as the sort operator expects as input (for example when dealing
	 * with an index that uses binary-compatible operators).  We must relabel
	 * these with the correct type so that the key expressions will be seen
	 * as equal() to expressions that have been correctly labeled.
	 */
	if (checkType)
	{
		Oid			lefttype,
					righttype;

		op_input_types(sortop, &lefttype, &righttype);
		if (exprType(key) != lefttype)
			key = (Node *) makeRelabelType((Expr *) key,
										   lefttype, -1,
										   COERCE_DONTCARE);
	}

	item->key = key;
	item->sortop = sortop;
	return item;
}

/*
 * add_equijoined_keys
 *	  The given clause has a mergejoinable operator, so its two sides
 *	  can be considered equal after restriction clause application; in
 *	  particular, any pathkey mentioning one side (with the correct sortop)
 *	  can be expanded to include the other as well.  Record the exprs and
 *	  associated sortops in the query's equi_key_list for future use.
 *
 * The query's equi_key_list field points to a list of sublists of PathKeyItem
 * nodes, where each sublist is a set of two or more exprs+sortops that have
 * been identified as logically equivalent (and, therefore, we may consider
 * any two in a set to be equal).  As described above, we will subsequently
 * use direct pointers to one of these sublists to represent any pathkey
 * that involves an equijoined variable.
 */
void
add_equijoined_keys(Query *root, RestrictInfo *restrictinfo)
{
	Expr	   *clause = restrictinfo->clause;
	PathKeyItem *item1 = makePathKeyItem(get_leftop(clause),
										 restrictinfo->left_sortop,
										 false);
	PathKeyItem *item2 = makePathKeyItem(get_rightop(clause),
										 restrictinfo->right_sortop,
										 false);
	List	   *newset,
			   *cursetlink;

	/* We might see a clause X=X; don't make a single-element list from it */
	if (equal(item1, item2))
		return;

	/*
	 * Our plan is to make a two-element set, then sweep through the
	 * existing equijoin sets looking for matches to item1 or item2.  When
	 * we find one, we remove that set from equi_key_list and union it
	 * into our new set. When done, we add the new set to the front of
	 * equi_key_list.
	 *
	 * It may well be that the two items we're given are already known to be
	 * equijoin-equivalent, in which case we don't need to change our data
	 * structure.  If we find both of them in the same equivalence set to
	 * start with, we can quit immediately.
	 *
	 * This is a standard UNION-FIND problem, for which there exist better
	 * data structures than simple lists.  If this code ever proves to be
	 * a bottleneck then it could be sped up --- but for now, simple is
	 * beautiful.
	 */
	newset = NIL;

	/* cannot use foreach here because of possible lremove */
	cursetlink = root->equi_key_list;
	while (cursetlink)
	{
		List	   *curset = lfirst(cursetlink);
		bool		item1here = member(item1, curset);
		bool		item2here = member(item2, curset);

		/* must advance cursetlink before lremove possibly pfree's it */
		cursetlink = lnext(cursetlink);

		if (item1here || item2here)
		{
			/*
			 * If find both in same equivalence set, no need to do any
			 * more
			 */
			if (item1here && item2here)
			{
				/* Better not have seen only one in an earlier set... */
				Assert(newset == NIL);
				return;
			}

			/* Build the new set only when we know we must */
			if (newset == NIL)
				newset = makeList2(item1, item2);

			/* Found a set to merge into our new set */
			newset = set_union(newset, curset);

			/*
			 * Remove old set from equi_key_list.
			 */
			root->equi_key_list = lremove(curset, root->equi_key_list);
			freeList(curset);	/* might as well recycle old cons cells */
		}
	}

	/* Build the new set only when we know we must */
	if (newset == NIL)
		newset = makeList2(item1, item2);

	root->equi_key_list = lcons(newset, root->equi_key_list);
}

/*
 * generate_implied_equalities
 *	  Scan the completed equi_key_list for the query, and generate explicit
 *	  qualifications (WHERE clauses) for all the pairwise equalities not
 *	  already mentioned in the quals; or remove qualifications found to be
 *	  redundant.
 *
 * Adding deduced equalities is useful because the additional clauses help
 * the selectivity-estimation code and may allow better joins to be chosen;
 * and in fact it's *necessary* to ensure that sort keys we think are
 * equivalent really are (see src/backend/optimizer/README for more info).
 *
 * If an equi_key_list set includes any constants then we adopt a different
 * strategy: we record all the "var = const" deductions we can make, and
 * actively remove all the "var = var" clauses that are implied by the set
 * (including the clauses that originally gave rise to the set!).  The reason
 * is that given input like "a = b AND b = 42", once we have deduced "a = 42"
 * there is no longer any need to apply the clause "a = b"; not only is
 * it a waste of time to check it, but we will misestimate selectivity if the
 * clause is left in.  So we must remove it.  For this purpose, any pathkey
 * item that mentions no Vars of the current level can be taken as a constant.
 * (The only case where this would be risky is if the item contains volatile
 * functions; but we will never consider such an expression to be a pathkey
 * at all, because check_mergejoinable() will reject it.)
 *
 * This routine just walks the equi_key_list to find all pairwise equalities.
 * We call process_implied_equality (in plan/initsplan.c) to adjust the
 * restrictinfo datastructures for each pair.
 */
void
generate_implied_equalities(Query *root)
{
	List	   *cursetlink;

	foreach(cursetlink, root->equi_key_list)
	{
		List	   *curset = lfirst(cursetlink);
		int			nitems = length(curset);
		Relids	   *relids;
		bool		have_consts;
		List	   *ptr1;
		int			i1;

		/*
		 * A set containing only two items cannot imply any equalities
		 * beyond the one that created the set, so we can skip it.
		 */
		if (nitems < 3)
			continue;

		/*
		 * Collect info about relids mentioned in each item.  For this
		 * routine we only really care whether there are any at all in
		 * each item, but process_implied_equality() needs the exact sets,
		 * so we may as well pull them here.
		 */
		relids = (Relids *) palloc(nitems * sizeof(Relids));
		have_consts = false;
		i1 = 0;
		foreach(ptr1, curset)
		{
			PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);

			relids[i1] = pull_varnos(item1->key);
			if (bms_is_empty(relids[i1]))
				have_consts = true;
			i1++;
		}

		/*
		 * Match each item in the set with all that appear after it (it's
		 * sufficient to generate A=B, need not process B=A too).
		 */
		i1 = 0;
		foreach(ptr1, curset)
		{
			PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
			bool		i1_is_variable = !bms_is_empty(relids[i1]);
			List	   *ptr2;
			int			i2 = i1 + 1;

			foreach(ptr2, lnext(ptr1))
			{
				PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2);
				bool		i2_is_variable = !bms_is_empty(relids[i2]);

				/*
				 * If it's "const = const" then just ignore it altogether.
				 * There is no place in the restrictinfo structure to
				 * store it.  (If the two consts are in fact unequal, then
				 * propagating the comparison to Vars will cause us to
				 * produce zero rows out, as expected.)
				 */
				if (i1_is_variable || i2_is_variable)
				{
					/*
					 * Tell process_implied_equality to delete the clause,
					 * not add it, if it's "var = var" and we have
					 * constants present in the list.
					 */
					bool		delete_it = (have_consts &&
											 i1_is_variable &&
											 i2_is_variable);

					process_implied_equality(root,
											 item1->key, item2->key,
											 item1->sortop, item2->sortop,
											 relids[i1], relids[i2],
											 delete_it);
				}
				i2++;
			}
			i1++;
		}
	}
}

/*
 * exprs_known_equal
 *	  Detect whether two expressions are known equal due to equijoin clauses.
 *
 * Note: does not bother to check for "equal(item1, item2)"; caller must
 * check that case if it's possible to pass identical items.
 */
bool
exprs_known_equal(Query *root, Node *item1, Node *item2)
{
	List	   *cursetlink;

	foreach(cursetlink, root->equi_key_list)
	{
		List	   *curset = lfirst(cursetlink);
		bool		item1member = false;
		bool		item2member = false;
		List	   *ptr;

		foreach(ptr, curset)
		{
			PathKeyItem *pitem = (PathKeyItem *) lfirst(ptr);

			if (equal(item1, pitem->key))
				item1member = true;
			else if (equal(item2, pitem->key))
				item2member = true;
			/* Exit as soon as equality is proven */
			if (item1member && item2member)
				return true;
		}
	}
	return false;
}


/*
 * make_canonical_pathkey
 *	  Given a PathKeyItem, find the equi_key_list subset it is a member of,
 *	  if any.  If so, return a pointer to that sublist, which is the
 *	  canonical representation (for this query) of that PathKeyItem's
 *	  equivalence set.	If it is not found, add a singleton "equivalence set"
 *	  to the equi_key_list and return that --- see compare_pathkeys.
 *
 * Note that this function must not be used until after we have completed
 * scanning the WHERE clause for equijoin operators.
 */
static List *
make_canonical_pathkey(Query *root, PathKeyItem *item)
{
	List	   *cursetlink;
	List	   *newset;

	foreach(cursetlink, root->equi_key_list)
	{
		List	   *curset = lfirst(cursetlink);

		if (member(item, curset))
			return curset;
	}
	newset = makeList1(item);
	root->equi_key_list = lcons(newset, root->equi_key_list);
	return newset;
}

/*
 * canonicalize_pathkeys
 *	   Convert a not-necessarily-canonical pathkeys list to canonical form.
 *
 * Note that this function must not be used until after we have completed
 * scanning the WHERE clause for equijoin operators.
 */
List *
canonicalize_pathkeys(Query *root, List *pathkeys)
{
	List	   *new_pathkeys = NIL;
	List	   *i;

	foreach(i, pathkeys)
	{
		List	   *pathkey = (List *) lfirst(i);
		PathKeyItem *item;
		List	   *cpathkey;

		/*
		 * It's sufficient to look at the first entry in the sublist; if
		 * there are more entries, they're already part of an equivalence
		 * set by definition.
		 */
		Assert(pathkey != NIL);
		item = (PathKeyItem *) lfirst(pathkey);
		cpathkey = make_canonical_pathkey(root, item);

		/*
		 * Eliminate redundant ordering requests --- ORDER BY A,A is the
		 * same as ORDER BY A.	We want to check this only after we have
		 * canonicalized the keys, so that equivalent-key knowledge is
		 * used when deciding if an item is redundant.
		 */
		if (!ptrMember(cpathkey, new_pathkeys))
			new_pathkeys = lappend(new_pathkeys, cpathkey);
	}
	return new_pathkeys;
}


/*
 * count_canonical_peers
 *	  Given a PathKeyItem, find the equi_key_list subset it is a member of,
 *	  if any.  If so, return the number of other members of the set.
 *	  If not, return 0 (without actually adding it to our equi_key_list).
 *
 * This is a hack to support the rather bogus heuristics in
 * build_subquery_pathkeys.
 */
static int
count_canonical_peers(Query *root, PathKeyItem *item)
{
	List	   *cursetlink;

	foreach(cursetlink, root->equi_key_list)
	{
		List	   *curset = lfirst(cursetlink);

		if (member(item, curset))
			return length(curset) - 1;
	}
	return 0;
}

/****************************************************************************
 *		PATHKEY COMPARISONS
 ****************************************************************************/

/*
 * compare_pathkeys