In the planner, replace an empty FROM clause with a dummy RTE.

The fact that "SELECT expression" has no base relations has long been a
thorn in the side of the planner.  It makes it hard to flatten a sub-query
that looks like that, or is a trivial VALUES() item, because the planner
generally uses relid sets to identify sub-relations, and such a sub-query
would have an empty relid set if we flattened it.  prepjointree.c contains
some baroque logic that works around this in certain special cases --- but
there is a much better answer.  We can replace an empty FROM clause with a
dummy RTE that acts like a table of one row and no columns, and then there
are no such corner cases to worry about.  Instead we need some logic to
get rid of useless dummy RTEs, but that's simpler and covers more cases
than what was there before.

For really trivial cases, where the query is just "SELECT expression" and
nothing else, there's a hazard that adding the extra RTE makes for a
noticeable slowdown; even though it's not much processing, there's not
that much for the planner to do overall.  However testing says that the
penalty is very small, close to the noise level.  In more complex queries,
this is able to find optimizations that we could not find before.

The new RTE type is called RTE_RESULT, since the "scan" plan type it
gives rise to is a Result node (the same plan we produced for a "SELECT
expression" query before).  To avoid confusion, rename the old ResultPath
path type to GroupResultPath, reflecting that it's only used in degenerate
grouping cases where we know the query produces just one grouped row.
(It wouldn't work to unify the two cases, because there are different
rules about where the associated quals live during query_planner.)

Note: although this touches readfuncs.c, I don't think a catversion
bump is required, because the added case can't occur in stored rules,
only plans.

Patch by me, reviewed by David Rowley and Mark Dilger

Discussion: https://postgr.es/m/15944.1521127664@sss.pgh.pa.us

1 files changed, 541 insertions, 255 deletions

diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 77dbf4eba3d..bcbca1a0f50 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -4,12 +4,14 @@
  *	  Planner preprocessing for subqueries and join tree manipulation.
  *
  * NOTE: the intended sequence for invoking these operations is
+ *		replace_empty_jointree
  *		pull_up_sublinks
  *		inline_set_returning_functions
  *		pull_up_subqueries
  *		flatten_simple_union_all
  *		do expression preprocessing (including flattening JOIN alias vars)
  *		reduce_outer_joins
+ *		remove_useless_result_rtes
  *
  *
  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
@@ -66,14 +68,12 @@ static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 static Node *pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 						   JoinExpr *lowest_outer_join,
 						   JoinExpr *lowest_nulling_outer_join,
-						   AppendRelInfo *containing_appendrel,
-						   bool deletion_ok);
+						   AppendRelInfo *containing_appendrel);
 static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
 						RangeTblEntry *rte,
 						JoinExpr *lowest_outer_join,
 						JoinExpr *lowest_nulling_outer_join,
-						AppendRelInfo *containing_appendrel,
-						bool deletion_ok);
+						AppendRelInfo *containing_appendrel);
 static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,
 						 RangeTblEntry *rte);
 static void pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root,
@@ -82,12 +82,10 @@ static void pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root,
 static void make_setop_translation_list(Query *query, Index newvarno,
 							List **translated_vars);
 static bool is_simple_subquery(Query *subquery, RangeTblEntry *rte,
-				   JoinExpr *lowest_outer_join,
-				   bool deletion_ok);
+				   JoinExpr *lowest_outer_join);
 static Node *pull_up_simple_values(PlannerInfo *root, Node *jtnode,
 					  RangeTblEntry *rte);
-static bool is_simple_values(PlannerInfo *root, RangeTblEntry *rte,
-				 bool deletion_ok);
+static bool is_simple_values(PlannerInfo *root, RangeTblEntry *rte);
 static bool is_simple_union_all(Query *subquery);
 static bool is_simple_union_all_recurse(Node *setOp, Query *setOpQuery,
 							List *colTypes);
@@ -103,7 +101,6 @@ static Node *pullup_replace_vars_callback(Var *var,
 							 replace_rte_variables_context *context);
 static Query *pullup_replace_vars_subquery(Query *query,
 							 pullup_replace_vars_context *context);
