equivclass.c

来自「postgresql8.3.4源码,开源数据库」· C语言 代码 · 共 1,975 行 · 第 1/5 页

/*-------------------------------------------------------------------------
 *
 * equivclass.c
 *	  Routines for managing EquivalenceClasses
 *
 * See src/backend/optimizer/README for discussion of EquivalenceClasses.
 *
 *
 * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql/src/backend/optimizer/path/equivclass.c,v 1.9.2.1 2008/03/31 16:59:33 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/skey.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "optimizer/prep.h"
#include "optimizer/var.h"
#include "utils/lsyscache.h"


static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
			  Expr *expr, Relids relids,
			  bool is_child, Oid datatype);
static void generate_base_implied_equalities_const(PlannerInfo *root,
									   EquivalenceClass *ec);
static void generate_base_implied_equalities_no_const(PlannerInfo *root,
										  EquivalenceClass *ec);
static void generate_base_implied_equalities_broken(PlannerInfo *root,
										EquivalenceClass *ec);
static List *generate_join_implied_equalities_normal(PlannerInfo *root,
										EquivalenceClass *ec,
										RelOptInfo *joinrel,
										RelOptInfo *outer_rel,
										RelOptInfo *inner_rel);
static List *generate_join_implied_equalities_broken(PlannerInfo *root,
										EquivalenceClass *ec,
										RelOptInfo *joinrel,
										RelOptInfo *outer_rel,
										RelOptInfo *inner_rel);
static Oid select_equality_operator(EquivalenceClass *ec,
						 Oid lefttype, Oid righttype);
static RestrictInfo *create_join_clause(PlannerInfo *root,
				   EquivalenceClass *ec, Oid opno,
				   EquivalenceMember *leftem,
				   EquivalenceMember *rightem,
				   EquivalenceClass *parent_ec);
static bool reconsider_outer_join_clause(PlannerInfo *root,
							 RestrictInfo *rinfo,
							 bool outer_on_left);
static bool reconsider_full_join_clause(PlannerInfo *root,
							RestrictInfo *rinfo);


/*
 * process_equivalence
 *	  The given clause has a mergejoinable operator and can be applied without
 *	  any delay by an outer join, so its two sides can be considered equal
 *	  anywhere they are both computable; moreover that equality can be
 *	  extended transitively.  Record this knowledge in the EquivalenceClass
 *	  data structure.  Returns TRUE if successful, FALSE if not (in which
 *	  case caller should treat the clause as ordinary, not an equivalence).
 *
 * If below_outer_join is true, then the clause was found below the nullable
 * side of an outer join, so its sides might validly be both NULL rather than
 * strictly equal.	We can still deduce equalities in such cases, but we take
 * care to mark an EquivalenceClass if it came from any such clauses.  Also,
 * we have to check that both sides are either pseudo-constants or strict
 * functions of Vars, else they might not both go to NULL above the outer
 * join.  (This is the reason why we need a failure return.  It's more
 * convenient to check this case here than at the call sites...)
 *
 * Note: constructing merged EquivalenceClasses 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.
 *
 * Note: this is only called during planner startup, not during GEQO
 * exploration, so we need not worry about whether we're in the right
 * memory context.
 */
