Recursive CTEs in CockroachDB

I have been thinking about how CockroachDB could be used to implement a very flexible authorization system.

I have previous experience using Graph databases which differ from relational databases in several key ways -- but one big differentiator is that graph databases are good for "highly relational data" (and I don't mean relational in the RDBMS sense). Graph databases are good at answering questions like, "Given a family tree, are persons X and Y related, and if so, what is their relationship?", or "In my LinkedIn professional network, am I connected to person X, and if so, how many 'hops' away are we?"

Questions like this are tricky to answer in general because the "distance" between things is not known, but they can be particularly difficult to answer in relational databases using standard data models, highly-structured schemas, and join-based queries.

For my authorization system needs, I want to be able these types of unstructured/unknown questions. For instance: "If I'm a user in a system, and I'm a member of a groups A, B, C, do I have permission to do action X" This is further complicated by the fact that I would want to allow a group hierarchy where a group can belong to another group which can belong to a tree of groups, and the necessary permission(s) can be attached to groups anywhere in that tree.

Most relational databases -- including CockroachDB -- have a structure that can help with these type of "walk the tree" problems; this structure is called a "Recursive CTE."

A normal, non-recursive CTE (Common Table Expression) is cool in and of itself since it allows you to create a query that can be re-used more than once in a series of queries. Beyond facilitating re-use, they can also simply your queries by eliminating complex derived tables which helps to create more easily maintainable SQL code.

A recursive CTE adds another layer of goodness because it allows recursive execution of the expression.

Let's look at an example of a non-recursive CTE borrowed from the CockroachDB docs:

WITH r AS
(
  SELECT *
  FROM rides
  WHERE revenue > 98
)
SELECT *
FROM users AS u, r -- here we're joining to the 'r' CTE
WHERE r.rider_id = u.id;

To use a recursive CTE, we need a slightly different syntax. Let's have a look at an example:

WITH RECURSIVE cte (n, factorial) AS
(
    VALUES (0, 1) -- initial subquery
    UNION ALL
    SELECT n+1, (n+1)*factorial
    FROM cte
    WHERE n < 9 -- recursive subquery
)
SELECT * FROM cte;

Recursive CTEs have to have the keyword "RECURSIVE", as well as an initial statement (a starting point) UNIONed together with a recursive query. There can also optionally be a field list which is used to explicitly name the columns returned in the CTE table-valued structure.

Now, back to the example of an authorization system. I created a GitHub repo which has an example with some example data on how such an authorization system could look in CockroachDB and how that data could be effectively queried using a recursive CTE.
https://github.com/cockroachlabs-field/perms-example

I won't repeat the contents of the GitHub repo here, but here's an example of the CTE I'm using there. We're asking the question: Does the identity 'Andy, GM' have rights to read data from the Customer table?
If the query returns results, the permission exists; if no results are returned, the permission doesn't exist.

WITH RECURSIVE roles_hierarchy_cte AS (

    --query all the roles for the user we care about
    SELECT r.rid AS rid
    FROM perms_example.role_instance r
    INNER JOIN perms_example.identity_role_assignment ira ON r.rid = ira.rid
    WHERE ira.iid = 'aaaaaaaa-1111-1111-1111-111111111111' -- Andy, GM

    UNION

    --walk up the tree and find any other parent roles
    SELECT rh.child_rid AS rid
    FROM perms_example.role_hierarchy rh
    INNER JOIN roles_hierarchy_cte rhc ON rhc.rid = rh.parent_rid
)

/* get all the permissions that this identity is assigned to directly */
SELECT i.iid, i.identity_name, NULL AS role_name, p.permission_name
FROM perms_example.identity_instance i
INNER JOIN perms_example.identity_permission_assignment ipa on i.iid = ipa.iid
INNER JOIN perms_example.permission_instance p on ipa.pid = p.pid
WHERE i.iid = 'aaaaaaaa-1111-1111-1111-111111111111' -- Andy, GM
AND p.pid = 'cccccccc-1111-1111-1111-111111111111' -- 'Read Customer Data

UNION ALL

/* also, get any permissions that this identity picks up due to role permissions
     and also role permissions from the role hierarchy */
SELECT i.iid, i.identity_name, r.role_name, p.permission_name
FROM perms_example.role_instance r
INNER JOIN perms_example.role_permission_assignment rpa on r.rid = rpa.rid
INNER JOIN perms_example.permission_instance p on rpa.pid = p.pid
--get me 1 identity row so I can include that on the output
CROSS JOIN
(
        SELECT i.iid, i.identity_name
        FROM perms_example.identity_instance i
        WHERE i.iid = 'aaaaaaaa-1111-1111-1111-111111111111' --Andy, GM
) i
WHERE r.rid IN (
    SELECT rhc.rid
    FROM roles_hierarchy_cte rhc
)
AND p.pid = 'cccccccc-1111-1111-1111-111111111111' -- 'view customer data
;

Do you have other examples where recursive CTEs may be useful?
Post them in the comments!

Happy recursing!