Fix up planner infrastructure to support LATERAL properly.

This patch takes care of a number of problems having to do with failure
to choose valid join orders and incorrect handling of lateral references
pulled up from subqueries.  Notable changes:

* Add a LateralJoinInfo data structure similar to SpecialJoinInfo, to
represent join ordering constraints created by lateral references.
(I first considered extending the SpecialJoinInfo structure, but the
semantics are different enough that a separate data structure seems
better.)  Extend join_is_legal() and related functions to prevent trying
to form unworkable joins, and to ensure that we will consider joins that
satisfy lateral references even if the joins would be clauseless.

* Fill in the infrastructure needed for the last few types of relation scan
paths to support parameterization.  We'd have wanted this eventually
anyway, but it is necessary now because a relation that gets pulled up out
of a UNION ALL subquery may acquire a reltargetlist containing lateral
references, meaning that its paths *have* to be parameterized whether or
not we have any code that can push join quals down into the scan.

* Compute data about lateral references early in query_planner(), and save
in RelOptInfo nodes, to avoid repetitive calculations later.

* Assorted corner-case bug fixes.

There's probably still some bugs left, but this is a lot closer to being
real than it was before.

4 files changed, 34 insertions, 29 deletions

diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index d16c3b8db1c..691afbf0ed6 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -902,18 +902,21 @@ create_bitmap_or_path(PlannerInfo *root,
  *	  Creates a path corresponding to a scan by TID, returning the pathnode.
  */
 TidPath *
-create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals)
+create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals,
+					Relids required_outer)
 {
 	TidPath    *pathnode = makeNode(TidPath);
 
 	pathnode->path.pathtype = T_TidScan;
 	pathnode->path.parent = rel;
-	pathnode->path.param_info = NULL;	/* never parameterized at present */
+	pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
+														  required_outer);
 	pathnode->path.pathkeys = NIL;		/* always unordered */
 
 	pathnode->tidquals = tidquals;
 
-	cost_tidscan(&pathnode->path, root, rel, tidquals);
+	cost_tidscan(&pathnode->path, root, rel, tidquals,
+				 pathnode->path.param_info);
 
 	return pathnode;
 }
@@ -1061,7 +1064,7 @@ create_result_path(List *quals)
 
 	pathnode->path.pathtype = T_Result;
 	pathnode->path.parent = NULL;
-	pathnode->path.param_info = NULL;
+	pathnode->path.param_info = NULL;		/* there are no other rels... */
 	pathnode->path.pathkeys = NIL;
 	pathnode->quals = quals;
 
@@ -1711,16 +1714,17 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel,
  *	  returning the pathnode.
  */
 Path *
-create_ctescan_path(PlannerInfo *root, RelOptInfo *rel)
+create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
 {
 	Path	   *pathnode = makeNode(Path);
 
 	pathnode->pathtype = T_CteScan;
 	pathnode->parent = rel;
-	pathnode->param_info = NULL;	/* never parameterized at present */
+	pathnode->param_info = get_baserel_parampathinfo(root, rel,
+													 required_outer);
 	pathnode->pathkeys = NIL;	/* XXX for now, result is always unordered */
 
-	cost_ctescan(pathnode, root, rel);
+	cost_ctescan(pathnode, root, rel, pathnode->param_info);
 
 	return pathnode;
 }
@@ -1731,17 +1735,19 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel)
  *	  returning the pathnode.
  */
 Path *
-create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel)
+create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel,
+						  Relids required_outer)
 {
 	Path	   *pathnode = makeNode(Path);
 
 	pathnode->pathtype = T_WorkTableScan;
 	pathnode->parent = rel;
-	pathnode->param_info = NULL;	/* never parameterized at present */
+	pathnode->param_info = get_baserel_parampathinfo(root, rel,
+													 required_outer);
 	pathnode->pathkeys = NIL;	/* result is always unordered */
 
 	/* Cost is the same as for a regular CTE scan */
-	cost_ctescan(pathnode, root, rel);
+	cost_ctescan(pathnode, root, rel, pathnode->param_info);
 
 	return pathnode;
 }
diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index e05c8ddef1b..317a01940e3 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -412,14 +412,14 @@ add_placeholders_to_base_rels(PlannerInfo *root)
 		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 		Relids		eval_at = phinfo->ph_eval_at;
 
