--
-- Tests for common table expressions (WITH query, ... SELECT ...)
--
-- Basic WITH
WITH q1(x,y) AS (SELECT 1,2)
SELECT * FROM q1, q1 AS q2;
 x | y | x | y 
---+---+---+---
 1 | 2 | 1 | 2
(1 row)

-- Multiple uses are evaluated only once
SELECT count(*) FROM (
  WITH q1(x) AS (SELECT random() FROM generate_series(1, 5))
    SELECT * FROM q1
  UNION
    SELECT * FROM q1
) ss;
 count 
-------
     5
(1 row)

-- WITH RECURSIVE
-- sum of 1..100
WITH RECURSIVE t(n) AS (
    VALUES (1)
UNION ALL
    SELECT n+1 FROM t WHERE n < 100
)
SELECT sum(n) FROM t;
 sum  
------
 5050
(1 row)

WITH RECURSIVE t(n) AS (
    SELECT (VALUES(1))
UNION ALL
    SELECT n+1 FROM t WHERE n < 5
)
SELECT * FROM t;
 n 
---
 1
 2
 3
 4
 5
(5 rows)

-- UNION DISTINCT requires hashable type
WITH RECURSIVE t(n) AS (
    VALUES (1::money)
UNION
    SELECT n+1::money FROM t WHERE n < 100::money
)
SELECT sum(n) FROM t;
ERROR:  could not implement recursive UNION
DETAIL:  All column datatypes must be hashable.
-- recursive view
CREATE RECURSIVE VIEW nums (n) AS
    VALUES (1)
UNION ALL
    SELECT n+1 FROM nums WHERE n < 5;
SELECT * FROM nums;
 n 
---
 1
 2
 3
 4
 5
(5 rows)

CREATE OR REPLACE RECURSIVE VIEW nums (n) AS
    VALUES (1)
UNION ALL
    SELECT n+1 FROM nums WHERE n < 6;
SELECT * FROM nums;
 n 
---
 1
 2
 3
 4
 5
 6
(6 rows)

-- This is an infinite loop with UNION ALL, but not with UNION
WITH RECURSIVE t(n) AS (
    SELECT 1
UNION
    SELECT 10-n FROM t)
SELECT * FROM t;
 n 
---
 1
 9
(2 rows)

-- This'd be an infinite loop, but outside query reads only as much as needed
WITH RECURSIVE t(n) AS (
    VALUES (1)
UNION ALL
    SELECT n+1 FROM t)
SELECT * FROM t LIMIT 10;
 n  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
(10 rows)

-- UNION case should have same property
WITH RECURSIVE t(n) AS (
    SELECT 1
UNION
    SELECT n+1 FROM t)
SELECT * FROM t LIMIT 10;
 n  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
(10 rows)

-- Test behavior with an unknown-type literal in the WITH
WITH q AS (SELECT 'foo' AS x)
SELECT x, pg_typeof(x) FROM q;
  x  | pg_typeof 
-----+-----------
 foo | text
(1 row)

WITH RECURSIVE t(n) AS (
    SELECT 'foo'
UNION ALL
    SELECT n || ' bar' FROM t WHERE length(n) < 20
)
SELECT n, pg_typeof(n) FROM t;
            n            | pg_typeof 
-------------------------+-----------
 foo                     | text
 foo bar                 | text
 foo bar bar             | text
 foo bar bar bar         | text
 foo bar bar bar bar     | text
 foo bar bar bar bar bar | text
(6 rows)

-- In a perfect world, this would work and resolve the literal as int ...
-- but for now, we have to be content with resolving to text too soon.
WITH RECURSIVE t(n) AS (
    SELECT '7'
UNION ALL
    SELECT n+1 FROM t WHERE n < 10
)
SELECT n, pg_typeof(n) FROM t;
ERROR:  operator does not exist: text + integer
LINE 4:     SELECT n+1 FROM t WHERE n < 10
                    ^
HINT:  No operator matches the given name and argument types. You might need to add explicit type casts.
-- Deeply nested WITH caused a list-munging problem in v13
-- Detection of cross-references and self-references
WITH RECURSIVE w1(c1) AS
 (WITH w2(c2) AS
  (WITH w3(c3) AS
   (WITH w4(c4) AS
    (WITH w5(c5) AS
     (WITH RECURSIVE w6(c6) AS
      (WITH w6(c6) AS
       (WITH w8(c8) AS
        (SELECT 1)
        SELECT * FROM w8)
       SELECT * FROM w6)
      SELECT * FROM w6)
     SELECT * FROM w5)
    SELECT * FROM w4)
   SELECT * FROM w3)
  SELECT * FROM w2)
SELECT * FROM w1;
 c1 
----
  1
(1 row)

-- Detection of invalid self-references
WITH RECURSIVE outermost(x) AS (
 SELECT 1
 UNION (WITH innermost1 AS (
  SELECT 2
  UNION (WITH innermost2 AS (
   SELECT 3
   UNION (WITH innermost3 AS (
    SELECT 4
    UNION (WITH innermost4 AS (
     SELECT 5
     UNION (WITH innermost5 AS (
      SELECT 6
      UNION (WITH innermost6 AS
       (SELECT 7)
       SELECT * FROM innermost6))
      SELECT * FROM innermost5))
     SELECT * FROM innermost4))
    SELECT * FROM innermost3))
   SELECT * FROM innermost2))
  SELECT * FROM outermost
  UNION SELECT * FROM innermost1)
 )
 SELECT * FROM outermost ORDER BY 1;
 x 
---
 1
 2
 3
 4
 5
 6
 7
(7 rows)

--
-- Some examples with a tree
--
-- department structure represented here is as follows:
--
-- ROOT-+->A-+->B-+->C
--      |         |
--      |         +->D-+->F
--      +->E-+->G
CREATE TEMP TABLE department (
	id INTEGER PRIMARY KEY,  -- department ID
	parent_department INTEGER REFERENCES department, -- upper department ID
	name TEXT -- department name
);
INSERT INTO department VALUES (0, NULL, 'ROOT');
INSERT INTO department VALUES (1, 0, 'A');
INSERT INTO department VALUES (2, 1, 'B');
INSERT INTO department VALUES (3, 2, 'C');
INSERT INTO department VALUES (4, 2, 'D');
INSERT INTO department VALUES (5, 0, 'E');
INSERT INTO department VALUES (6, 4, 'F');
INSERT INTO department VALUES (7, 5, 'G');
-- extract all departments under 'A'. Result should be A, B, C, D and F
WITH RECURSIVE subdepartment AS
(
	-- non recursive term
	SELECT name as root_name, * FROM department WHERE name = 'A'
	UNION ALL
	-- recursive term
	SELECT sd.root_name, d.* FROM department AS d, subdepartment AS sd
		WHERE d.parent_department = sd.id
)
SELECT * FROM subdepartment ORDER BY name;
 root_name | id | parent_department | name 
-----------+----+-------------------+------
 A         |  1 |                 0 | A
 A         |  2 |                 1 | B
 A         |  3 |                 2 | C
 A         |  4 |                 2 | D
 A         |  6 |                 4 | F
(5 rows)

-- extract all departments under 'A' with "level" number
WITH RECURSIVE subdepartment(level, id, parent_department, name) AS
(
	-- non recursive term
	SELECT 1, * FROM department WHERE name = 'A'
	UNION ALL
	-- recursive term
	SELECT sd.level + 1, d.* FROM department AS d, subdepartment AS sd
		WHERE d.parent_department = sd.id
)
SELECT * FROM subdepartment ORDER BY name;
 level | id | parent_department | name 
-------+----+-------------------+------
     1 |  1 |                 0 | A
     2 |  2 |                 1 | B
     3 |  3 |                 2 | C
     3 |  4 |                 2 | D
     4 |  6 |                 4 | F
(5 rows)

-- extract all departments under 'A' with "level" number.
-- Only shows level 2 or more
WITH RECURSIVE subdepartment(level, id, parent_department, name) AS
(
	-- non recursive term
	SELECT 1, * FROM department WHERE name = 'A'
	UNION ALL
	-- recursive term
	SELECT sd.level + 1, d.* FROM department AS d, subdepartment AS sd
		WHERE d.parent_department = sd.id
)
SELECT * FROM subdepartment WHERE level >= 2 ORDER BY name;
 level | id | parent_department | name 
-------+----+-------------------+------
     2 |  2 |                 1 | B
     3 |  3 |                 2 | C
     3 |  4 |                 2 | D
     4 |  6 |                 4 | F
(4 rows)

-- "RECURSIVE" is ignored if the query has no self-reference
WITH RECURSIVE subdepartment AS
(
	-- note lack of recursive UNION structure
	SELECT * FROM department WHERE name = 'A'
)
SELECT * FROM subdepartment ORDER BY name;
 id | parent_department | name 
----+-------------------+------
  1 |                 0 | A
(1 row)

-- inside subqueries
SELECT count(*) FROM (
    WITH RECURSIVE t(n) AS (
        SELECT 1 UNION ALL SELECT n + 1 FROM t WHERE n < 500
    )
    SELECT * FROM t) AS t WHERE n < (
        SELECT count(*) FROM (
            WITH RECURSIVE t(n) AS (
                   SELECT 1 UNION ALL SELECT n + 1 FROM t WHERE n < 100
                )
            SELECT * FROM t WHERE n < 50000
         ) AS t WHERE n < 100);
 count 
-------
    98
(1 row)

-- use same CTE twice at different subquery levels
WITH q1(x,y) AS (
    SELECT hundred, sum(ten) FROM tenk1 GROUP BY hundred
  )
SELECT count(*) FROM q1 WHERE y > (SELECT sum(y)/100 FROM q1 qsub);
 count 
-------
    50
(1 row)

-- via a VIEW
CREATE TEMPORARY VIEW vsubdepartment AS
	WITH RECURSIVE subdepartment AS
	(
		 -- non recursive term
		SELECT * FROM department WHERE name = 'A'
		UNION ALL
		-- recursive term
		SELECT d.* FROM department AS d, subdepartment AS sd
			WHERE d.parent_department = sd.id
	)
	SELECT * FROM subdepartment;
SELECT * FROM vsubdepartment ORDER BY name;
 id | parent_department | name 
----+-------------------+------
  1 |                 0 | A
  2 |                 1 | B
  3 |                 2 | C
  4 |                 2 | D
  6 |                 4 | F
(5 rows)

-- Check reverse listing
SELECT pg_get_viewdef('vsubdepartment'::regclass);
                pg_get_viewdef                 
-----------------------------------------------
  WITH RECURSIVE subdepartment AS (           +
          SELECT department.id,               +
             department.parent_department,    +
             department.name                  +
            FROM department                   +
           WHERE (department.name = 'A'::text)+
         UNION ALL                            +
          SELECT d.id,                        +
             d.parent_department,             +
             d.name                           +
            FROM department d,                +
             subdepartment sd                 +
           WHERE (d.parent_department = sd.id)+
         )                                    +
  SELECT subdepartment.id,                    +
     subdepartment.parent_department,         +
     subdepartment.name                       +
    FROM subdepartment;
(1 row)

SELECT pg_get_viewdef('vsubdepartment'::regclass, true);
               pg_get_viewdef                
---------------------------------------------
  WITH RECURSIVE subdepartment AS (         +
          SELECT department.id,             +
             department.parent_department,  +
             department.name                +
            FROM department                 +
           WHERE department.name = 'A'::text+
         UNION ALL                          +
          SELECT d.id,                      +
             d.parent_department,           +
             d.name                         +
            FROM department d,              +
             subdepartment sd               +
           WHERE d.parent_department = sd.id+
         )                                  +
  SELECT subdepartment.id,                  +
     subdepartment.parent_department,       +
     subdepartment.name                     +
    FROM subdepartment;
(1 row)

-- Another reverse-listing example
CREATE VIEW sums_1_100 AS
WITH RECURSIVE t(n) AS (
    VALUES (1)
UNION ALL
    SELECT n+1 FROM t WHERE n < 100
)
SELECT sum(n) FROM t;
\d+ sums_1_100
                         View "public.sums_1_100"
 Column |  Type  | Collation | Nullable | Default | Storage | Description 
--------+--------+-----------+----------+---------+---------+-------------
 sum    | bigint |           |          |         | plain   | 
View definition:
 WITH RECURSIVE t(n) AS (
         VALUES (1)
        UNION ALL
         SELECT t_1.n + 1
           FROM t t_1
          WHERE t_1.n < 100
        )
 SELECT sum(t.n) AS sum
   FROM t;

