Changelog Recursive CTEs
Changelog

Recursive CTEs

12.23.2024

We’re thrilled to announce that recursive CTEs are now stable in Materialize! This milestone unlocks an entirely new class of iterative SQL queries, enabling you to work with hierarchical and recursive data structures directly in SQL.

Recursive CTEs are indispensable for applications requiring traversal or accumulation along hierarchical data - think organizational structures, bill of materials, or nested permissions. They make it possible to compute dynamic, incremental results in scenarios where standard SQL falls short.

But we didn’t stop at just implementing the standard WITH RECURSIVE clause. Instead, we took it a step further by supporting mutual recursion, a more powerful and expressive primitive that handles some of the fundamental limitations of traditional recursive CTEs.

Why mutual recursion?

The standard WITH RECURSIVE clause has practical issues when handling more complex computations or when multiple recursive relations depend on each other. By introducing the extended WITH MUTUALLY RECURSIVE clause, Materialize allows you to define interdependent recursive queries, opening the door to advanced use cases like:

Example: permissions in hierarchical systems

One common use case for recursion in applications is resolving permissions in hierarchical systems. Think of scenarios like managing access for teams and sub-teams or sharing files within nested groups — permissions often need to flow from parent to child unless explicitly overridden. Using recursion, you can dynamically keep permissions up-to-date as the hierarchy structure changes.

1 
-- Permission groups.
2 
CREATE TABLE groups (
3 
    group_id        TEXT,
4 
    parent_group_id TEXT
5 
);
6
7 
INSERT INTO groups VALUES
8 
('group1', NULL),       -- Root group
9 
('group2', 'group1'),   -- Child of group1
10 
('group3', 'group2');   -- Child of group2
11
12 
-- Documents that not all (sub-)teams should have unrestricted access to! 🔒
13 
CREATE TABLE documents (
14 
    document_id TEXT
15 
);
16
17 
INSERT INTO documents VALUES
18 
('doc1'), ('doc2');
19
20 
-- Per-document permission matrix.
21 
CREATE TABLE permissions (
22 
    group_id        TEXT,
23 
    document_id     TEXT,
24 
    permission_type TEXT
25 
);
26
27 
INSERT INTO permissions VALUES
28 
('group1', 'doc1', 'reader'), -- group1 can read doc1
29 
('group2', 'doc2', 'editor'); -- group2 can edit doc2
30
31 
-- Based on group membership, recursively unnest the full document permission
32 
-- hierarchy. This view can then be used to control access to specific
33 
-- documents on the fly, as groups and permissions change.
34 
CREATE VIEW effective_permissions AS
35 
WITH MUTUALLY RECURSIVE permission_hierarchy (group_id TEXT, document_id TEXT, permission_type TEXT) AS (
36 
    SELECT
37 
        g.group_id,
38 
        p.document_id,
39 
        p.permission_type
40 
    FROM groups g
41 
    JOIN permissions p ON g.group_id = p.group_id
42 
    UNION ALL
43 
    SELECT
44 
        g.group_id,
45 
        ph.document_id,
46 
        ph.permission_type
47 
    FROM groups g
48 
    JOIN permission_hierarchy ph ON g.parent_group_id = ph.group_id
49 
    WHERE NOT EXISTS (
50 
        SELECT 1
51 
        FROM permissions bp
52 
        WHERE bp.group_id = g.group_id AND bp.document_id = ph.document_id
53 
    )
54 
)
55 
SELECT DISTINCT group_id, document_id, permission_type
56 
FROM permission_hierarchy;
57
58 
-- For demo purposes, the results here are static; you can easily instruct
59 
-- Materialize to keep the results incrementally up-to-date by creating an
60 
-- index on the view.
61 
SELECT * FROM effective_permissions;
62
63 
| group_id | document_id | permission_type |
64 
| -------- | ----------- | --------------- |
65 
| group1   | doc1        | reader          |
66 
| group2   | doc1        | reader          |
67 
| group2   | doc2        | editor          |
68 
| group3   | doc1        | reader          |
69 
| group3   | doc2        | editor          |
sql

Ready to dive in? For more details on how Recursive CTEs work in Materialize, check out this blog post. If you have questions about the implementation or are curious if recursive CTEs can solve your use case, ping us on Slack!