Re: Errors "failed to construct the join relation" and "failed to build any 2-way joins"

I wrote:
> Will Leinweber <will@bitfission.com> writes:
>> On 12.1, fresh initdb the following query gives me the error
>> "ERROR:  failed to construct the join relation"

> Eyeing the plan produced by v11, I'm suspecting some oversight in
> the RTE_RESULT changes (4be058fe9); but I haven't actually bisected.

Yup: it's folding the join tree to the point where a PlaceHolderVar ends
up marked as to be evaluated by the same relation that uses it, and then
things go all pear-shaped.  Here's a proposed patch for that.

            regards, tom lane

diff --git a/src/backend/nodes/nodeFuncs.c b/src/backend/nodes/nodeFuncs.c
index 880b0ec..8c4cab6 100644
--- a/src/backend/nodes/nodeFuncs.c
+++ b/src/backend/nodes/nodeFuncs.c
@@ -2378,59 +2378,74 @@ range_table_walker(List *rtable,

     foreach(rt, rtable)
     {
-        RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt);
+        RangeTblEntry *rte = lfirst_node(RangeTblEntry, rt);

-        /*
-         * Walkers might need to examine the RTE node itself either before or
-         * after visiting its contents (or, conceivably, both).  Note that if
-         * you specify neither flag, the walker won't visit the RTE at all.
-         */
-        if (flags & QTW_EXAMINE_RTES_BEFORE)
-            if (walker(rte, context))
-                return true;
+        if (range_table_entry_walker(rte, walker, context, flags))
+            return true;
+    }
+    return false;
+}

-        switch (rte->rtekind)
-        {
-            case RTE_RELATION:
-                if (walker(rte->tablesample, context))
-                    return true;
-                break;
-            case RTE_SUBQUERY:
-                if (!(flags & QTW_IGNORE_RT_SUBQUERIES))
-                    if (walker(rte->subquery, context))
-                        return true;
-                break;
-            case RTE_JOIN:
-                if (!(flags & QTW_IGNORE_JOINALIASES))
-                    if (walker(rte->joinaliasvars, context))
-                        return true;
-                break;
-            case RTE_FUNCTION:
-                if (walker(rte->functions, context))
-                    return true;
-                break;
-            case RTE_TABLEFUNC:
-                if (walker(rte->tablefunc, context))
+/*
+ * Some callers even want to scan the expressions in individual RTEs.
+ */
+bool
+range_table_entry_walker(RangeTblEntry *rte,
+                         bool (*walker) (),
+                         void *context,
+                         int flags)
+{
+    /*
+     * Walkers might need to examine the RTE node itself either before or
+     * after visiting its contents (or, conceivably, both).  Note that if you
+     * specify neither flag, the walker won't visit the RTE at all.
+     */
+    if (flags & QTW_EXAMINE_RTES_BEFORE)
+        if (walker(rte, context))
+            return true;
+
+    switch (rte->rtekind)
+    {
+        case RTE_RELATION:
+            if (walker(rte->tablesample, context))
+                return true;
+            break;
+        case RTE_SUBQUERY:
+            if (!(flags & QTW_IGNORE_RT_SUBQUERIES))
+                if (walker(rte->subquery, context))
                     return true;
-                break;
-            case RTE_VALUES:
-                if (walker(rte->values_lists, context))
+            break;
+        case RTE_JOIN:
+            if (!(flags & QTW_IGNORE_JOINALIASES))
+                if (walker(rte->joinaliasvars, context))
                     return true;
-                break;
-            case RTE_CTE:
-            case RTE_NAMEDTUPLESTORE:
-            case RTE_RESULT:
-                /* nothing to do */
-                break;
-        }
+            break;
+        case RTE_FUNCTION:
+            if (walker(rte->functions, context))
+                return true;
+            break;
+        case RTE_TABLEFUNC:
+            if (walker(rte->tablefunc, context))
+                return true;
+            break;
+        case RTE_VALUES:
+            if (walker(rte->values_lists, context))
+                return true;
+            break;
+        case RTE_CTE:
+        case RTE_NAMEDTUPLESTORE:
+        case RTE_RESULT:
+            /* nothing to do */
+            break;
+    }

-        if (walker(rte->securityQuals, context))
+    if (walker(rte->securityQuals, context))
+        return true;
+
+    if (flags & QTW_EXAMINE_RTES_AFTER)
+        if (walker(rte, context))
             return true;

-        if (flags & QTW_EXAMINE_RTES_AFTER)
-            if (walker(rte, context))
-                return true;
-    }
     return false;
 }

diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index db25bcf..65782c3 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -121,6 +121,8 @@ 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 bool find_dependent_phvs_in_jointree(PlannerInfo *root,
+                                            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,
@@ -3035,12 +3037,14 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode)
             lfirst(cell) = child;

             /*
-             * 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 it's an RTE_RESULT with at least one sibling, and no sibling
+             * contains dependent PHVs, 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)
+                (varno = get_result_relid(root, child)) != 0 &&
+                !find_dependent_phvs_in_jointree(root, (Node *) f, varno))
             {
                 f->fromlist = foreach_delete_current(f->fromlist, cell);
                 result_relids = bms_add_member(result_relids, varno);
@@ -3091,8 +3095,16 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode)
                  * 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.
+                 *
+                 * However, we can't collapse if the surviving side contains
+                 * any PHVs that are currently marked as to be evaluated at
+                 * the RTE_RESULT rel; they'd end up being marked as to be
+                 * evaluated at their own rel, which doesn't work.  But only
+                 * the RHS could contain such references to the LHS, not vice
+                 * versa.
                  */
