Continuation of #11757

Basic WITH got implemented in #12540
We should extend it with support for the RECURSIVE clause to support the query mentioned in #11757. A simpler version looks like this:

WITH RECURSIVE t(n) AS (
    VALUES (1)
  UNION ALL
    SELECT n+1 FROM t WHERE n < 100
)
SELECT sum(n) FROM t;

                               QUERY PLAN
-------------------------------------------------------------------------
 Aggregate  (cost=3.65..3.66 rows=1 width=8)
   CTE t
     ->  Recursive Union  (cost=0.00..2.95 rows=31 width=4)
           ->  Result  (cost=0.00..0.01 rows=1 width=4)
           ->  WorkTable Scan on t t_1  (cost=0.00..0.23 rows=3 width=4)
                 Filter: (n < 100)
   ->  CTE Scan on t  (cost=0.00..0.62 rows=31 width=4)

See PostgreSQL recursive queries

Resources and references

• cockroachdb/cockroach@7bc04d7
• https://calcite.apache.org/docs/algebra.html#recursive-queries
• https://calcite.apache.org/javadocAggregate/org/apache/calcite/rel/core/RepeatUnion.html

Out of scope

• Usage of intermediate tables (only in-memory buffering of the working table with ram accounting)
• Syntax sugar (SEARCH clause) for Search Order (depth- or breadth-first sort column)
• CYCLE clause to simplify cycle detection
• Correlations (with other WITHS or outside relations)

Discussion

• 20+ for now because implementation wasn't clear to everyone