Thread: [sqlsmith] Planner error on lateral joins

Hi,

testing with sqlsmith on master at 3df51ca8b3 produced one instance of
the following error:

    ERROR:  failed to build any 6-way joins

I can reproduce it on a fresh regression database with the query below.
These were last logged in 2015.  Back then, it resulted in this commit:

    http://git.postgresql.org/pg/commitdiff/cfe30a72fa80528997357cb0780412736767e8c4

regards,
Andreas

select * from
  (select sample_1.a as c0
      from fkpart5.fk2 as sample_1) as subq_0,
  lateral (select  1
      from
 (select
  subq_0.c0 as c3,
  subq_5.c0 as c7,
  sample_2.b as c9
       from
  public.brin_test as sample_2,
  lateral (select
        subq_3.c1 as c0
      from
        fkpart5.pk3 as sample_3,
        lateral (select
       sample_2.a as c0,
       sample_3.a as c1
     from
       public.rtest_interface as ref_0
     ) as subq_1,
        lateral (select
       subq_1.c1 as c1
     from
       public.alter_table_under_transition_tables as ref_1
     ) as subq_3
      ) as subq_5) as subq_6
   right join public.gtest30_1 as sample_6
   on (true)
      where subq_6.c7 = subq_6.c3) as subq_7;

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.

            regards, tom lane

select * from
  (select sample_1.f1 as c0
      from int4_tbl as sample_1) as subq_0,
  lateral (select  1
      from
 (select
  subq_0.c0 as c3,
  subq_5.c0 as c7,
  sample_2.q2 as c9
       from
  int8_tbl as sample_2,
  lateral (select
        subq_3.c1 as c0
      from
        int4_tbl as sample_3,
        lateral (select
       sample_2.q1 as c0,
       sample_3.f1 as c1
     from
       public.rtest_interface as ref_0
     ) as subq_1,
        lateral (select
       subq_1.c1 as c1
     from
       int4_tbl as ref_1
     ) as subq_3
      ) as subq_5) as subq_6
   right join int4_tbl as sample_6
   on (true)
      where subq_6.c7 = subq_6.c3) as subq_7;

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);
         }
     }
 }