Implement SQL-standard LATERAL subqueries.

This patch implements the standard syntax of LATERAL attached to a
sub-SELECT in FROM, and also allows LATERAL attached to a function in FROM,
since set-returning function calls are expected to be one of the principal
use-cases.

The main change here is a rewrite of the mechanism for keeping track of
which relations are visible for column references while the FROM clause is
being scanned.  The parser "namespace" lists are no longer lists of bare
RTEs, but are lists of ParseNamespaceItem structs, which carry an RTE
pointer as well as some visibility-controlling flags.  Aside from
supporting LATERAL correctly, this lets us get rid of the ancient hacks
that required rechecking subqueries and JOIN/ON and function-in-FROM
expressions for invalid references after they were initially parsed.
Invalid column references are now always correctly detected on sight.

In passing, remove assorted parser error checks that are now dead code by
virtue of our having gotten rid of add_missing_from, as well as some
comments that are obsolete for the same reason.  (It was mainly
add_missing_from that caused so much fudging here in the first place.)

The planner support for this feature is very minimal, and will be improved
in future patches.  It works well enough for testing purposes, though.

catversion bump forced due to new field in RangeTblEntry.

1 files changed, 147 insertions, 137 deletions

diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index 97ab9d5581a..f9faa11b2e9 100644
--- a/src/backend/parser/parse_clause.c
+++ b/src/backend/parser/parse_clause.c
@@ -58,8 +58,7 @@ static Node *transformJoinUsingClause(ParseState *pstate,
 static Node *transformJoinOnClause(ParseState *pstate, JoinExpr *j,
 					  RangeTblEntry *l_rte,
 					  RangeTblEntry *r_rte,
-					  List *relnamespace,
-					  Relids containedRels);
+					  List *relnamespace);
 static RangeTblEntry *transformTableEntry(ParseState *pstate, RangeVar *r);
 static RangeTblEntry *transformCTEReference(ParseState *pstate, RangeVar *r,
 					  CommonTableExpr *cte, Index levelsup);
@@ -69,10 +68,13 @@ static RangeTblEntry *transformRangeFunction(ParseState *pstate,
 					   RangeFunction *r);
 static Node *transformFromClauseItem(ParseState *pstate, Node *n,
 						RangeTblEntry **top_rte, int *top_rti,
-						List **relnamespace,
-						Relids *containedRels);
+						List **relnamespace);
 static Node *buildMergedJoinVar(ParseState *pstate, JoinType jointype,
 				   Var *l_colvar, Var *r_colvar);
+static ParseNamespaceItem *makeNamespaceItem(RangeTblEntry *rte,
+				  bool lateral_only, bool lateral_ok);
+static void setNamespaceLateralState(List *namespace,
+						 bool lateral_only, bool lateral_ok);
 static void checkExprIsVarFree(ParseState *pstate, Node *n,
 				   const char *constructName);
 static TargetEntry *findTargetlistEntrySQL92(ParseState *pstate, Node *node,
@@ -101,11 +103,6 @@ static Node *transformFrameOffset(ParseState *pstate, int frameOptions,
  * p_varnamespace lists were initialized to NIL when the pstate was created.
  * We will add onto any entries already present --- this is needed for rule
  * processing, as well as for UPDATE and DELETE.
- *
- * The range table may grow still further when we transform the expressions
- * in the query's quals and target list. (This is possible because in
- * POSTQUEL, we allowed references to relations not specified in the
- * from-clause.  PostgreSQL keeps this extension to standard SQL.)
  */
 void
 transformFromClause(ParseState *pstate, List *frmList)
@@ -117,6 +114,9 @@ transformFromClause(ParseState *pstate, List *frmList)
 	 * RangeFunctions, and/or JoinExprs. Transform each one (possibly adding
 	 * entries to the rtable), check for duplicate refnames, and then add it
 	 * to the joinlist and namespaces.
+	 *
+	 * Note we must process the items left-to-right for proper handling of
+	 * LATERAL references.
 	 */
 	foreach(fl, frmList)
 	{
@@ -124,20 +124,31 @@ transformFromClause(ParseState *pstate, List *frmList)
 		RangeTblEntry *rte;
 		int			rtindex;
 		List	   *relnamespace;
-		Relids		containedRels;
 
 		n = transformFromClauseItem(pstate, n,
 									&rte,
 									&rtindex,
-									&relnamespace,
-									&containedRels);
+									&relnamespace);
+		/* Mark the new relnamespace items as visible to LATERAL */
+		setNamespaceLateralState(relnamespace, true, true);
+
 		checkNameSpaceConflicts(pstate, pstate->p_relnamespace, relnamespace);
+
 		pstate->p_joinlist = lappend(pstate->p_joinlist, n);
 		pstate->p_relnamespace = list_concat(pstate->p_relnamespace,
 											 relnamespace);
-		pstate->p_varnamespace = lappend(pstate->p_varnamespace, rte);
-		bms_free(containedRels);
+		pstate->p_varnamespace = lappend(pstate->p_varnamespace,
+										 makeNamespaceItem(rte, true, true));
 	}
