Home > APIs > YSQL > The SQL language > WITH clause >

The recursive CTE

The optional RECURSIVE keyword fundamentally changes the meaning of a CTE. The recursive variant lets you implement SQL solutions that, without it, at best require verbose formulations involving, for example, self-joins. In the limit, the recursive CTE lets you implement SQL solutions that otherwise would require procedural programming.

Syntax

When the optional RECURSIVE keyword is used, the common_table_expression must be a SELECT statement—and this must have a specific form as the UNION or UNION ALL of the so-called non-recursive term and the recursive term, thus:

with
  recursive r(c1, c2, ...) as (

    -- Non-recursive term.
    (
      select ...
    )

    union [all]

    -- Recursive term. Notice the so-called recursive self-reference to r.
    (
      select ... from r ...
    )
  )
select ... from r ...;

The following minimal example is found in very many articles and in the documentation for several SQL databases.

with
  recursive r(n) as (

-- Non-recursive term.
    (
      values(1)
    )

    union all

    -- Recursive term.
    (
      select n + 1
      from r
      where n < 5
    )
  )
select n from r order by n;

Notice that the parentheses that surround the non-recursive term and the recursive term are not required. They are used for clarity. See the section The recursive term must be parenthesised to allow this to use a WITH clause for a scenario where the parentheses are essential.

This is the result:

The Semantics section explains how a recursive CTE is evaluated. When you understand this, you can predict the result of this minimal example and, by induction, the result of any arbitrarily complex example.

Restrictions

