How can I efficiently traverse graph data with this pattern?

Question

I have some relations embodying a directed acyclic graph that includes patterns similar to the following:

I'm looking for an efficient way to traverse this graph data. Here is an example of the seemingly simple task of counting descendants of node 0:

db<>fiddle

DROP TABLE IF EXISTS #edges;
CREATE TABLE #edges(tail int, head int);
INSERT INTO #edges(tail,head) VALUES
    (0,1), (5, 6),  (10,11), (15,16),
    (0,2), (5, 7),  (10,12), (15,17),
    (1,2), (6, 7),  (11,12), (16,17),
    (1,3), (7, 8),  (11,13), (17,18),
    (2,3), (7, 9),  (12,13), (17,19),
    (2,4), (8, 9),  (12,14), (18,19),
    (3,4), (8,10),  (13,14),
    (3,5), (9,10),  (13,15),
    (4,5), (9,11),  (14,15),
    (4,6),          (14,16);
WITH descendents(node)
AS(
    SELECT 0 as node
    UNION ALL
    SELECT head as node FROM descendents as prior
    JOIN #edges ON prior.node = tail
)
SELECT
    (SELECT COUNT(node) FROM descendents)             as total_nodes,
    (SELECT COUNT(node) FROM
        (SELECT DISTINCT node FROM descendents) as d) as distinct_nodes

This results in the following:

total_nodes | distinct_nodes
      10512 |             20

Every path is visited instead of each node once

total_nodes seems to grow at about 2^n where n is the number of nodes in the example. This is because every possible path is traversed rather than each node once. This n=29 example results in 1,305,729 total_nodes and took 75 seconds to complete on my local instance of SQL Server Express.

The obvious strategy is to only visit previously unvisited nodes on each iteration.

Excluding redundant additions using WHERE...NOT IN does not seem to be supported

The most direct method of preventing visits to previously visited nodes would seem to be to filter right in the recursive member of the CTE as follows:

SELECT head as node FROM descendents as prior
JOIN #edges ON prior.node = tail
WHERE head NOT IN (SELECT node from descendents)

This produces the error "Recursive member of a common table expression 'descendents' has multiple recursive references." I suspect this is an example of this restriction from the documenation:

The FROM clause of a recursive member must refer only one time to the CTE expression_name.

No success avoiding previously visited nodes in the CTE's recursive member

I've tried a few different techniques for avoiding previously visited nodes as recursion progresses in the CTE. I haven't found a technique that works with this graph pattern, however. The limitation seems to boil down to the following statement from the documentation:

...aggregate functions in the recursive part of the CTE are applied to the set for the current recursion level and not to the set for the CTE. Functions like ROW_NUMBER operate only on the subset of data passed to them by the current recursion level and not the entire set of data passed to the recursive part of the CTE.

Previously visited nodes appear at different recursion levels. The above limitation seems to rule out the deduplication across recursion levels that would be needed to make this query efficient.

Query Analysis

The following is from a run of a query run on 42 nodes invoked on my local instance of SQL Server Express. (Note that half the nodes are commented out in the fiddle because running with all 42 nodes causes the fiddle to timeout.)

The query was run as follows:

set statistics xml on;
SET STATISTICS IO ON;
SET STATISTICS TIME ON;
WITH descendents(node)
AS(
    SELECT 0 as node
    UNION ALL
    SELECT head as node FROM descendents as prior
    JOIN #edges ON prior.node = tail
)
SELECT DISTINCT
    node
FROM descendents
SET STATISTICS TIME OFF;
SET STATISTICS IO OFF;
set statistics xml off;

This resulted in the following messages:

Started executing query at Line 1 (76 rows affected)

SQL Server parse and compile time: CPU time = 0 ms, elapsed time = 14 ms. (42 rows affected)

Table 'Worktable'. Scan count 2, logical reads 943777243, physical reads 0, read-ahead reads 12117, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table '#edges______________________________________________________________________________________________________________000000002516'. Scan count 1, logical reads 157296207, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(1 row affected)

