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:
- Stable matching algorithms;
- Dynamic programming for optimization problems;
- Solving all of 2023’s Advent of Code challenges;
- And much more - it’s Turing complete!
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.
-- Permission groups.
CREATE TABLE groups (
group_id TEXT,
parent_group_id TEXT
);
INSERT INTO groups VALUES
('group1', NULL), -- Root group
('group2', 'group1'), -- Child of group1
('group3', 'group2'); -- Child of group2
-- Documents that not all (sub-)teams should have unrestricted access to! 🔒
CREATE TABLE documents (
document_id TEXT
);
INSERT INTO documents VALUES
('doc1'), ('doc2');
-- Per-document permission matrix.
CREATE TABLE permissions (
group_id TEXT,
document_id TEXT,
permission_type TEXT
);
INSERT INTO permissions VALUES
('group1', 'doc1', 'reader'), -- group1 can read doc1
('group2', 'doc2', 'editor'); -- group2 can edit doc2
-- Based on group membership, recursively unnest the full document permission
-- hierarchy. This view can then be used to control access to specific
-- documents on the fly, as groups and permissions change.
CREATE VIEW effective_permissions AS
WITH MUTUALLY RECURSIVE permission_hierarchy (group_id TEXT, document_id TEXT, permission_type TEXT) AS (
SELECT
g.group_id,
p.document_id,
p.permission_type
FROM groups g
JOIN permissions p ON g.group_id = p.group_id
UNION ALL
SELECT
g.group_id,
ph.document_id,
ph.permission_type
FROM groups g
JOIN permission_hierarchy ph ON g.parent_group_id = ph.group_id
WHERE NOT EXISTS (
SELECT 1
FROM permissions bp
WHERE bp.group_id = g.group_id AND bp.document_id = ph.document_id
)
)
SELECT DISTINCT group_id, document_id, permission_type
FROM permission_hierarchy;
-- For demo purposes, the results here are static; you can easily instruct
-- Materialize to keep the results incrementally up-to-date by creating an
-- index on the view.
SELECT * FROM effective_permissions;
| group_id | document_id | permission_type |
| -------- | ----------- | --------------- |
| group1 | doc1 | reader |
| group2 | doc1 | reader |
| group2 | doc2 | editor |
| group3 | doc1 | reader |
| group3 | doc2 | editor |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!