-static Node *pull_up_subqueries_cleanup(Node *jtnode);
 static reduce_outer_joins_state *reduce_outer_joins_pass1(Node *jtnode);
 static void reduce_outer_joins_pass2(Node *jtnode,
 						 reduce_outer_joins_state *state,
@@ -111,14 +108,62 @@ static void reduce_outer_joins_pass2(Node *jtnode,
 						 Relids nonnullable_rels,
 						 List *nonnullable_vars,
 						 List *forced_null_vars);
-static void substitute_multiple_relids(Node *node,
-						   int varno, Relids subrelids);
+static Node *remove_useless_results_recurse(PlannerInfo *root, Node *jtnode);
+static int	get_result_relid(PlannerInfo *root, Node *jtnode);
+static void remove_result_refs(PlannerInfo *root, int varno, Node *newjtloc);
+static bool find_dependent_phvs(Node *node, int varno);
+static void substitute_phv_relids(Node *node,
+					  int varno, Relids subrelids);
 static void fix_append_rel_relids(List *append_rel_list, int varno,
 					  Relids subrelids);
 static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
 
 
 /*
+ * replace_empty_jointree
+ *		If the Query's jointree is empty, replace it with a dummy RTE_RESULT
+ *		relation.
+ *
+ * By doing this, we can avoid a bunch of corner cases that formerly existed
+ * for SELECTs with omitted FROM clauses.  An example is that a subquery
+ * with empty jointree previously could not be pulled up, because that would
+ * have resulted in an empty relid set, making the subquery not uniquely
+ * identifiable for join or PlaceHolderVar processing.
+ *
+ * Unlike most other functions in this file, this function doesn't recurse;
+ * we rely on other processing to invoke it on sub-queries at suitable times.
+ */
+void
+replace_empty_jointree(Query *parse)
+{
+	RangeTblEntry *rte;
+	Index		rti;
+	RangeTblRef *rtr;
+
+	/* Nothing to do if jointree is already nonempty */
+	if (parse->jointree->fromlist != NIL)
+		return;
+
+	/* We mustn't change it in the top level of a setop tree, either */
+	if (parse->setOperations)
+		return;
+
+	/* Create suitable RTE */
+	rte = makeNode(RangeTblEntry);
+	rte->rtekind = RTE_RESULT;
+	rte->eref = makeAlias("*RESULT*", NIL);
+
+	/* Add it to rangetable */
+	parse->rtable = lappend(parse->rtable, rte);
+	rti = list_length(parse->rtable);
+
+	/* And jam a reference into the jointree */
+	rtr = makeNode(RangeTblRef);
+	rtr->rtindex = rti;
+	parse->jointree->fromlist = list_make1(rtr);
+}
+
+/*
  * pull_up_sublinks
  *		Attempt to pull up ANY and EXISTS SubLinks to be treated as
  *		semijoins or anti-semijoins.
@@ -611,16 +656,11 @@ pull_up_subqueries(PlannerInfo *root)
 {
 	/* Top level of jointree must always be a FromExpr */
 	Assert(IsA(root->parse->jointree, FromExpr));
-	/* Reset flag saying we need a deletion cleanup pass */
-	root->hasDeletedRTEs = false;
 	/* Recursion starts with no containing join nor appendrel */
 	root->parse->jointree = (FromExpr *)
 		pull_up_subqueries_recurse(root, (Node *) root->parse->jointree,
-								   NULL, NULL, NULL, false);
-	/* Apply cleanup phase if necessary */
-	if (root->hasDeletedRTEs)
-		root->parse->jointree = (FromExpr *)
-			pull_up_subqueries_cleanup((Node *) root->parse->jointree);
+								   NULL, NULL, NULL);
+	/* We should still have a FromExpr */
 	Assert(IsA(root->parse->jointree, FromExpr));
 }
 
@@ -629,8 +669,6 @@ pull_up_subqueries(PlannerInfo *root)
  *		Recursive guts of pull_up_subqueries.
  *
  * This recursively processes the jointree and returns a modified jointree.
- * Or, if it's valid to drop the current node from the jointree completely,
- * it returns NULL.
  *
  * If this jointree node is within either side of an outer join, then
  * lowest_outer_join references the lowest such JoinExpr node; otherwise
@@ -647,37 +685,27 @@ pull_up_subqueries(PlannerInfo *root)
  * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist
  * items, and puts some additional restrictions on what can be pulled up.
  *
- * deletion_ok is true if the caller can cope with us returning NULL for a
- * deletable leaf node (for example, a VALUES RTE that could be pulled up).
- * If it's false, we'll avoid pullup in such cases.
- *
  * 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 leaf
- * RangeTblRef entries and entirely-empty FromExprs will be replaced or
- * deleted.  Also, we can't turn pullup_replace_vars loose on the whole
- * jointree, because it'll return a mutated copy of the tree; we have to
+ * we are currently processing!  We handle this by being careful to maintain
+ * validity of the jointree structure while recursing, in the following sense:
+ * whenever we recurse, all qual expressions in the tree must be reachable
+ * from the top level, in case the recursive call needs to modify them.
+ *
+ * Notice also that we can't turn pullup_replace_vars loose on the whole
+ * jointree, because it'd return a mutated copy of the tree; we have to
  * invoke it just on the quals, instead.  This behavior is what makes it
  * reasonable to pass lowest_outer_join and lowest_nulling_outer_join as
  * pointers rather than some more-indirect way of identifying the lowest
  * OJs.  Likewise, we don't replace append_rel_list members but only their
  * substructure, so the containing_appendrel reference is safe to use.
- *
- * Because of the rule that no jointree nodes with substructure can be
- * replaced, we cannot fully handle the case of deleting nodes from the tree:
- * when we delete one child of a JoinExpr, we need to replace the JoinExpr
- * with a FromExpr, and that can't happen here.  Instead, we set the
- * root->hasDeletedRTEs flag, which tells pull_up_subqueries() that an
- * additional pass over the tree is needed to clean up.
  */
 static Node *
 pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 						   JoinExpr *lowest_outer_join,
 						   JoinExpr *lowest_nulling_outer_join,
-						   AppendRelInfo *containing_appendrel,
-						   bool deletion_ok)
+						   AppendRelInfo *containing_appendrel)
 {
 	Assert(jtnode != NULL);
 	if (IsA(jtnode, RangeTblRef))
@@ -693,15 +721,13 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 		 * unless is_safe_append_member says so.
 		 */
 		if (rte->rtekind == RTE_SUBQUERY &&
-			is_simple_subquery(rte->subquery, rte,
-							   lowest_outer_join, deletion_ok) &&
+			is_simple_subquery(rte->subquery, rte, lowest_outer_join) &&
 			(containing_appendrel == NULL ||
 			 is_safe_append_member(rte->subquery)))
 			return pull_up_simple_subquery(root, jtnode, rte,
 										   lowest_outer_join,
 										   lowest_nulling_outer_join,
-										   containing_appendrel,
-										   deletion_ok);
+										   containing_appendrel);
 
 		/*
 		 * Alternatively, is it a simple UNION ALL subquery?  If so, flatten
@@ -725,7 +751,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 		if (rte->rtekind == RTE_VALUES &&
 			lowest_outer_join == NULL &&
 			containing_appendrel == NULL &&
-			is_simple_values(root, rte, deletion_ok))
+			is_simple_values(root, rte))
 			return pull_up_simple_values(root, jtnode, rte);
 
 		/* Otherwise, do nothing at this node. */