-                if ((varno = get_result_relid(root, j->larg)) != 0)
+                if ((varno = get_result_relid(root, j->larg)) != 0 &&
+                    !find_dependent_phvs_in_jointree(root, j->rarg, varno))
                 {
                     remove_result_refs(root, varno, j->rarg);
                     if (j->quals)
@@ -3121,6 +3133,8 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode)
                  * 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.
+                 * (Again, the LHS could not contain a lateral reference to
+                 * the RHS.)
                  *
                  * Otherwise, it's still true that each LHS row should be
                  * returned exactly once, and since the RHS returns no columns
@@ -3246,6 +3260,12 @@ remove_result_refs(PlannerInfo *root, int varno, Node *newjtloc)
 /*
  * find_dependent_phvs - are there any PlaceHolderVars whose relids are
  * exactly the given varno?
+ *
+ * find_dependent_phvs can be applied to the whole Query to see if there
+ * are any such PHVs anywhere.  Another use-case is to see if a subtree
+ * of the join tree contains such PHVs; but for that, we have to look not
+ * only at the join tree nodes themselves but at the referenced RTEs.
+ * For that, use find_dependent_phvs_in_jointree.
  */

 typedef struct
@@ -3308,6 +3328,47 @@ find_dependent_phvs(Node *node, int varno)
                                            0);
 }

+static bool
+find_dependent_phvs_in_jointree(PlannerInfo *root, Node *node, int varno)
+{
+    find_dependent_phvs_context context;
+    Relids        subrelids;
+    int            relid;
+
+    context.relids = bms_make_singleton(varno);
+    context.sublevels_up = 0;
+
+    /*
+     * See if the jointree itself contains references (in join quals)
+     */
+    if (find_dependent_phvs_walker(node, &context))
+        return true;
+
+    /*
+     * Otherwise, identify the set of referenced RTEs (we can ignore joins,
+     * since they should be flattened already, and their join alias lists no
+     * longer matter).
+     */
+    subrelids = get_relids_in_jointree(node, false);
+
+    /*
+     * ... and tediously check each RTE.
+     */
+    relid = -1;
+    while ((relid = bms_next_member(subrelids, relid)) >= 0)
+    {
+        RangeTblEntry *rte = rt_fetch(relid, root->parse->rtable);
+
+        if (range_table_entry_walker(rte,
+                                     find_dependent_phvs_walker,
+                                     (void *) &context,
+                                     0))
+            return true;
+    }
+
+    return false;
+}
+
 /*
  * substitute_phv_relids - adjust PlaceHolderVar relid sets after pulling up
  * a subquery or removing an RTE_RESULT jointree item
diff --git a/src/include/nodes/nodeFuncs.h b/src/include/nodes/nodeFuncs.h
index 4b5408f..1e55683 100644
--- a/src/include/nodes/nodeFuncs.h
+++ b/src/include/nodes/nodeFuncs.h
@@ -141,6 +141,9 @@ extern bool range_table_walker(List *rtable, bool (*walker) (),
 extern List *range_table_mutator(List *rtable, Node *(*mutator) (),
                                  void *context, int flags);

+extern bool range_table_entry_walker(RangeTblEntry *rte, bool (*walker) (),
+                                     void *context, int flags);
+
 extern bool query_or_expression_tree_walker(Node *node, bool (*walker) (),
                                             void *context, int flags);
 extern Node *query_or_expression_tree_mutator(Node *node, Node *(*mutator) (),
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 1a08e63..761376b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -3242,6 +3242,32 @@ where t1.unique2 < 42 and t1.stringu1 > t2.stringu2;
       11 | WFAAAA   |       3 | LKIAAA
 (1 row)

+-- Here's a variant that we can't fold too aggressively, though,
+-- or we end up with noplace to evaluate the lateral PHV
+explain (verbose, costs off)
+select * from
+  (select 1 as x) ss1 left join (select 2 as y) ss2 on (true),
+  lateral (select ss2.y as z limit 1) ss3;
+        QUERY PLAN
+---------------------------
+ Nested Loop
+   Output: 1, (2), ((2))
+   ->  Result
+         Output: 2
+   ->  Limit
+         Output: ((2))
+         ->  Result
+               Output: (2)
+(8 rows)
+
+select * from
+  (select 1 as x) ss1 left join (select 2 as y) ss2 on (true),
+  lateral (select ss2.y as z limit 1) ss3;
+ x | y | z
+---+---+---
+ 1 | 2 | 2
+(1 row)
+
 --
 -- test inlining of immutable functions
 --
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 57481d0..5fc6617 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1018,6 +1018,16 @@ select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from
   on (subq1.y1 = t2.unique1)
 where t1.unique2 < 42 and t1.stringu1 > t2.stringu2;

+-- Here's a variant that we can't fold too aggressively, though,
+-- or we end up with noplace to evaluate the lateral PHV
+explain (verbose, costs off)
+select * from
+  (select 1 as x) ss1 left join (select 2 as y) ss2 on (true),
+  lateral (select ss2.y as z limit 1) ss3;
+select * from
+  (select 1 as x) ss1 left join (select 2 as y) ss2 on (true),
+  lateral (select ss2.y as z limit 1) ss3;
+
 --
 -- test inlining of immutable functions
 --