Recursive CTEs in Alopex DB: Comparing the Implementation with PostgreSQL, SQLite, and DataFusion

Use WITH RECURSIVE for queries whose hierarchy depth is not known in advance, such as tracing an employee up through their managers to the top of the organization, or expanding a bill of materials.

Alopex DB has supported recursive CTEs since v0.8.7. This article explains how they run in Alopex DB and where they stop. It also compares the implementation with PostgreSQL, SQLite, and DataFusion to show where they differ.

How a recursive CTE runs

A recursive CTE has two parts: a non-recursive term (also called the anchor) that produces the first rows, and a recursive term that refers to the CTE itself. The following query produces the numbers 1 through 5.

WITH RECURSIVE counter(n) AS (
    SELECT 1                              -- non-recursive term
    UNION ALL
    SELECT n + 1 FROM counter WHERE n < 5 -- recursive term
)
SELECT n FROM counter ORDER BY n;

The non-recursive term runs once and produces the first rows. Then the rows added in the previous iteration become the contents of counter, and the recursive term runs to produce new rows. This repeats, and the query ends when no new rows appear.

Every implementation keeps the rows added in the previous iteration and decides how to handle duplicates and when to stop. The differences between implementations come from how they keep those rows and how they stop.

The Alopex DB implementation

Deciding whether a query is recursive

Even when WITH RECURSIVE is written, no recursion is needed if the CTE does not refer to itself. Alopex DB treats a query as recursive only when the references between CTEs contain a cycle. Without a cycle, the CTE runs as an ordinary CTE.

Checking the shape before execution

Once a query is treated as recursive, Alopex DB checks before execution that its shape meets the following conditions.

• There is exactly one CTE.
• There is exactly one UNION or UNION ALL.
• The non-recursive term does not refer to the CTE.
• The recursive term refers to the CTE directly, exactly once.
• The recursive term has no subquery, nested WITH, or set operation.
• The CTE body has no ORDER BY, LIMIT, or OFFSET.
• The non-recursive and recursive terms have the same number of columns and the same column types.

A query that does not meet these conditions returns ALOPEX-F001 to report that it is unsupported. Alopex DB never ignores RECURSIVE and runs the query once instead.

Iterating on the added rows

The computation iterates on the rows added in the previous iteration until no new rows appear. The flow is as follows.

accumulated = result of the non-recursive term
added rows  = accumulated
while added rows is not empty:
    run the recursive term, using the added rows as the self-reference
    for UNION, remove rows that have already appeared
    append to accumulated, and carry the new rows into the next iteration

The recursive term reads only the rows added in the previous iteration. It does not read every row accumulated so far. With UNION, Alopex DB remembers the rows that have appeared across iterations so that the same row is never added twice. With UNION ALL, duplicate rows are added as they are.

Here is an example that walks a hierarchy. This query starts from the row with id = 3 and follows parent_id up to the topmost row.

CREATE TABLE employees (id INTEGER PRIMARY KEY, parent_id INTEGER, name TEXT);
INSERT INTO employees VALUES
    (1, NULL, 'root'), (2, 1, 'manager'), (3, 2, 'worker');

WITH RECURSIVE ancestors AS (
    SELECT id, parent_id, name FROM employees WHERE id = 3
    UNION ALL
    SELECT e.id, e.parent_id, e.name
    FROM employees e JOIN ancestors a ON e.id = a.parent_id
)
SELECT id, name FROM ancestors ORDER BY id;

[{'id': 1, 'name': 'root'}, {'id': 2, 'name': 'manager'}, {'id': 3, 'name': 'worker'}]

The parent_id of root is NULL, so the JOIN returns no rows. No new rows appear, and the processing ends there.

Limits for queries that do not stop

When UNION ALL is used on data that contains a cycle, rows keep increasing and the query never ends. For that reason, Alopex DB currently sets the following three limits.

When any of them is exceeded, Alopex DB stops the query and returns ALOPEX-E003. For example, the following query keeps adding rows from itself, so it stops when it reaches the iteration limit.

WITH RECURSIVE c(n) AS (SELECT 1 UNION ALL SELECT n FROM c)
SELECT n FROM c;

error[ALOPEX-E003]: resource exhausted: recursive CTE 'c' reached iteration limit 1000

At present, these values cannot be changed from SQL. If you want to adjust the limits for your use case, please send us your request. We can change the implementation based on your feedback.

Differences from other implementations

PostgreSQL

PostgreSQL also passes only the rows added in the previous iteration to the next iteration. It prepares two tables and swaps them at each iteration, carrying the result of the previous iteration into the next. With UNION, it removes duplicates with a hash table.

Its restrictions on the recursive term overlap closely with those of Alopex DB. A recursive reference cannot appear inside a subquery, an outer join, INTERSECT, or EXCEPT, and the same CTE cannot be referenced more than once. Mutual recursion, and ORDER BY and LIMIT on a recursive query, are not implemented. On the other hand, it sets no limit on the number of iterations or rows.

SQLite

SQLite processes rows one at a time. It puts the rows of the non-recursive term into a queue, takes them out one by one, and outputs each. It runs the recursive term with the extracted row as the self-reference and puts the result back into the queue. This loop is how the processing proceeds.

With ORDER BY, the queue changes from first-in, first-out to a priority queue, so you can choose the order of traversal. With LIMIT, processing stops once the specified number of rows has been output. Stopping a query that would run forever is the job of the LIMIT that the user writes. Window functions and aggregates cannot be used in a recursive query.

DataFusion

DataFusion has a non-recursive term and a recursive term. Like Alopex DB, it stores the result of the previous iteration in a work table and passes it to the recursive term. With UNION, it removes duplicates before passing the rows to the next iteration. It does not accept a query with two or more self-references.

The differences from Alopex DB are in how results are returned and how the query stops. DataFusion streams results to the output each time it receives a batch. Alopex DB collects results until the recursion ends and then returns them. DataFusion has no mechanism for detecting infinite recursion, and a comment in its source says that avoiding infinite recursion is the job of whoever builds the plan.

Comparison

The following table compares the four implementations by the unit of iteration, how results are returned, how the query stops, and how self-references are handled.

Alopex DB handles added rows in a way close to PostgreSQL. It passes only the rows added in the previous iteration to the recursive term, and with UNION it removes duplicates across all iterations.

For stopping, SQLite leaves it to the LIMIT that the user writes, and DataFusion leaves it to whoever builds the plan. Alopex DB places limits on the execution side so that a query stops even when the user writes nothing special.

A query in an unsupported shape is not run silently. Alopex DB returns ALOPEX-F001 to tell you it is unsupported.

You can try recursive CTEs from the quickstart.

References

• Alopex DB (GitHub)
• PostgreSQL nodeRecursiveunion.c
• PostgreSQL parse_cte.c
• SQLite select.c
• DataFusion recursive_query.rs