Implement SQL-standard LATERAL subqueries.

This patch implements the standard syntax of LATERAL attached to a
sub-SELECT in FROM, and also allows LATERAL attached to a function in FROM,
since set-returning function calls are expected to be one of the principal
use-cases.

The main change here is a rewrite of the mechanism for keeping track of
which relations are visible for column references while the FROM clause is
being scanned.  The parser "namespace" lists are no longer lists of bare
RTEs, but are lists of ParseNamespaceItem structs, which carry an RTE
pointer as well as some visibility-controlling flags.  Aside from
supporting LATERAL correctly, this lets us get rid of the ancient hacks
that required rechecking subqueries and JOIN/ON and function-in-FROM
expressions for invalid references after they were initially parsed.
Invalid column references are now always correctly detected on sight.

In passing, remove assorted parser error checks that are now dead code by
virtue of our having gotten rid of add_missing_from, as well as some
comments that are obsolete for the same reason.  (It was mainly
add_missing_from that caused so much fudging here in the first place.)

The planner support for this feature is very minimal, and will be improved
in future patches.  It works well enough for testing purposes, though.

catversion bump forced due to new field in RangeTblEntry.

5 files changed, 210 insertions, 1 deletions

diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index c46d35df89e..c5b92582b4c 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2986,3 +2986,163 @@ SELECT * FROM
 (5 rows)
 
 rollback;