+
+	/*
+	 * We're done parsing the FROM list, so make all namespace items
+	 * unconditionally visible.  Note that this will also reset lateral_only
+	 * for any namespace items that were already present when we were called;
+	 * but those should have been that way already.
+	 */
+	setNamespaceLateralState(pstate->p_relnamespace, false, true);
+	setNamespaceLateralState(pstate->p_varnamespace, false, true);
 }
 
 /*
@@ -375,55 +386,34 @@ static Node *
 transformJoinOnClause(ParseState *pstate, JoinExpr *j,
 					  RangeTblEntry *l_rte,
 					  RangeTblEntry *r_rte,
-					  List *relnamespace,
-					  Relids containedRels)
+					  List *relnamespace)
 {
 	Node	   *result;
 	List	   *save_relnamespace;
 	List	   *save_varnamespace;
-	Relids		clause_varnos;
-	int			varno;
 
 	/*
-	 * This is a tad tricky, for two reasons.  First, the namespace that the
-	 * join expression should see is just the two subtrees of the JOIN plus
-	 * any outer references from upper pstate levels.  So, temporarily set
-	 * this pstate's namespace accordingly.  (We need not check for refname
-	 * conflicts, because transformFromClauseItem() already did.) NOTE: this
-	 * code is OK only because the ON clause can't legally alter the namespace
-	 * by causing implicit relation refs to be added.
+	 * The namespace that the join expression should see is just the two
+	 * subtrees of the JOIN plus any outer references from upper pstate
+	 * levels.	Temporarily set this pstate's namespace accordingly.  (We need
+	 * not check for refname conflicts, because transformFromClauseItem()
+	 * already did.)  All namespace items are marked visible regardless of
+	 * LATERAL state.
 	 */
 	save_relnamespace = pstate->p_relnamespace;
 	save_varnamespace = pstate->p_varnamespace;
 
+	setNamespaceLateralState(relnamespace, false, true);
 	pstate->p_relnamespace = relnamespace;
-	pstate->p_varnamespace = list_make2(l_rte, r_rte);
+
+	pstate->p_varnamespace = list_make2(makeNamespaceItem(l_rte, false, true),
+									  makeNamespaceItem(r_rte, false, true));
 
 	result = transformWhereClause(pstate, j->quals, "JOIN/ON");
 
 	pstate->p_relnamespace = save_relnamespace;
 	pstate->p_varnamespace = save_varnamespace;
 