bool
process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
					bool below_outer_join)
{
	Expr	   *clause = restrictinfo->clause;
	Oid			opno,
				item1_type,
				item2_type;
	Expr	   *item1;
	Expr	   *item2;
	Relids		item1_relids,
				item2_relids;
	List	   *opfamilies;
	EquivalenceClass *ec1,
			   *ec2;
	EquivalenceMember *em1,
			   *em2;
	ListCell   *lc1;

	/* Extract info from given clause */
	Assert(is_opclause(clause));
	opno = ((OpExpr *) clause)->opno;
	item1 = (Expr *) get_leftop(clause);
	item2 = (Expr *) get_rightop(clause);
	item1_relids = restrictinfo->left_relids;
	item2_relids = restrictinfo->right_relids;

	/*
	 * If below outer join, check for strictness, else reject.
	 */
	if (below_outer_join)
	{
		if (!bms_is_empty(item1_relids) &&
			contain_nonstrict_functions((Node *) item1))
			return false;		/* LHS is non-strict but not constant */
		if (!bms_is_empty(item2_relids) &&
			contain_nonstrict_functions((Node *) item2))
			return false;		/* RHS is non-strict but not constant */
	}

	/*
	 * We use the declared input types of the operator, not exprType() of the
	 * inputs, as the nominal datatypes for opfamily lookup.  This presumes
	 * that btree operators are always registered with amoplefttype and
	 * amoprighttype equal to their declared input types.  We will need this
	 * info anyway to build EquivalenceMember nodes, and by extracting it now
	 * we can use type comparisons to short-circuit some equal() tests.
	 */
	op_input_types(opno, &item1_type, &item2_type);

	opfamilies = restrictinfo->mergeopfamilies;

	/*
	 * Sweep through the existing EquivalenceClasses looking for matches to
	 * item1 and item2.  These are the possible outcomes:
	 *
	 * 1. We find both in the same EC.	The equivalence is already known, so
	 * there's nothing to do.
	 *
	 * 2. We find both in different ECs.  Merge the two ECs together.
	 *
	 * 3. We find just one.  Add the other to its EC.
	 *
	 * 4. We find neither.	Make a new, two-entry EC.
	 *
	 * Note: since all ECs are built through this process, it's impossible
	 * that we'd match an item in more than one existing EC.  It is possible
	 * to match more than once within an EC, if someone fed us something silly
	 * like "WHERE X=X".  (However, we can't simply discard such clauses,
	 * since they should fail when X is null; so we will build a 2-member EC
	 * to ensure the correct restriction clause gets generated.  Hence there
	 * is no shortcut here for item1 and item2 equal.)
	 */
	ec1 = ec2 = NULL;
	em1 = em2 = NULL;
	foreach(lc1, root->eq_classes)
	{
		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
		ListCell   *lc2;

		/* Never match to a volatile EC */
		if (cur_ec->ec_has_volatile)
			continue;

		/*
		 * A "match" requires matching sets of btree opfamilies.  Use of
		 * equal() for this test has implications discussed in the comments
		 * for get_mergejoin_opfamilies().
		 */
		if (!equal(opfamilies, cur_ec->ec_opfamilies))
			continue;

		foreach(lc2, cur_ec->ec_members)
		{
			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);

			Assert(!cur_em->em_is_child);		/* no children yet */

			/*
			 * If below an outer join, don't match constants: they're not as
			 * constant as they look.
			 */
			if ((below_outer_join || cur_ec->ec_below_outer_join) &&
				cur_em->em_is_const)
				continue;

			if (!ec1 &&
				item1_type == cur_em->em_datatype &&
				equal(item1, cur_em->em_expr))
			{
				ec1 = cur_ec;
				em1 = cur_em;
				if (ec2)
					break;
			}

			if (!ec2 &&
				item2_type == cur_em->em_datatype &&
				equal(item2, cur_em->em_expr))
			{
				ec2 = cur_ec;
				em2 = cur_em;
				if (ec1)
					break;
			}
		}

		if (ec1 && ec2)
			break;
	}

	/* Sweep finished, what did we find? */

	if (ec1 && ec2)
	{
		/* If case 1, nothing to do, except add to sources */
		if (ec1 == ec2)
		{
			ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
			ec1->ec_below_outer_join |= below_outer_join;
			/* mark the RI as usable with this pair of EMs */
			/* NB: can't set left_ec/right_ec until merging is finished */
			restrictinfo->left_em = em1;
			restrictinfo->right_em = em2;
			return true;
		}

		/*
		 * Case 2: need to merge ec1 and ec2.  We add ec2's items to ec1, then
		 * set ec2's ec_merged link to point to ec1 and remove ec2 from the
		 * eq_classes list.  We cannot simply delete ec2 because that could
		 * leave dangling pointers in existing PathKeys.  We leave it behind
		 * with a link so that the merged EC can be found.
		 */
		ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
		ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
		ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
		ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
		ec1->ec_has_const |= ec2->ec_has_const;
		/* can't need to set has_volatile */
		ec1->ec_below_outer_join |= ec2->ec_below_outer_join;
		ec2->ec_merged = ec1;
		root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
		/* just to avoid debugging confusion w/ dangling pointers: */
		ec2->ec_members = NIL;
		ec2->ec_sources = NIL;
		ec2->ec_derives = NIL;
		ec2->ec_relids = NULL;
		ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
		ec1->ec_below_outer_join |= below_outer_join;
		/* mark the RI as usable with this pair of EMs */
		restrictinfo->left_em = em1;
		restrictinfo->right_em = em2;
	}
	else if (ec1)
	{
		/* Case 3: add item2 to ec1 */
		em2 = add_eq_member(ec1, item2, item2_relids, false, item2_type);
		ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
		ec1->ec_below_outer_join |= below_outer_join;
		/* mark the RI as usable with this pair of EMs */
		restrictinfo->left_em = em1;
		restrictinfo->right_em = em2;
	}
	else if (ec2)
	{
		/* Case 3: add item1 to ec2 */
		em1 = add_eq_member(ec2, item1, item1_relids, false, item1_type);
		ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
		ec2->ec_below_outer_join |= below_outer_join;
		/* mark the RI as usable with this pair of EMs */
		restrictinfo->left_em = em1;
		restrictinfo->right_em = em2;
	}
	else
	{
		/* Case 4: make a new, two-entry EC */
		EquivalenceClass *ec = makeNode(EquivalenceClass);

		ec->ec_opfamilies = opfamilies;
		ec->ec_members = NIL;
		ec->ec_sources = list_make1(restrictinfo);
		ec->ec_derives = NIL;
		ec->ec_relids = NULL;
		ec->ec_has_const = false;
		ec->ec_has_volatile = false;
		ec->ec_below_outer_join = below_outer_join;
		ec->ec_broken = false;
		ec->ec_sortref = 0;
		ec->ec_merged = NULL;
		em1 = add_eq_member(ec, item1, item1_relids, false, item1_type);
		em2 = add_eq_member(ec, item2, item2_relids, false, item2_type);

		root->eq_classes = lappend(root->eq_classes, ec);

		/* mark the RI as usable with this pair of EMs */
		restrictinfo->left_em = em1;
		restrictinfo->right_em = em2;
	}

	return true;
}

