prepjointree.c

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

/*-------------------------------------------------------------------------
 *
 * prepjointree.c
 *	  Planner preprocessing for subqueries and join tree manipulation.
 *
 * NOTE: the intended sequence for invoking these operations is
 *		pull_up_IN_clauses
 *		pull_up_subqueries
 *		do expression preprocessing (including flattening JOIN alias vars)
 *		reduce_outer_joins
 *		simplify_jointree
 *
 *
 * 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/prep/prepjointree.c,v 1.31.2.1 2005/11/22 18:23:11 momjian Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "optimizer/clauses.h"
#include "optimizer/prep.h"
#include "optimizer/subselect.h"
#include "optimizer/var.h"
#include "parser/parsetree.h"
#include "rewrite/rewriteManip.h"
#include "utils/lsyscache.h"


/* These parameters are set by GUC */
int			from_collapse_limit;
int			join_collapse_limit;


typedef struct reduce_outer_joins_state
{
	Relids		relids;			/* base relids within this subtree */
	bool		contains_outer; /* does subtree contain outer join(s)? */
	List	   *sub_states;		/* List of states for subtree components */
} reduce_outer_joins_state;

static bool is_simple_subquery(Query *subquery);
static bool has_nullable_targetlist(Query *subquery);
static void resolvenew_in_jointree(Node *jtnode, int varno,
					   RangeTblEntry *rte, List *subtlist);
static reduce_outer_joins_state *reduce_outer_joins_pass1(Node *jtnode);
static void reduce_outer_joins_pass2(Node *jtnode,
						 reduce_outer_joins_state *state,
						 PlannerInfo *root,
						 Relids nonnullable_rels);
static Relids find_nonnullable_rels(Node *node, bool top_level);
static void fix_in_clause_relids(List *in_info_list, int varno,
					 Relids subrelids);
static Node *find_jointree_node_for_rel(Node *jtnode, int relid);


/*
 * pull_up_IN_clauses
 *		Attempt to pull up top-level IN clauses to be treated like joins.
 *
 * A clause "foo IN (sub-SELECT)" appearing at the top level of WHERE can
 * be processed by pulling the sub-SELECT up to become a rangetable entry
 * and handling the implied equality comparisons as join operators (with
 * special join rules).
 * This optimization *only* works at the top level of WHERE, because
 * it cannot distinguish whether the IN ought to return FALSE or NULL in
 * cases involving NULL inputs.  This routine searches for such clauses
 * and does the necessary parsetree transformations if any are found.
 *
 * This routine has to run before preprocess_expression(), so the WHERE
 * clause is not yet reduced to implicit-AND format.  That means we need
 * to recursively search through explicit AND clauses, which are
 * probably only binary ANDs.  We stop as soon as we hit a non-AND item.
 *
 * Returns the possibly-modified version of the given qual-tree node.
 */
Node *
pull_up_IN_clauses(PlannerInfo *root, Node *node)
{
	if (node == NULL)
		return NULL;
	if (IsA(node, SubLink))
	{
		SubLink    *sublink = (SubLink *) node;
		Node	   *subst;

		/* Is it a convertible IN clause?  If not, return it as-is */
		subst = convert_IN_to_join(root, sublink);
		if (subst == NULL)
			return node;
		return subst;
	}
	if (and_clause(node))
	{
		List	   *newclauses = NIL;
		ListCell   *l;

		foreach(l, ((BoolExpr *) node)->args)
		{
			Node	   *oldclause = (Node *) lfirst(l);

			newclauses = lappend(newclauses,
								 pull_up_IN_clauses(root, oldclause));
		}
		return (Node *) make_andclause(newclauses);
	}
	/* Stop if not an AND */
	return node;
}

/*
 * pull_up_subqueries
 *		Look for subqueries in the rangetable that can be pulled up into
 *		the parent query.  If the subquery has no special features like
 *		grouping/aggregation then we can merge it into the parent's jointree.
 *
 * below_outer_join is true if this jointree node is within the nullable
 * side of an outer join.  This restricts what we can do.
 *
 * A tricky aspect of this code is that if we pull up a subquery we have
 * to replace Vars that reference the subquery's outputs throughout the
 * parent query, including quals attached to jointree nodes above the one
 * we are currently processing!  We handle this by being careful not to
 * change the jointree structure while recursing: no nodes other than
 * subquery RangeTblRef entries will be replaced.  Also, we can't turn
 * ResolveNew loose on the whole jointree, because it'll return a mutated
 * copy of the tree; we have to invoke it just on the quals, instead.
 */
