pathkeys.c

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

/*
 * sub_generate_join_implications
 *	  Propagate a constant equality through outer join clauses.
 *
 * The item described by item1/sortop1/item1_relids has been determined
 * to be equal to the constant(s) listed in equi_key_set.  Recursively
 * trace out the implications of this.
 *
 * equi_key_set and relids are as for generate_outer_join_implications.
 */
static void
sub_generate_join_implications(PlannerInfo *root,
							   List *equi_key_set, Relids *relids,
							   Node *item1, Oid sortop1, Relids item1_relids)

{
	ListCell   *l;

	/*
	 * Examine each mergejoinable outer-join clause with OUTERVAR on left,
	 * looking for an OUTERVAR identical to item1
	 */
	foreach(l, root->left_join_clauses)
	{
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
		Node	   *leftop = get_leftop(rinfo->clause);

		if (equal(leftop, item1) && rinfo->left_sortop == sortop1)
		{
			/*
			 * Match, so find constant member(s) of set and generate implied
			 * INNERVAR = CONSTANT
			 */
			Node	   *rightop = get_rightop(rinfo->clause);

			process_implied_const_eq(root, equi_key_set, relids,
									 rightop,
									 rinfo->right_sortop,
									 rinfo->right_relids,
									 false);

			/*
			 * We can remove explicit tests of this outer-join qual, too,
			 * since we now have tests forcing each of its sides to the same
			 * value.
			 */
			process_implied_equality(root,
									 leftop, rightop,
									 rinfo->left_sortop, rinfo->right_sortop,
									 rinfo->left_relids, rinfo->right_relids,
									 true);

			/*
			 * And recurse to see if we can deduce anything from INNERVAR =
			 * CONSTANT
			 */
			sub_generate_join_implications(root, equi_key_set, relids,
										   rightop,
										   rinfo->right_sortop,
										   rinfo->right_relids);
		}
	}

	/* The same, looking at clauses with OUTERVAR on right */
	foreach(l, root->right_join_clauses)
	{
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
		Node	   *rightop = get_rightop(rinfo->clause);

		if (equal(rightop, item1) && rinfo->right_sortop == sortop1)
		{
			/*
			 * Match, so find constant member(s) of set and generate implied
			 * INNERVAR = CONSTANT
			 */
			Node	   *leftop = get_leftop(rinfo->clause);

			process_implied_const_eq(root, equi_key_set, relids,
									 leftop,
									 rinfo->left_sortop,
									 rinfo->left_relids,
									 false);

			/*
			 * We can remove explicit tests of this outer-join qual, too,
			 * since we now have tests forcing each of its sides to the same
			 * value.
			 */
			process_implied_equality(root,
									 leftop, rightop,
									 rinfo->left_sortop, rinfo->right_sortop,
									 rinfo->left_relids, rinfo->right_relids,
									 true);

			/*
			 * And recurse to see if we can deduce anything from INNERVAR =
			 * CONSTANT
			 */
			sub_generate_join_implications(root, equi_key_set, relids,
										   leftop,
										   rinfo->left_sortop,
										   rinfo->left_relids);
		}
	}

	/*
	 * Only COALESCE(x,y) items can possibly match full joins
	 */
	if (IsA(item1, CoalesceExpr))
	{
		CoalesceExpr *cexpr = (CoalesceExpr *) item1;
		Node	   *cfirst;
		Node	   *csecond;

		if (list_length(cexpr->args) != 2)
			return;
		cfirst = (Node *) linitial(cexpr->args);
		csecond = (Node *) lsecond(cexpr->args);

		/*
		 * Examine each mergejoinable full-join clause, looking for a clause
		 * of the form "x = y" matching the COALESCE(x,y) expression
		 */
		foreach(l, root->full_join_clauses)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
			Node	   *leftop = get_leftop(rinfo->clause);
			Node	   *rightop = get_rightop(rinfo->clause);

			/*
			 * We can assume the COALESCE() inputs are in the same order as
			 * the join clause, since both were automatically generated in the
			 * cases we care about.
			 *
			 * XXX currently this may fail to match in cross-type cases
			 * because the COALESCE will contain typecast operations while the
			 * join clause may not (if there is a cross-type mergejoin
			 * operator available for the two column types). Is it OK to strip
			 * implicit coercions from the COALESCE arguments?	What of the
			 * sortops in such cases?
			 */
			if (equal(leftop, cfirst) &&
				equal(rightop, csecond) &&
				rinfo->left_sortop == sortop1 &&
				rinfo->right_sortop == sortop1)
			{
				/*
				 * Match, so find constant member(s) of set and generate
				 * implied LEFTVAR = CONSTANT
				 */
				process_implied_const_eq(root, equi_key_set, relids,
										 leftop,
										 rinfo->left_sortop,
										 rinfo->left_relids,
										 false);
				/* ... and RIGHTVAR = CONSTANT */
				process_implied_const_eq(root, equi_key_set, relids,
										 rightop,
										 rinfo->right_sortop,
										 rinfo->right_relids,
										 false);
				/* ... and remove COALESCE() = CONSTANT */
				process_implied_const_eq(root, equi_key_set, relids,
										 item1,
										 sortop1,
										 item1_relids,
										 true);

				/*
				 * We can remove explicit tests of this outer-join qual, too,
				 * since we now have tests forcing each of its sides to the
				 * same value.
				 */
				process_implied_equality(root,
										 leftop, rightop,
										 rinfo->left_sortop,
										 rinfo->right_sortop,
										 rinfo->left_relids,
										 rinfo->right_relids,
										 true);

				/*
				 * And recurse to see if we can deduce anything from LEFTVAR =
				 * CONSTANT
				 */
				sub_generate_join_implications(root, equi_key_set, relids,
											   leftop,
											   rinfo->left_sortop,
											   rinfo->left_relids);
				/* ... and RIGHTVAR = CONSTANT */
				sub_generate_join_implications(root, equi_key_set, relids,
											   rightop,
											   rinfo->right_sortop,
											   rinfo->right_relids);

			}
		}
	}
}