@@ -733,50 +759,16 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 	else if (IsA(jtnode, FromExpr))
 	{
 		FromExpr   *f = (FromExpr *) jtnode;
-		bool		have_undeleted_child = false;
 		ListCell   *l;
 
 		Assert(containing_appendrel == NULL);
-
-		/*
-		 * If the FromExpr has quals, it's not deletable even if its parent
-		 * would allow deletion.
-		 */
-		if (f->quals)
-			deletion_ok = false;
-
+		/* Recursively transform all the child nodes */
 		foreach(l, f->fromlist)
 		{
-			/*
-			 * In a non-deletable FromExpr, we can allow deletion of child
-			 * nodes so long as at least one child remains; so it's okay
-			 * either if any previous child survives, or if there's more to
-			 * come.  If all children are deletable in themselves, we'll force
-			 * the last one to remain unflattened.
-			 *
-			 * As a separate matter, we can allow deletion of all children of
-			 * the top-level FromExpr in a query, since that's a special case
-			 * anyway.
-			 */
-			bool		sub_deletion_ok = (deletion_ok ||
-										   have_undeleted_child ||
-										   lnext(l) != NULL ||
-										   f == root->parse->jointree);
-
 			lfirst(l) = pull_up_subqueries_recurse(root, lfirst(l),
 												   lowest_outer_join,
 												   lowest_nulling_outer_join,
-												   NULL,
-												   sub_deletion_ok);
-			if (lfirst(l) != NULL)
-				have_undeleted_child = true;
-		}
-
-		if (deletion_ok && !have_undeleted_child)
-		{
-			/* OK to delete this FromExpr entirely */
-			root->hasDeletedRTEs = true;	/* probably is set already */
-			return NULL;
+												   NULL);
 		}
 	}
 	else if (IsA(jtnode, JoinExpr))
@@ -788,22 +780,14 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 		switch (j->jointype)
 		{
 			case JOIN_INNER:
-
-				/*
-				 * INNER JOIN can allow deletion of either child node, but not
-				 * both.  So right child gets permission to delete only if
-				 * left child didn't get removed.
-				 */
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 lowest_outer_join,
 													 lowest_nulling_outer_join,
-													 NULL,
-													 true);
+													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 lowest_outer_join,
 													 lowest_nulling_outer_join,
-													 NULL,
-													 j->larg != NULL);
+													 NULL);
 				break;
 			case JOIN_LEFT:
 			case JOIN_SEMI:
@@ -811,37 +795,31 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
 													 lowest_nulling_outer_join,
-													 NULL,
-													 false);
+													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
 													 j,
-													 NULL,
-													 false);
+													 NULL);
 				break;
 			case JOIN_FULL:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
 													 j,
-													 NULL,
-													 false);
+													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
 													 j,
-													 NULL,
-													 false);
+													 NULL);
 				break;
 			case JOIN_RIGHT:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
 													 j,
-													 NULL,
-													 false);
+													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
 													 lowest_nulling_outer_join,
-													 NULL,
-													 false);
+													 NULL);
 				break;
 			default:
 				elog(ERROR, "unrecognized join type: %d",
@@ -861,8 +839,8 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
  *
  * jtnode is a RangeTblRef that has been tentatively identified as a simple
  * subquery by pull_up_subqueries.  We return the replacement jointree node,
- * or NULL if the subquery can be deleted entirely, or jtnode itself if we
- * determine that the subquery can't be pulled up after all.
+ * or jtnode itself if we determine that the subquery can't be pulled up
+ * after all.
  *
  * rte is the RangeTblEntry referenced by jtnode.  Remaining parameters are
  * as for pull_up_subqueries_recurse.
@@ -871,8 +849,7 @@ static Node *
 pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 						JoinExpr *lowest_outer_join,
 						JoinExpr *lowest_nulling_outer_join,
-						AppendRelInfo *containing_appendrel,
-						bool deletion_ok)
+						AppendRelInfo *containing_appendrel)
 {
 	Query	   *parse = root->parse;
 	int			varno = ((RangeTblRef *) jtnode)->rtindex;
@@ -926,6 +903,12 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	Assert(subquery->cteList == NIL);
 
 	/*
+	 * If the FROM clause is empty, replace it with a dummy RTE_RESULT RTE, so
+	 * that we don't need so many special cases to deal with that situation.
+	 */
+	replace_empty_jointree(subquery);
+
+	/*
 	 * Pull up any SubLinks within the subquery's quals, so that we don't
 	 * leave unoptimized SubLinks behind.
 	 */
@@ -957,8 +940,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	 * easier just to keep this "if" looking the same as the one in
 	 * pull_up_subqueries_recurse.
 	 */
-	if (is_simple_subquery(subquery, rte,
-						   lowest_outer_join, deletion_ok) &&
+	if (is_simple_subquery(subquery, rte, lowest_outer_join) &&
 		(containing_appendrel == NULL || is_safe_append_member(subquery)))
 	{
 		/* good to go */
@@ -1159,6 +1141,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 				case RTE_JOIN:
 				case RTE_CTE:
 				case RTE_NAMEDTUPLESTORE:
+				case RTE_RESULT:
 					/* these can't contain any lateral references */
 					break;
 			}
@@ -1195,7 +1178,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 		Relids		subrelids;
 
 		subrelids = get_relids_in_jointree((Node *) subquery->jointree, false);
-		substitute_multiple_relids((Node *) parse, varno, subrelids);
+		substitute_phv_relids((Node *) parse, varno, subrelids);
 		fix_append_rel_relids(root->append_rel_list, varno, subrelids);
 	}
 
@@ -1235,17 +1218,14 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 
 	/*
 	 * Return the adjusted subquery jointree to replace the RangeTblRef entry
-	 * in parent's jointree; or, if we're flattening a subquery with empty
-	 * FROM list, return NULL to signal deletion of the subquery from the
-	 * parent jointree (and set hasDeletedRTEs to ensure cleanup later).
+	 * in parent's jointree; or, if the FromExpr is degenerate, just return
+	 * its single member.
 	 */
-	if (subquery->jointree->fromlist == NIL)
-	{
-		Assert(deletion_ok);
-		Assert(subquery->jointree->quals == NULL);
-		root->hasDeletedRTEs = true;
-		return NULL;
-	}
+	Assert(IsA(subquery->jointree, FromExpr));
+	Assert(subquery->jointree->fromlist != NIL);
+	if (subquery->jointree->quals == NULL &&
+		list_length(subquery->jointree->fromlist) == 1)
+		return (Node *) linitial(subquery->jointree->fromlist);
 
 	return (Node *) subquery->jointree;
 }