Node *
pull_up_subqueries(PlannerInfo *root, Node *jtnode, bool below_outer_join)
{
	if (jtnode == NULL)
		return NULL;
	if (IsA(jtnode, RangeTblRef))
	{
		int			varno = ((RangeTblRef *) jtnode)->rtindex;
		Query	   *parse = root->parse;
		RangeTblEntry *rte = rt_fetch(varno, parse->rtable);
		Query	   *subquery = rte->subquery;

		/*
		 * Is this a subquery RTE, and if so, is the subquery simple enough to
		 * pull up?  (If not, do nothing at this node.)
		 *
		 * If we are inside an outer join, only pull up subqueries whose
		 * targetlists are nullable --- otherwise substituting their tlist
		 * entries for upper Var references would do the wrong thing (the
		 * results wouldn't become NULL when they're supposed to).
		 *
		 * XXX This could be improved by generating pseudo-variables for such
		 * expressions; we'd have to figure out how to get the pseudo-
		 * variables evaluated at the right place in the modified plan tree.
		 * Fix it someday.
		 */
		if (rte->rtekind == RTE_SUBQUERY &&
			is_simple_subquery(subquery) &&
			(!below_outer_join || has_nullable_targetlist(subquery)))
		{
			PlannerInfo *subroot;
			int			rtoffset;
			List	   *subtlist;
			ListCell   *rt;

			/*
			 * Need a modifiable copy of the subquery to hack on.  Even if we
			 * didn't sometimes choose not to pull up below, we must do this
			 * to avoid problems if the same subquery is referenced from
			 * multiple jointree items (which can't happen normally, but might
			 * after rule rewriting).
			 */
			subquery = copyObject(subquery);

			/*
			 * Create a PlannerInfo data structure for this subquery.
			 *
			 * NOTE: the next few steps should match the first processing in
			 * subquery_planner().	Can we refactor to avoid code duplication,
			 * or would that just make things uglier?
			 */
			subroot = makeNode(PlannerInfo);
			subroot->parse = subquery;

			/*
			 * Pull up any IN clauses within the subquery's WHERE, so that we
			 * don't leave unoptimized INs behind.
			 */
			subroot->in_info_list = NIL;
			if (subquery->hasSubLinks)
				subquery->jointree->quals = pull_up_IN_clauses(subroot,
												  subquery->jointree->quals);

			/*
			 * Recursively pull up the subquery's subqueries, so that this
			 * routine's processing is complete for its jointree and
			 * rangetable.
			 *
			 * Note: 'false' is correct here even if we are within an outer
			 * join in the upper query; the lower query starts with a clean
			 * slate for outer-join semantics.
			 */
			subquery->jointree = (FromExpr *)
				pull_up_subqueries(subroot, (Node *) subquery->jointree,
								   false);

			/*
			 * Now we must recheck whether the subquery is still simple enough
			 * to pull up.	If not, abandon processing it.
			 *
			 * We don't really need to recheck all the conditions involved,
			 * but it's easier just to keep this "if" looking the same as the
			 * one above.
			 */
			if (is_simple_subquery(subquery) &&
				(!below_outer_join || has_nullable_targetlist(subquery)))
			{
				/* good to go */
			}
			else
			{
				/*
				 * Give up, return unmodified RangeTblRef.
				 *
				 * Note: The work we just did will be redone when the subquery
				 * gets planned on its own.  Perhaps we could avoid that by
				 * storing the modified subquery back into the rangetable, but
				 * I'm not gonna risk it now.
				 */
				return jtnode;
			}

			/*
			 * Adjust level-0 varnos in subquery so that we can append its
			 * rangetable to upper query's.  We have to fix the subquery's
			 * in_info_list, as well.
			 */
			rtoffset = list_length(parse->rtable);
			OffsetVarNodes((Node *) subquery, rtoffset, 0);
			OffsetVarNodes((Node *) subroot->in_info_list, rtoffset, 0);

			/*
			 * Upper-level vars in subquery are now one level closer to their
			 * parent than before.
			 */
			IncrementVarSublevelsUp((Node *) subquery, -1, 1);
			IncrementVarSublevelsUp((Node *) subroot->in_info_list, -1, 1);

			/*
			 * Replace all of the top query's references to the subquery's
			 * outputs with copies of the adjusted subtlist items, being
			 * careful not to replace any of the jointree structure. (This'd
			 * be a lot cleaner if we could use query_tree_mutator.)
			 */
			subtlist = subquery->targetList;
			parse->targetList = (List *)
				ResolveNew((Node *) parse->targetList,
						   varno, 0, rte,
						   subtlist, CMD_SELECT, 0);
			resolvenew_in_jointree((Node *) parse->jointree, varno,
								   rte, subtlist);
			Assert(parse->setOperations == NULL);
			parse->havingQual =
				ResolveNew(parse->havingQual,
						   varno, 0, rte,
						   subtlist, CMD_SELECT, 0);
			root->in_info_list = (List *)
				ResolveNew((Node *) root->in_info_list,
						   varno, 0, rte,
						   subtlist, CMD_SELECT, 0);

			foreach(rt, parse->rtable)
			{
				RangeTblEntry *otherrte = (RangeTblEntry *) lfirst(rt);

				if (otherrte->rtekind == RTE_JOIN)
					otherrte->joinaliasvars = (List *)
						ResolveNew((Node *) otherrte->joinaliasvars,
								   varno, 0, rte,
								   subtlist, CMD_SELECT, 0);
			}

			/*
			 * Now append the adjusted rtable entries to upper query. (We hold
			 * off until after fixing the upper rtable entries; no point in
			 * running that code on the subquery ones too.)
			 */
			parse->rtable = list_concat(parse->rtable, subquery->rtable);

			/*
			 * Pull up any FOR UPDATE/SHARE markers, too.  (OffsetVarNodes
			 * already adjusted the marker values, so just list_concat the
			 * list.)
			 *
			 * Executor can't handle multiple FOR UPDATE/SHARE/NOWAIT flags,
			 * so complain if they are valid but different
			 */
			if (parse->rowMarks && subquery->rowMarks)
			{
				if (parse->forUpdate != subquery->forUpdate)
					ereport(ERROR,
							(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
							 errmsg("cannot use both FOR UPDATE and FOR SHARE in one query")));
				if (parse->rowNoWait != subquery->rowNoWait)
					ereport(ERROR,
							(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					errmsg("cannot use both wait and NOWAIT in one query")));
			}
			parse->rowMarks = list_concat(parse->rowMarks, subquery->rowMarks);
			if (subquery->rowMarks)
			{
				parse->forUpdate = subquery->forUpdate;
				parse->rowNoWait = subquery->rowNoWait;
			}

			/*
			 * We also have to fix the relid sets of any parent InClauseInfo
			 * nodes.  (This could perhaps be done by ResolveNew, but it would
			 * clutter that routine's API unreasonably.)
			 */
			if (root->in_info_list)
			{
				Relids		subrelids;

				subrelids = get_relids_in_jointree((Node *) subquery->jointree);
				fix_in_clause_relids(root->in_info_list, varno, subrelids);
			}

			/*
			 * And now append any subquery InClauseInfos to our list.
			 */
			root->in_info_list = list_concat(root->in_info_list,
											 subroot->in_info_list);

			/*
			 * Miscellaneous housekeeping.
			 */
			parse->hasSubLinks |= subquery->hasSubLinks;
			/* subquery won't be pulled up if it hasAggs, so no work there */

			/*
			 * Return the adjusted subquery jointree to replace the
			 * RangeTblRef entry in my jointree.
			 */
			return (Node *) subquery->jointree;
		}
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;

		foreach(l, f->fromlist)
			lfirst(l) = pull_up_subqueries(root, lfirst(l),
										   below_outer_join);
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;

		/* Recurse, being careful to tell myself when inside outer join */
		switch (j->jointype)
		{
			case JOIN_INNER:
				j->larg = pull_up_subqueries(root, j->larg,
											 below_outer_join);
				j->rarg = pull_up_subqueries(root, j->rarg,
											 below_outer_join);
				break;
			case JOIN_LEFT:
				j->larg = pull_up_subqueries(root, j->larg,
											 below_outer_join);
				j->rarg = pull_up_subqueries(root, j->rarg,
											 true);
				break;
			case JOIN_FULL:
				j->larg = pull_up_subqueries(root, j->larg,
											 true);
				j->rarg = pull_up_subqueries(root, j->rarg,
											 true);
				break;
			case JOIN_RIGHT:
				j->larg = pull_up_subqueries(root, j->larg,
											 true);
				j->rarg = pull_up_subqueries(root, j->rarg,
											 below_outer_join);
				break;
			case JOIN_UNION:

				/*
				 * This is where we fail if upper levels of planner haven't
				 * rewritten UNION JOIN as an Append ...
				 */
				ereport(ERROR,
						(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
						 errmsg("UNION JOIN is not implemented")));