-- corner case in which sub-WITH gets initialized first
with recursive q as (
      select * from department
    union all
      (with x as (select * from q)
       select * from x)
    )
select * from q limit 24;
 id | parent_department | name 
----+-------------------+------
  0 |                   | ROOT
  1 |                 0 | A
  2 |                 1 | B
  3 |                 2 | C
  4 |                 2 | D
  5 |                 0 | E
  6 |                 4 | F
  7 |                 5 | G
  0 |                   | ROOT
  1 |                 0 | A
  2 |                 1 | B
  3 |                 2 | C
  4 |                 2 | D
  5 |                 0 | E
  6 |                 4 | F
  7 |                 5 | G
  0 |                   | ROOT
  1 |                 0 | A
  2 |                 1 | B
  3 |                 2 | C
  4 |                 2 | D
  5 |                 0 | E
  6 |                 4 | F
  7 |                 5 | G
(24 rows)

with recursive q as (
      select * from department
    union all
      (with recursive x as (
           select * from department
         union all
           (select * from q union all select * from x)
        )
       select * from x)
    )
select * from q limit 32;
 id | parent_department | name 
----+-------------------+------
  0 |                   | ROOT
  1 |                 0 | A
  2 |                 1 | B
  3 |                 2 | C
  4 |                 2 | D
  5 |                 0 | E
  6 |                 4 | F
  7 |                 5 | G
  0 |                   | ROOT
  1 |                 0 | A
  2 |                 1 | B
  3 |                 2 | C
  4 |                 2 | D
  5 |                 0 | E
  6 |                 4 | F
  7 |                 5 | G
  0 |                   | ROOT
  1 |                 0 | A
  2 |                 1 | B
  3 |                 2 | C
  4 |                 2 | D
  5 |                 0 | E
  6 |                 4 | F
  7 |                 5 | G
  0 |                   | ROOT
  1 |                 0 | A
  2 |                 1 | B
  3 |                 2 | C
  4 |                 2 | D
  5 |                 0 | E
  6 |                 4 | F
  7 |                 5 | G
(32 rows)

-- recursive term has sub-UNION
WITH RECURSIVE t(i,j) AS (
	VALUES (1,2)
	UNION ALL
	SELECT t2.i, t.j+1 FROM
		(SELECT 2 AS i UNION ALL SELECT 3 AS i) AS t2
		JOIN t ON (t2.i = t.i+1))
	SELECT * FROM t;
 i | j 
---+---
 1 | 2
 2 | 3
 3 | 4
(3 rows)

--
-- different tree example
--
CREATE TEMPORARY TABLE tree(
    id INTEGER PRIMARY KEY,
    parent_id INTEGER REFERENCES tree(id)
);
INSERT INTO tree
VALUES (1, NULL), (2, 1), (3,1), (4,2), (5,2), (6,2), (7,3), (8,3),
       (9,4), (10,4), (11,7), (12,7), (13,7), (14, 9), (15,11), (16,11);
--
-- get all paths from "second level" nodes to leaf nodes
--
WITH RECURSIVE t(id, path) AS (
    VALUES(1,ARRAY[]::integer[])
UNION ALL
    SELECT tree.id, t.path || tree.id
    FROM tree JOIN t ON (tree.parent_id = t.id)
)
SELECT t1.*, t2.* FROM t AS t1 JOIN t AS t2 ON
	(t1.path[1] = t2.path[1] AND
	array_upper(t1.path,1) = 1 AND
	array_upper(t2.path,1) > 1)
	ORDER BY t1.id, t2.id;
 id | path | id |    path     
----+------+----+-------------
  2 | {2}  |  4 | {2,4}
  2 | {2}  |  5 | {2,5}
  2 | {2}  |  6 | {2,6}
  2 | {2}  |  9 | {2,4,9}
  2 | {2}  | 10 | {2,4,10}
  2 | {2}  | 14 | {2,4,9,14}
  3 | {3}  |  7 | {3,7}
  3 | {3}  |  8 | {3,8}
  3 | {3}  | 11 | {3,7,11}
  3 | {3}  | 12 | {3,7,12}
  3 | {3}  | 13 | {3,7,13}
  3 | {3}  | 15 | {3,7,11,15}
  3 | {3}  | 16 | {3,7,11,16}
(13 rows)

-- just count 'em
WITH RECURSIVE t(id, path) AS (
    VALUES(1,ARRAY[]::integer[])
UNION ALL
    SELECT tree.id, t.path || tree.id
    FROM tree JOIN t ON (tree.parent_id = t.id)
)
SELECT t1.id, count(t2.*) FROM t AS t1 JOIN t AS t2 ON
	(t1.path[1] = t2.path[1] AND
	array_upper(t1.path,1) = 1 AND
	array_upper(t2.path,1) > 1)
	GROUP BY t1.id
	ORDER BY t1.id;
 id | count 
----+-------
  2 |     6
  3 |     7
(2 rows)

-- this variant tickled a whole-row-variable bug in 8.4devel
WITH RECURSIVE t(id, path) AS (
    VALUES(1,ARRAY[]::integer[])
UNION ALL
    SELECT tree.id, t.path || tree.id
    FROM tree JOIN t ON (tree.parent_id = t.id)
)
SELECT t1.id, t2.path, t2 FROM t AS t1 JOIN t AS t2 ON
(t1.id=t2.id);
 id |    path     |         t2         
----+-------------+--------------------
  1 | {}          | (1,{})
  2 | {2}         | (2,{2})
  3 | {3}         | (3,{3})
  4 | {2,4}       | (4,"{2,4}")
  5 | {2,5}       | (5,"{2,5}")
  6 | {2,6}       | (6,"{2,6}")
  7 | {3,7}       | (7,"{3,7}")
  8 | {3,8}       | (8,"{3,8}")
  9 | {2,4,9}     | (9,"{2,4,9}")
 10 | {2,4,10}    | (10,"{2,4,10}")
 11 | {3,7,11}    | (11,"{3,7,11}")
 12 | {3,7,12}    | (12,"{3,7,12}")
 13 | {3,7,13}    | (13,"{3,7,13}")
 14 | {2,4,9,14}  | (14,"{2,4,9,14}")
 15 | {3,7,11,15} | (15,"{3,7,11,15}")
 16 | {3,7,11,16} | (16,"{3,7,11,16}")
(16 rows)

-- SEARCH clause
create temp table graph0( f int, t int, label text );
insert into graph0 values
	(1, 2, 'arc 1 -> 2'),
	(1, 3, 'arc 1 -> 3'),
	(2, 3, 'arc 2 -> 3'),
	(1, 4, 'arc 1 -> 4'),
	(4, 5, 'arc 4 -> 5');
explain (verbose, costs off)
with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union all
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search depth first by f, t set seq
select * from search_graph order by seq;
                                          QUERY PLAN                                          
----------------------------------------------------------------------------------------------
 Sort
   Output: search_graph.f, search_graph.t, search_graph.label, search_graph.seq
   Sort Key: search_graph.seq
   CTE search_graph
     ->  Recursive Union
           ->  Seq Scan on pg_temp.graph0 g
                 Output: g.f, g.t, g.label, ARRAY[ROW(g.f, g.t)]
           ->  Merge Join
                 Output: g_1.f, g_1.t, g_1.label, array_cat(sg.seq, ARRAY[ROW(g_1.f, g_1.t)])
                 Merge Cond: (g_1.f = sg.t)
                 ->  Sort
                       Output: g_1.f, g_1.t, g_1.label
                       Sort Key: g_1.f
                       ->  Seq Scan on pg_temp.graph0 g_1
                             Output: g_1.f, g_1.t, g_1.label
                 ->  Sort
                       Output: sg.seq, sg.t
                       Sort Key: sg.t
                       ->  WorkTable Scan on search_graph sg
                             Output: sg.seq, sg.t
   ->  CTE Scan on search_graph
         Output: search_graph.f, search_graph.t, search_graph.label, search_graph.seq
(22 rows)

with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union all
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search depth first by f, t set seq
select * from search_graph order by seq;
 f | t |   label    |        seq        
---+---+------------+-------------------
 1 | 2 | arc 1 -> 2 | {"(1,2)"}
 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"}
 1 | 3 | arc 1 -> 3 | {"(1,3)"}
 1 | 4 | arc 1 -> 4 | {"(1,4)"}
 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"}
 2 | 3 | arc 2 -> 3 | {"(2,3)"}
 4 | 5 | arc 4 -> 5 | {"(4,5)"}
(7 rows)

with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union distinct
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search depth first by f, t set seq
select * from search_graph order by seq;
 f | t |   label    |        seq        
---+---+------------+-------------------
 1 | 2 | arc 1 -> 2 | {"(1,2)"}
 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"}
 1 | 3 | arc 1 -> 3 | {"(1,3)"}
 1 | 4 | arc 1 -> 4 | {"(1,4)"}
 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"}
 2 | 3 | arc 2 -> 3 | {"(2,3)"}
 4 | 5 | arc 4 -> 5 | {"(4,5)"}
(7 rows)

explain (verbose, costs off)
with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union all
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search breadth first by f, t set seq
select * from search_graph order by seq;
                                           QUERY PLAN                                            
-------------------------------------------------------------------------------------------------
 Sort
   Output: search_graph.f, search_graph.t, search_graph.label, search_graph.seq
   Sort Key: search_graph.seq
   CTE search_graph
     ->  Recursive Union
           ->  Seq Scan on pg_temp.graph0 g
                 Output: g.f, g.t, g.label, ROW('0'::bigint, g.f, g.t)
           ->  Merge Join
                 Output: g_1.f, g_1.t, g_1.label, ROW(int8inc((sg.seq)."*DEPTH*"), g_1.f, g_1.t)
                 Merge Cond: (g_1.f = sg.t)
                 ->  Sort
                       Output: g_1.f, g_1.t, g_1.label
                       Sort Key: g_1.f
                       ->  Seq Scan on pg_temp.graph0 g_1
                             Output: g_1.f, g_1.t, g_1.label
                 ->  Sort
                       Output: sg.seq, sg.t
                       Sort Key: sg.t
                       ->  WorkTable Scan on search_graph sg
                             Output: sg.seq, sg.t
   ->  CTE Scan on search_graph
         Output: search_graph.f, search_graph.t, search_graph.label, search_graph.seq
(22 rows)

with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union all
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search breadth first by f, t set seq
select * from search_graph order by seq;
 f | t |   label    |   seq   
---+---+------------+---------
 1 | 2 | arc 1 -> 2 | (0,1,2)
 1 | 3 | arc 1 -> 3 | (0,1,3)
 1 | 4 | arc 1 -> 4 | (0,1,4)
 2 | 3 | arc 2 -> 3 | (0,2,3)
 4 | 5 | arc 4 -> 5 | (0,4,5)
 2 | 3 | arc 2 -> 3 | (1,2,3)
 4 | 5 | arc 4 -> 5 | (1,4,5)
(7 rows)

with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union distinct
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search breadth first by f, t set seq
select * from search_graph order by seq;
 f | t |   label    |   seq   
---+---+------------+---------
 1 | 2 | arc 1 -> 2 | (0,1,2)
 1 | 3 | arc 1 -> 3 | (0,1,3)
 1 | 4 | arc 1 -> 4 | (0,1,4)
 2 | 3 | arc 2 -> 3 | (0,2,3)
 4 | 5 | arc 4 -> 5 | (0,4,5)
 2 | 3 | arc 2 -> 3 | (1,2,3)
 4 | 5 | arc 4 -> 5 | (1,4,5)
(7 rows)

-- a constant initial value causes issues for EXPLAIN
explain (verbose, costs off)
with recursive test as (
  select 1 as x
  union all
  select x + 1
  from test
) search depth first by x set y
select * from test limit 5;
                                       QUERY PLAN                                        
-----------------------------------------------------------------------------------------
 Limit
   Output: test.x, test.y
   CTE test
     ->  Recursive Union
           ->  Result
                 Output: 1, '{(1)}'::record[]
           ->  WorkTable Scan on test test_1
                 Output: (test_1.x + 1), array_cat(test_1.y, ARRAY[ROW((test_1.x + 1))])
   ->  CTE Scan on test
         Output: test.x, test.y
(10 rows)

with recursive test as (
  select 1 as x
  union all
  select x + 1
  from test
) search depth first by x set y
select * from test limit 5;
 x |           y           