-	/*
-	 * Second, we need to check that the ON condition doesn't refer to any
-	 * rels outside the input subtrees of the JOIN.  It could do that despite
-	 * our hack on the namespace if it uses fully-qualified names. So, grovel
-	 * through the transformed clause and make sure there are no bogus
-	 * references.	(Outer references are OK, and are ignored here.)
-	 */
-	clause_varnos = pull_varnos(result);
-	clause_varnos = bms_del_members(clause_varnos, containedRels);
-	if ((varno = bms_first_member(clause_varnos)) >= 0)
-	{
-		ereport(ERROR,
-				(errcode(ERRCODE_INVALID_COLUMN_REFERENCE),
-		 errmsg("JOIN/ON clause refers to \"%s\", which is not part of JOIN",
-				rt_fetch(varno, pstate->p_rtable)->eref->aliasname),
-				 parser_errposition(pstate,
-								 locate_var_of_relation(result, varno, 0))));
-	}
-	bms_free(clause_varnos);
-
 	return result;
 }
 
@@ -435,13 +425,7 @@ transformTableEntry(ParseState *pstate, RangeVar *r)
 {
 	RangeTblEntry *rte;
 
-	/*
-	 * mark this entry to indicate it comes from the FROM clause. In SQL, the
-	 * target list can only refer to range variables specified in the from
-	 * clause but we follow the more powerful POSTQUEL semantics and
-	 * automatically generate the range variable if not specified. However
-	 * there are times we need to know whether the entries are legitimate.
-	 */
+	/* We need only build a range table entry */
 	rte = addRangeTableEntry(pstate, r, r->alias,
 							 interpretInhOption(r->inhOpt), true);
 
@@ -476,17 +460,28 @@ transformRangeSubselect(ParseState *pstate, RangeSubselect *r)
 	 * We require user to supply an alias for a subselect, per SQL92. To relax
 	 * this, we'd have to be prepared to gin up a unique alias for an
 	 * unlabeled subselect.  (This is just elog, not ereport, because the
-	 * grammar should have enforced it already.)
+	 * grammar should have enforced it already.  It'd probably be better to
+	 * report the error here, but we don't have a good error location here.)
 	 */
 	if (r->alias == NULL)
 		elog(ERROR, "subquery in FROM must have an alias");
 
 	/*
+	 * If the subselect is LATERAL, make lateral_only names of this level
+	 * visible to it.  (LATERAL can't nest within a single pstate level, so we
+	 * don't need save/restore logic here.)
+	 */
+	Assert(!pstate->p_lateral_active);
+	pstate->p_lateral_active = r->lateral;
+
+	/*
 	 * Analyze and transform the subquery.
 	 */
 	query = parse_sub_analyze(r->subquery, pstate, NULL,
 							  isLockedRefname(pstate, r->alias->aliasname));
 
+	pstate->p_lateral_active = false;
+
 	/*
 	 * Check that we got something reasonable.	Many of these conditions are
 	 * impossible given restrictions of the grammar, but check 'em anyway.
@@ -497,32 +492,13 @@ transformRangeSubselect(ParseState *pstate, RangeSubselect *r)
 		elog(ERROR, "unexpected non-SELECT command in subquery in FROM");
 
 	/*
-	 * The subquery cannot make use of any variables from FROM items created
-	 * earlier in the current query.  Per SQL92, the scope of a FROM item does
-	 * not include other FROM items.  Formerly we hacked the namespace so that
-	 * the other variables weren't even visible, but it seems more useful to
-	 * leave them visible and give a specific error message.
-	 *
-	 * XXX this will need further work to support SQL99's LATERAL() feature,
-	 * wherein such references would indeed be legal.
-	 *
-	 * We can skip groveling through the subquery if there's not anything
-	 * visible in the current query.  Also note that outer references are OK.
-	 */
-	if (pstate->p_relnamespace || pstate->p_varnamespace)
-	{
-		if (contain_vars_of_level((Node *) query, 1))
-			ereport(ERROR,
-					(errcode(ERRCODE_INVALID_COLUMN_REFERENCE),
-					 errmsg("subquery in FROM cannot refer to other relations of same query level"),
-					 parser_errposition(pstate,
-								   locate_var_of_level((Node *) query, 1))));
-	}
-
-	/*
 	 * OK, build an RTE for the subquery.
 	 */
-	rte = addRangeTableEntryForSubquery(pstate, query, r->alias, true);
+	rte = addRangeTableEntryForSubquery(pstate,
+										query,
+										r->alias,
+										r->lateral,
+										true);
 
 	return rte;
 }
