prepjointree.c

/*-------------------------------------------------------------------------
 *
 * 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-2004, 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.23 2004/08/29 05:06:44 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,
					   List *rtable, 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,
						 Query *parse,
						 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(Query *parse, 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(parse, 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(parse,
													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(Query *parse, Node *jtnode, bool below_outer_join)
{
	if (jtnode == NULL)
		return NULL;
	if (IsA(jtnode, RangeTblRef))
	{
		int			varno = ((RangeTblRef *) jtnode)->rtindex;
		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)))
		{
			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);

			/*
			 * Pull up any IN clauses within the subquery's WHERE, so that
			 * we don't leave unoptimized INs behind.
			 */
			if (subquery->hasSubLinks)
				subquery->jointree->quals = pull_up_IN_clauses(subquery,
											  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(subquery, (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.
			 */
			rtoffset = list_length(parse->rtable);
			OffsetVarNodes((Node *) subquery, rtoffset, 0);

			/*
			 * Upper-level vars in subquery are now one level closer to
			 * their parent than before.
			 */
			IncrementVarSublevelsUp((Node *) subquery, -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, parse->rtable,
						   subtlist, CMD_SELECT, 0);
			resolvenew_in_jointree((Node *) parse->jointree, varno,
								   parse->rtable, subtlist);
			Assert(parse->setOperations == NULL);
			parse->havingQual =
				ResolveNew(parse->havingQual,
						   varno, 0, parse->rtable,
						   subtlist, CMD_SELECT, 0);
			parse->in_info_list = (List *)
				ResolveNew((Node *) parse->in_info_list,
						   varno, 0, parse->rtable,
						   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, parse->rtable,
								   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 markers, too.  (OffsetVarNodes
			 * already adjusted the marker values, so just list_concat the
			 * list.)
			 */
			parse->rowMarks = list_concat(parse->rowMarks, subquery->rowMarks);

			/*
			 * 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 (parse->in_info_list)
			{
				Relids		subrelids;

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

			/*
			 * And now append any subquery InClauseInfos to our list.
			 */
			parse->in_info_list = list_concat(parse->in_info_list,
											  subquery->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(parse, 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(parse, j->larg,
											 below_outer_join);
				j->rarg = pull_up_subqueries(parse, j->rarg,
											 below_outer_join);
				break;
			case JOIN_LEFT:
				j->larg = pull_up_subqueries(parse, j->larg,
											 below_outer_join);
				j->rarg = pull_up_subqueries(parse, j->rarg,
											 true);
				break;
			case JOIN_FULL:
				j->larg = pull_up_subqueries(parse, j->larg,
											 true);
				j->rarg = pull_up_subqueries(parse, j->rarg,
											 true);
				break;
			case JOIN_RIGHT:
				j->larg = pull_up_subqueries(parse, j->larg,
											 true);
				j->rarg = pull_up_subqueries(parse, 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")));
				break;
			default:
				elog(ERROR, "unrecognized join type: %d",
					 (int) j->jointype);
				break;
		}
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
	return jtnode;
}

/*
 * is_simple_subquery
 *	  Check a subquery in the range table to see if it's simple enough
 *	  to pull up into the parent query.
 */
static bool
is_simple_subquery(Query *subquery)
{
	/*
	 * Let's just make sure it's a valid subselect ...
	 */
	if (!IsA(subquery, Query) ||
		subquery->commandType != CMD_SELECT ||
		subquery->resultRelation != 0 ||
		subquery->into != NULL)
		elog(ERROR, "subquery is bogus");

	/*
	 * Can't currently pull up a query with setops. Maybe after querytree
	 * redesign...
	 */
	if (subquery->setOperations)
		return false;

	/*
	 * Can't pull up a subquery involving grouping, aggregation, sorting,
	 * or limiting.
	 */
	if (subquery->hasAggs ||
		subquery->groupClause ||
		subquery->havingQual ||
		subquery->sortClause ||
		subquery->distinctClause ||
		subquery->limitOffset ||
		subquery->limitCount)
		return false;

	/*
	 * Don't pull up a subquery that has any set-returning functions in
	 * its targetlist.	Otherwise we might well wind up inserting
	 * set-returning functions into places where they mustn't go, such as
	 * quals of higher queries.
	 */
	if (expression_returns_set((Node *) subquery->targetList))
		return false;

	/*
	 * Hack: don't try to pull up a subquery with an empty jointree.
	 * query_planner() will correctly generate a Result plan for a
	 * jointree that's totally empty, but I don't think the right things
	 * happen if an empty FromExpr appears lower down in a jointree. Not
	 * worth working hard on this, just to collapse SubqueryScan/Result
	 * into Result...
	 */
	if (subquery->jointree->fromlist == NIL)
		return false;

	return true;
}

/*
 * has_nullable_targetlist
 *	  Check a subquery in the range table to see if all the non-junk
 *	  targetlist items are simple variables or strict functions of simple
 *	  variables (and, hence, will correctly go to NULL when examined above
 *	  the point of an outer join).
 *
 * NOTE: it would be correct (and useful) to ignore output columns that aren't
 * actually referenced by the enclosing query ... but we do not have that
 * information available at this point.
 */
static bool
has_nullable_targetlist(Query *subquery)
{
	ListCell   *l;

	foreach(l, subquery->targetList)
	{
		TargetEntry *tle = (TargetEntry *) lfirst(l);

		/* ignore resjunk columns */
		if (tle->resdom->resjunk)
			continue;

		/* Must contain a Var of current level */
		if (!contain_vars_of_level((Node *) tle->expr, 0))
			return false;

		/* Must not contain any non-strict constructs */
		if (contain_nonstrict_functions((Node *) tle->expr))
			return false;

		/* This one's OK, keep scanning */
	}
	return true;
}

/*
 * Helper routine for pull_up_subqueries: do ResolveNew on every expression
 * in the jointree, without changing the jointree structure itself.  Ugly,
 * but there's no other way...
 */
static void
resolvenew_in_jointree(Node *jtnode, int varno,
					   List *rtable, List *subtlist)
{
	if (jtnode == NULL)
		return;
	if (IsA(jtnode, RangeTblRef))
	{
		/* nothing to do here */
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;

		foreach(l, f->fromlist)
			resolvenew_in_jointree(lfirst(l), varno, rtable, subtlist);
		f->quals = ResolveNew(f->quals,
							  varno, 0, rtable,
							  subtlist, CMD_SELECT, 0);
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;

		resolvenew_in_jointree(j->larg, varno, rtable, subtlist);
		resolvenew_in_jointree(j->rarg, varno, rtable, subtlist);
		j->quals = ResolveNew(j->quals,
							  varno, 0, rtable,
							  subtlist, CMD_SELECT, 0);

		/*
		 * We don't bother to update the colvars list, since it won't be
		 * used again ...
		 */
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
}

/*
 * reduce_outer_joins
 *		Attempt to reduce outer joins to plain inner joins.
 *
 * The idea here is that given a query like
 *		SELECT ... FROM a LEFT JOIN b ON (...) WHERE b.y = 42;
 * we can reduce the LEFT JOIN to a plain JOIN if the "=" operator in WHERE
 * is strict.  The strict operator will always return NULL, causing the outer
 * WHERE to fail, on any row where the LEFT JOIN filled in NULLs for b's
 * columns.  Therefore, there's no need for the join to produce null-extended
 * rows in the first place --- which makes it a plain join not an outer join.
 * (This scenario may not be very likely in a query written out by hand, but
 * it's reasonably likely when pushing quals down into complex views.)
 *
 * More generally, an outer join can be reduced in strength if there is a
 * strict qual above it in the qual tree that constrains a Var from the
 * nullable side of the join to be non-null.  (For FULL joins this applies
 * to each side separately.)
 *
 * To ease recognition of strict qual clauses, we require this routine to be
 * run after expression preprocessing (i.e., qual canonicalization and JOIN
 * alias-var expansion).
 */
void
reduce_outer_joins(Query *parse)
{
	reduce_outer_joins_state *state;

	/*
	 * To avoid doing strictness checks on more quals than necessary, we
	 * want to stop descending the jointree as soon as there are no outer
	 * joins below our current point.  This consideration forces a
	 * two-pass process.  The first pass gathers information about which
	 * base rels appear below each side of each join clause, and about
	 * whether there are outer join(s) below each side of each join
	 * clause. The second pass examines qual clauses and changes join
	 * types as it descends the tree.
	 */
	state = reduce_outer_joins_pass1((Node *) parse->jointree);

	/* planner.c shouldn't have called me if no outer joins */
	if (state == NULL || !state->contains_outer)
		elog(ERROR, "so where are the outer joins?");

	reduce_outer_joins_pass2((Node *) parse->jointree, state, parse, NULL);
}

/*
 * reduce_outer_joins_pass1 - phase 1 data collection
 *
 * Returns a state node describing the given jointree node.
 */
static reduce_outer_joins_state *
reduce_outer_joins_pass1(Node *jtnode)
{
	reduce_outer_joins_state *result;

	result = (reduce_outer_joins_state *)
		palloc(sizeof(reduce_outer_joins_state));
	result->relids = NULL;
	result->contains_outer = false;
	result->sub_states = NIL;

	if (jtnode == NULL)
		return result;
	if (IsA(jtnode, RangeTblRef))
	{
		int			varno = ((RangeTblRef *) jtnode)->rtindex;

		result->relids = bms_make_singleton(varno);
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;

		foreach(l, f->fromlist)
		{
			reduce_outer_joins_state *sub_state;

			sub_state = reduce_outer_joins_pass1(lfirst(l));
			result->relids = bms_add_members(result->relids,
											 sub_state->relids);
			result->contains_outer |= sub_state->contains_outer;
			result->sub_states = lappend(result->sub_states, sub_state);
		}
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;
		reduce_outer_joins_state *sub_state;

		/* join's own RT index is not wanted in result->relids */
		if (IS_OUTER_JOIN(j->jointype))
			result->contains_outer = true;

		sub_state = reduce_outer_joins_pass1(j->larg);
		result->relids = bms_add_members(result->relids,
										 sub_state->relids);
		result->contains_outer |= sub_state->contains_outer;
		result->sub_states = lappend(result->sub_states, sub_state);

		sub_state = reduce_outer_joins_pass1(j->rarg);
		result->relids = bms_add_members(result->relids,
										 sub_state->relids);
		result->contains_outer |= sub_state->contains_outer;
		result->sub_states = lappend(result->sub_states, sub_state);
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
	return result;
}

/*
 * reduce_outer_joins_pass2 - phase 2 processing
 *
 *	jtnode: current jointree node
 *	state: state data collected by phase 1 for this node
 *	parse: toplevel Query
 *	nonnullable_rels: set of base relids forced non-null by upper quals
 */
static void
reduce_outer_joins_pass2(Node *jtnode,
						 reduce_outer_joins_state *state,
						 Query *parse,
						 Relids nonnullable_rels)
{
	/*
	 * pass 2 should never descend as far as an empty subnode or base rel,
	 * because it's only called on subtrees marked as contains_outer.
	 */
	if (jtnode == NULL)
		elog(ERROR, "reached empty jointree");
	if (IsA(jtnode, RangeTblRef))
		elog(ERROR, "reached base rel");
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;
		ListCell   *s;
		Relids		pass_nonnullable;

		/* Scan quals to see if we can add any nonnullability constraints */
		pass_nonnullable = find_nonnullable_rels(f->quals, true);
		pass_nonnullable = bms_add_members(pass_nonnullable,
										   nonnullable_rels);
		/* And recurse --- but only into interesting subtrees */
		Assert(list_length(f->fromlist) == list_length(state->sub_states));
		forboth(l, f->fromlist, s, state->sub_states)
		{
			reduce_outer_joins_state *sub_state = lfirst(s);

			if (sub_state->contains_outer)
				reduce_outer_joins_pass2(lfirst(l), sub_state, parse,
										 pass_nonnullable);
		}
		bms_free(pass_nonnullable);
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;
		int			rtindex = j->rtindex;
		JoinType	jointype = j->jointype;
		reduce_outer_joins_state *left_state = linitial(state->sub_states);
		reduce_outer_joins_state *right_state = lsecond(state->sub_states);

		/* Can we simplify this join? */
		switch (jointype)
		{
			case JOIN_LEFT:
				if (bms_overlap(nonnullable_rels, right_state->relids))
					jointype = JOIN_INNER;
				break;
			case JOIN_RIGHT:
				if (bms_overlap(nonnullable_rels, left_state->relids))
					jointype = JOIN_INNER;
				break;
			case JOIN_FULL:
				if (bms_overlap(nonnullable_rels, left_state->relids))
				{
					if (bms_overlap(nonnullable_rels, right_state->relids))
						jointype = JOIN_INNER;
					else
						jointype = JOIN_LEFT;
				}
				else
				{
					if (bms_overlap(nonnullable_rels, right_state->relids))
						jointype = JOIN_RIGHT;
				}
				break;
			default:
				break;
		}
		if (jointype != j->jointype)
		{
			/* apply the change to both jointree node and RTE */
			RangeTblEntry *rte = rt_fetch(rtindex, parse->rtable);

			Assert(rte->rtekind == RTE_JOIN);
			Assert(rte->jointype == j->jointype);
			rte->jointype = j->jointype = jointype;
		}

		/* Only recurse if there's more to do below here */
		if (left_state->contains_outer || right_state->contains_outer)
		{
			Relids		local_nonnullable;
			Relids		pass_nonnullable;

			/*
			 * If this join is (now) inner, we can add any nonnullability
			 * constraints its quals provide to those we got from above.
			 * But if it is outer, we can only pass down the local
			 * constraints into the nullable side, because an outer join
			 * never eliminates any rows from its non-nullable side.  If
			 * it's a FULL join then it doesn't eliminate anything from
			 * either side.
			 */
			if (jointype != JOIN_FULL)
			{
				local_nonnullable = find_nonnullable_rels(j->quals, true);
				local_nonnullable = bms_add_members(local_nonnullable,
													nonnullable_rels);
			}
			else
				local_nonnullable = NULL;		/* no use in calculating
												 * it */

			if (left_state->contains_outer)
			{
				if (jointype == JOIN_INNER || jointype == JOIN_RIGHT)
					pass_nonnullable = local_nonnullable;
				else
					pass_nonnullable = nonnullable_rels;
				reduce_outer_joins_pass2(j->larg, left_state, parse,
										 pass_nonnullable);
			}
			if (right_state->contains_outer)
			{
				if (jointype == JOIN_INNER || jointype == JOIN_LEFT)
					pass_nonnullable = local_nonnullable;
				else
					pass_nonnullable = nonnullable_rels;
				reduce_outer_joins_pass2(j->rarg, right_state, parse,
										 pass_nonnullable);
			}
			bms_free(local_nonnullable);
		}
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
}

/*
 * find_nonnullable_rels
 *		Determine which base rels are forced nonnullable by given quals
 *
 * We don't use expression_tree_walker here because we don't want to
 * descend through very many kinds of nodes; only the ones we can be sure
 * are strict.	We can descend through the top level of implicit AND'ing,
 * but not through any explicit ANDs (or ORs) below that, since those are not
 * strict constructs.  The List case handles the top-level implicit AND list
 * as well as lists of arguments to strict operators/functions.
 */
static Relids
find_nonnullable_rels(Node *node, bool top_level)
{
	Relids		result = NULL;

	if (node == NULL)
		return NULL;
	if (IsA(node, Var))
	{
		Var		   *var = (Var *) node;

		if (var->varlevelsup == 0)
			result = bms_make_singleton(var->varno);
	}
	else if (IsA(node, List))
	{
		ListCell   *l;

		foreach(l, (List *) node)
		{
			result = bms_join(result, find_nonnullable_rels(lfirst(l),
															top_level));
		}
	}
	else if (IsA(node, FuncExpr))
	{
		FuncExpr   *expr = (FuncExpr *) node;

		if (func_strict(expr->funcid))
			result = find_nonnullable_rels((Node *) expr->args, false);
	}
	else if (IsA(node, OpExpr))
	{
		OpExpr	   *expr = (OpExpr *) node;

		if (op_strict(expr->opno))
			result = find_nonnullable_rels((Node *) expr->args, false);
	}
	else if (IsA(node, BoolExpr))
	{
		BoolExpr   *expr = (BoolExpr *) node;

		/* NOT is strict, others are not */
		if (expr->boolop == NOT_EXPR)
			result = find_nonnullable_rels((Node *) expr->args, false);
	}
	else if (IsA(node, RelabelType))
	{
		RelabelType *expr = (RelabelType *) node;

		result = find_nonnullable_rels((Node *) expr->arg, top_level);
	}
	else if (IsA(node, NullTest))
	{
		NullTest   *expr = (NullTest *) node;

		/*
		 * IS NOT NULL can be considered strict, but only at top level;
		 * else we might have something like NOT (x IS NOT NULL).
		 */
		if (top_level && expr->nulltesttype == IS_NOT_NULL)
			result = find_nonnullable_rels((Node *) expr->arg, false);
	}
	else if (IsA(node, BooleanTest))
	{
		BooleanTest *expr = (BooleanTest *) node;

		/*
		 * Appropriate boolean tests are strict at top level.
		 */
		if (top_level &&
			(expr->booltesttype == IS_TRUE ||
			 expr->booltesttype == IS_FALSE ||
			 expr->booltesttype == IS_NOT_UNKNOWN))
			result = find_nonnullable_rels((Node *) expr->arg, false);
	}
	return result;
}

/*
 * simplify_jointree
 *		Attempt to simplify a query's jointree.
 *
 * If we succeed in pulling up a subquery then we might form a jointree
 * in which a FromExpr is a direct child of another FromExpr.  In that
 * case we can consider collapsing the two FromExprs into one.	This is
 * an optional conversion, since the planner will work correctly either
 * way.  But we may find a better plan (at the cost of more planning time)
 * if we merge the two nodes, creating a single join search space out of
 * two.  To allow the user to trade off planning time against plan quality,
 * we provide a control parameter from_collapse_limit that limits the size
 * of the join search space that can be created this way.
 *
 * We also consider flattening explicit inner JOINs into FromExprs (which
 * will in turn allow them to be merged into parent FromExprs).  The tradeoffs
 * here are the same as for flattening FromExprs, but we use a different
 * control parameter so that the user can use explicit JOINs to control the
 * join order even when they are inner JOINs.
 *
 * NOTE: don't try to do this in the same jointree scan that does subquery
 * pullup!	Since we're changing the jointree structure here, that wouldn't
 * work reliably --- see comments for pull_up_subqueries().
 */
Node *
simplify_jointree(Query *parse, Node *jtnode)
{
	if (jtnode == NULL)
		return NULL;
	if (IsA(jtnode, RangeTblRef))
	{
		/* nothing to do here... */
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		List	   *newlist = NIL;
		int			children_remaining;
		ListCell   *l;

		children_remaining = list_length(f->fromlist);
		foreach(l, f->fromlist)
		{
			Node	   *child = (Node *) lfirst(l);

			children_remaining--;
			/* Recursively simplify this child... */
			child = simplify_jointree(parse, child);
			/* Now, is it a FromExpr? */
			if (child && IsA(child, FromExpr))
			{
				/*
				 * Yes, so do we want to merge it into parent?	Always do
				 * so if child has just one element (since that doesn't
				 * make the parent's list any longer).  Otherwise merge if
				 * the resulting join list would be no longer than
				 * from_collapse_limit.
				 */
				FromExpr   *subf = (FromExpr *) child;
				int			childlen = list_length(subf->fromlist);
				int			myothers = list_length(newlist) + children_remaining;

				if (childlen <= 1 ||
					(childlen + myothers) <= from_collapse_limit)
				{
					newlist = list_concat(newlist, subf->fromlist);

					/*
					 * By now, the quals have been converted to
					 * implicit-AND lists, so we just need to join the
					 * lists.  NOTE: we put the pulled-up quals first.
					 */
					f->quals = (Node *) list_concat((List *) subf->quals,
													(List *) f->quals);
				}
				else
					newlist = lappend(newlist, child);
			}
			else
				newlist = lappend(newlist, child);
		}
		f->fromlist = newlist;
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;

		/* Recursively simplify the children... */
		j->larg = simplify_jointree(parse, j->larg);
		j->rarg = simplify_jointree(parse, j->rarg);

		/*
		 * If it is an outer join, we must not flatten it.	An inner join
		 * is semantically equivalent to a FromExpr; we convert it to one,
		 * allowing it to be flattened into its parent, if the resulting
		 * FromExpr would have no more than join_collapse_limit members.
		 */
		if (j->jointype == JOIN_INNER && join_collapse_limit > 1)
		{
			int			leftlen,
						rightlen;

			if (j->larg && IsA(j->larg, FromExpr))
				leftlen = list_length(((FromExpr *) j->larg)->fromlist);
			else
				leftlen = 1;
			if (j->rarg && IsA(j->rarg, FromExpr))
				rightlen = list_length(((FromExpr *) j->rarg)->fromlist);
			else
				rightlen = 1;
			if ((leftlen + rightlen) <= join_collapse_limit)
			{
				FromExpr   *f = makeNode(FromExpr);

				f->fromlist = NIL;
				f->quals = NULL;

				if (j->larg && IsA(j->larg, FromExpr))
				{
					FromExpr   *subf = (FromExpr *) j->larg;

					f->fromlist = subf->fromlist;
					f->quals = subf->quals;
				}
				else
					f->fromlist = list_make1(j->larg);

				if (j->rarg && IsA(j->rarg, FromExpr))
				{
					FromExpr   *subf = (FromExpr *) j->rarg;

					f->fromlist = list_concat(f->fromlist,
											  subf->fromlist);
					f->quals = (Node *) list_concat((List *) f->quals,
													(List *) subf->quals);
				}
				else
					f->fromlist = lappend(f->fromlist, j->rarg);

				/* pulled-up quals first */
				f->quals = (Node *) list_concat((List *) f->quals,
												(List *) j->quals);

				return (Node *) f;
			}
		}
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
	return jtnode;
}

/*
 * fix_in_clause_relids: update RT-index sets of InClauseInfo nodes
 *
 * When we pull up a subquery, any InClauseInfo references to the subquery's
 * RT index have to be replaced by the set of substituted relids.
 *
 * We assume we may modify the InClauseInfo nodes in-place.
 */
static void
fix_in_clause_relids(List *in_info_list, int varno, Relids subrelids)
{
	ListCell   *l;

	foreach(l, in_info_list)
	{
		InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);

		if (bms_is_member(varno, ininfo->lefthand))
		{
			ininfo->lefthand = bms_del_member(ininfo->lefthand, varno);
			ininfo->lefthand = bms_add_members(ininfo->lefthand, subrelids);
		}
		if (bms_is_member(varno, ininfo->righthand))
		{
			ininfo->righthand = bms_del_member(ininfo->righthand, varno);
			ininfo->righthand = bms_add_members(ininfo->righthand, subrelids);
		}
	}
}

/*
 * get_relids_in_jointree: get set of base RT indexes present in a jointree
 */
Relids
get_relids_in_jointree(Node *jtnode)
{
	Relids		result = NULL;

	if (jtnode == NULL)
		return result;
	if (IsA(jtnode, RangeTblRef))
	{
		int			varno = ((RangeTblRef *) jtnode)->rtindex;

		result = bms_make_singleton(varno);
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;

		foreach(l, f->fromlist)
		{
			result = bms_join(result,
							  get_relids_in_jointree(lfirst(l)));
		}
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;

		/* join's own RT index is not wanted in result */
		result = get_relids_in_jointree(j->larg);
		result = bms_join(result, get_relids_in_jointree(j->rarg));
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
	return result;
}

/*
 * get_relids_for_join: get set of base RT indexes making up a join
 *
 * NB: this will not work reliably after simplify_jointree() is run,
 * since that may eliminate join nodes from the jointree.
 */
Relids
get_relids_for_join(Query *parse, int joinrelid)
{
	Node	   *jtnode;

	jtnode = find_jointree_node_for_rel((Node *) parse->jointree, joinrelid);
	if (!jtnode)
		elog(ERROR, "could not find join node %d", joinrelid);
	return get_relids_in_jointree(jtnode);
}

/*
 * find_jointree_node_for_rel: locate jointree node for a base or join RT index
 *
 * Returns NULL if not found
 */
static Node *
find_jointree_node_for_rel(Node *jtnode, int relid)
{
	if (jtnode == NULL)
		return NULL;
	if (IsA(jtnode, RangeTblRef))
	{
		int			varno = ((RangeTblRef *) jtnode)->rtindex;

		if (relid == varno)
			return jtnode;
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;

		foreach(l, f->fromlist)
		{
			jtnode = find_jointree_node_for_rel(lfirst(l), relid);
			if (jtnode)
				return jtnode;
		}
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;

		if (relid == j->rtindex)
			return jtnode;
		jtnode = find_jointree_node_for_rel(j->larg, relid);
		if (jtnode)
			return jtnode;
		jtnode = find_jointree_node_for_rel(j->rarg, relid);
		if (jtnode)
			return jtnode;
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
	return NULL;
}