Introduction to MySQL 8.0 Recursive Common Table Expression (Part 2)

By Corrado Pandiani Insight for DBAs, MySQL, Percona Software cte, MySQL, Percona Software, recursive 2 Comments

This is the second part of a two-articles series. In the first part, we introduced the Common Table Expression (CTE), a new feature available on MySQL 8.0 as well as Percona Server for MySQL 8.0. In this article, we’ll present the Recursive Common Table Expression. SQL is generally poor at recursive structures, but it is now possible on MySQL to write recursive queries. Before MySQL 8.0, recursion was possible only by creating stored routines.

What is a Recursive Common Table Expression?

A recursive CTE is one having a subquery that refers to its own name. It is particularly useful in the following cases:

To generate series
Hierarchical or tree-structured data traversal

Let’s see the main components of a recursive CTE. The following is the syntax to create it:

WITH RECURSIVE cte AS (
   initial_query    -- "seed" member
   UNION ALL
   recursive_query    -- recusive member that references to the same CTE name
)
SELECT * FROM cte;    -- main query

WITH RECURSIVE cte AS (

initial_query -- "seed" member

UNION ALL

recursive_query -- recusive member that references to the same CTE name

)

SELECT * FROM cte; -- main query

First of all, the clause RECURSIVE is mandatory, and then there are two mandatory components. The seed member is the initial query, the one that will be executed at the first iteration. The recursive member is the query containing the reference to the same CTE name. This second component will generate all the remaining items of the main query.

The process stops when an iteration does not generate any rows. Be aware of that in order to avoid generating a lot of iterations that can exhaust the memory.

It is important for recursive CTEs that the recursive member includes a condition to terminate the recursion. As a development technique you can force termination by placing a limit on execution time:

The cte_max_recursion_depth system variable enforces a limit on the number of recursion levels for CTEs. The server terminates the execution of any CTE that recurses more levels than the value of this variable. The default value is 1000.
The max_execution_time system variable enforces an execution timeout for SELECT statements executed within the current session.
The MAX_EXECUTION_TIME optimizer hint enforces a per-query execution timeout for the SELECT statement in which it appears.

Generate Series

Let’s see now some simple usage of Recursive CTE to generate series.

One-Level Sequence

First, create a simple series of integer numbers from 1 to 10. This a one-level sequence because the N+1 value is a function of the previous one N only.

WITH RECURSIVE natural_sequence AS
  ( SELECT 1 AS n       -- seed member: our sequence starts from 1
    UNION ALL
    SELECT n + 1 FROM natural_sequence    -- recursive member: reference to itself
    WHERE n < 10                          -- stop condition
  )
SELECT * FROM natural_sequence;           -- main query
+------+
| n    |
+------+
|    1 |
|    2 |
|    3 |
|    4 |
|    5 |
|    6 |
|    7 |
|    8 |
|    9 |
|   10 |
+------+

# let's see what happen if we miss the stop condition
mysql> WITH RECURSIVE natural_sequence AS ( SELECT 1 AS n   UNION ALL SELECT n + 1 FROM natural_sequence   ) SELECT * FROM natural_sequence;
ERROR 3636 (HY000): Recursive query aborted after 1001 iterations. Try increasing @@cte_max_recursion_depth to a larger value.

WITH RECURSIVE natural_sequence AS

( SELECT 1 AS n -- seed member: our sequence starts from 1

UNION ALL

SELECT n + 1 FROM natural_sequence -- recursive member: reference to itself

WHERE n < 10 -- stop condition

)

SELECT * FROM natural_sequence; -- main query

+------+

| n |

+------+

| 1 |

| 2 |

| 3 |

| 4 |

| 5 |

| 6 |

| 7 |

| 8 |

| 9 |

| 10 |

+------+

# let's see what happen if we miss the stop condition

mysql> WITH RECURSIVE natural_sequence AS ( SELECT 1 AS n UNION ALL SELECT n + 1 FROM natural_sequence ) SELECT * FROM natural_sequence;

ERROR 3636 (HY000): Recursive query aborted after 1001 iterations. Try increasing @@cte_max_recursion_depth to a larger value.

Another typical example is calculating the factorial.

mysql> WITH RECURSIVE factorial(n, fact) AS ( 
          SELECT 0, 1 
          UNION ALL  
          SELECT n + 1, fact * (n+1)  
          FROM factorial 
          WHERE n < 20 ) 
       SELECT * from factorial;
