Re: [sqlsmith] Planner error on lateral joins - Mailing list pgsql-hackers

I wrote:
> Andreas Seltenreich <seltenreich@gmx.de> writes:
>> testing with sqlsmith on master at 3df51ca8b3 produced one instance of
>> the following error:
>> ERROR:  failed to build any 6-way joins

> Thanks for the test case!  The attached modification to use only
> longstanding test tables fails back to 9.5, but succeeds in 9.4.
> I've not tried to bisect yet.

Seems to be a missed consideration in add_placeholders_to_joinrel.
The attached fixes it for me.

            regards, tom lane

diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index 6abdc0299b..d05ea14234 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -404,8 +404,10 @@ add_placeholders_to_base_rels(PlannerInfo *root)
  *        and if they contain lateral references, add those references to the
  *        joinrel's direct_lateral_relids.
  *
- * A join rel should emit a PlaceHolderVar if (a) the PHV is needed above
- * this join level and (b) the PHV can be computed at or below this level.
+ * A join rel should emit a PlaceHolderVar if (a) the PHV can be computed
+ * at or below this level and (b) the PHV is needed above this join level.
+ * However, condition (a) is sufficient to add to direct_lateral_relids,
+ * as explained below.
  */
 void
 add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
@@ -418,11 +420,11 @@ add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
     {
         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);

-        /* Is it still needed above this joinrel? */
-        if (bms_nonempty_difference(phinfo->ph_needed, relids))
+        /* Is it computable here? */
+        if (bms_is_subset(phinfo->ph_eval_at, relids))
         {
-            /* Is it computable here? */
-            if (bms_is_subset(phinfo->ph_eval_at, relids))
+            /* Is it still needed above this joinrel? */
+            if (bms_nonempty_difference(phinfo->ph_needed, relids))
             {
                 /* Yup, add it to the output */
                 joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
@@ -450,12 +452,26 @@ add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
                     joinrel->reltarget->cost.startup += cost.startup;
                     joinrel->reltarget->cost.per_tuple += cost.per_tuple;
                 }
-
-                /* Adjust joinrel's direct_lateral_relids as needed */
-                joinrel->direct_lateral_relids =
-                    bms_add_members(joinrel->direct_lateral_relids,
-                                    phinfo->ph_lateral);
             }
+
+            /*
+             * Also adjust joinrel's direct_lateral_relids to include the
+             * PHV's source rel(s).  We must do this even if we're not
+             * actually going to emit the PHV, otherwise join_is_legal will
+             * reject valid join orderings.  (In principle maybe we could
+             * instead remove the joinrel's lateral_relids dependency; but
+             * that's complicated to get right, and cases where we're not
+             * going to emit the PHV are too rare to justify the work.)
+             *
+             * In principle we should only do this if the join doesn't yet
+             * include the PHV's source rel(s).  But our caller
+             * build_join_rel() will clean things up by removing the join's
+             * own relids from its direct_lateral_relids, so we needn't
+             * account for that here.
+             */
+            joinrel->direct_lateral_relids =
+                bms_add_members(joinrel->direct_lateral_relids,
+                                phinfo->ph_lateral);
         }
     }
 }