Traversing parent-child relations

In this short tutorial, we’ll look at traversing parent-child structures using recursive common table expressions, and turning the data into human-readable lists. This is a great way to represent paths and hierarchy-based data in reports and end-user outputs.

The example

The example data we’re using here is an imaginary blocking chain. In SQL Server, as in practically any database software, a database transaction will create locks on objects that it uses. When an object is locked by one process, any other process that wants to use or modify this object will have to wait for the first process to first let go of the lock. In this context, you would say that the second process is “blocked” by the first process.

You can view a current list of blocking sessions on the server using the following dynamic management view in SQL Server:

SELECT DISTINCT session_id, blocking_session_id, wait_type, wait_duration_ms,
    ROW_NUMBER() OVER (
        PARTITION BY waiting_task_address
        ORDER BY wait_duration_ms, resource_address) AS dupl
FROM sys.dm_os_waiting_tasks
ORDER BY session_id;

Hopefully, however, your server won’t contain a lot of blocking transactions, so we’ll create our own working table with some test data.

CREATE TABLE #connections (
    spid         int NOT NULL,
    blockedBy    int NULL,
    PRIMARY KEY CLUSTERED (spid)
);
--- Example data:
INSERT INTO #connections (spid, blockedBy)
VALUES (53, NULL),
       (54, NULL),
       (55, NULL),
       (56,   64),
       (57, NULL),
       (59,   56),
       (60, NULL),
       (61, NULL),
       (62, NULL),
       (63,   64),
       (64,   53),
       (65, NULL),
       (66,   56);

Listing recursive relations

Blocking transactions can be recursive. In this example, SPID 63 is blocked by 64, which in turn is blocked by 53. Because of this recursive nature, we’re going to use a recursive common table expression to map all the relations.

All recursive CTEs consist of two parts, an anchor and a recursion. Here, the anchor is a list of first-level (direct) relations. After the UNION ALL section, we’re recursing up through the chain of relations.

--- Table of blocking SPIDs:
WITH list (spid, blockedBy, [level])
AS (--- The anchor of the recursive CTE is the first-level relation
    --- from the SPID to the blocking SPID.
    SELECT spid, blockedBy, 1
    FROM #connections
    WHERE blockedBy IS NOT NULL

    UNION ALL

    --- From here, we'll recurse the blocking SPID's own blocking
    --- SPIDs, and increment the "level" counter by one.
    SELECT list.spid, conn.blockedBy, list.[level]+1
    FROM list
    INNER JOIN #connections AS conn ON list.blockedBy=conn.spid
    WHERE conn.blockedBy IS NOT NULL)

SELECT spid, blockedBy, [level]
FROM list
ORDER BY spid, [level], blockedBy;

Here’s the result:

Turning recursive relations into paths

Finally, we can use the same recursive common table expression to build a string containing the “path” of each SPID’s blocking processes.

WITH list (spid, blockedBy, [level], list)
AS (--- The anchor of the recursive CTE is the first-level relation
    --- from the SPID to the blocking SPID.
    --- The "list" column is a varchar(100) column that contains an
    --- ordered path of all the blocking relations.
    SELECT spid, blockedBy, 1, CAST(blockedBy AS varchar(100)) AS list
    FROM #connections
    WHERE blockedBy IS NOT NULL

    UNION ALL

    --- From here, we'll recurse the blocking SPID's own blocking
    --- SPIDs, and increment the "level" counter by one.
    SELECT list.spid, conn.blockedBy, list.[level]+1,
        --- Suffix the new level's SPID to the end of the "list" string.
        CAST(list+' <- '+CAST(conn.blockedBy AS varchar(100)) AS varchar(100)) AS list
    FROM list
    INNER JOIN #connections AS conn ON list.blockedBy=conn.spid
    WHERE conn.blockedBy IS NOT NULL)

SELECT spid, list AS blockedByChain
FROM list
WHERE [level]=(SELECT MAX(sub.[level]) FROM list AS sub WHERE sub.spid=list.spid)
ORDER BY spid, [level], blockedBy;

For every recursion of the CTE, we’re building a string containing the blocking path in the “list” column. The WHERE clause at the end is meant to filter only the final product of the recursion, and not all the intermediate steps used to create it.

Here’s the output:

Real-world implementation

To implement this query on actual blocking data on your server, just populate the temp table from the DMV mentioned in the beginning of the article:

TRUNCATE TABLE #connections;

INSERT INTO #connections (spid, blockedBy)
SELECT DISTINCT session_id, blocking_session_id
FROM sys.dm_os_waiting_tasks;