Re: BUG #18953: Planner fails to build plan for complex query with LATERAL references - Mailing list pgsql-bugs

Richard Guo <guofenglinux@gmail.com> writes:
> I think we should avoid adding the PHV to the outer subplan's tlist if
> there is already an equivalent one there.  Ideally, we should fix this
> by making the PHVs in the NestLoopParam expressions have accurate
> nullingrels, but that doesn't seem like a trivial task.  As a band-aid
> fix, I think we could match on phid only in create_nestloop_plan()
> when checking whether the PHV is already available, like below.

I don't love this solution, because it's not clear that it'd avoid
a failure if there *isn't* an equivalent PHV already there.
Also it seems like it's piling another level of band-aid on what's
already a mess.

I experimented with making identify_current_nestloop_params compute
the correct nullingrels "from scratch", and that seems to resolve
the problem.  Now this is arguably not an ideal answer, because the
point of the setrefs.c cross-checks is to verify that we placed
Vars and PHVs at safe places to calculate correctly-nulled values,
and we're basically defeating those checks.  But this feels like
the least crufty answer, and it's also confining the cruft to the
right place: if we can think of a more principled answer for
computing the nestloop params' nullingrels, we just have to fix
identify_current_nestloop_params to do that instead.

BTW, having done this it seems like we could get rid of the use
of NRM_SUBSET and instead use NRM_EQUAL for processing nestloop
params in setrefs.c.  I tried that, and it gets through check-world,
but I'm too chicken to risk such a change in v18 at this stage.
I propose applying the attached for now and then removing NRM_SUBSET
when v19 opens for business.

For ease of review, 0001 attached is the same patch as before and
then 0002 is the new stuff.  I'd squash them to one patch for
commit, though.

            regards, tom lane

diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 8baf36ba4b7..8011c3c4bc8 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -4344,6 +4344,7 @@ create_nestloop_plan(PlannerInfo *root,
     NestLoop   *join_plan;
     Plan       *outer_plan;
     Plan       *inner_plan;
+    Relids        outerrelids;
     List       *tlist = build_path_tlist(root, &best_path->jpath.path);
     List       *joinrestrictclauses = best_path->jpath.joinrestrictinfo;
     List       *joinclauses;
@@ -4374,8 +4375,8 @@ create_nestloop_plan(PlannerInfo *root,
     outer_plan = create_plan_recurse(root, best_path->jpath.outerjoinpath, 0);

     /* For a nestloop, include outer relids in curOuterRels for inner side */
-    root->curOuterRels = bms_union(root->curOuterRels,
-                                   best_path->jpath.outerjoinpath->parent->relids);
+    outerrelids = best_path->jpath.outerjoinpath->parent->relids;
+    root->curOuterRels = bms_union(root->curOuterRels, outerrelids);

     inner_plan = create_plan_recurse(root, best_path->jpath.innerjoinpath, 0);

@@ -4415,7 +4416,8 @@ create_nestloop_plan(PlannerInfo *root,
      * node, and remove them from root->curOuterParams.
      */
     nestParams = identify_current_nestloop_params(root,
-                                                  best_path->jpath.outerjoinpath);
+                                                  outerrelids,
+                                                  PATH_REQ_OUTER((Path *) best_path));

     /*
      * While nestloop parameters that are Vars had better be available from
@@ -4423,32 +4425,77 @@ create_nestloop_plan(PlannerInfo *root,
      * that are PHVs won't be.  In such cases we must add them to the
      * outer_plan's tlist, since the executor's NestLoopParam machinery
      * requires the params to be simple outer-Var references to that tlist.
+     * (This is cheating a little bit, because the outer path's required-outer
+     * relids might not be enough to allow evaluating such a PHV.  But in
+     * practice, if we could have evaluated the PHV at the nestloop node, we
+     * can do so in the outer plan too.)
      */
     outer_tlist = outer_plan->targetlist;
     outer_parallel_safe = outer_plan->parallel_safe;
     foreach(lc, nestParams)
     {
         NestLoopParam *nlp = (NestLoopParam *) lfirst(lc);
+        PlaceHolderVar *phv;
         TargetEntry *tle;

         if (IsA(nlp->paramval, Var))
             continue;            /* nothing to do for simple Vars */
-        if (tlist_member((Expr *) nlp->paramval, outer_tlist))
+        /* Otherwise it must be a PHV */
+        phv = castNode(PlaceHolderVar, nlp->paramval);
+
+        if (tlist_member((Expr *) phv, outer_tlist))
             continue;            /* already available */

+        /*
+         * Deal with an even edgier edge case: if the PHV was pulled up out of
+         * a subquery and it contains a subquery that was originally pushed
+         * down from this query level, then that will still be represented as
+         * a SubLink, because SS_process_sublinks won't recurse into outer
+         * PHVs, so it didn't get transformed during expression preprocessing
+         * in the subquery.  We need a version of the PHV that has a SubPlan,
+         * which we can get from the current query level's placeholder_list.
+         * This is quite grotty of course, but dealing with it earlier in the
+         * handling of subplan params would be just as grotty, and it might
+         * end up being a waste of cycles if we don't decide to treat the PHV
+         * as a NestLoopParam.  (Perhaps that whole mechanism should be
+         * redesigned someday, but today is not that day.)
+         *
+         * It's not important to change the NestLoopParam tree, because the
+         * two PHVs will still be considered equal() and thus setrefs.c will
+         * still be able to replace the NestLoopParam's PHV with an outer-plan
+         * reference Var.
+         *
+         * In either case, make sure we have a copy of the PHV to put into
+         * outer_tlist, just for safety.
+         */
+        if (root->parse->hasSubLinks)
+        {
+            PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
+            PlaceHolderVar *newphv = copyObject(phinfo->ph_var);
+
+            /*
+             * The ph_var will have empty nullingrels, but we need the right
+             * nullingrels in the PHV we push into outer_tlist.  Other fields
+             * should match already.
+             */
+            newphv->phnullingrels = phv->phnullingrels;
+            phv = newphv;
+        }
+        else
+            phv = copyObject(phv);
+
         /* Make a shallow copy of outer_tlist, if we didn't already */
         if (outer_tlist == outer_plan->targetlist)
             outer_tlist = list_copy(outer_tlist);
         /* ... and add the needed expression */
-        tle = makeTargetEntry((Expr *) copyObject(nlp->paramval),
+        tle = makeTargetEntry((Expr *) phv,
                               list_length(outer_tlist) + 1,
                               NULL,
                               true);
         outer_tlist = lappend(outer_tlist, tle);
         /* ... and track whether tlist is (still) parallel-safe */
         if (outer_parallel_safe)
-            outer_parallel_safe = is_parallel_safe(root,
-                                                   (Node *) nlp->paramval);
+            outer_parallel_safe = is_parallel_safe(root, (Node *) phv);
     }
     if (outer_tlist != outer_plan->targetlist)
         outer_plan = change_plan_targetlist(outer_plan, outer_tlist,
diff --git a/src/backend/optimizer/util/paramassign.c b/src/backend/optimizer/util/paramassign.c
index 9836abf9479..5403ae89eab 100644
--- a/src/backend/optimizer/util/paramassign.c
+++ b/src/backend/optimizer/util/paramassign.c
@@ -599,9 +599,10 @@ process_subquery_nestloop_params(PlannerInfo *root, List *subplan_params)
 }

 /*
- * Identify any NestLoopParams that should be supplied by a NestLoop plan
- * node with the specified lefthand input path.  Remove them from the active
- * root->curOuterParams list and return them as the result list.
+ * Identify any NestLoopParams that should be supplied by a NestLoop
+ * plan node with the specified lefthand rels and required-outer rels.
+ * Remove them from the active root->curOuterParams list and return
+ * them as the result list.
  *
  * XXX Here we also hack up the returned Vars and PHVs so that they do not
  * contain nullingrel sets exceeding what is available from the outer side.
@@ -626,11 +627,11 @@ process_subquery_nestloop_params(PlannerInfo *root, List *subplan_params)
  * subquery, which'd be unduly expensive.
  */
 List *
-identify_current_nestloop_params(PlannerInfo *root, Path *leftpath)
+identify_current_nestloop_params(PlannerInfo *root,
+                                 Relids leftrelids,
+                                 Relids outerrelids)
 {
     List       *result;
-    Relids        leftrelids = leftpath->parent->relids;
-    Relids        outerrelids = PATH_REQ_OUTER(leftpath);
     Relids        allleftrelids;
     ListCell   *cell;

diff --git a/src/include/optimizer/paramassign.h b/src/include/optimizer/paramassign.h
index d30d20de299..bbf7214289b 100644
--- a/src/include/optimizer/paramassign.h
+++ b/src/include/optimizer/paramassign.h
@@ -30,7 +30,8 @@ extern Param *replace_nestloop_param_placeholdervar(PlannerInfo *root,
 extern void process_subquery_nestloop_params(PlannerInfo *root,
                                              List *subplan_params);
 extern List *identify_current_nestloop_params(PlannerInfo *root,
-                                              Path *leftpath);
+                                              Relids leftrelids,
+                                              Relids outerrelids);
 extern Param *generate_new_exec_param(PlannerInfo *root, Oid paramtype,
                                       int32 paramtypmod, Oid paramcollation);
 extern int    assign_special_exec_param(PlannerInfo *root);
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index c292f04fdba..6266820b69a 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4119,6 +4119,91 @@ select * from int8_tbl t1
 (16 rows)

 rollback;
+-- PHVs containing SubLinks are quite tricky to get right
+explain (verbose, costs off)
+select *
+from int8_tbl i8
+  inner join
+    (select (select true) as x
+       from int4_tbl i4, lateral (select i4.f1 as y limit 1) ss1
+       where i4.f1 = 0) ss2 on true
+  right join (select false as z) ss3 on true,
+  lateral (select i8.q2 as q2l where x limit 1) ss4
+where i8.q2 = 123;
+                           QUERY PLAN
+----------------------------------------------------------------
+ Nested Loop
+   Output: i8.q1, i8.q2, (InitPlan 1).col1, false, (i8.q2)
+   InitPlan 1
+     ->  Result
+           Output: true
+   InitPlan 2
+     ->  Result
+           Output: true
+   ->  Seq Scan on public.int4_tbl i4
+         Output: i4.f1
+         Filter: (i4.f1 = 0)
+   ->  Nested Loop
+         Output: i8.q1, i8.q2, (i8.q2)
+         ->  Subquery Scan on ss1
+               Output: ss1.y, (InitPlan 1).col1
+               ->  Limit
+                     Output: NULL::integer
+                     ->  Result
+                           Output: NULL::integer
+         ->  Nested Loop
+               Output: i8.q1, i8.q2, (i8.q2)
+               ->  Seq Scan on public.int8_tbl i8
+                     Output: i8.q1, i8.q2
+                     Filter: (i8.q2 = 123)
+               ->  Limit
+                     Output: (i8.q2)
+                     ->  Result
+                           Output: i8.q2
+                           One-Time Filter: ((InitPlan 1).col1)
+(29 rows)
+
+explain (verbose, costs off)
+select *
+from int8_tbl i8
+  inner join
+    (select (select true) as x
+       from int4_tbl i4, lateral (select 1 as y limit 1) ss1
+       where i4.f1 = 0) ss2 on true
+  right join (select false as z) ss3 on true,
+  lateral (select i8.q2 as q2l where x limit 1) ss4
+where i8.q2 = 123;
+                           QUERY PLAN
+----------------------------------------------------------------
+ Nested Loop
+   Output: i8.q1, i8.q2, (InitPlan 1).col1, false, (i8.q2)
+   InitPlan 1
+     ->  Result
+           Output: true
+   InitPlan 2
+     ->  Result
+           Output: true
+   ->  Limit
+         Output: NULL::integer
+         ->  Result
+               Output: NULL::integer
+   ->  Nested Loop
+         Output: i8.q1, i8.q2, (i8.q2)
+         ->  Seq Scan on public.int4_tbl i4
+               Output: i4.f1, (InitPlan 1).col1
+               Filter: (i4.f1 = 0)
+         ->  Nested Loop
+               Output: i8.q1, i8.q2, (i8.q2)
+               ->  Seq Scan on public.int8_tbl i8
+                     Output: i8.q1, i8.q2
+                     Filter: (i8.q2 = 123)
+               ->  Limit
+                     Output: (i8.q2)
+                     ->  Result
+                           Output: i8.q2
+                           One-Time Filter: ((InitPlan 1).col1)
+(27 rows)
+
 -- Test proper handling of appendrel PHVs during useless-RTE removal
 explain (costs off)
 select * from
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 88d2204e447..6b7a26cf295 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1361,6 +1361,29 @@ select * from int8_tbl t1
   on true;
 rollback;

+-- PHVs containing SubLinks are quite tricky to get right
+explain (verbose, costs off)
+select *
+from int8_tbl i8
+  inner join
+    (select (select true) as x
+       from int4_tbl i4, lateral (select i4.f1 as y limit 1) ss1
+       where i4.f1 = 0) ss2 on true
+  right join (select false as z) ss3 on true,
+  lateral (select i8.q2 as q2l where x limit 1) ss4
+where i8.q2 = 123;
+
+explain (verbose, costs off)
+select *
+from int8_tbl i8
+  inner join
+    (select (select true) as x
+       from int4_tbl i4, lateral (select 1 as y limit 1) ss1
+       where i4.f1 = 0) ss2 on true
+  right join (select false as z) ss3 on true,
+  lateral (select i8.q2 as q2l where x limit 1) ss4
+where i8.q2 = 123;
+
 -- Test proper handling of appendrel PHVs during useless-RTE removal
 explain (costs off)
 select * from
diff --git a/src/backend/optimizer/util/paramassign.c b/src/backend/optimizer/util/paramassign.c
index 5403ae89eab..b1128d62371 100644
--- a/src/backend/optimizer/util/paramassign.c
+++ b/src/backend/optimizer/util/paramassign.c
@@ -604,25 +604,17 @@ process_subquery_nestloop_params(PlannerInfo *root, List *subplan_params)
  * Remove them from the active root->curOuterParams list and return
  * them as the result list.
  *
- * XXX Here we also hack up the returned Vars and PHVs so that they do not
- * contain nullingrel sets exceeding what is available from the outer side.
- * This is needed if we have applied outer join identity 3,
- *        (A leftjoin B on (Pab)) leftjoin C on (Pb*c)
- *        = A leftjoin (B leftjoin C on (Pbc)) on (Pab)
- * and C contains lateral references to B.  It's still safe to apply the
- * identity, but the parser will have created those references in the form
- * "b*" (i.e., with varnullingrels listing the A/B join), while what we will
- * have available from the nestloop's outer side is just "b".  We deal with
- * that here by stripping the nullingrels down to what is available from the
- * outer side according to leftrelids.
- *
- * That fixes matters for the case of forward application of identity 3.
- * If the identity was applied in the reverse direction, we will have
- * parameter Vars containing too few nullingrel bits rather than too many.
- * Currently, that causes no problems because setrefs.c applies only a
- * subset check to nullingrels in NestLoopParams, but we'd have to work
- * harder if we ever want to tighten that check.  This is all pretty annoying
- * because it greatly weakens setrefs.c's cross-check, but the alternative
+ * Vars and PHVs appearing in the result list must have nullingrel sets
+ * that could validly appear in the lefthand rel's output.  Ordinarily that
+ * would be true already, but if we have applied outer join identity 3,
+ * there could be more or fewer nullingrel bits in the nodes appearing in
+ * curOuterParams than are in the nominal leftrelids.  We deal with that by
+ * forcing their nullingrel sets to include exactly the outer-join relids
+ * that appear in leftrelids and can null the respective Var or PHV.
+ * This fix is a bit ad-hoc and intellectually unsatisfactory, because it's
+ * essentially jumping to the conclusion that we've placed evaluation of
+ * the nestloop parameters correctly, and thus it defeats the intent of the
+ * subsequent nullingrel cross-checks in setrefs.c.  But the alternative
  * seems to be to generate multiple versions of each laterally-parameterized
  * subquery, which'd be unduly expensive.
  */
@@ -662,25 +654,28 @@ identify_current_nestloop_params(PlannerInfo *root,
             bms_is_member(nlp->paramval->varno, leftrelids))
         {
             Var           *var = (Var *) nlp->paramval;
+            RelOptInfo *rel = root->simple_rel_array[var->varno];

             root->curOuterParams = foreach_delete_current(root->curOuterParams,
                                                           cell);
-            var->varnullingrels = bms_intersect(var->varnullingrels,
+            var->varnullingrels = bms_intersect(rel->nulling_relids,
                                                 leftrelids);
             result = lappend(result, nlp);
         }
         else if (IsA(nlp->paramval, PlaceHolderVar))
         {
             PlaceHolderVar *phv = (PlaceHolderVar *) nlp->paramval;
-            Relids        eval_at = find_placeholder_info(root, phv)->ph_eval_at;
+            PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
+            Relids        eval_at = phinfo->ph_eval_at;

             if (bms_is_subset(eval_at, allleftrelids) &&
                 bms_overlap(eval_at, leftrelids))
             {
                 root->curOuterParams = foreach_delete_current(root->curOuterParams,
                                                               cell);
-                phv->phnullingrels = bms_intersect(phv->phnullingrels,
-                                                   leftrelids);
+                phv->phnullingrels =
+                    bms_intersect(get_placeholder_nulling_relids(root, phinfo),
+                                  leftrelids);
                 result = lappend(result, nlp);
             }
         }
diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index 41a4c81e94a..e1cd00a72fb 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -545,3 +545,43 @@ contain_placeholder_references_walker(Node *node,
     return expression_tree_walker(node, contain_placeholder_references_walker,
                                   context);
 }
+
+/*
+ * Compute the set of outer-join relids that can null a placeholder.
+ *
+ * This is analogous to RelOptInfo.nulling_relids for Vars, but we compute it
+ * on-the-fly rather than saving it somewhere.  Currently the value is needed
+ * at most once per query, so there's little value in doing otherwise.  If it
+ * ever gains more widespread use, perhaps we should cache the result in
+ * PlaceHolderInfo.
+ */
+Relids
+get_placeholder_nulling_relids(PlannerInfo *root, PlaceHolderInfo *phinfo)
+{
+    Relids        result = NULL;
+    int            relid = -1;
+
+    /*
+     * Form the union of all potential nulling OJs for each baserel included
+     * in ph_eval_at.
+     */
+    while ((relid = bms_next_member(phinfo->ph_eval_at, relid)) > 0)
+    {
+        RelOptInfo *rel = root->simple_rel_array[relid];
+
+        /* ignore the RTE_GROUP RTE */
+        if (relid == root->group_rtindex)
+            continue;
+
+        if (rel == NULL)        /* must be an outer join */
+        {
+            Assert(bms_is_member(relid, root->outer_join_rels));
+            continue;
+        }
+        result = bms_add_members(result, rel->nulling_relids);
+    }
+
+    /* Now remove any OJs already included in ph_eval_at, and we're done. */
+    result = bms_del_members(result, phinfo->ph_eval_at);
+    return result;
+}
diff --git a/src/include/optimizer/placeholder.h b/src/include/optimizer/placeholder.h
index d351045e2e0..db92d8861ba 100644
--- a/src/include/optimizer/placeholder.h
+++ b/src/include/optimizer/placeholder.h
@@ -30,5 +30,7 @@ extern void add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
                                         SpecialJoinInfo *sjinfo);
 extern bool contain_placeholder_references_to(PlannerInfo *root, Node *clause,
                                               int relid);
+extern Relids get_placeholder_nulling_relids(PlannerInfo *root,
+                                             PlaceHolderInfo *phinfo);

 #endif                            /* PLACEHOLDER_H */
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 6266820b69a..67793292054 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4118,6 +4118,44 @@ select * from int8_tbl t1
                            Output: NULL::bigint, NULL::bigint
 (16 rows)

+rollback;
+-- A related failure
+begin;
+create temp table t(i int primary key);
+explain (verbose, costs off)
+select * from t t1
+    left join (select 1 as x, * from t t2(i2)) t2ss on t1.i = t2ss.i2
+    left join t t3(i3) on false
+    left join t t4(i4) on t4.i4 > t2ss.x;
+                        QUERY PLAN
+----------------------------------------------------------
+ Nested Loop Left Join
+   Output: t1.i, (1), t2.i2, i3, t4.i4
+   ->  Nested Loop Left Join
+         Output: t1.i, t2.i2, (1), i3
+         Join Filter: false
+         ->  Hash Left Join
+               Output: t1.i, t2.i2, (1)
+               Inner Unique: true
+               Hash Cond: (t1.i = t2.i2)
+               ->  Seq Scan on pg_temp.t t1
+                     Output: t1.i
+               ->  Hash
+                     Output: t2.i2, (1)
+                     ->  Seq Scan on pg_temp.t t2
+                           Output: t2.i2, 1
+         ->  Result
+               Output: i3
+               One-Time Filter: false
+   ->  Memoize
+         Output: t4.i4
+         Cache Key: (1)
+         Cache Mode: binary
+         ->  Index Only Scan using t_pkey on pg_temp.t t4
+               Output: t4.i4
+               Index Cond: (t4.i4 > (1))
+(25 rows)
+
 rollback;
 -- PHVs containing SubLinks are quite tricky to get right
 explain (verbose, costs off)
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 6b7a26cf295..21747841808 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1361,6 +1361,16 @@ select * from int8_tbl t1
   on true;
 rollback;

+-- A related failure
+begin;
+create temp table t(i int primary key);
+explain (verbose, costs off)
+select * from t t1
+    left join (select 1 as x, * from t t2(i2)) t2ss on t1.i = t2ss.i2
+    left join t t3(i3) on false
+    left join t t4(i4) on t4.i4 > t2ss.x;
+rollback;
+
 -- PHVs containing SubLinks are quite tricky to get right
 explain (verbose, costs off)
 select *