---+-----------------------
 1 | {(1)}
 2 | {(1),(2)}
 3 | {(1),(2),(3)}
 4 | {(1),(2),(3),(4)}
 5 | {(1),(2),(3),(4),(5)}
(5 rows)

explain (verbose, costs off)
with recursive test as (
  select 1 as x
  union all
  select x + 1
  from test
) search breadth first by x set y
select * from test limit 5;
                                         QUERY PLAN                                         
--------------------------------------------------------------------------------------------
 Limit
   Output: test.x, test.y
   CTE test
     ->  Recursive Union
           ->  Result
                 Output: 1, '(0,1)'::record
           ->  WorkTable Scan on test test_1
                 Output: (test_1.x + 1), ROW(int8inc((test_1.y)."*DEPTH*"), (test_1.x + 1))
   ->  CTE Scan on test
         Output: test.x, test.y
(10 rows)

with recursive test as (
  select 1 as x
  union all
  select x + 1
  from test
) search breadth first by x set y
select * from test limit 5;
 x |   y   
---+-------
 1 | (0,1)
 2 | (1,2)
 3 | (2,3)
 4 | (3,4)
 5 | (4,5)
(5 rows)

-- various syntax errors
with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union all
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search depth first by foo, tar set seq
select * from search_graph;
ERROR:  search column "foo" not in WITH query column list
LINE 7: ) search depth first by foo, tar set seq
          ^
with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union all
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search depth first by f, t set label
select * from search_graph;
ERROR:  search sequence column name "label" already used in WITH query column list
LINE 7: ) search depth first by f, t set label
          ^
with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union all
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search depth first by f, t, f set seq
select * from search_graph;
ERROR:  search column "f" specified more than once
LINE 7: ) search depth first by f, t, f set seq
          ^