SQL Server Execution Times: CPU time = 2972344 ms, elapsed time = 3319271 ms. Total execution time: 00:55:19.424

Here is the execution plan:

And these are screenshots of the tooltips for what would seem to be the most time consuming steps:

Possible alternatives

I can think of a few programmatic approaches that achieve node traversal without relying on CTE recursion. I'm reluctant to prematurely abandon CTEs given the abundance of advice to prefer set logic where possible. I expect that there are some built-in SQL Server features that would support some improved approaches. The other approaches I've contemplated are as follows:

• stored procedure that implements recursion programmatically
• hierarchyid
• SQL Graph

I have limited or no experience with each of these approaches and so am interested in advice about the tradeoffs of these approaches for the above example.

Questions

1. Is there a more efficient way to traverse the graph in the above example using recursive CTEs?
2. Of the above alternatives, what are the tradeoffs?
3. Are there any other alternatives I should consider?

Answer 1

The problem really is, your graph image is not exactly one to one with your example #edges data. In your graph image, node 2 is unique. In the #edges table, node 2 exists twice because it is a child of node 0 and node 1. So this actually implicitly ends up breaking your graph into a tree instead, with node 2 duplicated.

1. Is there a more efficient way to traverse the graph in the above example using recursive CTEs?

Is the current implementation unacceptably inefficient? Just because it's traversing duplicate nodes doesn't necessarily mean the process to get there was inefficient. What does the execution plan show happened under the hood? What does the TIME and IO STATISTICS say in regards to runtime computation? I've generally found recursive CTEs to be rather performant even when iterating over decently sized collections of data.

For cyclic graphs, if you wanted to visit each node only once, then you can workaround the redundancy issue by keeping track of nodes that were already visited, on each iteration of the recursion. One way to do that is by building a string of already visited nodes with a separator and doing a wildcard contains search, like such:

WITH descendents(node)
AS(
    SELECT 0 as node, CONVERT(VARCHAR(MAX), '0') AS NodesVisited
    UNION ALL
    SELECT head as node, CONCAT(prior.NodesVisited, '|', head) AS NodesVisited
    FROM descendents as prior
    JOIN #edges ON prior.node = tail
    WHERE prior.NodesVisited NOT LIKE CONCAT('%|', #edges.head, '|%')
)
...

But this methodology can be inefficient in itself because there is overhead to doing the wildcard contains search in the WHERE clause on each iteration. This coupled with the NOT LIKE clause also makes the predicate non-sargable which effectively means it can't take use of an index to efficiently serve that predicate. Depending on the size of the #edges data, that could also impact the performance negatively.

A slightly alternative option (assuming you're on SQL Server 2016 or newer) is to build the string of visited nodes, then use CROSS APPLY with the built-in STRING_SPLIT() function to join to the collection of visited nodes as a dataset, as opposed to using a wildcard contains search. This too can be resource intensive though (from the repeated calls to the STRING_SPLIT() function).

Unfortunately, neither of these solutions apply to your problem with your acyclic graph, because your problem isn't with cyclic descendent chains, rather it's siblings with duplicate children (as discussed in the comments).

At the end of the day, you're going to want to look at the execution plan and runtime statistics, as previously mentioned, to determine how performant each implementation is, and compare them.

• stored procedure that implements recursion programmatically
• hierarchyid
• SQL Graph

2. Of the above alternatives, what are the tradeoffs?

The stored procedure route will likely be less efficient than your recursive CTE implementation. It's more of a procedural code approach as opposed to a relational one. I've converted recursive stored procedures that took over 1 hour to compute down to under 1 second by implementing them as recursive CTEs.

The hierarchyid data type I have no experience with, but I would guess you would still need to implement a recursive-based solution to get the end results you're after, either way. I don't believe this data type is commonly used.

Using the SQL Graph feature would be interesting. I only have minimal experience using that as well. But again, I think it's a much less utilized feature of SQL Server, and so there's probably less information out there on how to properly use it efficiently.

3. Are there any other alternatives I should consider?

Not that I can think of at the moment. The most common solution is a recursive CTE, generally.

Answer 2

Quasi-CTE function with access to prior rows during recursion

Consider the following flow chart in which the non-bold text describes (I think) the logical operation of a normal SQL CTE:

I think of @prior_rows, @last_rows, and @cur_rows as temporary tables (though they're surely something somewhat different in the actual SQL Server engine.) The recursive member of a normal CTE does not seem to have access to @prior_rows. This seems to mean that graph data of the form in the question cannot be efficiently traversed using a normal CTE. This is because the recursive member cannot help but repeatedly add already-visited nodes to @prior_rows for it has no way of determining whether a node is already in @prior_rows.

Giving the recursive member access to the @prior_rows allows for filtering-out already-visited nodes immediately.

Example function

The function below implements the above flow chart for the selection of descendant nodes given the table of edges in the question. SELECT statements corresponding to the anchor and recursive members of a normal CTE are indicated.

CREATE TYPE edge_table_t AS TABLE (tail int, head int);
GO

CREATE OR ALTER FUNCTION descendents(
    @edges AS edge_table_t READONLY
)
RETURNS
    @prior_rows         TABLE (node int)
BEGIN
    DECLARE @last_rows  TABLE (node int);
    DECLARE @cur_rows   TABLE (node int);

    -- Select Anchor Rows:
    INSERT INTO @last_rows
        -- anchor member
        SELECT 0;

    WHILE EXISTS (SELECT node FROM @last_rows)
    BEGIN
        -- Commit Rows:
        INSERT INTO @prior_rows SELECT node from @last_rows;

        -- Select New Rows
        DELETE FROM @cur_rows;
        WITH
        edges      AS (SELECT * FROM @edges),
        prior_nodes AS (SELECT * FROM @prior_rows),
        last_nodes  AS (SELECT * FROM @last_rows)
        INSERT INTO @cur_rows
            -- recursive member
            SELECT DISTINCT head as node FROM edges JOIN last_nodes ON node = tail
            WHERE head NOT IN (SELECT node FROM prior_nodes)

        -- Update Last Rows:
        DELETE FROM @last_rows; INSERT INTO @last_rows SELECT node from @cur_rows;
    END
    RETURN
END
;

Test Invocation

The following generates test data and invokes and collects statistics about the above function:

-- create the edges
DECLARE @edges edge_table_t;
WITH many_integers AS(
    SELECT ones.n + 10*tens.n + 100*hundreds.n + 1000*thousands.n as number
    FROM (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) ones(n),
        (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) tens(n),
        (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) hundreds(n),
        (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) thousands(n)
),
select_integers AS (SELECT number FROM many_integers WHERE number < 1000),
edges AS (
    SELECT DISTINCT number as tail, number + 1 as head FROM select_integers UNION
    SELECT DISTINCT number as tail, number + 2 as head FROM select_integers
)
INSERT INTO @edges(tail,head) SELECT tail,head FROM edges

-- invoke and measure the function
SET STATISTICS XML ON;
SET STATISTICS IO ON;
SET STATISTICS TIME ON;
SELECT node FROM descendents(@edges);
SET STATISTICS TIME OFF;
SET STATISTICS IO OFF;
SET STATISTICS XML OFF;

Analysis

The above invocation yielded this execution plan. I don't know how to interpret that plan given the procedural nature of the function it seems to have measured.

The same invocation resulted in the following messages:

(2000 rows affected)

SQL Server parse and compile time: CPU time = 0 ms, elapsed time = 0 ms.

(1002 rows affected)

Table '#A1A175C9'. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(1 row affected)

SQL Server Execution Times: CPU time = 1243 ms, elapsed time = 1243 ms.

Total execution time: 00:00:01.344

This implementation took 1.3 seconds for 1000 nodes. This is a dramatic improvement over the original CTE which took 55 minutes for 40 nodes. More importantly, the time complexity seems to be roughly O(d) where d is the depth of recursion. Here is a table of single-runs at different depths d where the value for d is substituted into WHERE number < d in the test invocation code above:

d	Time
100	0.15 s
1000	1.3 s
5000	21 s
10000	66 s