@@ -547,35 +523,26 @@ transformRangeFunction(ParseState *pstate, RangeFunction *r)
 	funcname = FigureColname(r->funccallnode);
 
 	/*
+	 * If the function is LATERAL, make lateral_only names of this level
+	 * visible to it.  (LATERAL can't nest within a single pstate level, so we
+	 * don't need save/restore logic here.)
+	 */
+	Assert(!pstate->p_lateral_active);
+	pstate->p_lateral_active = r->lateral;
+
+	/*
 	 * Transform the raw expression.
 	 */
 	funcexpr = transformExpr(pstate, r->funccallnode);
 
+	pstate->p_lateral_active = false;
+
 	/*
 	 * We must assign collations now so that we can fill funccolcollations.
 	 */
 	assign_expr_collations(pstate, funcexpr);
 
 	/*
-	 * The function parameters cannot make use of any variables from other
-	 * FROM items.	(Compare to transformRangeSubselect(); the coding is
-	 * different though because we didn't parse as a sub-select with its own
-	 * level of namespace.)
-	 *
-	 * XXX this will need further work to support SQL99's LATERAL() feature,
-	 * wherein such references would indeed be legal.
-	 */
-	if (pstate->p_relnamespace || pstate->p_varnamespace)
-	{
-		if (contain_vars_of_level(funcexpr, 0))
-			ereport(ERROR,
-					(errcode(ERRCODE_INVALID_COLUMN_REFERENCE),
-					 errmsg("function expression in FROM cannot refer to other relations of same query level"),
-					 parser_errposition(pstate,
-										locate_var_of_level(funcexpr, 0))));
-	}
-
-	/*
 	 * Disallow aggregate functions in the expression.	(No reason to postpone
 	 * this check until parseCheckAggregates.)
 	 */
