Fix up planner infrastructure to support LATERAL properly.

This patch takes care of a number of problems having to do with failure
to choose valid join orders and incorrect handling of lateral references
pulled up from subqueries.  Notable changes:

* Add a LateralJoinInfo data structure similar to SpecialJoinInfo, to
represent join ordering constraints created by lateral references.
(I first considered extending the SpecialJoinInfo structure, but the
semantics are different enough that a separate data structure seems
better.)  Extend join_is_legal() and related functions to prevent trying
to form unworkable joins, and to ensure that we will consider joins that
satisfy lateral references even if the joins would be clauseless.

* Fill in the infrastructure needed for the last few types of relation scan
paths to support parameterization.  We'd have wanted this eventually
anyway, but it is necessary now because a relation that gets pulled up out
of a UNION ALL subquery may acquire a reltargetlist containing lateral
references, meaning that its paths *have* to be parameterized whether or
not we have any code that can push join quals down into the scan.

* Compute data about lateral references early in query_planner(), and save
in RelOptInfo nodes, to avoid repetitive calculations later.

* Assorted corner-case bug fixes.

There's probably still some bugs left, but this is a lot closer to being
real than it was before.

2 files changed, 129 insertions, 10 deletions

diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 0856b457bfc..264d8966605 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -3167,16 +3167,15 @@ explain (costs off)
   select * from int8_tbl a,
     int8_tbl x left join lateral (select a.q1 from int4_tbl y) ss(z)
       on x.q2 = ss.z;
-                QUERY PLAN                
-------------------------------------------
- Nested Loop Left Join
-   Join Filter: (x.q2 = ($0))
-   ->  Nested Loop
-         ->  Seq Scan on int8_tbl a
-         ->  Materialize
-               ->  Seq Scan on int8_tbl x
-   ->  Seq Scan on int4_tbl y
-(7 rows)
+             QUERY PLAN             
+------------------------------------
+ Nested Loop
+   ->  Seq Scan on int8_tbl a
+   ->  Nested Loop Left Join
+         Join Filter: (x.q2 = ($0))
+         ->  Seq Scan on int8_tbl x
+         ->  Seq Scan on int4_tbl y
+(6 rows)
 
 select * from int8_tbl a,
   int8_tbl x left join lateral (select a.q1 from int4_tbl y) ss(z)
@@ -3336,6 +3335,109 @@ select * from
  4567890123456789 | -4567890123456789 |                  |                   | 4567890123456789 |                  |                  
 (10 rows)
 
+select x.* from
+  int8_tbl x left join (select q1,coalesce(q2,0) q2 from int8_tbl) y on x.q2 = y.q1,
+  lateral (select x.q1,y.q1,y.q2) v(xq1,yq1,yq2);
+        q1        |        q2         
+------------------+-------------------
+              123 |               456
+              123 |  4567890123456789
+              123 |  4567890123456789
+              123 |  4567890123456789
+ 4567890123456789 |               123
+ 4567890123456789 |               123
+ 4567890123456789 |  4567890123456789
+ 4567890123456789 |  4567890123456789
+ 4567890123456789 |  4567890123456789
+ 4567890123456789 | -4567890123456789
+(10 rows)
+
+select v.* from
+  (int8_tbl x left join (select q1,coalesce(q2,0) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 union all select x.q2,y.q2) v(vx,vy);
+        vx         |        vy         
+-------------------+-------------------
+               123 |                  
+               456 |                  
+               123 |  4567890123456789
+  4567890123456789 | -4567890123456789
+               123 |  4567890123456789
+  4567890123456789 |  4567890123456789
+               123 |  4567890123456789
+  4567890123456789 |               123
+  4567890123456789 |               123
+               123 |  4567890123456789
+  4567890123456789 |               123
+               123 |               456
+  4567890123456789 |  4567890123456789
+  4567890123456789 | -4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |               123
+  4567890123456789 |                  
+ -4567890123456789 |                  
+(20 rows)
+
+select v.* from
+  (int8_tbl x left join (select q1,(select coalesce(q2,0)) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 union all select x.q2,y.q2) v(vx,vy);
+        vx         |        vy         
+-------------------+-------------------
+               123 |                  
+               456 |                  
+               123 |  4567890123456789
+  4567890123456789 | -4567890123456789
+               123 |  4567890123456789
+  4567890123456789 |  4567890123456789
+               123 |  4567890123456789
+  4567890123456789 |               123
+  4567890123456789 |               123
+               123 |  4567890123456789
+  4567890123456789 |               123
+               123 |               456
+  4567890123456789 |  4567890123456789
+  4567890123456789 | -4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |               123
+  4567890123456789 |                  
+ -4567890123456789 |                  
+(20 rows)
+
+create temp table dual();
+insert into dual default values;
+select v.* from
+  (int8_tbl x left join (select q1,(select coalesce(q2,0)) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 from dual union all select x.q2,y.q2 from dual) v(vx,vy);
+        vx         |        vy         
+-------------------+-------------------
+               123 |                  
+               456 |                  
+               123 |  4567890123456789
+  4567890123456789 |               123
+               123 |  4567890123456789
+  4567890123456789 |  4567890123456789
+               123 |  4567890123456789
+  4567890123456789 | -4567890123456789
+  4567890123456789 |               123
+               123 |               456
+  4567890123456789 |               123
+               123 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |               123
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 | -4567890123456789
+  4567890123456789 |                  
+ -4567890123456789 |                  
+(20 rows)
+
 -- test some error cases where LATERAL should have been used but wasn't
 select f1,g from int4_tbl a, generate_series(0, f1) g;
 ERROR:  column "f1" does not exist
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 3c8ed5027ef..24553045da1 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -916,6 +916,23 @@ select * from
 select * from
   int8_tbl x left join (select q1,coalesce(q2,0) q2 from int8_tbl) y on x.q2 = y.q1,
   lateral (select x.q1,y.q1,y.q2) v(xq1,yq1,yq2);
+select x.* from
+  int8_tbl x left join (select q1,coalesce(q2,0) q2 from int8_tbl) y on x.q2 = y.q1,
+  lateral (select x.q1,y.q1,y.q2) v(xq1,yq1,yq2);
+select v.* from
+  (int8_tbl x left join (select q1,coalesce(q2,0) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 union all select x.q2,y.q2) v(vx,vy);
+select v.* from
+  (int8_tbl x left join (select q1,(select coalesce(q2,0)) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 union all select x.q2,y.q2) v(vx,vy);
+create temp table dual();
+insert into dual default values;
+select v.* from
+  (int8_tbl x left join (select q1,(select coalesce(q2,0)) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 from dual union all select x.q2,y.q2 from dual) v(vx,vy);
 
 -- test some error cases where LATERAL should have been used but wasn't
 select f1,g from int4_tbl a, generate_series(0, f1) g;