/*
 * add_eq_member - build a new EquivalenceMember and add it to an EC
 */
static EquivalenceMember *
add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
			  bool is_child, Oid datatype)
{
	EquivalenceMember *em = makeNode(EquivalenceMember);

	em->em_expr = expr;
	em->em_relids = relids;
	em->em_is_const = false;
	em->em_is_child = is_child;
	em->em_datatype = datatype;

	if (bms_is_empty(relids))
	{
		/*
		 * No Vars, assume it's a pseudoconstant.  This is correct for entries
		 * generated from process_equivalence(), because a WHERE clause can't
		 * contain aggregates or SRFs, and non-volatility was checked before
		 * process_equivalence() ever got called.  But
		 * get_eclass_for_sort_expr() has to work harder.  We put the tests
		 * there not here to save cycles in the equivalence case.
		 */
		Assert(!is_child);
		em->em_is_const = true;
		ec->ec_has_const = true;
		/* it can't affect ec_relids */
	}
	else if (!is_child)			/* child members don't add to ec_relids */
	{
		ec->ec_relids = bms_add_members(ec->ec_relids, relids);
	}
	ec->ec_members = lappend(ec->ec_members, em);

	return em;
}


/*
 * get_eclass_for_sort_expr
 *	  Given an expression and opfamily info, find an existing equivalence
 *	  class it is a member of; if none, build a new single-member
 *	  EquivalenceClass for it.
 *
 * sortref is the SortGroupRef of the originating SortClause, if any,
 * or zero if not.
 *
 * This can be used safely both before and after EquivalenceClass merging;
 * since it never causes merging it does not invalidate any existing ECs
 * or PathKeys.
 *
 * Note: opfamilies must be chosen consistently with the way
 * process_equivalence() would do; that is, generated from a mergejoinable
 * equality operator.  Else we might fail to detect valid equivalences,
 * generating poor (but not incorrect) plans.
 */
EquivalenceClass *
get_eclass_for_sort_expr(PlannerInfo *root,
						 Expr *expr,
						 Oid expr_datatype,
						 List *opfamilies,
						 Index sortref)
{
	EquivalenceClass *newec;
	EquivalenceMember *newem;
	ListCell   *lc1;
	MemoryContext oldcontext;

	/*
	 * Scan through the existing EquivalenceClasses for a match
	 */
	foreach(lc1, root->eq_classes)
	{
		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
		ListCell   *lc2;

		/* Never match to a volatile EC */
		if (cur_ec->ec_has_volatile)
			continue;

		if (!equal(opfamilies, cur_ec->ec_opfamilies))
			continue;