/*
 * process_implied_const_eq
 *	  Apply process_implied_equality with the given item and each
 *	  pseudoconstant member of equi_key_set.
 *
 * equi_key_set and relids are as for generate_outer_join_implications,
 * the other parameters as for process_implied_equality.
 */
static void
process_implied_const_eq(PlannerInfo *root, List *equi_key_set, Relids *relids,
						 Node *item1, Oid sortop1, Relids item1_relids,
						 bool delete_it)
{
	ListCell   *l;
	bool		found = false;
	int			i = 0;

	foreach(l, equi_key_set)
	{
		PathKeyItem *item2 = (PathKeyItem *) lfirst(l);

		if (bms_is_empty(relids[i]))
		{
			process_implied_equality(root,
									 item1, item2->key,
									 sortop1, item2->sortop,
									 item1_relids, NULL,
									 delete_it);
			found = true;
		}
		i++;
	}
	/* Caller screwed up if no constants in list */
	Assert(found);
}

/*
 * 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(PlannerInfo *root, Node *item1, Node *item2)
{
	ListCell   *cursetlink;

	foreach(cursetlink, root->equi_key_list)
	{
		List	   *curset = (List *) lfirst(cursetlink);
		bool		item1member = false;
		bool		item2member = false;
		ListCell   *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(PlannerInfo *root, PathKeyItem *item)
{
	List	   *newset;
	ListCell   *cursetlink;

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

		if (list_member(curset, item))
			return curset;
	}
	newset = list_make1(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(PlannerInfo *root, List *pathkeys)
{
	List	   *new_pathkeys = NIL;
	ListCell   *l;

	foreach(l, pathkeys)
	{
		List	   *pathkey = (List *) lfirst(l);
		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 *) linitial(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.
		 */
		new_pathkeys = list_append_unique_ptr(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
 * convert_subquery_pathkeys.
 */
static int
count_canonical_peers(PlannerInfo *root, PathKeyItem *item)
{
	ListCell   *cursetlink;

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

		if (list_member(curset, item))
			return list_length(curset) - 1;
	}
	return 0;
}

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

/*
 * compare_pathkeys
 *	  Compare two pathkeys to see if they are equivalent, and if not whether
 *	  one is "better" than the other.
 *
 *	  This function may only be applied to canonicalized pathkey lists.
 *	  In the canonical representation, sublists can be checked for equality
 *	  by simple pointer comparison.
 */
PathKeysComparison
compare_pathkeys(List *keys1, List *keys2)
{
	ListCell   *key1,
			   *key2;