SQL Recursive WITH CTE queries

Imagine having a tool that can automatically detect JPA and Hibernate performance issues. Hypersistence Optimizer is that tool!

Introduction

In this article, we are going to see how SQL Recursive WITH CTE (Common Table Expression) queries work and how we can apply them for processing hierarchical data models.

SQL WITH clause

In SQL, the WITH clause allows us to define a Common Table Expression or CTE to assign an alias to a transient query result set.

While we can use the WITH clause as an alternative to Derived Tables or Inline Views, the WITH clause allows us to build a result set in a recursive fashion.

Consecutive Sums

To see how Recursive WITH queries work, consider the following example that calculates the consecutive sums until a given threshold:

WITH RECURSIVE consecutive_number_sum (i, consecutive_sum) AS (
  SELECT 0, 0
  UNION ALL
  SELECT i + 1, (i + 1) + consecutive_sum
  FROM consecutive_number_sum
  WHERE i < 5
)
SELECT i, consecutive_sum
FROM consecutive_number_sum

If you’re using Oracle or SQL Server, notice that the RECURSIVE keyword is not supported, so you need to omit it when writing a Recursive CTE query.

When running the Recursive CTE query above, we get the following result set:

| i | consecutive_sum |
|---|-----------------|
| 0 | 0               |
| 1 | 1               |
| 2 | 3               |
| 3 | 6               |
| 4 | 10              |
| 5 | 15              |

So, how does it work?

The very first line defines the name of the Recursive CTE and the columns of this temporary result set, i and consecutive_sum in our case:

WITH RECURSIVE consecutive_number_sum (i, consecutive_sum) AS (
  SELECT 0, 0
  UNION ALL
  SELECT i + 1, (i + 1) + consecutive_sum
  FROM consecutive_number_sum
  WHERE i < 5
)
SELECT i, consecutive_sum
FROM consecutive_number_sum

The second line defines the anchor member of the Recursive CTE:

WITH RECURSIVE consecutive_number_sum (i, consecutive_sum) AS (
  SELECT 0, 0
  UNION ALL
  SELECT i + 1, (i + 1) + consecutive_sum
  FROM consecutive_number_sum
  WHERE i < 5
)
SELECT i, consecutive_sum
FROM consecutive_number_sum

The anchor member is responsible for producing the first record of the Recursive CTE result set:

| i | consecutive_sum |
|---|-----------------|
| 0 | 0               |
| 1 | 1               |
| 2 | 3               |
| 3 | 6               |
| 4 | 10              |
| 5 | 15              |

The UNION ALL operator is used because we need to simulate the recursion using relational algebra. In fact, the Recursive CTE result set is built iteratively, similarly to a while loop in a procedural programming language:

WITH RECURSIVE consecutive_number_sum (i, consecutive_sum) AS (
  SELECT 0, 0
  UNION ALL
  SELECT i + 1, (i + 1) + consecutive_sum
  FROM consecutive_number_sum
  WHERE i < 5
)
SELECT i, consecutive_sum
FROM consecutive_number_sum

Lines 4 to 6 define the recursive member, which is an SQL query that provides the records to be added on each iteration.

WITH RECURSIVE consecutive_number_sum (i, consecutive_sum) AS (
  SELECT 0, 0
  UNION ALL
  SELECT i + 1, (i + 1) + consecutive_sum
  FROM consecutive_number_sum
  WHERE i < 5
)
SELECT i, consecutive_sum
FROM consecutive_number_sum

Because the FROM clause of the recursive member is the Recursive CTE itself, it means we are going to pass the previously generated record on each iteration.

The first time the recursive member is executed, the i and consecutive_sum columns have the value of 0 because those were provided by the anchor member, and the record produced by the first recursive iteration is going to be:

| i | consecutive_sum |
|---|-----------------|
| 0 | 0               |
| 1 | 1               |
| 2 | 3               |
| 3 | 6               |
| 4 | 10              |
| 5 | 15              |