The WITH clause syntax (see the section WITH clause—SQL syntax and semantics implies a pair of restrictions.

Grammar
Diagram

with_clause ::= [ WITH [ RECURSIVE ] 
                  { common_table_expression [ , ... ] } ]

with_clause

It shows that you can use the RECURSIVE keyword only immediately after the keyword WITH and that, therefore only the first CTE in a WITH clause can be a recursive CTE. These restrictions are illustrated in the immediately following sections Maximum one recursive CTE and The recursive CTE must be first in the clause.

Maximum one recursive CTE

The attempt to define more than one recursive CTE within a particular WITH clause causes a generic 42601 syntax error. You can work around this restriction by pushing it down by one level of nesting, thus:

with
  a1(n) as (
    select 42),

  a2(n) as (
    with
      recursive r(n) as (
        values(1)

        union all

        select n + 1
        from r
        where n < 5
        )
    select n from r),

  a3(n) as (
    select 99)

(
  select n from a1
  union all
  select n from a2
  union all
  select n from a3
)
order by n desc;

This is the result:

The recursive CTE must be first in the clause

This code:

with
  a1(n) as (
    select 42),

  recursive r(n) as (
    values(1)

    union all

    select n + 1
    from r
    where n < 5
    ),

  a2(n) as (
    select 99)

(
  select n from r
  union all
  select n from a2
)
order by n desc;

causes a 42601 syntax error to be reported for the line recursive r(n) as... If you remove this:

a1(n) as (
    select 42),

then the statement executes without error to produce this result:

Alternatively, you can push down the recursive CTE one level as shown above.

The recursive term must be parenthesised to allow this to use a WITH clause

First try this positive example:

with
  recursive r(n) as (
    (
      with a1(n) as (
        values(1))
      select n from a1
    )

    union all

    (
      with a2(n) as (
        select n + 1
        from r
        where n < 5)
      select n from a2
    )
  )
select n from r order by n;

Notice that this is simply a syntax example. Using WITH clauses within the recursive and non-recursive terms brings no value. The statement executes without error and produces this result:

Next, first, remove the parenthesis pair that surrounds the non-recursive term. The statement runs without error to produce the same result. Now, re-instate this pair and remove the parenthesis pair that surrounds the recursive term. You get the generic 42601 syntax error, reported for this line:

with a2(n) as (

Aggregate functions are not allowed in a recursive term

Try this:

with
  recursive r(n) as (
    (
      values(1)
    )

    union all

    (
      select max(n) + 1
      from r
      where n < 5
    )
  )
select n from r order by n;

It causes this specific error:

42P19: aggregate functions are not allowed in a recursive query's recursive term

The restriction, more carefully stated, disallows aggregate functions when the FROM list item is the recursive self-reference. By extension, the keywords GROUP BY and HAVING are also disallowed when the FROM list item is the recursive self-reference.

Here is an example that executes without error that uses an aggregate function on a FROM list item that is not the recursive self-reference:

set client_min_messages = warning;
drop table if exists t cascade;
create table t(n int primary key);
insert into t(n) values (1), (2), (3);

with
  recursive r(n) as (
    (
      values(1)
    )

    union all

    (
      select n + (select min(n) from t)
      from r
      where n < 5
    )
  )
select n from r order by n;

This is the results:

Semantics

You can find various formulations of the following explanation by Internet search. In particular, here is a version from the PostgreSQL Version 11 documentation.

In informal prose:

The non-recursive term is invoked just once and establishes a starting relation.
The recursive term is invoked time and again. On its first invocation, it acts on the relation produced by the evaluation of the non-recursive term. On subsequent invocations, it acts on the relation produced by its previous invocation.
Each successive term evaluation appends its output to the growing result of the recursive CTE.
The repeating invocation of the recursive term stops when it produces an empty relation.

Pseudocode definition of the semantics

A compact, and exact, formulation is given by using pseudocode. The final_results table, the previous_results table, and the "TEMP_RESULTS" table are transient, statement-duration, structures.

Purge the final_results table and the previous_results table.

Evaluate the non-recursive term, inserting the resulting rows into the previous_results table.

Insert the contents of the previous_results table into the final_results table.

while the previous_results table is not empty loop

Purge the temp_results table.

Evaluate the recursive term using the current contents of the previous_results table for the recursive self-reference, inserting the resulting rows into the temp_results table.

Purge the previous_results table and insert the contents of the temp_results table.

Append the contents of the temp_results table into the final_results table.

end loop

Deliver the present contents of the final_results table so that whatever follows the recursive CTE can use them.

PL/pgSQL procedure implementation of the pseudocode : example 1

This pseudocode can be easily implemented, as a PL/pgSQL procedure, for the minimal example shown in the Syntax section above. First, do this set-up:

set client_min_messages = warning;

drop procedure if exists recursive_with_semantics_1 cascade;
drop table if exists final_results cascade;
drop table if exists previous_results cascade;
drop table if exists temp_results cascade;

create table final_results(n int primary key);
create table previous_results(n int primary key);
create table temp_results(n int primary key);

Now create the procedure:

create procedure recursive_with_semantics_1(max_n in int)
  language plpgsql
as $body$
begin
  -- Emulate the non-recursive term.
  delete from final_results;
  delete from previous_results;
  insert into previous_results(n) values(1);
  insert into final_results(n) select n from previous_results;

  -- Emulate the recursive term.
  while ((select count(*) from previous_results) > 0) loop
    delete from temp_results;
    insert into temp_results
    select n + 1 from previous_results
    where n < max_n;

    delete from previous_results;
    insert into previous_results(n) select n from temp_results;
    insert into final_results(n) select n from temp_results;
  end loop;
end;
$body$;

Notice that the PostgreSQL Version 11 documentation says this:

Strictly speaking, this process is iteration not recursion, but RECURSIVE is the terminology chosen by the SQL standards committee.

This is a somewhat dubious claim because, in any language, recursion is implemented at a lower level in the hierarchy of abstractions, as iteration. The code of the PL/pgSQL procedure, because it uses a WHILE loop, makes this point explicitly.

Now invoke the procedure and observe the contents of the final_results table:

call recursive_with_semantics_1(5);
select n from final_results order by 1;

The result is identical to that produced by the SQL implementation that it emulates (shown in the Syntax section above).

PL/pgSQL procedure implementation of the pseudocode : example 2

Try this extended version of the minimal example:

with
  recursive r(c1, c2) as (

    -- Non-recursive term.
    (
      values (0, 1), (0, 2), (0, 3)
    )

    union all

    -- Recursive term.
    (
      select c1 + 1, c2 + 1
      from r
      where c1 < 4
    )
  )
select c1, c2 from r order by c1, c2;

This is the result:

The whitespace was added by hand to group the results into those produced first by evaluating the non-recursive term and then those produced by each successive repeat evaluation of the recursive term.

The procedural implementation that emulates the pseudocode is a natural extension of the first example. First, do this set-up:

set client_min_messages = warning;

drop procedure if exists recursive_with_semantics_2 cascade;
drop table if exists final_results cascade;
drop table if exists previous_results cascade;
drop table if exists temp_results cascade;

create table final_results(
  c1 int not null,
  c2 int not null,
  constraint recursive_cte_results_pk primary key(c1, c2));

create table previous_results(
  c1 int not null,
  c2 int not null,
  constraint previous_results_pk primary key(c1, c2));

create table temp_results(
  c1 int not null,
  c2 int not null,
  constraint temp_results_pk primary key(c1, c2));

Now create the procedure:

create procedure recursive_with_semantics_2(max_c1 in int)
  language plpgsql
as $body$
begin
  -- Emulate the non-recursive term.
  delete from final_results;
  delete from previous_results;
  insert into previous_results(c1, c2) values (0, 1), (0, 2), (0, 3);
  insert into final_results(c1, c2) select c1, c2 from previous_results;

  -- Emulate the recursive term.
  while ((select count(*) from previous_results) > 0) loop
    delete from temp_results;
    insert into temp_results
    select c1 + 1, c2 + 1 from previous_results
    where c1 < max_c1;

    delete from previous_results;
    insert into previous_results(c1, c2) select c1, c2 from temp_results;
    insert into final_results(c1, c2) select c1, c2 from temp_results;
  end loop;
end;
$body$;

Notice that, here, each iteration accumulates three rows.

Now invoke the procedure and observe the contents of the final_results table:

call recursive_with_semantics_2(4);
select c1, c2 from final_results order by c1, c2;

The result is identical to that produced by the SQL implementation that it emulates.

The section Using a recursive CTE to traverse graphs of all kinds shows how to do graph traversal of undirected and directed graphs using application-agnostic examples. When the graph is cyclic, it shows how to detect and prevent endless repetition.

Case studies

The remaining sections (in the overall main WITH clause parent section) describe how to use a recursive CTE to implement path finding for the special case of a hierarchy, for the general case of an undirected cyclic graph (and other more restricted kinds of graph), and for a specific application of the approach for the general graph.

Case study—Using a recursive CTE to traverse an employee hierarchy describes the use case (traversing an employee hierarchy) that is most commonly used to illustrate a practical application of the recursive CTE. Different SQL databases with different variants of SQL use importantly different approaches. PostgreSQL, and therefore YSQL, have only standard SQL features here (and not, therefore, the CONNECT BY PRIOR feature that is typically used with Oracle Database). Neither do they have dedicated syntax to ask for breadth-first or depth-first traversal. Rather, these two kinds of traversal must be programmed explicitly. The explicit solutions use array functionality and are straightforward. Moreover, using this approach allows various second-order display choices easily to be implemented.
Using a recursive CTE to traverse graphs of all kinds leading to Using a recursive CTE to compute Bacon Numbers for actors listed in the IMDb. The approach to traversing graphs of all kinds is a natural extension of the approach shown for the employee hierarchy traversal. It adds logic to accommodate the fact that the edges are undirected and for cycle prevention. However, this straightforward approach collapses when, as is the case with the IMBd data, there are very many paths between most pairs of actors. This brings an exponential explosion in both time to completion and use of memory. The Bacon Numbers account shows how to avoid this collapse by implementing the algorithm that the recursive CTE implements using explicit SQL issued from a PL/pgSQL stored procedure. This allows early pruning to leave only the shortest paths with each repetition of the recursive term.