@@ -598,7 +565,7 @@ transformRangeFunction(ParseState *pstate, RangeFunction *r)
 	 * OK, build an RTE for the function.
 	 */
 	rte = addRangeTableEntryForFunction(pstate, funcname, funcexpr,
-										r, true);
+										r, r->lateral, true);
 
 	/*
 	 * If a coldeflist was supplied, ensure it defines a legal set of names
@@ -637,12 +604,9 @@ transformRangeFunction(ParseState *pstate, RangeFunction *r)
  *
  * *top_rti: receives the rangetable index of top_rte.	(Ditto.)
  *
- * *relnamespace: receives a List of the RTEs exposed as relation names
- * by this item.
- *
- * *containedRels: receives a bitmap set of the rangetable indexes
- * of all the base and join relations represented in this jointree item.
- * This is needed for checking JOIN/ON conditions in higher levels.
+ * *relnamespace: receives a List of ParseNamespaceItems for the RTEs exposed
+ * as relation names by this item.	(The lateral_only flags in these items
+ * are indeterminate and should be explicitly set by the caller before use.)
  *
  * We do not need to pass back an explicit varnamespace value, because
  * in all cases the varnamespace contribution is exactly top_rte.
@@ -650,8 +614,7 @@ transformRangeFunction(ParseState *pstate, RangeFunction *r)
 static Node *
 transformFromClauseItem(ParseState *pstate, Node *n,
 						RangeTblEntry **top_rte, int *top_rti,
-						List **relnamespace,
-						Relids *containedRels)
+						List **relnamespace)
 {
 	if (IsA(n, RangeVar))
 	{
@@ -681,8 +644,7 @@ transformFromClauseItem(ParseState *pstate, Node *n,
 		Assert(rte == rt_fetch(rtindex, pstate->p_rtable));
 		*top_rte = rte;
 		*top_rti = rtindex;
-		*relnamespace = list_make1(rte);
-		*containedRels = bms_make_singleton(rtindex);
+		*relnamespace = list_make1(makeNamespaceItem(rte, false, true));
 		rtr = makeNode(RangeTblRef);
 		rtr->rtindex = rtindex;
 		return (Node *) rtr;
@@ -700,8 +662,7 @@ transformFromClauseItem(ParseState *pstate, Node *n,
 		Assert(rte == rt_fetch(rtindex, pstate->p_rtable));
 		*top_rte = rte;
 		*top_rti = rtindex;
-		*relnamespace = list_make1(rte);
-		*containedRels = bms_make_singleton(rtindex);
+		*relnamespace = list_make1(makeNamespaceItem(rte, false, true));
 		rtr = makeNode(RangeTblRef);
 		rtr->rtindex = rtindex;
 		return (Node *) rtr;
@@ -719,8 +680,7 @@ transformFromClauseItem(ParseState *pstate, Node *n,
 		Assert(rte == rt_fetch(rtindex, pstate->p_rtable));
 		*top_rte = rte;
 		*top_rti = rtindex;
-		*relnamespace = list_make1(rte);
-		*containedRels = bms_make_singleton(rtindex);
+		*relnamespace = list_make1(makeNamespaceItem(rte, false, true));
 		rtr = makeNode(RangeTblRef);
 		rtr->rtindex = rtindex;
 		return (Node *) rtr;
@@ -733,9 +693,6 @@ transformFromClauseItem(ParseState *pstate, Node *n,
 		RangeTblEntry *r_rte;
 		int			l_rtindex;
 		int			r_rtindex;
-		Relids		l_containedRels,
-					r_containedRels,
-					my_containedRels;
 		List	   *l_relnamespace,
 				   *r_relnamespace,
 				   *my_relnamespace,
@@ -745,38 +702,66 @@ transformFromClauseItem(ParseState *pstate, Node *n,
 				   *l_colvars,
 				   *r_colvars,
 				   *res_colvars;
+		bool		lateral_ok;
+		int			sv_relnamespace_length,
+					sv_varnamespace_length;
 		RangeTblEntry *rte;
 		int			k;
 
 		/*
-		 * Recursively process the left and right subtrees
+		 * Recursively process the left subtree, then the right.  We must do
+		 * it in this order for correct visibility of LATERAL references.
 		 */
 		j->larg = transformFromClauseItem(pstate, j->larg,
 										  &l_rte,
 										  &l_rtindex,
-										  &l_relnamespace,
-										  &l_containedRels);
+										  &l_relnamespace);
+
+		/*
+		 * Make the left-side RTEs available for LATERAL access within the
+		 * right side, by temporarily adding them to the pstate's namespace
+		 * lists.  Per SQL:2008, if the join type is not INNER or LEFT then
+		 * the left-side names must still be exposed, but it's an error to
+		 * reference them.	(Stupid design, but that's what it says.)  Hence,
+		 * we always push them into the namespaces, but mark them as not
+		 * lateral_ok if the jointype is wrong.
+		 *
+		 * NB: this coding relies on the fact that list_concat is not
+		 * destructive to its second argument.
+		 */
+		lateral_ok = (j->jointype == JOIN_INNER || j->jointype == JOIN_LEFT);
+		setNamespaceLateralState(l_relnamespace, true, lateral_ok);
+		checkNameSpaceConflicts(pstate, pstate->p_relnamespace, l_relnamespace);
+		sv_relnamespace_length = list_length(pstate->p_relnamespace);
+		pstate->p_relnamespace = list_concat(pstate->p_relnamespace,
+											 l_relnamespace);
+		sv_varnamespace_length = list_length(pstate->p_varnamespace);
+		pstate->p_varnamespace = lappend(pstate->p_varnamespace,
+								 makeNamespaceItem(l_rte, true, lateral_ok));
+
+		/* And now we can process the RHS */
 		j->rarg = transformFromClauseItem(pstate, j->rarg,
 										  &r_rte,
 										  &r_rtindex,
-										  &r_relnamespace,
-										  &r_containedRels);
+										  &r_relnamespace);
+
+		/* Remove the left-side RTEs from the namespace lists again */
+		pstate->p_relnamespace = list_truncate(pstate->p_relnamespace,
+											   sv_relnamespace_length);
+		pstate->p_varnamespace = list_truncate(pstate->p_varnamespace,
+											   sv_varnamespace_length);
 
 		/*
 		 * Check for conflicting refnames in left and right subtrees. Must do
 		 * this because higher levels will assume I hand back a self-
-		 * consistent namespace subtree.
+		 * consistent namespace list.
 		 */
 		checkNameSpaceConflicts(pstate, l_relnamespace, r_relnamespace);
 
 		/*
-		 * Generate combined relation membership info for possible use by
-		 * transformJoinOnClause below.
+		 * Generate combined relnamespace info for possible use below.
 		 */
 		my_relnamespace = list_concat(l_relnamespace, r_relnamespace);