For the second iteration of the recursive member, the value produced for i is going to be 1 + 1, and consecutive_sum is going to be (1 + 1) + 1:

| i | consecutive_sum |
|---|-----------------|
| 0 | 0               |
| 1 | 1               |
| 2 | 3               |
| 3 | 6               |
| 4 | 10              |
| 5 | 15              |

The recursive member query executes until there’s no record produced by a given iteration, which happens when the value of i becomes 5.

Hierarchical data models

Let’s assume we have the following post_comment table:

SQL Recursive WITH CTE table

The parent_id column in the post_comment table references the id column in the very same table. So, we can use the parent_id column to build a hierarchical comment structure.

The post_comment table contains the following data:

| id | parent_id | review        | created_on          | score |
|----|-----------|---------------|---------------------|-------|
| 1  |           | Comment 1     | 2019-10-13 12:23:05 |  1    |
| 2  | 1         | Comment 1.1   | 2019-10-14 13:23:10 |  2    |
| 3  | 1         | Comment 1.2   | 2019-10-14 15:45:15 |  2    |
| 4  | 3         | Comment 1.2.1 | 2019-10-15 10:15:20 |  1    |
| 5  |           | Comment 2     | 2019-10-13 15:23:25 |  1    |
| 6  | 5         | Comment 2.1   | 2019-10-14 11:23:30 |  1    |
| 7  | 5         | Comment 2.2   | 2019-10-14 14:45:35 |  1    |
| 8  |           | Comment 3     | 2019-10-15 10:15:40 |  1    |
| 9  | 8         | Comment 3.1   | 2019-10-16 11:15:45 | 10    |
| 10 | 8         | Comment 3.2   | 2019-10-17 18:30:50 | -2    |
| 11 |           | Comment 4     | 2019-10-19 21:43:55 | -5    |
| 12 |           | Comment 5     | 2019-10-22 23:45:00 |  0    |

We now want to calculate the total score per each comment hierarchy. For that, we would need a root_id column that defines the top-most post_comment identifier of a given hierarchy:

| id | parent_id | review        | created_on          | score | root_id |
|----|-----------|---------------|---------------------|-------|---------|
| 1  |           | Comment 1     | 2019-10-13 12:23:05 | 1     | 1       |
| 2  | 1         | Comment 1.1   | 2019-10-14 13:23:10 | 2     | 1       |
| 3  | 1         | Comment 1.2   | 2019-10-14 15:45:15 | 2     | 1       |
| 4  | 3         | Comment 1.2.1 | 2019-10-15 10:15:20 | 1     | 1       |
| 5  |           | Comment 2     | 2019-10-13 15:23:25 | 1     | 5       |
| 6  | 5         | Comment 2.1   | 2019-10-14 11:23:30 | 1     | 5       |
| 7  | 5         | Comment 2.2   | 2019-10-14 14:45:35 | 1     | 5       |
| 8  |           | Comment 3     | 2019-10-15 10:15:40 | 1     | 8       |
| 9  | 8         | Comment 3.1   | 2019-10-16 11:15:45 | 10    | 8       |
| 10 | 8         | Comment 3.2   | 2019-10-17 18:30:50 | -2    | 8       |
| 11 |           | Comment 4     | 2019-10-19 21:43:55 | -5    | 11      |
| 12 |           | Comment 5     | 2019-10-22 23:45:00 | 0     | 12      |

Because we shouldn’t create columns that we can simply derive using SQL, we will generate the root_id column using the following Recursive WITH Common Table Expression (CTE) query:

WITH RECURSIVE post_comment_score(
    id, root_id, post_id, parent_id, review, created_on, score) AS (
  SELECT id, id, post_id, parent_id, review, created_on, score
  FROM post_comment
  WHERE post_id = 1 AND parent_id IS NULL
  UNION ALL
  SELECT pc.id, pcs.root_id, pc.post_id, pc.parent_id, pc.review, 
         pc.created_on, pc.score
  FROM post_comment pc
  INNER JOIN post_comment_score pcs ON pc.parent_id = pcs.id
)
SELECT id, parent_id, review, created_on, score, root_id
FROM post_comment_score
ORDER BY id

And, because we now have the root_id column, we can use it to calculate the score for each hierarchy using the SUM Window Function:

WITH RECURSIVE post_comment_score(
    id, root_id, post_id, parent_id, review, created_on, score) AS (
  SELECT id, id, post_id, parent_id, review, created_on, score
  FROM post_comment
  WHERE post_id = 1 AND parent_id IS NULL
  UNION ALL
  SELECT pc.id, pcs.root_id, pc.post_id, pc.parent_id, pc.review, 
         pc.created_on, pc.score
  FROM post_comment pc
  INNER JOIN post_comment_score pcs ON pc.parent_id = pcs.id
)
SELECT id, parent_id, review, created_on, score,
       SUM(score) OVER (PARTITION BY root_id) AS total_score
FROM post_comment_score
ORDER BY id

And, we will get the expected result set:

| id | parent_id | review        | created_on                 | score | total_score |
|----|-----------|---------------|----------------------------|-------|-------------|
| 1  |           | Comment 1     | 2019-10-13 12:23:05.000000 | 1     | 6           |
| 2  | 1         | Comment 1.1   | 2019-10-14 13:23:10.000000 | 2     | 6           |
| 3  | 1         | Comment 1.2   | 2019-10-14 15:45:15.000000 | 2     | 6           |
| 4  | 3         | Comment 1.2.1 | 2019-10-15 10:15:20.000000 | 1     | 6           |
| 5  |           | Comment 2     | 2019-10-13 15:23:25.000000 | 1     | 3           |
| 6  | 5         | Comment 2.1   | 2019-10-14 11:23:30.000000 | 1     | 3           |
| 7  | 5         | Comment 2.2   | 2019-10-14 14:45:35.000000 | 1     | 3           |
| 8  |           | Comment 3     | 2019-10-15 10:15:40.000000 | 1     | 9           |
| 9  | 8         | Comment 3.1   | 2019-10-16 11:15:45.000000 | 10    | 9           |
| 10 | 8         | Comment 3.2   | 2019-10-17 18:30:50.000000 | -2    | 9           |
| 11 |           | Comment 4     | 2019-10-19 21:43:55.000000 | -5    |-5           |
| 12 |           | Comment 5     | 2019-10-22 23:45:00.000000 | 0     | 0           |

Awesome, right?

Online Workshops

If you enjoyed this article, I bet you are going to love my upcoming 4-day Online Workshop!

Conclusion

The SQL Recursive WITH CTE (Common Table Expression) allows us to build a result set iteratively, and this is very useful when processing hierarchical data models.

The Recursive WITH clause is supported by all top-used relational databases since the following versions:

  • Oracle 9i R2
  • SQL Server 2005
  • PostgreSQL 8.4
  • MySQL 8.0.1
  • MariaDB 10.2.2

So, if you are using a newer version of those relational databases, then you can definitely benefit from this awesome SQL feature.

Transactions and Concurrency Control eBook

One Comment on “SQL Recursive WITH CTE queries

  1. Hi Vlad,

    Thank you for this article. Yes, it’s really awesome!
    I can run the count query in Oracle 11g as follows:

    WITH consecutive_number_sum (i, consecutive_sum) AS (
    SELECT 0, 0 FROM dual
    UNION ALL
    SELECT i + 1, (i + 1) + consecutive_sum
    FROM consecutive_number_sum
    WHERE i < 5
    )
    SELECT i, consecutive_sum
    FROM consecutive_number_sum

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

4 day training with a Java Champion 🏆 29th Nov - 2nd Dec