with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union all
	select * from graph0 g
	union all
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search depth first by f, t set seq
select * from search_graph order by seq;
ERROR:  with a SEARCH or CYCLE clause, the left side of the UNION must be a SELECT
with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union all
	(select * from graph0 g
	union all
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t)
) search depth first by f, t set seq
select * from search_graph order by seq;
ERROR:  with a SEARCH or CYCLE clause, the right side of the UNION must be a SELECT
-- check that we distinguish same CTE name used at different levels
-- (this case could be supported, perhaps, but it isn't today)
with recursive x(col) as (
	select 1
	union
	(with x as (select * from x)
	 select * from x)
) search depth first by col set seq
select * from x;
ERROR:  with a SEARCH or CYCLE clause, the recursive reference to WITH query "x" must be at the top level of its right-hand SELECT
-- test ruleutils and view expansion
create temp view v_search as
with recursive search_graph(f, t, label) as (
	select * from graph0 g
	union all
	select g.*
	from graph0 g, search_graph sg
	where g.f = sg.t
) search depth first by f, t set seq
select f, t, label from search_graph;
select pg_get_viewdef('v_search');
                 pg_get_viewdef                 
------------------------------------------------
  WITH RECURSIVE search_graph(f, t, label) AS (+
          SELECT g.f,                          +
             g.t,                              +
             g.label                           +
            FROM graph0 g                      +
         UNION ALL                             +
          SELECT g.f,                          +
             g.t,                              +
             g.label                           +
            FROM graph0 g,                     +
             search_graph sg                   +
           WHERE (g.f = sg.t)                  +
         ) SEARCH DEPTH FIRST BY f, t SET seq  +
  SELECT search_graph.f,                       +
     search_graph.t,                           +
     search_graph.label                        +
    FROM search_graph;
(1 row)

select * from v_search;
 f | t |   label    
---+---+------------
 1 | 2 | arc 1 -> 2
 1 | 3 | arc 1 -> 3
 2 | 3 | arc 2 -> 3
 1 | 4 | arc 1 -> 4
 4 | 5 | arc 4 -> 5
 2 | 3 | arc 2 -> 3
 4 | 5 | arc 4 -> 5
(7 rows)

--
-- test cycle detection
--
create temp table graph( f int, t int, label text );
insert into graph values
	(1, 2, 'arc 1 -> 2'),
	(1, 3, 'arc 1 -> 3'),
	(2, 3, 'arc 2 -> 3'),
	(1, 4, 'arc 1 -> 4'),
	(4, 5, 'arc 4 -> 5'),
	(5, 1, 'arc 5 -> 1');
with recursive search_graph(f, t, label, is_cycle, path) as (
	select *, false, array[row(g.f, g.t)] from graph g
	union all
	select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
	from graph g, search_graph sg
	where g.f = sg.t and not is_cycle
)
select * from search_graph;
 f | t |   label    | is_cycle |                   path                    
---+---+------------+----------+-------------------------------------------
 1 | 2 | arc 1 -> 2 | f        | {"(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(1,3)"}
 2 | 3 | arc 2 -> 3 | f        | {"(2,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(1,4)"}
 4 | 5 | arc 4 -> 5 | f        | {"(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | f        | {"(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | f        | {"(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | f        | {"(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | f        | {"(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(1,4)","(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(1,4)","(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(1,4)","(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | t        | {"(1,4)","(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | f        | {"(4,5)","(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | t        | {"(4,5)","(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | t        | {"(5,1)","(1,4)","(4,5)","(5,1)"}
 2 | 3 | arc 2 -> 3 | f        | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
(25 rows)

-- UNION DISTINCT exercises row type hashing support
with recursive search_graph(f, t, label, is_cycle, path) as (
	select *, false, array[row(g.f, g.t)] from graph g
	union distinct
	select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
	from graph g, search_graph sg
	where g.f = sg.t and not is_cycle
)
select * from search_graph;
 f | t |   label    | is_cycle |                   path                    
---+---+------------+----------+-------------------------------------------
 1 | 2 | arc 1 -> 2 | f        | {"(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(1,3)"}
 2 | 3 | arc 2 -> 3 | f        | {"(2,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(1,4)"}
 4 | 5 | arc 4 -> 5 | f        | {"(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | f        | {"(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | f        | {"(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | f        | {"(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | f        | {"(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(1,4)","(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(1,4)","(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(1,4)","(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | t        | {"(1,4)","(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | f        | {"(4,5)","(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | t        | {"(4,5)","(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | t        | {"(5,1)","(1,4)","(4,5)","(5,1)"}
 2 | 3 | arc 2 -> 3 | f        | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
(25 rows)

-- ordering by the path column has same effect as SEARCH DEPTH FIRST
with recursive search_graph(f, t, label, is_cycle, path) as (
	select *, false, array[row(g.f, g.t)] from graph g
	union all
	select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
	from graph g, search_graph sg
	where g.f = sg.t and not is_cycle
)
select * from search_graph order by path;
 f | t |   label    | is_cycle |                   path                    
---+---+------------+----------+-------------------------------------------
 1 | 2 | arc 1 -> 2 | f        | {"(1,2)"}
 2 | 3 | arc 2 -> 3 | f        | {"(1,2)","(2,3)"}
 1 | 3 | arc 1 -> 3 | f        | {"(1,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(1,4)"}
 4 | 5 | arc 4 -> 5 | f        | {"(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(1,4)","(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(1,4)","(4,5)","(5,1)","(1,2)"}
 2 | 3 | arc 2 -> 3 | f        | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
 1 | 3 | arc 1 -> 3 | f        | {"(1,4)","(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | t        | {"(1,4)","(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | f        | {"(2,3)"}
 4 | 5 | arc 4 -> 5 | f        | {"(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(4,5)","(5,1)","(1,2)"}
 2 | 3 | arc 2 -> 3 | f        | {"(4,5)","(5,1)","(1,2)","(2,3)"}
 1 | 3 | arc 1 -> 3 | f        | {"(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(4,5)","(5,1)","(1,4)"}
 4 | 5 | arc 4 -> 5 | t        | {"(4,5)","(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(5,1)","(1,2)"}
 2 | 3 | arc 2 -> 3 | f        | {"(5,1)","(1,2)","(2,3)"}
 1 | 3 | arc 1 -> 3 | f        | {"(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(5,1)","(1,4)"}
 4 | 5 | arc 4 -> 5 | f        | {"(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | t        | {"(5,1)","(1,4)","(4,5)","(5,1)"}
(25 rows)

-- CYCLE clause
explain (verbose, costs off)
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t set is_cycle using path
select * from search_graph;
                                                                              QUERY PLAN                                                                               
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
 CTE Scan on search_graph
   Output: search_graph.f, search_graph.t, search_graph.label, search_graph.is_cycle, search_graph.path
   CTE search_graph
     ->  Recursive Union
           ->  Seq Scan on pg_temp.graph g
                 Output: g.f, g.t, g.label, false, ARRAY[ROW(g.f, g.t)]
           ->  Merge Join
                 Output: g_1.f, g_1.t, g_1.label, CASE WHEN (ROW(g_1.f, g_1.t) = ANY (sg.path)) THEN true ELSE false END, array_cat(sg.path, ARRAY[ROW(g_1.f, g_1.t)])
                 Merge Cond: (g_1.f = sg.t)
                 ->  Sort
                       Output: g_1.f, g_1.t, g_1.label
                       Sort Key: g_1.f
                       ->  Seq Scan on pg_temp.graph g_1
                             Output: g_1.f, g_1.t, g_1.label
                 ->  Sort
                       Output: sg.path, sg.t
                       Sort Key: sg.t
                       ->  WorkTable Scan on search_graph sg
                             Output: sg.path, sg.t
                             Filter: (NOT sg.is_cycle)
(20 rows)

with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t set is_cycle using path
select * from search_graph;
 f | t |   label    | is_cycle |                   path                    
---+---+------------+----------+-------------------------------------------
 1 | 2 | arc 1 -> 2 | f        | {"(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(1,3)"}
 2 | 3 | arc 2 -> 3 | f        | {"(2,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(1,4)"}
 4 | 5 | arc 4 -> 5 | f        | {"(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | f        | {"(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | f        | {"(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | f        | {"(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | f        | {"(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | f        | {"(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | f        | {"(1,4)","(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | f        | {"(1,4)","(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | f        | {"(1,4)","(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | t        | {"(1,4)","(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | f        | {"(4,5)","(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | t        | {"(4,5)","(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | t        | {"(5,1)","(1,4)","(4,5)","(5,1)"}
 2 | 3 | arc 2 -> 3 | f        | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
(25 rows)

with recursive search_graph(f, t, label) as (
	select * from graph g
	union distinct
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t set is_cycle to 'Y' default 'N' using path
select * from search_graph;
 f | t |   label    | is_cycle |                   path                    
---+---+------------+----------+-------------------------------------------
 1 | 2 | arc 1 -> 2 | N        | {"(1,2)"}
 1 | 3 | arc 1 -> 3 | N        | {"(1,3)"}
 2 | 3 | arc 2 -> 3 | N        | {"(2,3)"}
 1 | 4 | arc 1 -> 4 | N        | {"(1,4)"}
 4 | 5 | arc 4 -> 5 | N        | {"(4,5)"}
 5 | 1 | arc 5 -> 1 | N        | {"(5,1)"}
 1 | 2 | arc 1 -> 2 | N        | {"(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | N        | {"(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | N        | {"(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | N        | {"(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | N        | {"(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | N        | {"(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | N        | {"(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | N        | {"(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | N        | {"(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | N        | {"(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | N        | {"(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | N        | {"(1,4)","(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | N        | {"(1,4)","(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | N        | {"(1,4)","(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | Y        | {"(1,4)","(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | N        | {"(4,5)","(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | Y        | {"(4,5)","(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | Y        | {"(5,1)","(1,4)","(4,5)","(5,1)"}
 2 | 3 | arc 2 -> 3 | N        | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
(25 rows)

explain (verbose, costs off)
with recursive test as (
  select 0 as x
  union all
  select (x + 1) % 10
  from test
) cycle x set is_cycle using path
select * from test;
                                                                                          QUERY PLAN                                                                                           
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 CTE Scan on test
   Output: test.x, test.is_cycle, test.path
   CTE test
     ->  Recursive Union
           ->  Result
                 Output: 0, false, '{(0)}'::record[]
           ->  WorkTable Scan on test test_1
                 Output: ((test_1.x + 1) % 10), CASE WHEN (ROW(((test_1.x + 1) % 10)) = ANY (test_1.path)) THEN true ELSE false END, array_cat(test_1.path, ARRAY[ROW(((test_1.x + 1) % 10))])
                 Filter: (NOT test_1.is_cycle)
(9 rows)

with recursive test as (
  select 0 as x
  union all
  select (x + 1) % 10
  from test
) cycle x set is_cycle using path
select * from test;
 x | is_cycle |                     path                      
---+----------+-----------------------------------------------
 0 | f        | {(0)}
 1 | f        | {(0),(1)}
 2 | f        | {(0),(1),(2)}
 3 | f        | {(0),(1),(2),(3)}
 4 | f        | {(0),(1),(2),(3),(4)}
 5 | f        | {(0),(1),(2),(3),(4),(5)}
 6 | f        | {(0),(1),(2),(3),(4),(5),(6)}
 7 | f        | {(0),(1),(2),(3),(4),(5),(6),(7)}
 8 | f        | {(0),(1),(2),(3),(4),(5),(6),(7),(8)}
 9 | f        | {(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)}
 0 | t        | {(0),(1),(2),(3),(4),(5),(6),(7),(8),(9),(0)}
(11 rows)

with recursive test as (
  select 0 as x
  union all
  select (x + 1) % 10
  from test
    where not is_cycle  -- redundant, but legal
) cycle x set is_cycle using path
select * from test;
 x | is_cycle |                     path                      
---+----------+-----------------------------------------------
 0 | f        | {(0)}
 1 | f        | {(0),(1)}
 2 | f        | {(0),(1),(2)}
 3 | f        | {(0),(1),(2),(3)}
 4 | f        | {(0),(1),(2),(3),(4)}
 5 | f        | {(0),(1),(2),(3),(4),(5)}
 6 | f        | {(0),(1),(2),(3),(4),(5),(6)}
 7 | f        | {(0),(1),(2),(3),(4),(5),(6),(7)}
 8 | f        | {(0),(1),(2),(3),(4),(5),(6),(7),(8)}
 9 | f        | {(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)}
 0 | t        | {(0),(1),(2),(3),(4),(5),(6),(7),(8),(9),(0)}
(11 rows)

-- multiple CTEs
with recursive
graph(f, t, label) as (
  values (1, 2, 'arc 1 -> 2'),
         (1, 3, 'arc 1 -> 3'),
         (2, 3, 'arc 2 -> 3'),
         (1, 4, 'arc 1 -> 4'),
         (4, 5, 'arc 4 -> 5'),
         (5, 1, 'arc 5 -> 1')
),
search_graph(f, t, label) as (
        select * from graph g
        union all
        select g.*
        from graph g, search_graph sg
        where g.f = sg.t
) cycle f, t set is_cycle to true default false using path
select f, t, label from search_graph;
 f | t |   label    
---+---+------------
 1 | 2 | arc 1 -> 2
 1 | 3 | arc 1 -> 3
 2 | 3 | arc 2 -> 3
 1 | 4 | arc 1 -> 4
 4 | 5 | arc 4 -> 5
 5 | 1 | arc 5 -> 1
 2 | 3 | arc 2 -> 3
 4 | 5 | arc 4 -> 5
 5 | 1 | arc 5 -> 1
 1 | 4 | arc 1 -> 4
 1 | 3 | arc 1 -> 3
 1 | 2 | arc 1 -> 2
 5 | 1 | arc 5 -> 1
 1 | 4 | arc 1 -> 4
 1 | 3 | arc 1 -> 3
 1 | 2 | arc 1 -> 2
 4 | 5 | arc 4 -> 5
 2 | 3 | arc 2 -> 3
 1 | 4 | arc 1 -> 4
 1 | 3 | arc 1 -> 3
 1 | 2 | arc 1 -> 2
 4 | 5 | arc 4 -> 5
 2 | 3 | arc 2 -> 3
 5 | 1 | arc 5 -> 1
 2 | 3 | arc 2 -> 3
(25 rows)

-- star expansion
with recursive a as (
	select 1 as b
	union all
	select * from a
) cycle b set c using p
select * from a;
 b | c |     p     
---+---+-----------
 1 | f | {(1)}
 1 | t | {(1),(1)}
(2 rows)

-- search+cycle
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) search depth first by f, t set seq
  cycle f, t set is_cycle using path
select * from search_graph;
 f | t |   label    |                    seq                    | is_cycle |                   path                    
---+---+------------+-------------------------------------------+----------+-------------------------------------------
 1 | 2 | arc 1 -> 2 | {"(1,2)"}                                 | f        | {"(1,2)"}
 1 | 3 | arc 1 -> 3 | {"(1,3)"}                                 | f        | {"(1,3)"}
 2 | 3 | arc 2 -> 3 | {"(2,3)"}                                 | f        | {"(2,3)"}
 1 | 4 | arc 1 -> 4 | {"(1,4)"}                                 | f        | {"(1,4)"}
 4 | 5 | arc 4 -> 5 | {"(4,5)"}                                 | f        | {"(4,5)"}
 5 | 1 | arc 5 -> 1 | {"(5,1)"}                                 | f        | {"(5,1)"}
 1 | 2 | arc 1 -> 2 | {"(5,1)","(1,2)"}                         | f        | {"(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | {"(5,1)","(1,3)"}                         | f        | {"(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | {"(5,1)","(1,4)"}                         | f        | {"(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"}                         | f        | {"(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"}                         | f        | {"(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | {"(4,5)","(5,1)"}                         | f        | {"(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | {"(4,5)","(5,1)","(1,2)"}                 | f        | {"(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | {"(4,5)","(5,1)","(1,3)"}                 | f        | {"(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | {"(4,5)","(5,1)","(1,4)"}                 | f        | {"(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | {"(5,1)","(1,2)","(2,3)"}                 | f        | {"(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | {"(5,1)","(1,4)","(4,5)"}                 | f        | {"(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | {"(1,4)","(4,5)","(5,1)"}                 | f        | {"(1,4)","(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | {"(1,4)","(4,5)","(5,1)","(1,2)"}         | f        | {"(1,4)","(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,3)"}         | f        | {"(1,4)","(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | {"(1,4)","(4,5)","(5,1)","(1,4)"}         | t        | {"(1,4)","(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | {"(4,5)","(5,1)","(1,2)","(2,3)"}         | f        | {"(4,5)","(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | {"(4,5)","(5,1)","(1,4)","(4,5)"}         | t        | {"(4,5)","(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | {"(5,1)","(1,4)","(4,5)","(5,1)"}         | t        | {"(5,1)","(1,4)","(4,5)","(5,1)"}
 2 | 3 | arc 2 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} | f        | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
(25 rows)

with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) search breadth first by f, t set seq
  cycle f, t set is_cycle using path
select * from search_graph;
 f | t |   label    |   seq   | is_cycle |                   path                    
---+---+------------+---------+----------+-------------------------------------------
 1 | 2 | arc 1 -> 2 | (0,1,2) | f        | {"(1,2)"}
 1 | 3 | arc 1 -> 3 | (0,1,3) | f        | {"(1,3)"}
 2 | 3 | arc 2 -> 3 | (0,2,3) | f        | {"(2,3)"}
 1 | 4 | arc 1 -> 4 | (0,1,4) | f        | {"(1,4)"}
 4 | 5 | arc 4 -> 5 | (0,4,5) | f        | {"(4,5)"}
 5 | 1 | arc 5 -> 1 | (0,5,1) | f        | {"(5,1)"}
 1 | 2 | arc 1 -> 2 | (1,1,2) | f        | {"(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | (1,1,3) | f        | {"(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | (1,1,4) | f        | {"(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | (1,2,3) | f        | {"(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | (1,4,5) | f        | {"(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | (1,5,1) | f        | {"(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | (2,1,2) | f        | {"(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | (2,1,3) | f        | {"(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | (2,1,4) | f        | {"(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | (2,2,3) | f        | {"(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | (2,4,5) | f        | {"(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | (2,5,1) | f        | {"(1,4)","(4,5)","(5,1)"}
 1 | 2 | arc 1 -> 2 | (3,1,2) | f        | {"(1,4)","(4,5)","(5,1)","(1,2)"}
 1 | 3 | arc 1 -> 3 | (3,1,3) | f        | {"(1,4)","(4,5)","(5,1)","(1,3)"}
 1 | 4 | arc 1 -> 4 | (3,1,4) | t        | {"(1,4)","(4,5)","(5,1)","(1,4)"}
 2 | 3 | arc 2 -> 3 | (3,2,3) | f        | {"(4,5)","(5,1)","(1,2)","(2,3)"}
 4 | 5 | arc 4 -> 5 | (3,4,5) | t        | {"(4,5)","(5,1)","(1,4)","(4,5)"}
 5 | 1 | arc 5 -> 1 | (3,5,1) | t        | {"(5,1)","(1,4)","(4,5)","(5,1)"}
 2 | 3 | arc 2 -> 3 | (4,2,3) | f        | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
(25 rows)

-- various syntax errors
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle foo, tar set is_cycle using path
select * from search_graph;
ERROR:  cycle column "foo" not in WITH query column list
LINE 7: ) cycle foo, tar set is_cycle using path
          ^
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t set is_cycle to true default 55 using path
select * from search_graph;
ERROR:  CYCLE types boolean and integer cannot be matched
LINE 7: ) cycle f, t set is_cycle to true default 55 using path
                                                  ^
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t set is_cycle to point '(1,1)' default point '(0,0)' using path
select * from search_graph;
ERROR:  could not identify an equality operator for type point
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t set label to true default false using path
select * from search_graph;
ERROR:  cycle mark column name "label" already used in WITH query column list
LINE 7: ) cycle f, t set label to true default false using path
          ^
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t set is_cycle to true default false using label
select * from search_graph;
ERROR:  cycle path column name "label" already used in WITH query column list
LINE 7: ) cycle f, t set is_cycle to true default false using label
          ^
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t set foo to true default false using foo
select * from search_graph;
ERROR:  cycle mark column name and cycle path column name are the same
LINE 7: ) cycle f, t set foo to true default false using foo
          ^
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t, f set is_cycle to true default false using path
select * from search_graph;
ERROR:  cycle column "f" specified more than once
LINE 7: ) cycle f, t, f set is_cycle to true default false using pat...
          ^
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) search depth first by f, t set foo
  cycle f, t set foo to true default false using path
select * from search_graph;
ERROR:  search sequence column name and cycle mark column name are the same
LINE 7: ) search depth first by f, t set foo
          ^
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) search depth first by f, t set foo
  cycle f, t set is_cycle to true default false using foo
select * from search_graph;
ERROR:  search sequence column name and cycle path column name are the same
LINE 7: ) search depth first by f, t set foo
          ^
-- test ruleutils and view expansion
create temp view v_cycle1 as
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t set is_cycle using path
select f, t, label from search_graph;
create temp view v_cycle2 as
with recursive search_graph(f, t, label) as (
	select * from graph g
	union all
	select g.*
	from graph g, search_graph sg
	where g.f = sg.t
) cycle f, t set is_cycle to 'Y' default 'N' using path
select f, t, label from search_graph;
select pg_get_viewdef('v_cycle1');
                 pg_get_viewdef                 
------------------------------------------------
  WITH RECURSIVE search_graph(f, t, label) AS (+
          SELECT g.f,                          +
             g.t,                              +
             g.label                           +
            FROM graph g                       +
         UNION ALL                             +
          SELECT g.f,                          +
             g.t,                              +
             g.label                           +
            FROM graph g,                      +
             search_graph sg                   +
           WHERE (g.f = sg.t)                  +
         ) CYCLE f, t SET is_cycle USING path  +
  SELECT search_graph.f,                       +
     search_graph.t,                           +
     search_graph.label                        +
    FROM search_graph;
(1 row)

select pg_get_viewdef('v_cycle2');
                               pg_get_viewdef                                
-----------------------------------------------------------------------------
  WITH RECURSIVE search_graph(f, t, label) AS (                             +
          SELECT g.f,                                                       +
             g.t,                                                           +
             g.label                                                        +
            FROM graph g                                                    +
         UNION ALL                                                          +
          SELECT g.f,                                                       +
             g.t,                                                           +
             g.label                                                        +
            FROM graph g,                                                   +
             search_graph sg                                                +
           WHERE (g.f = sg.t)                                               +
         ) CYCLE f, t SET is_cycle TO 'Y'::text DEFAULT 'N'::text USING path+
  SELECT search_graph.f,                                                    +
     search_graph.t,                                                        +
     search_graph.label                                                     +
    FROM search_graph;
(1 row)

select * from v_cycle1;
 f | t |   label    
---+---+------------
 1 | 2 | arc 1 -> 2
 1 | 3 | arc 1 -> 3
 2 | 3 | arc 2 -> 3
 1 | 4 | arc 1 -> 4
 4 | 5 | arc 4 -> 5
 5 | 1 | arc 5 -> 1
 1 | 2 | arc 1 -> 2
 1 | 3 | arc 1 -> 3
 1 | 4 | arc 1 -> 4
 2 | 3 | arc 2 -> 3
 4 | 5 | arc 4 -> 5
 5 | 1 | arc 5 -> 1
 1 | 2 | arc 1 -> 2
 1 | 3 | arc 1 -> 3
 1 | 4 | arc 1 -> 4
 2 | 3 | arc 2 -> 3
 4 | 5 | arc 4 -> 5
 5 | 1 | arc 5 -> 1
 1 | 2 | arc 1 -> 2
 1 | 3 | arc 1 -> 3
 1 | 4 | arc 1 -> 4
 2 | 3 | arc 2 -> 3
 4 | 5 | arc 4 -> 5
 5 | 1 | arc 5 -> 1
 2 | 3 | arc 2 -> 3
(25 rows)

select * from v_cycle2;
 f | t |   label    
---+---+------------
 1 | 2 | arc 1 -> 2
 1 | 3 | arc 1 -> 3
 2 | 3 | arc 2 -> 3
 1 | 4 | arc 1 -> 4
 4 | 5 | arc 4 -> 5
 5 | 1 | arc 5 -> 1
 1 | 2 | arc 1 -> 2
 1 | 3 | arc 1 -> 3
 1 | 4 | arc 1 -> 4
 2 | 3 | arc 2 -> 3
 4 | 5 | arc 4 -> 5
 5 | 1 | arc 5 -> 1
 1 | 2 | arc 1 -> 2
 1 | 3 | arc 1 -> 3
 1 | 4 | arc 1 -> 4
 2 | 3 | arc 2 -> 3
 4 | 5 | arc 4 -> 5
 5 | 1 | arc 5 -> 1
 1 | 2 | arc 1 -> 2
 1 | 3 | arc 1 -> 3
 1 | 4 | arc 1 -> 4
 2 | 3 | arc 2 -> 3
 4 | 5 | arc 4 -> 5
 5 | 1 | arc 5 -> 1
 2 | 3 | arc 2 -> 3
(25 rows)

--
-- test multiple WITH queries
--
WITH RECURSIVE
  y (id) AS (VALUES (1)),
  x (id) AS (SELECT * FROM y UNION ALL SELECT id+1 FROM x WHERE id < 5)
SELECT * FROM x;
 id 
----
  1
  2
  3
  4
  5
(5 rows)

-- forward reference OK
WITH RECURSIVE
    x(id) AS (SELECT * FROM y UNION ALL SELECT id+1 FROM x WHERE id < 5),
    y(id) AS (values (1))
 SELECT * FROM x;
 id 
----
  1
  2
  3
  4
  5
(5 rows)

WITH RECURSIVE
   x(id) AS
     (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 5),
   y(id) AS
     (VALUES (1) UNION ALL SELECT id+1 FROM y WHERE id < 10)
 SELECT y.*, x.* FROM y LEFT JOIN x USING (id);
 id | id 
----+----
  1 |  1
  2 |  2
  3 |  3
  4 |  4
  5 |  5
  6 |   
  7 |   
  8 |   
  9 |   
 10 |   
(10 rows)

WITH RECURSIVE
   x(id) AS
     (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 5),
   y(id) AS
     (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 10)
 SELECT y.*, x.* FROM y LEFT JOIN x USING (id);
 id | id 
----+----
  1 |  1
  2 |  2
  3 |  3
  4 |  4
  5 |  5
  6 |   
(6 rows)

WITH RECURSIVE
   x(id) AS
     (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 3 ),
   y(id) AS
     (SELECT * FROM x UNION ALL SELECT * FROM x),
   z(id) AS
     (SELECT * FROM x UNION ALL SELECT id+1 FROM z WHERE id < 10)
 SELECT * FROM z;
 id 
----
  1
  2
  3
  2
  3
  4
  3
  4
  5
  4
  5
  6
  5
  6
  7
  6
  7
  8
  7
  8
  9
  8
  9
 10
  9
 10
 10
(27 rows)

WITH RECURSIVE
   x(id) AS
     (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 3 ),
   y(id) AS
     (SELECT * FROM x UNION ALL SELECT * FROM x),
   z(id) AS
     (SELECT * FROM y UNION ALL SELECT id+1 FROM z WHERE id < 10)
 SELECT * FROM z;
 id 
----
  1
  2
  3
  1
  2
  3
  2
  3
  4
  2
  3
  4
  3
  4
  5
  3
  4
  5
  4
  5
  6
  4
  5
  6
  5
  6
  7
  5
  6
  7
  6
  7
  8
  6
  7
  8
  7
  8
  9
  7
  8
  9
  8
  9
 10
  8
  9
 10
  9
 10
  9
 10
 10
 10
(54 rows)

--
-- Test WITH attached to a data-modifying statement
--
CREATE TEMPORARY TABLE y (a INTEGER);
INSERT INTO y SELECT generate_series(1, 10);
WITH t AS (
	SELECT a FROM y
)
INSERT INTO y
SELECT a+20 FROM t RETURNING *;
 a  
----
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
(10 rows)

SELECT * FROM y;
 a  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
(20 rows)

WITH t AS (
	SELECT a FROM y
)
UPDATE y SET a = y.a-10 FROM t WHERE y.a > 20 AND t.a = y.a RETURNING y.a;
 a  
----
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
(10 rows)

SELECT * FROM y;
 a  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
(20 rows)

WITH RECURSIVE t(a) AS (
	SELECT 11
	UNION ALL
	SELECT a+1 FROM t WHERE a < 50
)
DELETE FROM y USING t WHERE t.a = y.a RETURNING y.a;
 a  
----
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
(10 rows)

SELECT * FROM y;
 a  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
(10 rows)

DROP TABLE y;
--
-- error cases
--
WITH x(n, b) AS (SELECT 1)
SELECT * FROM x;
ERROR:  WITH query "x" has 1 columns available but 2 columns specified
LINE 1: WITH x(n, b) AS (SELECT 1)
             ^
-- INTERSECT
WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x)
	SELECT * FROM x;
ERROR:  recursive query "x" does not have the form non-recursive-term UNION [ALL] recursive-term
LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x...
                       ^
WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT ALL SELECT n+1 FROM x)
	SELECT * FROM x;
ERROR:  recursive query "x" does not have the form non-recursive-term UNION [ALL] recursive-term
LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT ALL SELECT n+1 FR...
                       ^
-- EXCEPT
WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT SELECT n+1 FROM x)
	SELECT * FROM x;
ERROR:  recursive query "x" does not have the form non-recursive-term UNION [ALL] recursive-term
LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT SELECT n+1 FROM x)
                       ^
WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT ALL SELECT n+1 FROM x)
	SELECT * FROM x;
ERROR:  recursive query "x" does not have the form non-recursive-term UNION [ALL] recursive-term
LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT ALL SELECT n+1 FROM ...
                       ^
-- no non-recursive term
WITH RECURSIVE x(n) AS (SELECT n FROM x)
	SELECT * FROM x;
ERROR:  recursive query "x" does not have the form non-recursive-term UNION [ALL] recursive-term
LINE 1: WITH RECURSIVE x(n) AS (SELECT n FROM x)
                       ^
-- recursive term in the left hand side (strictly speaking, should allow this)
WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1)
	SELECT * FROM x;
ERROR:  recursive reference to query "x" must not appear within its non-recursive term
LINE 1: WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1)
                                              ^
CREATE TEMPORARY TABLE y (a INTEGER);
INSERT INTO y SELECT generate_series(1, 10);
-- LEFT JOIN
WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1
	UNION ALL
	SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a WHERE n < 10)
SELECT * FROM x;
ERROR:  recursive reference to query "x" must not appear within an outer join
LINE 3:  SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a WHERE n < 10)
                                       ^
-- RIGHT JOIN
WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1
	UNION ALL
	SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a WHERE n < 10)
SELECT * FROM x;
ERROR:  recursive reference to query "x" must not appear within an outer join
LINE 3:  SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a WHERE n < 10)
                           ^
-- FULL JOIN
WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1
	UNION ALL
	SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a WHERE n < 10)
SELECT * FROM x;
ERROR:  recursive reference to query "x" must not appear within an outer join
LINE 3:  SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a WHERE n < 10)
                           ^
-- subquery
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x
                          WHERE n IN (SELECT * FROM x))
  SELECT * FROM x;
ERROR:  recursive reference to query "x" must not appear within a subquery
LINE 2:                           WHERE n IN (SELECT * FROM x))
                                                            ^
-- aggregate functions
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) FROM x)
  SELECT * FROM x;
ERROR:  aggregate functions are not allowed in a recursive query's recursive term
LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) F...
                                                          ^
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT sum(n) FROM x)
  SELECT * FROM x;
ERROR:  aggregate functions are not allowed in a recursive query's recursive term
LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT sum(n) FRO...
                                                          ^
-- ORDER BY
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x ORDER BY 1)
  SELECT * FROM x;
ERROR:  ORDER BY in a recursive query is not implemented
LINE 1: ...VE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x ORDER BY 1)
                                                                     ^
-- LIMIT/OFFSET
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1)
  SELECT * FROM x;
ERROR:  OFFSET in a recursive query is not implemented
LINE 1: ... AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1)
                                                                     ^
-- FOR UPDATE
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x FOR UPDATE)
  SELECT * FROM x;
ERROR:  FOR UPDATE/SHARE in a recursive query is not implemented
-- target list has a recursive query name
WITH RECURSIVE x(id) AS (values (1)
    UNION ALL
    SELECT (SELECT * FROM x) FROM x WHERE id < 5
) SELECT * FROM x;
ERROR:  recursive reference to query "x" must not appear within a subquery
LINE 3:     SELECT (SELECT * FROM x) FROM x WHERE id < 5
                                  ^
-- mutual recursive query (not implemented)
WITH RECURSIVE
  x (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM y WHERE id < 5),
  y (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 5)
SELECT * FROM x;
ERROR:  mutual recursion between WITH items is not implemented
LINE 2:   x (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM y WHERE id ...
          ^
-- non-linear recursion is not allowed
WITH RECURSIVE foo(i) AS
    (values (1)
    UNION ALL
       (SELECT i+1 FROM foo WHERE i < 10
          UNION ALL
       SELECT i+1 FROM foo WHERE i < 5)
) SELECT * FROM foo;
ERROR:  recursive reference to query "foo" must not appear more than once
LINE 6:        SELECT i+1 FROM foo WHERE i < 5)
                               ^
WITH RECURSIVE foo(i) AS
    (values (1)
    UNION ALL
	   SELECT * FROM
       (SELECT i+1 FROM foo WHERE i < 10
          UNION ALL
       SELECT i+1 FROM foo WHERE i < 5) AS t
) SELECT * FROM foo;
ERROR:  recursive reference to query "foo" must not appear more than once
LINE 7:        SELECT i+1 FROM foo WHERE i < 5) AS t
                               ^
WITH RECURSIVE foo(i) AS
    (values (1)
    UNION ALL
       (SELECT i+1 FROM foo WHERE i < 10
          EXCEPT
       SELECT i+1 FROM foo WHERE i < 5)
) SELECT * FROM foo;
ERROR:  recursive reference to query "foo" must not appear within EXCEPT
LINE 6:        SELECT i+1 FROM foo WHERE i < 5)
                               ^
WITH RECURSIVE foo(i) AS
    (values (1)
    UNION ALL
       (SELECT i+1 FROM foo WHERE i < 10
          INTERSECT
       SELECT i+1 FROM foo WHERE i < 5)
) SELECT * FROM foo;
ERROR:  recursive reference to query "foo" must not appear more than once
LINE 6:        SELECT i+1 FROM foo WHERE i < 5)
                               ^
-- Wrong type induced from non-recursive term
WITH RECURSIVE foo(i) AS
   (SELECT i FROM (VALUES(1),(2)) t(i)
   UNION ALL
   SELECT (i+1)::numeric(10,0) FROM foo WHERE i < 10)
SELECT * FROM foo;
ERROR:  recursive query "foo" column 1 has type integer in non-recursive term but type numeric overall
LINE 2:    (SELECT i FROM (VALUES(1),(2)) t(i)
                   ^
HINT:  Cast the output of the non-recursive term to the correct type.
-- rejects different typmod, too (should we allow this?)
WITH RECURSIVE foo(i) AS
   (SELECT i::numeric(3,0) FROM (VALUES(1),(2)) t(i)
   UNION ALL
   SELECT (i+1)::numeric(10,0) FROM foo WHERE i < 10)
SELECT * FROM foo;
ERROR:  recursive query "foo" column 1 has type numeric(3,0) in non-recursive term but type numeric overall
LINE 2:    (SELECT i::numeric(3,0) FROM (VALUES(1),(2)) t(i)
                   ^
HINT:  Cast the output of the non-recursive term to the correct type.
-- disallow OLD/NEW reference in CTE
CREATE TEMPORARY TABLE x (n integer);
CREATE RULE r2 AS ON UPDATE TO x DO INSTEAD
    WITH t AS (SELECT OLD.*) UPDATE y SET a = t.n FROM t;
ERROR:  cannot refer to OLD within WITH query
--
-- test for bug #4902
--
with cte(foo) as ( values(42) ) values((select foo from cte));
 column1 
---------
      42
(1 row)

with cte(foo) as ( select 42 ) select * from ((select foo from cte)) q;
 foo 
-----
  42
(1 row)

-- test CTE referencing an outer-level variable (to see that changed-parameter
-- signaling still works properly after fixing this bug)
select ( with cte(foo) as ( values(f1) )
         select (select foo from cte) )
from int4_tbl;
     foo     
-------------
           0
      123456
     -123456
  2147483647
 -2147483647
(5 rows)

select ( with cte(foo) as ( values(f1) )
          values((select foo from cte)) )
from int4_tbl;
   column1   
-------------
           0
      123456
     -123456
  2147483647
 -2147483647
(5 rows)

--
-- test for nested-recursive-WITH bug
--
WITH RECURSIVE t(j) AS (
    WITH RECURSIVE s(i) AS (
        VALUES (1)
        UNION ALL
        SELECT i+1 FROM s WHERE i < 10
    )
    SELECT i FROM s
    UNION ALL
    SELECT j+1 FROM t WHERE j < 10
)
SELECT * FROM t;
 j  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
  2
  3
  4
  5
  6
  7
  8
  9
 10
  3
  4
  5
  6
  7
  8
  9
 10
  4
  5
  6
  7
  8
  9
 10
  5
  6
  7
  8
  9
 10
  6
  7
  8
  9
 10
  7
  8
  9
 10
  8
  9
 10
  9
 10
 10
(55 rows)

--
-- test WITH attached to intermediate-level set operation
--
WITH outermost(x) AS (
  SELECT 1
  UNION (WITH innermost as (SELECT 2)
         SELECT * FROM innermost
         UNION SELECT 3)
)
SELECT * FROM outermost ORDER BY 1;
 x 
---
 1
 2
 3
(3 rows)

WITH outermost(x) AS (
  SELECT 1
  UNION (WITH innermost as (SELECT 2)
         SELECT * FROM outermost  -- fail
         UNION SELECT * FROM innermost)
)
SELECT * FROM outermost ORDER BY 1;
ERROR:  relation "outermost" does not exist
LINE 4:          SELECT * FROM outermost  -- fail
                               ^
DETAIL:  There is a WITH item named "outermost", but it cannot be referenced from this part of the query.
HINT:  Use WITH RECURSIVE, or re-order the WITH items to remove forward references.
WITH RECURSIVE outermost(x) AS (
  SELECT 1
  UNION (WITH innermost as (SELECT 2)
         SELECT * FROM outermost
         UNION SELECT * FROM innermost)
)
SELECT * FROM outermost ORDER BY 1;
 x 
---
 1
 2
(2 rows)

WITH RECURSIVE outermost(x) AS (
  WITH innermost as (SELECT 2 FROM outermost) -- fail
    SELECT * FROM innermost
    UNION SELECT * from outermost
)
SELECT * FROM outermost ORDER BY 1;
ERROR:  recursive reference to query "outermost" must not appear within a subquery
LINE 2:   WITH innermost as (SELECT 2 FROM outermost) -- fail
                                           ^
--
-- This test will fail with the old implementation of PARAM_EXEC parameter
-- assignment, because the "q1" Var passed down to A's targetlist subselect
-- looks exactly like the "A.id" Var passed down to C's subselect, causing
-- the old code to give them the same runtime PARAM_EXEC slot.  But the
-- lifespans of the two parameters overlap, thanks to B also reading A.
--
with
A as ( select q2 as id, (select q1) as x from int8_tbl ),
B as ( select id, row_number() over (partition by id) as r from A ),
C as ( select A.id, array(select B.id from B where B.id = A.id) from A )
select * from C;
        id         |                array                
-------------------+-------------------------------------
               456 | {456}
  4567890123456789 | {4567890123456789,4567890123456789}
               123 | {123}
  4567890123456789 | {4567890123456789,4567890123456789}
 -4567890123456789 | {-4567890123456789}
(5 rows)

--
-- Test CTEs read in non-initialization orders
--
WITH RECURSIVE
  tab(id_key,link) AS (VALUES (1,17), (2,17), (3,17), (4,17), (6,17), (5,17)),
  iter (id_key, row_type, link) AS (
      SELECT 0, 'base', 17
    UNION ALL (
      WITH remaining(id_key, row_type, link, min) AS (
        SELECT tab.id_key, 'true'::text, iter.link, MIN(tab.id_key) OVER ()
        FROM tab INNER JOIN iter USING (link)
        WHERE tab.id_key > iter.id_key
      ),
      first_remaining AS (
        SELECT id_key, row_type, link
        FROM remaining
        WHERE id_key=min
      ),
      effect AS (
        SELECT tab.id_key, 'new'::text, tab.link
        FROM first_remaining e INNER JOIN tab ON e.id_key=tab.id_key
        WHERE e.row_type = 'false'
      )
      SELECT * FROM first_remaining
      UNION ALL SELECT * FROM effect
    )
  )
SELECT * FROM iter;
 id_key | row_type | link 
--------+----------+------
      0 | base     |   17
      1 | true     |   17
      2 | true     |   17
      3 | true     |   17
      4 | true     |   17
      5 | true     |   17
      6 | true     |   17
(7 rows)

WITH RECURSIVE
  tab(id_key,link) AS (VALUES (1,17), (2,17), (3,17), (4,17), (6,17), (5,17)),
  iter (id_key, row_type, link) AS (
      SELECT 0, 'base', 17
    UNION (
      WITH remaining(id_key, row_type, link, min) AS (
        SELECT tab.id_key, 'true'::text, iter.link, MIN(tab.id_key) OVER ()
        FROM tab INNER JOIN iter USING (link)
        WHERE tab.id_key > iter.id_key
      ),
      first_remaining AS (
        SELECT id_key, row_type, link
        FROM remaining
        WHERE id_key=min
      ),
      effect AS (
        SELECT tab.id_key, 'new'::text, tab.link
        FROM first_remaining e INNER JOIN tab ON e.id_key=tab.id_key
        WHERE e.row_type = 'false'
      )
      SELECT * FROM first_remaining
      UNION ALL SELECT * FROM effect
    )
  )
SELECT * FROM iter;
 id_key | row_type | link 
--------+----------+------
      0 | base     |   17
      1 | true     |   17
      2 | true     |   17
      3 | true     |   17
      4 | true     |   17
      5 | true     |   17
      6 | true     |   17
(7 rows)

--
-- Data-modifying statements in WITH
--
-- INSERT ... RETURNING
WITH t AS (
    INSERT INTO y
    VALUES
        (11),
        (12),
        (13),
        (14),
        (15),
        (16),
        (17),
        (18),
        (19),
        (20)
    RETURNING *
)
SELECT * FROM t;
 a  
----
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
(10 rows)

SELECT * FROM y;
 a  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
(20 rows)

-- UPDATE ... RETURNING
WITH t AS (
    UPDATE y
    SET a=a+1
    RETURNING *
)
SELECT * FROM t;
 a  
----
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
(20 rows)

SELECT * FROM y;
 a  
----
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
(20 rows)

-- DELETE ... RETURNING
WITH t AS (
    DELETE FROM y
    WHERE a <= 10
    RETURNING *
)
SELECT * FROM t;
 a  
----
  2
  3
  4
  5
  6
  7
  8
  9
 10
(9 rows)

SELECT * FROM y;
 a  
----
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
(11 rows)

-- forward reference
WITH RECURSIVE t AS (
	INSERT INTO y
		SELECT a+5 FROM t2 WHERE a > 5
	RETURNING *
), t2 AS (
	UPDATE y SET a=a-11 RETURNING *
)
SELECT * FROM t
UNION ALL
SELECT * FROM t2;
 a  
----
 11
 12
 13
 14
 15
  0
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
(16 rows)

SELECT * FROM y;
 a  
----
  0
  1
  2
  3
  4
  5
  6
 11
  7
 12
  8
 13
  9
 14
 10
 15
(16 rows)

-- unconditional DO INSTEAD rule
CREATE RULE y_rule AS ON DELETE TO y DO INSTEAD
  INSERT INTO y VALUES(42) RETURNING *;
WITH t AS (
	DELETE FROM y RETURNING *
)
SELECT * FROM t;
 a  
----
 42
(1 row)

SELECT * FROM y;
 a  
----
  0
  1
  2
  3
  4
  5
  6
 11
  7
 12
  8
 13
  9
 14
 10
 15
 42
(17 rows)

DROP RULE y_rule ON y;
-- check merging of outer CTE with CTE in a rule action
CREATE TEMP TABLE bug6051 AS
  select i from generate_series(1,3) as t(i);
SELECT * FROM bug6051;
 i 
---
 1
 2
 3
(3 rows)

WITH t1 AS ( DELETE FROM bug6051 RETURNING * )
INSERT INTO bug6051 SELECT * FROM t1;
SELECT * FROM bug6051;
 i 
---
 1
 2
 3
(3 rows)

CREATE TEMP TABLE bug6051_2 (i int);
CREATE RULE bug6051_ins AS ON INSERT TO bug6051 DO INSTEAD
 INSERT INTO bug6051_2
 VALUES(NEW.i);
WITH t1 AS ( DELETE FROM bug6051 RETURNING * )
INSERT INTO bug6051 SELECT * FROM t1;
SELECT * FROM bug6051;
 i 
---
(0 rows)

SELECT * FROM bug6051_2;
 i 
---
 1
 2
 3
(3 rows)

-- check INSERT...SELECT rule actions are disallowed on commands
-- that have modifyingCTEs
CREATE OR REPLACE RULE bug6051_ins AS ON INSERT TO bug6051 DO INSTEAD
 INSERT INTO bug6051_2
 SELECT NEW.i;
WITH t1 AS ( DELETE FROM bug6051 RETURNING * )
INSERT INTO bug6051 SELECT * FROM t1;
ERROR:  INSERT...SELECT rule actions are not supported for queries having data-modifying statements in WITH
-- silly example to verify that hasModifyingCTE flag is propagated
CREATE TEMP TABLE bug6051_3 AS
  SELECT a FROM generate_series(11,13) AS a;
CREATE RULE bug6051_3_ins AS ON INSERT TO bug6051_3 DO INSTEAD
  SELECT i FROM bug6051_2;
BEGIN; SET LOCAL force_parallel_mode = on;
WITH t1 AS ( DELETE FROM bug6051_3 RETURNING * )
  INSERT INTO bug6051_3 SELECT * FROM t1;
 i 
---
 1
 2
 3
 1
 2
 3
 1
 2
 3
(9 rows)

COMMIT;
SELECT * FROM bug6051_3;
 a 
---
(0 rows)

-- check case where CTE reference is removed due to optimization
EXPLAIN (VERBOSE, COSTS OFF)
SELECT q1 FROM
(
  WITH t_cte AS (SELECT * FROM int8_tbl t)
  SELECT q1, (SELECT q2 FROM t_cte WHERE t_cte.q1 = i8.q1) AS t_sub
  FROM int8_tbl i8
) ss;
              QUERY PLAN              
--------------------------------------
 Subquery Scan on ss
   Output: ss.q1
   ->  Seq Scan on public.int8_tbl i8
         Output: i8.q1, NULL::bigint
(4 rows)

SELECT q1 FROM
(
  WITH t_cte AS (SELECT * FROM int8_tbl t)
  SELECT q1, (SELECT q2 FROM t_cte WHERE t_cte.q1 = i8.q1) AS t_sub
  FROM int8_tbl i8
) ss;
        q1        
------------------
              123
              123
 4567890123456789
 4567890123456789
 4567890123456789
(5 rows)

EXPLAIN (VERBOSE, COSTS OFF)
SELECT q1 FROM
(
  WITH t_cte AS MATERIALIZED (SELECT * FROM int8_tbl t)
  SELECT q1, (SELECT q2 FROM t_cte WHERE t_cte.q1 = i8.q1) AS t_sub
  FROM int8_tbl i8
) ss;
                 QUERY PLAN                  
---------------------------------------------
 Subquery Scan on ss
   Output: ss.q1
   ->  Seq Scan on public.int8_tbl i8
         Output: i8.q1, NULL::bigint
         CTE t_cte
           ->  Seq Scan on public.int8_tbl t
                 Output: t.q1, t.q2
(7 rows)

SELECT q1 FROM
(
  WITH t_cte AS MATERIALIZED (SELECT * FROM int8_tbl t)
  SELECT q1, (SELECT q2 FROM t_cte WHERE t_cte.q1 = i8.q1) AS t_sub
  FROM int8_tbl i8
) ss;
        q1        
------------------
              123
              123
 4567890123456789
 4567890123456789
 4567890123456789
(5 rows)

-- a truly recursive CTE in the same list
WITH RECURSIVE t(a) AS (
	SELECT 0
		UNION ALL
	SELECT a+1 FROM t WHERE a+1 < 5
), t2 as (
	INSERT INTO y
		SELECT * FROM t RETURNING *
)
SELECT * FROM t2 JOIN y USING (a) ORDER BY a;
 a 
---
 0
 1
 2
 3
 4
(5 rows)

SELECT * FROM y;
 a  
----
  0
  1
  2
  3
  4
  5
  6
 11
  7
 12
  8
 13
  9
 14
 10
 15
 42
  0
  1
  2
  3
  4
(22 rows)

-- data-modifying WITH in a modifying statement
WITH t AS (
    DELETE FROM y
    WHERE a <= 10
    RETURNING *
)
INSERT INTO y SELECT -a FROM t RETURNING *;
  a  
-----
   0
  -1
  -2
  -3
  -4
  -5
  -6
  -7
  -8
  -9
 -10
   0
  -1
  -2
  -3
  -4
(16 rows)

SELECT * FROM y;
  a  
-----
  11
  12
  13
  14
  15
  42
   0
  -1
  -2
  -3
  -4
  -5
  -6
  -7
  -8
  -9
 -10
   0
  -1
  -2
  -3
  -4
(22 rows)

-- check that WITH query is run to completion even if outer query isn't
WITH t AS (
    UPDATE y SET a = a * 100 RETURNING *
)
SELECT * FROM t LIMIT 10;
  a   
------
 1100
 1200
 1300
 1400
 1500
 4200
    0
 -100
 -200
 -300
(10 rows)

SELECT * FROM y;
   a   
-------
  1100
  1200
  1300
  1400
  1500
  4200
     0
  -100
  -200
  -300
  -400
  -500
  -600
  -700
  -800
  -900
 -1000
     0
  -100
  -200
  -300
  -400
(22 rows)

-- data-modifying WITH containing INSERT...ON CONFLICT DO UPDATE
CREATE TABLE withz AS SELECT i AS k, (i || ' v')::text v FROM generate_series(1, 16, 3) i;
ALTER TABLE withz ADD UNIQUE (k);
WITH t AS (
    INSERT INTO withz SELECT i, 'insert'
    FROM generate_series(0, 16) i
    ON CONFLICT (k) DO UPDATE SET v = withz.v || ', now update'
    RETURNING *
)
SELECT * FROM t JOIN y ON t.k = y.a ORDER BY a, k;
 k |   v    | a 
---+--------+---
 0 | insert | 0
 0 | insert | 0
(2 rows)

-- Test EXCLUDED.* reference within CTE
WITH aa AS (
    INSERT INTO withz VALUES(1, 5) ON CONFLICT (k) DO UPDATE SET v = EXCLUDED.v
    WHERE withz.k != EXCLUDED.k
    RETURNING *
)
SELECT * FROM aa;
 k | v 
---+---
(0 rows)

-- New query/snapshot demonstrates side-effects of previous query.
SELECT * FROM withz ORDER BY k;
 k  |        v         
----+------------------
  0 | insert
  1 | 1 v, now update
  2 | insert
  3 | insert
  4 | 4 v, now update
  5 | insert
  6 | insert
  7 | 7 v, now update
  8 | insert
  9 | insert
 10 | 10 v, now update
 11 | insert
 12 | insert
 13 | 13 v, now update
 14 | insert
 15 | insert
 16 | 16 v, now update
(17 rows)

--
-- Ensure subqueries within the update clause work, even if they
-- reference outside values
--
WITH aa AS (SELECT 1 a, 2 b)
INSERT INTO withz VALUES(1, 'insert')
ON CONFLICT (k) DO UPDATE SET v = (SELECT b || ' update' FROM aa WHERE a = 1 LIMIT 1);
WITH aa AS (SELECT 1 a, 2 b)
INSERT INTO withz VALUES(1, 'insert')
ON CONFLICT (k) DO UPDATE SET v = ' update' WHERE withz.k = (SELECT a FROM aa);
WITH aa AS (SELECT 1 a, 2 b)
INSERT INTO withz VALUES(1, 'insert')
ON CONFLICT (k) DO UPDATE SET v = (SELECT b || ' update' FROM aa WHERE a = 1 LIMIT 1);
WITH aa AS (SELECT 'a' a, 'b' b UNION ALL SELECT 'a' a, 'b' b)
INSERT INTO withz VALUES(1, 'insert')
ON CONFLICT (k) DO UPDATE SET v = (SELECT b || ' update' FROM aa WHERE a = 'a' LIMIT 1);
WITH aa AS (SELECT 1 a, 2 b)
INSERT INTO withz VALUES(1, (SELECT b || ' insert' FROM aa WHERE a = 1 ))
ON CONFLICT (k) DO UPDATE SET v = (SELECT b || ' update' FROM aa WHERE a = 1 LIMIT 1);
-- Update a row more than once, in different parts of a wCTE. That is
-- an allowed, presumably very rare, edge case, but since it was
-- broken in the past, having a test seems worthwhile.
WITH simpletup AS (
  SELECT 2 k, 'Green' v),
upsert_cte AS (
  INSERT INTO withz VALUES(2, 'Blue') ON CONFLICT (k) DO
    UPDATE SET (k, v) = (SELECT k, v FROM simpletup WHERE simpletup.k = withz.k)
    RETURNING k, v)
INSERT INTO withz VALUES(2, 'Red') ON CONFLICT (k) DO
UPDATE SET (k, v) = (SELECT k, v FROM upsert_cte WHERE upsert_cte.k = withz.k)
RETURNING k, v;
 k | v 
---+---
(0 rows)

DROP TABLE withz;
-- WITH referenced by MERGE statement
CREATE TABLE m AS SELECT i AS k, (i || ' v')::text v FROM generate_series(1, 16, 3) i;
ALTER TABLE m ADD UNIQUE (k);
WITH RECURSIVE cte_basic AS (SELECT 1 a, 'cte_basic val' b)
MERGE INTO m USING (select 0 k, 'merge source SubPlan' v) o ON m.k=o.k
WHEN MATCHED THEN UPDATE SET v = (SELECT b || ' merge update' FROM cte_basic WHERE cte_basic.a = m.k LIMIT 1)
WHEN NOT MATCHED THEN INSERT VALUES(o.k, o.v);
ERROR:  WITH RECURSIVE is not supported for MERGE statement
-- Basic:
WITH cte_basic AS MATERIALIZED (SELECT 1 a, 'cte_basic val' b)
MERGE INTO m USING (select 0 k, 'merge source SubPlan' v offset 0) o ON m.k=o.k
WHEN MATCHED THEN UPDATE SET v = (SELECT b || ' merge update' FROM cte_basic WHERE cte_basic.a = m.k LIMIT 1)
WHEN NOT MATCHED THEN INSERT VALUES(o.k, o.v);
-- Examine
SELECT * FROM m where k = 0;
 k |          v           
---+----------------------
 0 | merge source SubPlan
(1 row)

-- See EXPLAIN output for same query:
EXPLAIN (VERBOSE, COSTS OFF)
WITH cte_basic AS MATERIALIZED (SELECT 1 a, 'cte_basic val' b)
MERGE INTO m USING (select 0 k, 'merge source SubPlan' v offset 0) o ON m.k=o.k
WHEN MATCHED THEN UPDATE SET v = (SELECT b || ' merge update' FROM cte_basic WHERE cte_basic.a = m.k LIMIT 1)
WHEN NOT MATCHED THEN INSERT VALUES(o.k, o.v);
                            QUERY PLAN                             
-------------------------------------------------------------------
 Merge on public.m
   CTE cte_basic
     ->  Result
           Output: 1, 'cte_basic val'::text
   ->  Hash Right Join
         Output: m.ctid, o.k, o.v, o.*
         Hash Cond: (m.k = o.k)
         ->  Seq Scan on public.m
               Output: m.ctid, m.k
         ->  Hash
               Output: o.k, o.v, o.*
               ->  Subquery Scan on o
                     Output: o.k, o.v, o.*
                     ->  Result
                           Output: 0, 'merge source SubPlan'::text
   SubPlan 2
     ->  Limit
           Output: ((cte_basic.b || ' merge update'::text))
           ->  CTE Scan on cte_basic
                 Output: (cte_basic.b || ' merge update'::text)
                 Filter: (cte_basic.a = m.k)
(21 rows)

-- InitPlan
WITH cte_init AS MATERIALIZED (SELECT 1 a, 'cte_init val' b)
MERGE INTO m USING (select 1 k, 'merge source InitPlan' v offset 0) o ON m.k=o.k
WHEN MATCHED THEN UPDATE SET v = (SELECT b || ' merge update' FROM cte_init WHERE a = 1 LIMIT 1)
WHEN NOT MATCHED THEN INSERT VALUES(o.k, o.v);
-- Examine
SELECT * FROM m where k = 1;
 k |             v             
---+---------------------------
 1 | cte_init val merge update
(1 row)

-- See EXPLAIN output for same query:
EXPLAIN (VERBOSE, COSTS OFF)
WITH cte_init AS MATERIALIZED (SELECT 1 a, 'cte_init val' b)
MERGE INTO m USING (select 1 k, 'merge source InitPlan' v offset 0) o ON m.k=o.k
WHEN MATCHED THEN UPDATE SET v = (SELECT b || ' merge update' FROM cte_init WHERE a = 1 LIMIT 1)
WHEN NOT MATCHED THEN INSERT VALUES(o.k, o.v);
                             QUERY PLAN                             
--------------------------------------------------------------------
 Merge on public.m
   CTE cte_init
     ->  Result
           Output: 1, 'cte_init val'::text
   InitPlan 2 (returns $1)
     ->  Limit
           Output: ((cte_init.b || ' merge update'::text))
           ->  CTE Scan on cte_init
                 Output: (cte_init.b || ' merge update'::text)
                 Filter: (cte_init.a = 1)
   ->  Hash Right Join
         Output: m.ctid, o.k, o.v, o.*
         Hash Cond: (m.k = o.k)
         ->  Seq Scan on public.m
               Output: m.ctid, m.k
         ->  Hash
               Output: o.k, o.v, o.*
               ->  Subquery Scan on o
                     Output: o.k, o.v, o.*
                     ->  Result
                           Output: 1, 'merge source InitPlan'::text
(21 rows)

-- MERGE source comes from CTE:
WITH merge_source_cte AS MATERIALIZED (SELECT 15 a, 'merge_source_cte val' b)
MERGE INTO m USING (select * from merge_source_cte) o ON m.k=o.a
WHEN MATCHED THEN UPDATE SET v = (SELECT b || merge_source_cte.*::text || ' merge update' FROM merge_source_cte WHERE a = 15)
WHEN NOT MATCHED THEN INSERT VALUES(o.a, o.b || (SELECT merge_source_cte.*::text || ' merge insert' FROM merge_source_cte));
-- Examine
SELECT * FROM m where k = 15;
 k  |                              v                               
----+--------------------------------------------------------------
 15 | merge_source_cte val(15,"merge_source_cte val") merge insert
(1 row)

-- See EXPLAIN output for same query:
EXPLAIN (VERBOSE, COSTS OFF)
WITH merge_source_cte AS MATERIALIZED (SELECT 15 a, 'merge_source_cte val' b)
MERGE INTO m USING (select * from merge_source_cte) o ON m.k=o.a
WHEN MATCHED THEN UPDATE SET v = (SELECT b || merge_source_cte.*::text || ' merge update' FROM merge_source_cte WHERE a = 15)
WHEN NOT MATCHED THEN INSERT VALUES(o.a, o.b || (SELECT merge_source_cte.*::text || ' merge insert' FROM merge_source_cte));
                                             QUERY PLAN                                              
-----------------------------------------------------------------------------------------------------
 Merge on public.m
   CTE merge_source_cte
     ->  Result
           Output: 15, 'merge_source_cte val'::text
   InitPlan 2 (returns $1)
     ->  CTE Scan on merge_source_cte merge_source_cte_1
           Output: ((merge_source_cte_1.b || (merge_source_cte_1.*)::text) || ' merge update'::text)
           Filter: (merge_source_cte_1.a = 15)
   InitPlan 3 (returns $2)
     ->  CTE Scan on merge_source_cte merge_source_cte_2
           Output: ((merge_source_cte_2.*)::text || ' merge insert'::text)
   ->  Hash Right Join
         Output: m.ctid, merge_source_cte.a, merge_source_cte.b, merge_source_cte.*
         Hash Cond: (m.k = merge_source_cte.a)
         ->  Seq Scan on public.m
               Output: m.ctid, m.k
         ->  Hash
               Output: merge_source_cte.a, merge_source_cte.b, merge_source_cte.*
               ->  CTE Scan on merge_source_cte
                     Output: merge_source_cte.a, merge_source_cte.b, merge_source_cte.*
(20 rows)

DROP TABLE m;
-- check that run to completion happens in proper ordering
TRUNCATE TABLE y;
INSERT INTO y SELECT generate_series(1, 3);
CREATE TEMPORARY TABLE yy (a INTEGER);
WITH RECURSIVE t1 AS (
  INSERT INTO y SELECT * FROM y RETURNING *
), t2 AS (
  INSERT INTO yy SELECT * FROM t1 RETURNING *
)
SELECT 1;
 ?column? 
----------
        1
(1 row)

SELECT * FROM y;
 a 
---
 1
 2
 3
 1
 2
 3
(6 rows)

SELECT * FROM yy;
 a 
---
 1
 2
 3
(3 rows)

WITH RECURSIVE t1 AS (
  INSERT INTO yy SELECT * FROM t2 RETURNING *
), t2 AS (
  INSERT INTO y SELECT * FROM y RETURNING *
)
SELECT 1;
 ?column? 
----------
        1
(1 row)

SELECT * FROM y;
 a 
---
 1
 2
 3
 1
 2
 3
 1
 2
 3
 1
 2
 3
(12 rows)

SELECT * FROM yy;
 a 
---
 1
 2
 3
 1
 2
 3
 1
 2
 3
(9 rows)

-- triggers
TRUNCATE TABLE y;
INSERT INTO y SELECT generate_series(1, 10);
CREATE FUNCTION y_trigger() RETURNS trigger AS $$
begin
  raise notice 'y_trigger: a = %', new.a;
  return new;
end;
$$ LANGUAGE plpgsql;
CREATE TRIGGER y_trig BEFORE INSERT ON y FOR EACH ROW
    EXECUTE PROCEDURE y_trigger();
WITH t AS (
    INSERT INTO y
    VALUES
        (21),
        (22),
        (23)
    RETURNING *
)
SELECT * FROM t;
NOTICE:  y_trigger: a = 21
NOTICE:  y_trigger: a = 22
NOTICE:  y_trigger: a = 23
 a  
----
 21
 22
 23
(3 rows)

SELECT * FROM y;
 a  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 21
 22
 23
(13 rows)

DROP TRIGGER y_trig ON y;
CREATE TRIGGER y_trig AFTER INSERT ON y FOR EACH ROW
    EXECUTE PROCEDURE y_trigger();
WITH t AS (
    INSERT INTO y
    VALUES
        (31),
        (32),
        (33)
    RETURNING *
)
SELECT * FROM t LIMIT 1;
NOTICE:  y_trigger: a = 31
NOTICE:  y_trigger: a = 32
NOTICE:  y_trigger: a = 33
 a  
----
 31
(1 row)

SELECT * FROM y;
 a  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 21
 22
 23
 31
 32
 33
(16 rows)

DROP TRIGGER y_trig ON y;
CREATE OR REPLACE FUNCTION y_trigger() RETURNS trigger AS $$
begin
  raise notice 'y_trigger';
  return null;
end;
$$ LANGUAGE plpgsql;
CREATE TRIGGER y_trig AFTER INSERT ON y FOR EACH STATEMENT
    EXECUTE PROCEDURE y_trigger();
WITH t AS (
    INSERT INTO y
    VALUES
        (41),
        (42),
        (43)
    RETURNING *
)
SELECT * FROM t;
NOTICE:  y_trigger
 a  
----
 41
 42
 43
(3 rows)

SELECT * FROM y;
 a  
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 21
 22
 23
 31
 32
 33
 41
 42
 43
(19 rows)

DROP TRIGGER y_trig ON y;
DROP FUNCTION y_trigger();
-- WITH attached to inherited UPDATE or DELETE
CREATE TEMP TABLE parent ( id int, val text );
CREATE TEMP TABLE child1 ( ) INHERITS ( parent );
CREATE TEMP TABLE child2 ( ) INHERITS ( parent );
INSERT INTO parent VALUES ( 1, 'p1' );
INSERT INTO child1 VALUES ( 11, 'c11' ),( 12, 'c12' );
INSERT INTO child2 VALUES ( 23, 'c21' ),( 24, 'c22' );
WITH rcte AS ( SELECT sum(id) AS totalid FROM parent )
UPDATE parent SET id = id + totalid FROM rcte;
SELECT * FROM parent;
 id | val 
----+-----
 72 | p1
 82 | c11
 83 | c12
 94 | c21
 95 | c22
(5 rows)

WITH wcte AS ( INSERT INTO child1 VALUES ( 42, 'new' ) RETURNING id AS newid )
UPDATE parent SET id = id + newid FROM wcte;
SELECT * FROM parent;
 id  | val 
-----+-----
 114 | p1
  42 | new
 124 | c11
 125 | c12
 136 | c21
 137 | c22
(6 rows)

WITH rcte AS ( SELECT max(id) AS maxid FROM parent )
DELETE FROM parent USING rcte WHERE id = maxid;
SELECT * FROM parent;
 id  | val 
-----+-----
 114 | p1
  42 | new
 124 | c11
 125 | c12
 136 | c21
(5 rows)

WITH wcte AS ( INSERT INTO child2 VALUES ( 42, 'new2' ) RETURNING id AS newid )
DELETE FROM parent USING wcte WHERE id = newid;
SELECT * FROM parent;
 id  | val  
-----+------
 114 | p1
 124 | c11
 125 | c12
 136 | c21
  42 | new2
(5 rows)

-- check EXPLAIN VERBOSE for a wCTE with RETURNING
EXPLAIN (VERBOSE, COSTS OFF)
WITH wcte AS ( INSERT INTO int8_tbl VALUES ( 42, 47 ) RETURNING q2 )
DELETE FROM a_star USING wcte WHERE aa = q2;
                                QUERY PLAN                                 
---------------------------------------------------------------------------
 Delete on public.a_star
   Delete on public.a_star a_star_1
   Delete on public.b_star a_star_2
   Delete on public.c_star a_star_3
   Delete on public.d_star a_star_4
   Delete on public.e_star a_star_5
   Delete on public.f_star a_star_6
   CTE wcte
     ->  Insert on public.int8_tbl
           Output: int8_tbl.q2
           ->  Result
                 Output: '42'::bigint, '47'::bigint
   ->  Hash Join
         Output: wcte.*, a_star.tableoid, a_star.ctid
         Hash Cond: (a_star.aa = wcte.q2)
         ->  Append
               ->  Seq Scan on public.a_star a_star_1
                     Output: a_star_1.aa, a_star_1.tableoid, a_star_1.ctid
               ->  Seq Scan on public.b_star a_star_2
                     Output: a_star_2.aa, a_star_2.tableoid, a_star_2.ctid
               ->  Seq Scan on public.c_star a_star_3
                     Output: a_star_3.aa, a_star_3.tableoid, a_star_3.ctid
               ->  Seq Scan on public.d_star a_star_4
                     Output: a_star_4.aa, a_star_4.tableoid, a_star_4.ctid
               ->  Seq Scan on public.e_star a_star_5
                     Output: a_star_5.aa, a_star_5.tableoid, a_star_5.ctid
               ->  Seq Scan on public.f_star a_star_6
                     Output: a_star_6.aa, a_star_6.tableoid, a_star_6.ctid
         ->  Hash
               Output: wcte.*, wcte.q2
               ->  CTE Scan on wcte
                     Output: wcte.*, wcte.q2
(32 rows)

-- error cases
-- data-modifying WITH tries to use its own output
WITH RECURSIVE t AS (
	INSERT INTO y
		SELECT * FROM t
)
VALUES(FALSE);
ERROR:  recursive query "t" must not contain data-modifying statements
LINE 1: WITH RECURSIVE t AS (
                       ^
-- no RETURNING in a referenced data-modifying WITH
WITH t AS (
	INSERT INTO y VALUES(0)
)
SELECT * FROM t;
ERROR:  WITH query "t" does not have a RETURNING clause
LINE 4: SELECT * FROM t;
                      ^
-- data-modifying WITH allowed only at the top level
SELECT * FROM (
	WITH t AS (UPDATE y SET a=a+1 RETURNING *)
	SELECT * FROM t
) ss;
ERROR:  WITH clause containing a data-modifying statement must be at the top level
LINE 2:  WITH t AS (UPDATE y SET a=a+1 RETURNING *)
              ^
-- most variants of rules aren't allowed
CREATE RULE y_rule AS ON INSERT TO y WHERE a=0 DO INSTEAD DELETE FROM y;
WITH t AS (
	INSERT INTO y VALUES(0)
)
VALUES(FALSE);
ERROR:  conditional DO INSTEAD rules are not supported for data-modifying statements in WITH
CREATE OR REPLACE RULE y_rule AS ON INSERT TO y DO INSTEAD NOTHING;
WITH t AS (
	INSERT INTO y VALUES(0)
)
VALUES(FALSE);
ERROR:  DO INSTEAD NOTHING rules are not supported for data-modifying statements in WITH
CREATE OR REPLACE RULE y_rule AS ON INSERT TO y DO INSTEAD NOTIFY foo;
WITH t AS (
	INSERT INTO y VALUES(0)
)
VALUES(FALSE);
ERROR:  DO INSTEAD NOTIFY rules are not supported for data-modifying statements in WITH
CREATE OR REPLACE RULE y_rule AS ON INSERT TO y DO ALSO NOTIFY foo;
WITH t AS (
	INSERT INTO y VALUES(0)
)
VALUES(FALSE);
ERROR:  DO ALSO rules are not supported for data-modifying statements in WITH
CREATE OR REPLACE RULE y_rule AS ON INSERT TO y
  DO INSTEAD (NOTIFY foo; NOTIFY bar);
WITH t AS (
	INSERT INTO y VALUES(0)
)
VALUES(FALSE);
ERROR:  multi-statement DO INSTEAD rules are not supported for data-modifying statements in WITH
DROP RULE y_rule ON y;
-- check that parser lookahead for WITH doesn't cause any odd behavior
create table foo (with baz);  -- fail, WITH is a reserved word
ERROR:  syntax error at or near "with"
LINE 1: create table foo (with baz);
                          ^
create table foo (with ordinality);  -- fail, WITH is a reserved word
ERROR:  syntax error at or near "with"
LINE 1: create table foo (with ordinality);
                          ^
with ordinality as (select 1 as x) select * from ordinality;
 x 
---
 1
(1 row)

-- check sane response to attempt to modify CTE relation
WITH with_test AS (SELECT 42) INSERT INTO with_test VALUES (1);
ERROR:  relation "with_test" does not exist
LINE 1: WITH with_test AS (SELECT 42) INSERT INTO with_test VALUES (...
                                                  ^
-- check response to attempt to modify table with same name as a CTE (perhaps
-- surprisingly it works, because CTEs don't hide tables from data-modifying
-- statements)
create temp table with_test (i int);
with with_test as (select 42) insert into with_test select * from with_test;
select * from with_test;
 i  
----
 42
(1 row)

drop table with_test;