pathkeys.c

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

/*-------------------------------------------------------------------------
 *
 * 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-2005, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.73.2.2 2006/01/29 17:27:50 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 void generate_outer_join_implications(PlannerInfo *root,
								 List *equi_key_set,
								 Relids *relids);
static void sub_generate_join_implications(PlannerInfo *root,
							   List *equi_key_set, Relids *relids,
							   Node *item1, Oid sortop1,
							   Relids item1_relids);
static void process_implied_const_eq(PlannerInfo *root,
						 List *equi_key_set, Relids *relids,
						 Node *item1, Oid sortop1,
						 Relids item1_relids,
						 bool delete_it);
static List *make_canonical_pathkey(PlannerInfo *root, PathKeyItem *item);
static Var *find_indexkey_var(PlannerInfo *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(PlannerInfo *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;
	ListCell   *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 = list_head(root->equi_key_list);
	while (cursetlink)
	{
		List	   *curset = (List *) lfirst(cursetlink);
		bool		item1here = list_member(curset, item1);
		bool		item2here = list_member(curset, item2);

		/* 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 = list_make2(item1, item2);

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

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

	/* Build the new set only when we know we must */
	if (newset == NIL)
		newset = list_make2(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.)
 *
 * Also, when we have constants in an equi_key_list we can try to propagate
 * the constants into outer joins; see generate_outer_join_implications
 * for discussion.
 *
 * 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(PlannerInfo *root)
{
	ListCell   *cursetlink;

	foreach(cursetlink, root->equi_key_list)
	{
		List	   *curset = (List *) lfirst(cursetlink);
		int			nitems = list_length(curset);
		Relids	   *relids;
		bool		have_consts;
		ListCell   *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 --- unless outer
		 * joins appear in the query.
		 */
		if (nitems < 3 && !root->hasOuterJoins)
			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).
		 *
		 * A set containing only two items cannot imply any equalities beyond
		 * the one that created the set, so we can skip this processing in
		 * that case.
		 */
		if (nitems >= 3)
		{
			i1 = 0;
			foreach(ptr1, curset)
			{
				PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
				bool		i1_is_variable = !bms_is_empty(relids[i1]);
				ListCell   *ptr2;
				int			i2 = i1 + 1;

				for_each_cell(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++;
			}
		}

		/*
		 * If we have constant(s) and outer joins, try to propagate the
		 * constants through outer-join quals.
		 */
		if (have_consts && root->hasOuterJoins)
			generate_outer_join_implications(root, curset, relids);
	}
}

/*
 * generate_outer_join_implications
 *	  Generate clauses that can be deduced in outer-join situations.
 *
 * When we have mergejoinable clauses A = B that are outer-join clauses,
 * we can't blindly combine them with other clauses A = C to deduce B = C,
 * since in fact the "equality" A = B won't necessarily hold above the
 * outer join (one of the variables might be NULL instead).  Nonetheless
 * there are cases where we can add qual clauses using transitivity.
 *
 * One case that we look for here is an outer-join clause OUTERVAR = INNERVAR
 * combined with a pushed-down (valid everywhere) clause OUTERVAR = CONSTANT.
 * It is safe and useful to push a clause INNERVAR = CONSTANT into the
 * evaluation of the inner (nullable) relation, because any inner rows not
 * meeting this condition will not contribute to the outer-join result anyway.
 * (Any outer rows they could join to will be eliminated by the pushed-down
 * clause.)
 *
 * Note that the above rule does not work for full outer joins, nor for
 * pushed-down restrictions on an inner-side variable; nor is it very
 * interesting to consider cases where the pushed-down clause involves
 * relations entirely outside the outer join, since such clauses couldn't
 * be pushed into the inner side's scan anyway.  So the restriction to
 * outervar = pseudoconstant is not really giving up anything.
 *
 * For full-join cases, we can only do something useful if it's a FULL JOIN
 * USING and a merged column has a restriction MERGEDVAR = CONSTANT.  By
 * the time it gets here, the restriction will look like
 *		COALESCE(LEFTVAR, RIGHTVAR) = CONSTANT
 * and we will have a join clause LEFTVAR = RIGHTVAR that we can match the
 * COALESCE expression to.	In this situation we can push LEFTVAR = CONSTANT
 * and RIGHTVAR = CONSTANT into the input relations, since any rows not
 * meeting these conditions cannot contribute to the join result.
 *
 * Again, there isn't any traction to be gained by trying to deal with
 * clauses comparing a mergedvar to a non-pseudoconstant.  So we can make
 * use of the equi_key_lists to quickly find the interesting pushed-down
 * clauses.  The interesting outer-join clauses were accumulated for us by
 * distribute_qual_to_rels.
 *
 * equi_key_set: a list of PathKeyItems that are known globally equivalent,
 * at least one of which is a pseudoconstant.
 * relids: an array of Relids sets showing the relation membership of each
 * PathKeyItem in equi_key_set.
 */
static void
generate_outer_join_implications(PlannerInfo *root,
								 List *equi_key_set,
								 Relids *relids)
{
	ListCell   *l;
	int			i = 0;

	/* Process each non-constant element of equi_key_set */
	foreach(l, equi_key_set)
	{
		PathKeyItem *item1 = (PathKeyItem *) lfirst(l);

		if (!bms_is_empty(relids[i]))
		{
			sub_generate_join_implications(root, equi_key_set, relids,
										   item1->key,
										   item1->sortop,
										   relids[i]);
		}
		i++;
	}
}