+--
+-- Test LATERAL
+--
+select unique2, x.*
+from tenk1 a, lateral (select * from int4_tbl b where f1 = a.unique1) x;
+ unique2 | f1 
+---------+----
+    9998 |  0
+(1 row)
+
+explain (costs off)
+  select unique2, x.*
+  from tenk1 a, lateral (select * from int4_tbl b where f1 = a.unique1) x;
+            QUERY PLAN            
+----------------------------------
+ Nested Loop
+   ->  Seq Scan on tenk1 a
+   ->  Seq Scan on int4_tbl b
+         Filter: (f1 = a.unique1)
+(4 rows)
+
+select unique2, x.*
+from int4_tbl x, lateral (select unique2 from tenk1 where f1 = unique1) ss;
+ unique2 | f1 
+---------+----
+    9998 |  0
+(1 row)
+
+explain (costs off)
+  select unique2, x.*
+  from int4_tbl x, lateral (select unique2 from tenk1 where f1 = unique1) ss;
+                  QUERY PLAN                   
+-----------------------------------------------
+ Nested Loop
+   ->  Seq Scan on int4_tbl x
+   ->  Index Scan using tenk1_unique1 on tenk1
+         Index Cond: (x.f1 = unique1)
+(4 rows)
+
+explain (costs off)
+  select unique2, x.*
+  from int4_tbl x cross join lateral (select unique2 from tenk1 where f1 = unique1) ss;
+                  QUERY PLAN                   
+-----------------------------------------------
+ Nested Loop
+   ->  Seq Scan on int4_tbl x
+   ->  Index Scan using tenk1_unique1 on tenk1
+         Index Cond: (x.f1 = unique1)
+(4 rows)
+
+select unique2, x.*
+from int4_tbl x left join lateral (select unique1, unique2 from tenk1 where f1 = unique1) ss on f1 = unique1;
+ unique2 |     f1      
+---------+-------------
+    9998 |           0
+         |      123456
+         |     -123456
+         |  2147483647
+         | -2147483647
+(5 rows)
+
+explain (costs off)
+  select unique2, x.*
+  from int4_tbl x left join lateral (select unique1, unique2 from tenk1 where f1 = unique1) ss on f1 = unique1;
+                     QUERY PLAN                      
+-----------------------------------------------------
+ Nested Loop Left Join
+   ->  Seq Scan on int4_tbl x
+   ->  Subquery Scan on ss
+         Filter: (x.f1 = ss.unique1)
+         ->  Index Scan using tenk1_unique1 on tenk1
+               Index Cond: (x.f1 = unique1)
+(6 rows)
+
+-- check scoping of lateral versus parent references
+-- the first of these should return int8_tbl.q2, the second int8_tbl.q1
+select *, (select r from (select q1 as q2) x, (select q2 as r) y) from int8_tbl;
+        q1        |        q2         |         r         
+------------------+-------------------+-------------------
+              123 |               456 |               456
+              123 |  4567890123456789 |  4567890123456789
+ 4567890123456789 |               123 |               123
+ 4567890123456789 |  4567890123456789 |  4567890123456789
+ 4567890123456789 | -4567890123456789 | -4567890123456789
+(5 rows)
+
+select *, (select r from (select q1 as q2) x, lateral (select q2 as r) y) from int8_tbl;
+        q1        |        q2         |        r         
+------------------+-------------------+------------------
+              123 |               456 |              123
+              123 |  4567890123456789 |              123
+ 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789
+(5 rows)
+
+-- lateral SRF
+select count(*) from tenk1 a, lateral generate_series(1,two) g;
+ count 
+-------
+  5000
+(1 row)
+
+explain (costs off)
+  select count(*) from tenk1 a, lateral generate_series(1,two) g;
+                   QUERY PLAN                   
+------------------------------------------------
+ Aggregate
+   ->  Nested Loop
+         ->  Seq Scan on tenk1 a
+         ->  Function Scan on generate_series g
+(4 rows)
+
+explain (costs off)
+  select count(*) from tenk1 a cross join lateral generate_series(1,two) g;
+                   QUERY PLAN                   
+------------------------------------------------
+ Aggregate
+   ->  Nested Loop
+         ->  Seq Scan on tenk1 a
+         ->  Function Scan on generate_series g
+(4 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
+LINE 1: select f1,g from int4_tbl a, generate_series(0, f1) g;
+                                                        ^
+HINT:  There is a column named "f1" in table "a", but it cannot be referenced from this part of the query.
+select f1,g from int4_tbl a, generate_series(0, a.f1) g;
+ERROR:  invalid reference to FROM-clause entry for table "a"
+LINE 1: select f1,g from int4_tbl a, generate_series(0, a.f1) g;
+                                                        ^
+HINT:  There is an entry for table "a", but it cannot be referenced from this part of the query.
+select f1,g from int4_tbl a cross join generate_series(0, f1) g;
+ERROR:  column "f1" does not exist
+LINE 1: ...ct f1,g from int4_tbl a cross join generate_series(0, f1) g;
+                                                                 ^
+HINT:  There is a column named "f1" in table "a", but it cannot be referenced from this part of the query.
+select f1,g from int4_tbl a cross join generate_series(0, a.f1) g;
+ERROR:  invalid reference to FROM-clause entry for table "a"
+LINE 1: ... f1,g from int4_tbl a cross join generate_series(0, a.f1) g;
+                                                               ^
+HINT:  There is an entry for table "a", but it cannot be referenced from this part of the query.
+-- SQL:2008 says the left table is in scope but illegal to access here
+select f1,g from int4_tbl a right join lateral generate_series(0, a.f1) g on true;
+ERROR:  invalid reference to FROM-clause entry for table "a"
+LINE 1: ... int4_tbl a right join lateral generate_series(0, a.f1) g on...
+                                                             ^
+DETAIL:  The combining JOIN type must be INNER or LEFT for a LATERAL reference.
+select f1,g from int4_tbl a full join lateral generate_series(0, a.f1) g on true;
+ERROR:  invalid reference to FROM-clause entry for table "a"
+LINE 1: ...m int4_tbl a full join lateral generate_series(0, a.f1) g on...
+                                                             ^
+DETAIL:  The combining JOIN type must be INNER or LEFT for a LATERAL reference.
+-- LATERAL can be used to put an aggregate into the FROM clause of its query
+select 1 from tenk1 a, lateral (select max(a.unique1) from int4_tbl b) ss;
+ERROR:  aggregates not allowed in FROM clause
+LINE 1: select 1 from tenk1 a, lateral (select max(a.unique1) from i...
+                                               ^
diff --git a/src/test/regress/expected/rangefuncs.out b/src/test/regress/expected/rangefuncs.out
index 6710b9c15ed..0fe8ca4c4e9 100644
--- a/src/test/regress/expected/rangefuncs.out
+++ b/src/test/regress/expected/rangefuncs.out
@@ -21,9 +21,10 @@ INSERT INTO foo2 VALUES(1, 111);
 CREATE FUNCTION foot(int) returns setof foo2 as 'SELECT * FROM foo2 WHERE fooid = $1;' LANGUAGE SQL;
 -- supposed to fail with ERROR
 select * from foo2, foot(foo2.fooid) z where foo2.f2 = z.f2;
-ERROR:  function expression in FROM cannot refer to other relations of same query level
+ERROR:  invalid reference to FROM-clause entry for table "foo2"
 LINE 1: select * from foo2, foot(foo2.fooid) z where foo2.f2 = z.f2;
                                  ^
+HINT:  There is an entry for table "foo2", but it cannot be referenced from this part of the query.
 -- function in subselect
 select * from foo2 where f2 in (select f2 from foot(foo2.fooid) z where z.fooid = foo2.fooid) ORDER BY 1,2;
  fooid | f2  
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out
index f07f39534a5..b041550f006 100644
--- a/src/test/regress/expected/rules.out
+++ b/src/test/regress/expected/rules.out
@@ -1190,6 +1190,7 @@ do instead insert into foo2 values (f1);
 ERROR:  column "f1" does not exist
 LINE 2: do instead insert into foo2 values (f1);
                                             ^
+HINT:  There is a column named "f1" in table "old", but it cannot be referenced from this part of the query.
 -- this is the correct way:
 create rule foorule as on insert to foo where f1 < 100
 do instead insert into foo2 values (new.f1);
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
index 14028314e8e..f78218822f5 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -412,6 +412,7 @@ SELECT q1 FROM int8_tbl EXCEPT SELECT q2 FROM int8_tbl ORDER BY q2 LIMIT 1;
 ERROR:  column "q2" does not exist
 LINE 1: ... int8_tbl EXCEPT SELECT q2 FROM int8_tbl ORDER BY q2 LIMIT 1...
                                                              ^
+HINT:  There is a column named "q2" in table "*SELECT* 2", but it cannot be referenced from this part of the query.
 -- But this should work:
 SELECT q1 FROM int8_tbl EXCEPT (((SELECT q2 FROM int8_tbl ORDER BY q2 LIMIT 1)));
         q1        
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 8676e2f7610..5de98dc0a72 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -840,3 +840,49 @@ SELECT * FROM
   ON true;
 
 rollback;
+
+--
+-- Test LATERAL
+--
+
+select unique2, x.*
+from tenk1 a, lateral (select * from int4_tbl b where f1 = a.unique1) x;
+explain (costs off)
+  select unique2, x.*
+  from tenk1 a, lateral (select * from int4_tbl b where f1 = a.unique1) x;
+select unique2, x.*
+from int4_tbl x, lateral (select unique2 from tenk1 where f1 = unique1) ss;
+explain (costs off)
+  select unique2, x.*
+  from int4_tbl x, lateral (select unique2 from tenk1 where f1 = unique1) ss;
+explain (costs off)
+  select unique2, x.*
+  from int4_tbl x cross join lateral (select unique2 from tenk1 where f1 = unique1) ss;
+select unique2, x.*
+from int4_tbl x left join lateral (select unique1, unique2 from tenk1 where f1 = unique1) ss on f1 = unique1;
+explain (costs off)
+  select unique2, x.*
+  from int4_tbl x left join lateral (select unique1, unique2 from tenk1 where f1 = unique1) ss on f1 = unique1;
+
+-- check scoping of lateral versus parent references
+-- the first of these should return int8_tbl.q2, the second int8_tbl.q1
+select *, (select r from (select q1 as q2) x, (select q2 as r) y) from int8_tbl;
+select *, (select r from (select q1 as q2) x, lateral (select q2 as r) y) from int8_tbl;
+
+-- lateral SRF
+select count(*) from tenk1 a, lateral generate_series(1,two) g;
+explain (costs off)
+  select count(*) from tenk1 a, lateral generate_series(1,two) g;
+explain (costs off)
+  select count(*) from tenk1 a cross join lateral generate_series(1,two) g;
+
+-- 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;
+select f1,g from int4_tbl a, generate_series(0, a.f1) g;
+select f1,g from int4_tbl a cross join generate_series(0, f1) g;
+select f1,g from int4_tbl a cross join generate_series(0, a.f1) g;
+-- SQL:2008 says the left table is in scope but illegal to access here
+select f1,g from int4_tbl a right join lateral generate_series(0, a.f1) g on true;
+select f1,g from int4_tbl a full join lateral generate_series(0, a.f1) g on true;
+-- LATERAL can be used to put an aggregate into the FROM clause of its query
+select 1 from tenk1 a, lateral (select max(a.unique1) from int4_tbl b) ss;