+------+---------------------+
| n    | fact                |
+------+---------------------+
|    0 |                   1 |
|    1 |                   1 |
|    2 |                   2 |
|    3 |                   6 |
|    4 |                  24 |
|    5 |                 120 |
|    6 |                 720 |
|    7 |                5040 |
|    8 |               40320 |
|    9 |              362880 |
|   10 |             3628800 |
|   11 |            39916800 |
|   12 |           479001600 |
|   13 |          6227020800 |
|   14 |         87178291200 |
|   15 |       1307674368000 |
|   16 |      20922789888000 |
|   17 |     355687428096000 |
|   18 |    6402373705728000 |
|   19 |  121645100408832000 |
|   20 | 2432902008176640000 |
+------+---------------------+

mysql> WITH RECURSIVE factorial(n, fact) AS (

SELECT 0, 1

UNION ALL

SELECT n + 1, fact * (n+1)

FROM factorial

WHERE n < 20 )

SELECT * from factorial;

+------+---------------------+

| n | fact |

+------+---------------------+

| 0 | 1 |

| 1 | 1 |

| 2 | 2 |

| 3 | 6 |

| 4 | 24 |

| 5 | 120 |

| 6 | 720 |

| 7 | 5040 |

| 8 | 40320 |

| 9 | 362880 |

| 10 | 3628800 |

| 11 | 39916800 |

| 12 | 479001600 |

| 13 | 6227020800 |

| 14 | 87178291200 |

| 15 | 1307674368000 |

| 16 | 20922789888000 |

| 17 | 355687428096000 |

| 18 | 6402373705728000 |

| 19 | 121645100408832000 |

| 20 | 2432902008176640000 |

+------+---------------------+

Two-Level Sequence

In this case, we would like to create a two-level sequence where the N+2 value is a function of the two previous values N+1 and N.

The typical example here is the Fibonacci Series; each number is the sum of the two preceding ones, starting from 0 and 1. Let’s calculate the first 20 items of the Fibonacci series.

mysql> WITH RECURSIVE fibonacci (n, fib_n, next_fib_n) AS (   
          SELECT 1, 0, 1   
          UNION ALL   
          SELECT n + 1, next_fib_n, fib_n + next_fib_n     
          FROM fibonacci 
          WHERE n < 20 ) 
       SELECT * FROM fibonacci;
+------+-------+------------+
| n    | fib_n | next_fib_n |
+------+-------+------------+
|    1 |     0 |          1 |
|    2 |     1 |          1 |
|    3 |     1 |          2 |
|    4 |     2 |          3 |
|    5 |     3 |          5 |
|    6 |     5 |          8 |
|    7 |     8 |         13 |
|    8 |    13 |         21 |
|    9 |    21 |         34 |
|   10 |    34 |         55 |
|   11 |    55 |         89 |
|   12 |    89 |        144 |
|   13 |   144 |        233 |
|   14 |   233 |        377 |
|   15 |   377 |        610 |
|   16 |   610 |        987 |
|   17 |   987 |       1597 |
|   18 |  1597 |       2584 |
|   19 |  2584 |       4181 |
|   20 |  4181 |       6765 |
+------+-------+------------+

mysql> WITH RECURSIVE fibonacci (n, fib_n, next_fib_n) AS (

SELECT 1, 0, 1

UNION ALL

SELECT n + 1, next_fib_n, fib_n + next_fib_n

FROM fibonacci

WHERE n < 20 )

SELECT * FROM fibonacci;

+------+-------+------------+

| n | fib_n | next_fib_n |

+------+-------+------------+

| 1 | 0 | 1 |

| 2 | 1 | 1 |

| 3 | 1 | 2 |

| 4 | 2 | 3 |

| 5 | 3 | 5 |

| 6 | 5 | 8 |

| 7 | 8 | 13 |

| 8 | 13 | 21 |

| 9 | 21 | 34 |

| 10 | 34 | 55 |

| 11 | 55 | 89 |

| 12 | 89 | 144 |

| 13 | 144 | 233 |

| 14 | 233 | 377 |

| 15 | 377 | 610 |

| 16 | 610 | 987 |

| 17 | 987 | 1597 |

| 18 | 1597 | 2584 |

| 19 | 2584 | 4181 |