-		if (bms_membership(eval_at) == BMS_SINGLETON)
+		if (bms_membership(eval_at) == BMS_SINGLETON &&
+			bms_nonempty_difference(phinfo->ph_needed, eval_at))
 		{
 			int			varno = bms_singleton_member(eval_at);
 			RelOptInfo *rel = find_base_rel(root, varno);
 
-			if (bms_nonempty_difference(phinfo->ph_needed, rel->relids))
-				rel->reltargetlist = lappend(rel->reltargetlist,
-											 copyObject(phinfo->ph_var));
+			rel->reltargetlist = lappend(rel->reltargetlist,
+										 copyObject(phinfo->ph_var));
 		}
 	}
 }
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 8d4ab03d20e..680184c0e9f 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -109,6 +109,8 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind)
 	rel->relid = relid;
 	rel->rtekind = rte->rtekind;
 	/* min_attr, max_attr, attr_needed, attr_widths are set below */
+	rel->lateral_vars = NIL;
+	rel->lateral_relids = NULL;
 	rel->indexlist = NIL;
 	rel->pages = 0;
 	rel->tuples = 0;
@@ -365,6 +367,8 @@ build_join_rel(PlannerInfo *root,
 	joinrel->max_attr = 0;
 	joinrel->attr_needed = NULL;
 	joinrel->attr_widths = NULL;
+	joinrel->lateral_vars = NIL;
+	joinrel->lateral_relids = NULL;
 	joinrel->indexlist = NIL;
 	joinrel->pages = 0;
 	joinrel->tuples = 0;
@@ -472,8 +476,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
 
 	foreach(vars, input_rel->reltargetlist)
 	{
-		Node	   *origvar = (Node *) lfirst(vars);
-		Var		   *var;
+		Var		   *var = (Var *) lfirst(vars);
 		RelOptInfo *baserel;
 		int			ndx;
 
@@ -481,22 +484,17 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
 		 * Ignore PlaceHolderVars in the input tlists; we'll make our own
 		 * decisions about whether to copy them.
 		 */
-		if (IsA(origvar, PlaceHolderVar))
+		if (IsA(var, PlaceHolderVar))
 			continue;
 
 		/*
-		 * We can't run into any child RowExprs here, but we could find a
-		 * whole-row Var with a ConvertRowtypeExpr atop it.
+		 * Otherwise, anything in a baserel or joinrel targetlist ought to be
+		 * a Var.  (More general cases can only appear in appendrel child
+		 * rels, which will never be seen here.)
 		 */
-		var = (Var *) origvar;
-		while (!IsA(var, Var))
-		{
-			if (IsA(var, ConvertRowtypeExpr))
-				var = (Var *) ((ConvertRowtypeExpr *) var)->arg;
-			else
-				elog(ERROR, "unexpected node type in reltargetlist: %d",
-					 (int) nodeTag(var));
-		}
+		if (!IsA(var, Var))
+			elog(ERROR, "unexpected node type in reltargetlist: %d",
+				 (int) nodeTag(var));
 
 		/* Get the Var's original base rel */
 		baserel = find_base_rel(root, var->varno);
@@ -506,7 +504,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
 		if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
 		{
 			/* Yup, add it to the output */
-			joinrel->reltargetlist = lappend(joinrel->reltargetlist, origvar);
+			joinrel->reltargetlist = lappend(joinrel->reltargetlist, var);
 			joinrel->width += baserel->attr_widths[ndx];
 		}
 	}
diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c
index 21b7753f05d..a0668c9615b 100644
--- a/src/backend/optimizer/util/var.c
+++ b/src/backend/optimizer/util/var.c
@@ -746,6 +746,7 @@ flatten_join_alias_vars_mutator(Node *node,
 	Assert(!IsA(node, SubPlan));
 	/* Shouldn't need to handle these planner auxiliary nodes here */
 	Assert(!IsA(node, SpecialJoinInfo));
+	Assert(!IsA(node, LateralJoinInfo));
 	Assert(!IsA(node, PlaceHolderInfo));
 	Assert(!IsA(node, MinMaxAggInfo));