@@ -1381,7 +1361,7 @@ pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex,
 		rtr = makeNode(RangeTblRef);
 		rtr->rtindex = childRTindex;
 		(void) pull_up_subqueries_recurse(root, (Node *) rtr,
-										  NULL, NULL, appinfo, false);
+										  NULL, NULL, appinfo);
 	}
 	else if (IsA(setOp, SetOperationStmt))
 	{
@@ -1436,12 +1416,10 @@ make_setop_translation_list(Query *query, Index newvarno,
  * (Note subquery is not necessarily equal to rte->subquery; it could be a
  * processed copy of that.)
  * lowest_outer_join is the lowest outer join above the subquery, or NULL.
- * deletion_ok is true if it'd be okay to delete the subquery entirely.
  */
 static bool
 is_simple_subquery(Query *subquery, RangeTblEntry *rte,
-				   JoinExpr *lowest_outer_join,
-				   bool deletion_ok)
+				   JoinExpr *lowest_outer_join)
 {
 	/*
 	 * Let's just make sure it's a valid subselect ...
@@ -1491,44 +1469,6 @@ is_simple_subquery(Query *subquery, RangeTblEntry *rte,
 		return false;
 
 	/*
-	 * Don't pull up a subquery with an empty jointree, unless it has no quals
-	 * and deletion_ok is true and we're not underneath an outer join.
-	 *
-	 * query_planner() will correctly generate a Result plan for a jointree
-	 * that's totally empty, but we can't cope with an empty FromExpr
-	 * appearing lower down in a jointree: we identify join rels via baserelid
-	 * sets, so we couldn't distinguish a join containing such a FromExpr from
-	 * one without it.  We can only handle such cases if the place where the
-	 * subquery is linked is a FromExpr or inner JOIN that would still be
-	 * nonempty after removal of the subquery, so that it's still identifiable
-	 * via its contained baserelids.  Safe contexts are signaled by
-	 * deletion_ok.
-	 *
-	 * But even in a safe context, we must keep the subquery if it has any
-	 * quals, because it's unclear where to put them in the upper query.
-	 *
-	 * Also, we must forbid pullup if such a subquery is underneath an outer
-	 * join, because then we might need to wrap its output columns with
-	 * PlaceHolderVars, and the PHVs would then have empty relid sets meaning
-	 * we couldn't tell where to evaluate them.  (This test is separate from
-	 * the deletion_ok flag for possible future expansion: deletion_ok tells
-	 * whether the immediate parent site in the jointree could cope, not
-	 * whether we'd have PHV issues.  It's possible this restriction could be
-	 * fixed by letting the PHVs use the relids of the parent jointree item,
-	 * but that complication is for another day.)
-	 *
-	 * Note that deletion of a subquery is also dependent on the check below
-	 * that its targetlist contains no set-returning functions.  Deletion from
-	 * a FROM list or inner JOIN is okay only if the subquery must return
-	 * exactly one row.
-	 */
-	if (subquery->jointree->fromlist == NIL &&
-		(subquery->jointree->quals != NULL ||
-		 !deletion_ok ||
-		 lowest_outer_join != NULL))
-		return false;
-
-	/*
 	 * If the subquery is LATERAL, check for pullup restrictions from that.
 	 */
 	if (rte->lateral)
@@ -1602,9 +1542,10 @@ is_simple_subquery(Query *subquery, RangeTblEntry *rte,
  *		Pull up a single simple VALUES RTE.
  *
  * jtnode is a RangeTblRef that has been identified as a simple VALUES RTE
- * by pull_up_subqueries.  We always return NULL indicating that the RTE
- * can be deleted entirely (all failure cases should have been detected by
- * is_simple_values()).
+ * by pull_up_subqueries.  We always return a RangeTblRef representing a
+ * RESULT RTE to replace it (all failure cases should have been detected by
+ * is_simple_values()).  Actually, what we return is just jtnode, because
+ * we replace the VALUES RTE in the rangetable with the RESULT RTE.
  *
  * rte is the RangeTblEntry referenced by jtnode.  Because of the limited
  * possible usage of VALUES RTEs, we do not need the remaining parameters
@@ -1703,11 +1644,23 @@ pull_up_simple_values(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte)
 	Assert(root->placeholder_list == NIL);
 
 	/*
-	 * Return NULL to signal deletion of the VALUES RTE from the parent
-	 * jointree (and set hasDeletedRTEs to ensure cleanup later).
+	 * Replace the VALUES RTE with a RESULT RTE.  The VALUES RTE is the only
+	 * rtable entry in the current query level, so this is easy.
 	 */
-	root->hasDeletedRTEs = true;
-	return NULL;
+	Assert(list_length(parse->rtable) == 1);
+
+	/* Create suitable RTE */
+	rte = makeNode(RangeTblEntry);
+	rte->rtekind = RTE_RESULT;
+	rte->eref = makeAlias("*RESULT*", NIL);
+
+	/* Replace rangetable */
+	parse->rtable = list_make1(rte);
+
+	/* We could manufacture a new RangeTblRef, but the one we have is fine */
+	Assert(varno == 1);
+
+	return jtnode;
 }
 
 /*
@@ -1716,24 +1669,16 @@ pull_up_simple_values(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte)
  *	  to pull up into the parent query.
  *
  * rte is the RTE_VALUES RangeTblEntry to check.
- * deletion_ok is true if it'd be okay to delete the VALUES RTE entirely.
  */
 static bool
-is_simple_values(PlannerInfo *root, RangeTblEntry *rte, bool deletion_ok)
+is_simple_values(PlannerInfo *root, RangeTblEntry *rte)
 {
 	Assert(rte->rtekind == RTE_VALUES);
 
 	/*
-	 * We can only pull up a VALUES RTE if deletion_ok is true.  It's
-	 * basically the same case as a sub-select with empty FROM list; see
-	 * comments in is_simple_subquery().
-	 */
-	if (!deletion_ok)
-		return false;
-
-	/*
-	 * Also, there must be exactly one VALUES list, else it's not semantically
-	 * correct to delete the VALUES RTE.
+	 * There must be exactly one VALUES list, else it's not semantically
+	 * correct to replace the VALUES RTE with a RESULT RTE, nor would we have
+	 * a unique set of expressions to substitute into the parent query.
 	 */
 	if (list_length(rte->values_lists) != 1)
 		return false;
@@ -1746,8 +1691,8 @@ is_simple_values(PlannerInfo *root, RangeTblEntry *rte, bool deletion_ok)
 
 	/*
 	 * Don't pull up a VALUES that contains any set-returning or volatile
-	 * functions.  Again, the considerations here are basically identical to
-	 * restrictions on a subquery's targetlist.
+	 * functions.  The considerations here are basically identical to the
+	 * restrictions on a pull-able subquery's targetlist.
 	 */
 	if (expression_returns_set((Node *) rte->values_lists) ||
 		contain_volatile_functions((Node *) rte->values_lists))
@@ -1850,7 +1795,9 @@ is_safe_append_member(Query *subquery)
 	/*
 	 * It's only safe to pull up the child if its jointree contains exactly
 	 * one RTE, else the AppendRelInfo data structure breaks. The one base RTE
-	 * could be buried in several levels of FromExpr, however.
+	 * could be buried in several levels of FromExpr, however.  Also, if the
+	 * child's jointree is completely empty, we can pull up because
+	 * pull_up_simple_subquery will insert a single RTE_RESULT RTE instead.
 	 *
 	 * Also, the child can't have any WHERE quals because there's no place to
 	 * put them in an appendrel.  (This is a bit annoying...) If we didn't
@@ -1859,6 +1806,11 @@ is_safe_append_member(Query *subquery)
 	 * fix_append_rel_relids().
 	 */
 	jtnode = subquery->jointree;
+	Assert(IsA(jtnode, FromExpr));
+	/* Check the completely-empty case */
+	if (jtnode->fromlist == NIL && jtnode->quals == NULL)
+		return true;
+	/* Check the more general case */
 	while (IsA(jtnode, FromExpr))
 	{
 		if (jtnode->quals != NULL)
@@ -2014,6 +1966,7 @@ replace_vars_in_jointree(Node *jtnode,
 					case RTE_JOIN:
 					case RTE_CTE:
 					case RTE_NAMEDTUPLESTORE:
+					case RTE_RESULT:
 						/* these shouldn't be marked LATERAL */
 						Assert(false);
 						break;
@@ -2290,65 +2243,6 @@ pullup_replace_vars_subquery(Query *query,
 										   NULL);
 }
 
-/*
- * pull_up_subqueries_cleanup
- *		Recursively fix up jointree after deletion of some subqueries.
- *
- * The jointree now contains some NULL subtrees, which we need to get rid of.
- * In a FromExpr, just rebuild the child-node list with null entries deleted.
- * In an inner JOIN, replace the JoinExpr node with a one-child FromExpr.
- */
-static Node *
-pull_up_subqueries_cleanup(Node *jtnode)
-{
-	Assert(jtnode != NULL);
-	if (IsA(jtnode, RangeTblRef))
-	{
-		/* Nothing to do at leaf nodes. */
-	}
-	else if (IsA(jtnode, FromExpr))
-	{
-		FromExpr   *f = (FromExpr *) jtnode;
-		List	   *newfrom = NIL;
-		ListCell   *l;
-
-		foreach(l, f->fromlist)
-		{
-			Node	   *child = (Node *) lfirst(l);
-
-			if (child == NULL)
-				continue;
-			child = pull_up_subqueries_cleanup(child);
-			newfrom = lappend(newfrom, child);
-		}
-		f->fromlist = newfrom;
-	}
-	else if (IsA(jtnode, JoinExpr))
-	{
-		JoinExpr   *j = (JoinExpr *) jtnode;
-
-		if (j->larg)
-			j->larg = pull_up_subqueries_cleanup(j->larg);
-		if (j->rarg)
-			j->rarg = pull_up_subqueries_cleanup(j->rarg);
-		if (j->larg == NULL)
-		{
-			Assert(j->jointype == JOIN_INNER);
-			Assert(j->rarg != NULL);
-			return (Node *) makeFromExpr(list_make1(j->rarg), j->quals);
-		}
-		else if (j->rarg == NULL)
-		{
-			Assert(j->jointype == JOIN_INNER);
-			return (Node *) makeFromExpr(list_make1(j->larg), j->quals);
-		}
-	}
-	else
-		elog(ERROR, "unrecognized node type: %d",
-			 (int) nodeTag(jtnode));
-	return jtnode;
-}
-
 
 /*
  * flatten_simple_union_all
@@ -2858,9 +2752,399 @@ reduce_outer_joins_pass2(Node *jtnode,
 			 (int) nodeTag(jtnode));
 }
 
+
+/*
+ * remove_useless_result_rtes
+ *		Attempt to remove RTE_RESULT RTEs from the join tree.
+ *
+ * We can remove RTE_RESULT entries from the join tree using the knowledge
+ * that RTE_RESULT returns exactly one row and has no output columns.  Hence,
+ * if one is inner-joined to anything else, we can delete it.  Optimizations
+ * are also possible for some outer-join cases, as detailed below.
+ *
+ * Some of these optimizations depend on recognizing empty (constant-true)
+ * quals for FromExprs and JoinExprs.  That makes it useful to apply this
+ * optimization pass after expression preprocessing, since that will have
+ * eliminated constant-true quals, allowing more cases to be recognized as
+ * optimizable.  What's more, the usual reason for an RTE_RESULT to be present
+ * is that we pulled up a subquery or VALUES clause, thus very possibly
+ * replacing Vars with constants, making it more likely that a qual can be
+ * reduced to constant true.  Also, because some optimizations depend on
+ * the outer-join type, it's best to have done reduce_outer_joins() first.
+ *
+ * A PlaceHolderVar referencing an RTE_RESULT RTE poses an obstacle to this
+ * process: we must remove the RTE_RESULT's relid from the PHV's phrels, but
+ * we must not reduce the phrels set to empty.  If that would happen, and
+ * the RTE_RESULT is an immediate child of an outer join, we have to give up
+ * and not remove the RTE_RESULT: there is noplace else to evaluate the
+ * PlaceHolderVar.  (That is, in such cases the RTE_RESULT *does* have output
+ * columns.)  But if the RTE_RESULT is an immediate child of an inner join,
+ * we can change the PlaceHolderVar's phrels so as to evaluate it at the
+ * inner join instead.  This is OK because we really only care that PHVs are
+ * evaluated above or below the correct outer joins.
+ *
+ * We used to try to do this work as part of pull_up_subqueries() where the
+ * potentially-optimizable cases get introduced; but it's way simpler, and
+ * more effective, to do it separately.
+ */
+void
+remove_useless_result_rtes(PlannerInfo *root)
+{
+	ListCell   *cell;
+	ListCell   *prev;
+	ListCell   *next;
+
+	/* Top level of jointree must always be a FromExpr */
+	Assert(IsA(root->parse->jointree, FromExpr));
+	/* Recurse ... */
+	root->parse->jointree = (FromExpr *)
+		remove_useless_results_recurse(root, (Node *) root->parse->jointree);
+	/* We should still have a FromExpr */
+	Assert(IsA(root->parse->jointree, FromExpr));
+
+	/*
+	 * Remove any PlanRowMark referencing an RTE_RESULT RTE.  We obviously
+	 * must do that for any RTE_RESULT that we just removed.  But one for a
+	 * RTE that we did not remove can be dropped anyway: since the RTE has
+	 * only one possible output row, there is no need for EPQ to mark and
+	 * restore that row.
+	 *
+	 * It's necessary, not optional, to remove the PlanRowMark for a surviving
+	 * RTE_RESULT RTE; otherwise we'll generate a whole-row Var for the
+	 * RTE_RESULT, which the executor has no support for.
+	 */
+	prev = NULL;
+	for (cell = list_head(root->rowMarks); cell; cell = next)
+	{
+		PlanRowMark *rc = (PlanRowMark *) lfirst(cell);
+
+		next = lnext(cell);
+		if (rt_fetch(rc->rti, root->parse->rtable)->rtekind == RTE_RESULT)
+			root->rowMarks = list_delete_cell(root->rowMarks, cell, prev);
+		else
+			prev = cell;
+	}
+}
+
+/*
+ * remove_useless_results_recurse
+ *		Recursive guts of remove_useless_result_rtes.
+ *
+ * This recursively processes the jointree and returns a modified jointree.
+ */
+static Node *
+remove_useless_results_recurse(PlannerInfo *root, Node *jtnode)
+{
+	Assert(jtnode != NULL);
+	if (IsA(jtnode, RangeTblRef))
+	{
+		/* Can't immediately do anything with a RangeTblRef */
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		Relids		result_relids = NULL;
+		ListCell   *cell;
+		ListCell   *prev;
+		ListCell   *next;
+
+		/*
+		 * We can drop RTE_RESULT rels from the fromlist so long as at least
+		 * one child remains, since joining to a one-row table changes
+		 * nothing.  The easiest way to mechanize this rule is to modify the
+		 * list in-place, using list_delete_cell.
+		 */
+		prev = NULL;
+		for (cell = list_head(f->fromlist); cell; cell = next)
+		{
+			Node	   *child = (Node *) lfirst(cell);
+			int			varno;
+
+			/* Recursively transform child ... */
+			child = remove_useless_results_recurse(root, child);
+			/* ... and stick it back into the tree */
+			lfirst(cell) = child;
+			next = lnext(cell);
+
+			/*
+			 * If it's an RTE_RESULT with at least one sibling, we can drop
+			 * it.  We don't yet know what the inner join's final relid set
+			 * will be, so postpone cleanup of PHVs etc till after this loop.
+			 */
+			if (list_length(f->fromlist) > 1 &&
+				(varno = get_result_relid(root, child)) != 0)
+			{
+				f->fromlist = list_delete_cell(f->fromlist, cell, prev);
+				result_relids = bms_add_member(result_relids, varno);
+			}
+			else
+				prev = cell;
+		}
+
+		/*
+		 * Clean up if we dropped any RTE_RESULT RTEs.  This is a bit
+		 * inefficient if there's more than one, but it seems better to
+		 * optimize the support code for the single-relid case.
+		 */
+		if (result_relids)
+		{
+			int			varno = -1;
+
+			while ((varno = bms_next_member(result_relids, varno)) >= 0)
+				remove_result_refs(root, varno, (Node *) f);
+		}
+
+		/*
+		 * If we're not at the top of the jointree, it's valid to simplify a
+		 * degenerate FromExpr into its single child.  (At the top, we must
+		 * keep the FromExpr since Query.jointree is required to point to a
+		 * FromExpr.)
+		 */
+		if (f != root->parse->jointree &&
+			f->quals == NULL &&
+			list_length(f->fromlist) == 1)
+			return (Node *) linitial(f->fromlist);
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+		int			varno;
+
+		/* First, recurse */
+		j->larg = remove_useless_results_recurse(root, j->larg);
+		j->rarg = remove_useless_results_recurse(root, j->rarg);
+
+		/* Apply join-type-specific optimization rules */
+		switch (j->jointype)
+		{
+			case JOIN_INNER:
+
+				/*
+				 * An inner join is equivalent to a FromExpr, so if either
+				 * side was simplified to an RTE_RESULT rel, we can replace
+				 * the join with a FromExpr with just the other side; and if
+				 * the qual is empty (JOIN ON TRUE) then we can omit the
+				 * FromExpr as well.
+				 */
+				if ((varno = get_result_relid(root, j->larg)) != 0)
+				{
+					remove_result_refs(root, varno, j->rarg);
+					if (j->quals)
+						jtnode = (Node *)
+							makeFromExpr(list_make1(j->rarg), j->quals);
+					else
+						jtnode = j->rarg;
+				}
+				else if ((varno = get_result_relid(root, j->rarg)) != 0)
+				{
+					remove_result_refs(root, varno, j->larg);
+					if (j->quals)
+						jtnode = (Node *)
+							makeFromExpr(list_make1(j->larg), j->quals);
+					else
+						jtnode = j->larg;
+				}
+				break;
+			case JOIN_LEFT:
+
+				/*
+				 * We can simplify this case if the RHS is an RTE_RESULT, with
+				 * two different possibilities:
+				 *
+				 * If the qual is empty (JOIN ON TRUE), then the join can be
+				 * strength-reduced to a plain inner join, since each LHS row
+				 * necessarily has exactly one join partner.  So we can always
+				 * discard the RHS, much as in the JOIN_INNER case above.
+				 *
+				 * Otherwise, it's still true that each LHS row should be
+				 * returned exactly once, and since the RHS returns no columns
+				 * (unless there are PHVs that have to be evaluated there), we
+				 * don't much care if it's null-extended or not.  So in this
+				 * case also, we can just ignore the qual and discard the left
+				 * join.
+				 */
+				if ((varno = get_result_relid(root, j->rarg)) != 0 &&
+					(j->quals == NULL ||
+					 !find_dependent_phvs((Node *) root->parse, varno)))
+				{
+					remove_result_refs(root, varno, j->larg);
+					jtnode = j->larg;
+				}
+				break;
+			case JOIN_RIGHT:
+				/* Mirror-image of the JOIN_LEFT case */
+				if ((varno = get_result_relid(root, j->larg)) != 0 &&
+					(j->quals == NULL ||
+					 !find_dependent_phvs((Node *) root->parse, varno)))
+				{
+					remove_result_refs(root, varno, j->rarg);
+					jtnode = j->rarg;
+				}
+				break;
+			case JOIN_SEMI:
+
+				/*
+				 * We may simplify this case if the RHS is an RTE_RESULT; the
+				 * join qual becomes effectively just a filter qual for the
+				 * LHS, since we should either return the LHS row or not.  For
+				 * simplicity we inject the filter qual into a new FromExpr.
+				 *
+				 * Unlike the LEFT/RIGHT cases, we just Assert that there are
+				 * no PHVs that need to be evaluated at the semijoin's RHS,
+				 * since the rest of the query couldn't reference any outputs
+				 * of the semijoin's RHS.
+				 */
+				if ((varno = get_result_relid(root, j->rarg)) != 0)
+				{
+					Assert(!find_dependent_phvs((Node *) root->parse, varno));
+					remove_result_refs(root, varno, j->larg);
+					if (j->quals)
+						jtnode = (Node *)
+							makeFromExpr(list_make1(j->larg), j->quals);
+					else
+						jtnode = j->larg;
+				}
+				break;
+			case JOIN_FULL:
+			case JOIN_ANTI:
+				/* We have no special smarts for these cases */
+				break;
+			default:
+				elog(ERROR, "unrecognized join type: %d",
+					 (int) j->jointype);
+				break;
+		}
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d",
+			 (int) nodeTag(jtnode));
+	return jtnode;
+}
+
+/*
+ * get_result_relid
+ *		If jtnode is a RangeTblRef for an RTE_RESULT RTE, return its relid;
+ *		otherwise return 0.
+ */
+static inline int
+get_result_relid(PlannerInfo *root, Node *jtnode)
+{
+	int			varno;
+
+	if (!IsA(jtnode, RangeTblRef))
+		return 0;
+	varno = ((RangeTblRef *) jtnode)->rtindex;
+	if (rt_fetch(varno, root->parse->rtable)->rtekind != RTE_RESULT)
+		return 0;
+	return varno;
+}
+
+/*
+ * remove_result_refs
+ *		Helper routine for dropping an unneeded RTE_RESULT RTE.
+ *
+ * This doesn't physically remove the RTE from the jointree, because that's
+ * more easily handled in remove_useless_results_recurse.  What it does do
+ * is the necessary cleanup in the rest of the tree: we must adjust any PHVs
+ * that may reference the RTE.  Be sure to call this at a point where the
+ * jointree is valid (no disconnected nodes).
+ *
+ * Note that we don't need to process the append_rel_list, since RTEs
+ * referenced directly in the jointree won't be appendrel members.
+ *
+ * varno is the RTE_RESULT's relid.
+ * newjtloc is the jointree location at which any PHVs referencing the
+ * RTE_RESULT should be evaluated instead.
+ */
+static void
+remove_result_refs(PlannerInfo *root, int varno, Node *newjtloc)
+{
+	/* Fix up PlaceHolderVars as needed */
+	/* If there are no PHVs anywhere, we can skip this bit */
+	if (root->glob->lastPHId != 0)
+	{
+		Relids		subrelids;
+
+		subrelids = get_relids_in_jointree(newjtloc, false);
+		Assert(!bms_is_empty(subrelids));
+		substitute_phv_relids((Node *) root->parse, varno, subrelids);
+	}
+
+	/*
+	 * We also need to remove any PlanRowMark referencing the RTE, but we
+	 * postpone that work until we return to remove_useless_result_rtes.
+	 */
+}
+
+
+/*
+ * find_dependent_phvs - are there any PlaceHolderVars whose relids are
+ * exactly the given varno?
+ */
+
+typedef struct
+{
+	Relids		relids;
+	int			sublevels_up;
+} find_dependent_phvs_context;
+
+static bool
+find_dependent_phvs_walker(Node *node,
+						   find_dependent_phvs_context *context)
+{
+	if (node == NULL)
+		return false;
+	if (IsA(node, PlaceHolderVar))
+	{
+		PlaceHolderVar *phv = (PlaceHolderVar *) node;
+
+		if (phv->phlevelsup == context->sublevels_up &&
+			bms_equal(context->relids, phv->phrels))
+			return true;
+		/* fall through to examine children */
+	}
+	if (IsA(node, Query))
+	{
+		/* Recurse into subselects */
+		bool		result;
+
+		context->sublevels_up++;
+		result = query_tree_walker((Query *) node,
+								   find_dependent_phvs_walker,
+								   (void *) context, 0);
+		context->sublevels_up--;
+		return result;
+	}
+	/* Shouldn't need to handle planner auxiliary nodes here */
+	Assert(!IsA(node, SpecialJoinInfo));
+	Assert(!IsA(node, AppendRelInfo));
+	Assert(!IsA(node, PlaceHolderInfo));
+	Assert(!IsA(node, MinMaxAggInfo));
+
+	return expression_tree_walker(node, find_dependent_phvs_walker,
+								  (void *) context);
+}
+
+static bool
+find_dependent_phvs(Node *node, int varno)
+{
+	find_dependent_phvs_context context;
+
+	context.relids = bms_make_singleton(varno);
+	context.sublevels_up = 0;
+
+	/*
+	 * Must be prepared to start with a Query or a bare expression tree.
+	 */
+	return query_or_expression_tree_walker(node,
+										   find_dependent_phvs_walker,
+										   (void *) &context,
+										   0);
+}
+
 /*
- * substitute_multiple_relids - adjust node relid sets after pulling up
- * a subquery
+ * substitute_phv_relids - adjust PlaceHolderVar relid sets after pulling up
+ * a subquery or removing an RTE_RESULT jointree item
  *
  * Find any PlaceHolderVar nodes in the given tree that reference the
  * pulled-up relid, and change them to reference the replacement relid(s).
@@ -2876,11 +3160,11 @@ typedef struct
 	int			varno;
 	int			sublevels_up;
 	Relids		subrelids;
-} substitute_multiple_relids_context;
+} substitute_phv_relids_context;
 
 static bool
-substitute_multiple_relids_walker(Node *node,
-								  substitute_multiple_relids_context *context)
+substitute_phv_relids_walker(Node *node,
+							 substitute_phv_relids_context *context)
 {
 	if (node == NULL)
 		return false;
@@ -2895,6 +3179,8 @@ substitute_multiple_relids_walker(Node *node,
 									context->subrelids);
 			phv->phrels = bms_del_member(phv->phrels,
 										 context->varno);
+			/* Assert we haven't broken the PHV */
+			Assert(!bms_is_empty(phv->phrels));
 		}
 		/* fall through to examine children */
 	}
@@ -2905,7 +3191,7 @@ substitute_multiple_relids_walker(Node *node,
 
 		context->sublevels_up++;
 		result = query_tree_walker((Query *) node,
-								   substitute_multiple_relids_walker,
+								   substitute_phv_relids_walker,
 								   (void *) context, 0);
 		context->sublevels_up--;
 		return result;
@@ -2916,14 +3202,14 @@ substitute_multiple_relids_walker(Node *node,
 	Assert(!IsA(node, PlaceHolderInfo));
 	Assert(!IsA(node, MinMaxAggInfo));
 
-	return expression_tree_walker(node, substitute_multiple_relids_walker,
+	return expression_tree_walker(node, substitute_phv_relids_walker,
 								  (void *) context);
 }
 
 static void
-substitute_multiple_relids(Node *node, int varno, Relids subrelids)
+substitute_phv_relids(Node *node, int varno, Relids subrelids)
 {
-	substitute_multiple_relids_context context;
+	substitute_phv_relids_context context;
 
 	context.varno = varno;
 	context.sublevels_up = 0;
@@ -2933,7 +3219,7 @@ substitute_multiple_relids(Node *node, int varno, Relids subrelids)
 	 * Must be prepared to start with a Query or a bare expression tree.
 	 */
 	query_or_expression_tree_walker(node,
-									substitute_multiple_relids_walker,
+									substitute_phv_relids_walker,
 									(void *) &context,
 									0);
 }
@@ -2943,7 +3229,7 @@ substitute_multiple_relids(Node *node, int varno, Relids subrelids)
  *
  * When we pull up a subquery, any AppendRelInfo references to the subquery's
  * RT index have to be replaced by the substituted relid (and there had better
- * be only one).  We also need to apply substitute_multiple_relids to their
+ * be only one).  We also need to apply substitute_phv_relids to their
  * translated_vars lists, since those might contain PlaceHolderVars.
  *
  * We assume we may modify the AppendRelInfo nodes in-place.
@@ -2974,9 +3260,9 @@ fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
 			appinfo->child_relid = subvarno;
 		}
 
-		/* Also finish fixups for its translated vars */
-		substitute_multiple_relids((Node *) appinfo->translated_vars,
-								   varno, subrelids);
+		/* Also fix up any PHVs in its translated vars */
+		substitute_phv_relids((Node *) appinfo->translated_vars,
+							  varno, subrelids);
 	}
 }