-		my_containedRels = bms_join(l_containedRels, r_containedRels);
-
-		pfree(r_relnamespace);	/* free unneeded list header */
 
 		/*
 		 * Extract column name and var lists from both subtrees
@@ -941,8 +926,7 @@ transformFromClauseItem(ParseState *pstate, Node *n,
 			/* User-written ON-condition; transform it */
 			j->quals = transformJoinOnClause(pstate, j,
 											 l_rte, r_rte,
-											 my_relnamespace,
-											 my_containedRels);
+											 my_relnamespace);
 		}
 		else
 		{
@@ -1006,18 +990,10 @@ transformFromClauseItem(ParseState *pstate, Node *n,
 		 * relnamespace.
 		 */
 		if (j->alias)
-		{
-			*relnamespace = list_make1(rte);
-			list_free(my_relnamespace);
-		}
+			*relnamespace = list_make1(makeNamespaceItem(rte, false, true));
 		else
 			*relnamespace = my_relnamespace;
 
-		/*
-		 * Include join RTE in returned containedRels set
-		 */
-		*containedRels = bms_add_member(my_containedRels, j->rtindex);
-
 		return (Node *) j;
 	}
 	else
@@ -1144,6 +1120,40 @@ buildMergedJoinVar(ParseState *pstate, JoinType jointype,
 	return res_node;
 }
 
+/*
+ * makeNamespaceItem -
+ *	  Convenience subroutine to construct a ParseNamespaceItem.
+ */
+static ParseNamespaceItem *
+makeNamespaceItem(RangeTblEntry *rte, bool lateral_only, bool lateral_ok)
+{
+	ParseNamespaceItem *nsitem;
+
+	nsitem = (ParseNamespaceItem *) palloc(sizeof(ParseNamespaceItem));
+	nsitem->p_rte = rte;
+	nsitem->p_lateral_only = lateral_only;
+	nsitem->p_lateral_ok = lateral_ok;
+	return nsitem;
+}
+
+/*
+ * setNamespaceLateralState -
+ *	  Convenience subroutine to update LATERAL flags in a namespace list.
+ */
+static void
+setNamespaceLateralState(List *namespace, bool lateral_only, bool lateral_ok)
+{
+	ListCell   *lc;
+
+	foreach(lc, namespace)
+	{
+		ParseNamespaceItem *nsitem = (ParseNamespaceItem *) lfirst(lc);
+
+		nsitem->p_lateral_only = lateral_only;
+		nsitem->p_lateral_ok = lateral_ok;
+	}
+}
+
 
 /*
  * transformWhereClause -