Recursive Queries in SQL Server

[Rabbit]

Introduction
Starting with SQL Server 2005, you have the ability to create recursive queries using common table expressions (CTE). They are very powerful tools that can be used to query hierarchical data where you don't know beforehand how many times you have to join back to the same table. This is probably the most common use. But they can also be used to do all sorts of things, including but not limited to: Creating n number of rows based on a quantity field, extracting multiple matching substrings out of a field, creating permutations/combinations from a set, or taking date ranges from a row and breaking it up into multiple rows of smaller ranges.

The Basic Structure of a Recursive CTE
This is the basic structure of a CTE:

WITH cte AS ( 
    Base Query
 
    UNION ALL
 
    Recursive Query call back to cte
    WHERE termination check
)
 
SELECT * FROM cte

A recursive CTE is made up of 3 key components.

1. A base query that returns the initial rows to use in recursion.
2. A query that has a call back to the CTE itself.
3. A clause that eventually results in an empty result set so the recursion can terminate.

#3 is absolutely key. At some point the recursion needs to end so the results can be returned. Otherwise, it will error out when it hits the max recursion set in SQL Server or will run infinitely until terminated if max recursion is set to 0. You can set the max recursion option with OPTION (MAXRECURSION #), where # is a number between 0 and 32767. The default, when the option is not specified, is 100.

All examples below were created and tested on SQL Server 2008 R2.

Ex. 1: Create Additional Rows from a Quantity Field

This example takes a row and repeats the data as many times as stated by the quantity.

Sample Data:

item    quantity
a    1
b    2
c    3
d    4
e    5

Query:

DECLARE @t TABLE (item char(1), quantity int)
INSERT INTO @t VALUES ('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)
 
; WITH cte AS (
    SELECT item, 
        quantity - 1 AS quantityLeft
    FROM @t
 
    UNION ALL
 
    SELECT item, 
        quantityLeft - 1 AS quantityLeft
    FROM 
        cte
    -- termination clause
    WHERE quantityLeft > 0 
)
 
SELECT * FROM cte ORDER BY item;

Results:

item    quantityLeft
a    0
b    1
b    0
c    1
c    0
c    2
d    3
d    2
d    1
d    0
e    4
e    3
e    2
e    1
e    0

Ex. 2: Creating Permutations/Combinations

This example takes the set of data and creates all the possible combinations and permutations of the rows. Be careful with this one as the number of possibilities grows exponentially.

Sample Data:

item
a
b
c
d
e

Query:

DECLARE @t TABLE (item CHAR(1))
INSERT INTO @t VALUES ('a'), ('b'), ('c'), ('d'), ('e')
DECLARE @maxLen INT
SET @maxLen = (SELECT COUNT(*) FROM @t)
 
-- Combination, order does not matter
; WITH cte AS (
    SELECT item, 
        CONVERT(VARCHAR(255), item) AS combined
    FROM @t
 
    UNION ALL
 
    SELECT t.item,
        CONVERT(VARCHAR(255), cte.combined + t.item) AS combined
    FROM 
        cte
        INNER JOIN @t t
        ON cte.item < t.item
    WHERE LEN(cte.combined + t.item) <= @maxLen
)
 
SELECT combined FROM cte ORDER BY LEN(combined), combined;
 
 
-- Permutation, order matters
; WITH cte AS (
    SELECT item, 
        CONVERT(VARCHAR(255), item) AS combined
    FROM @t
 
    UNION ALL
 
    SELECT t.item,
        CONVERT(VARCHAR(255), cte.combined + t.item) AS combined
    FROM 
        cte
        INNER JOIN @t t
        ON cte.combined NOT LIKE '%' + t.item + '%'
    WHERE LEN(cte.combined + t.item) <= @maxLen
)
 
SELECT combined FROM cte ORDER BY LEN(combined), combined;

Combination Results:

combined
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde

Permutation Results: Too many rows to put in the article.

Ex. 3: Extracting Multiple PDF File Names from a Field

This example substrings out an unknown number of PDF file names from a larger string in a field where each PDF file name ends with .pdf and begins at the first > symbol right before the .pdf and everything else is superfluous.

Sample Data:

IDField    fieldName
1    >>>>>>1.pdf test> >b>c>xyz.pdf bob >hello world.pdf foo >womp womp.pdf>
2    >2.pdf other unnecssary stuff > bar.pdf

Query:
The lines that are commented out are the building blocks of finding and substringing out the PDF file name.

DECLARE @f TABLE (fieldName VARCHAR(255), IDField int)
INSERT INTO @f VALUES('>>>>>>1.pdf test> >b>c>xyz.pdf bob >hello world.pdf foo >womp womp.pdf>', 1)
INSERT INTO @f VALUES('>2.pdf other unnecssary stuff > bar.pdf', 2)
 
; WITH cte2 AS (
    SELECT 
        IDField,
        --PATINDEX('%.pdf%', fieldName) + 3 AS PDFLocation,
        --SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3)) AS PDFSubstring,
        --REVERSE(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3))) AS PDFSubstringReverse,
        --PATINDEX('%>%', REVERSE(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3)))) AS ReverseSymbolLocationBeforePDF,
        --LEN(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3)))) + 2 AS SymbolLocationBeforePDF,
 
        CONVERT(VARCHAR(255), SUBSTRING(fieldName, 
            LEN(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3)))) + 2, 
            PATINDEX('%.pdf%', fieldName) + 3 - (LEN(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3)))) + 2) + 1
        )) AS PDFName,
 
        CONVERT(VARCHAR(255), STUFF(fieldName, 1, PATINDEX('%.pdf%', fieldName) + 3, '')) AS strWhatsLeft
    FROM @f
 
    UNION ALL
 
    SELECT 
        IDField,
        --PATINDEX('%.pdf%', strWhatsLeft) + 3 AS PDFLocation,
        --SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3)) AS PDFSubstring,
        --REVERSE(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3))) AS PDFSubstringReverse,
        --PATINDEX('%>%', REVERSE(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3)))) AS ReverseSymbolLocationBeforePDF,
        --LEN(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3)))) + 2 AS SymbolLocationBeforePDF,
 
        CONVERT(VARCHAR(255), SUBSTRING(strWhatsLeft, 
            LEN(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3)))) + 2, 
            PATINDEX('%.pdf%', strWhatsLeft) + 3 - (LEN(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3)))) + 2) + 1
        )) AS PDFName,
 
        CONVERT(VARCHAR(255), STUFF(strWhatsLeft, 1, PATINDEX('%.pdf%', strWhatsLeft) + 3, '')) AS strWhatsLeft
    FROM cte2
    WHERE strWhatsLeft LIKE '%.pdf%'
)
 
SELECT * FROM cte2 ORDER BY IDField

Results:

IDField    PDFName    strWhatsLeft
1    1.pdf     test> >b>c>xyz.pdf bob >hello world.pdf foo >womp womp.pdf>
1    xyz.pdf     bob >hello world.pdf foo >womp womp.pdf>
1    hello world.pdf     foo >womp womp.pdf>
1    womp womp.pdf    >
2    2.pdf     other unnecssary stuff > bar.pdf
2     bar.pdf    

Ex. 4: Splitting a Date Range into Multiple Smaller Ranges

This example takes rows that define a start and end date and creates multiple rows with a max interval of 3 days.

Sample Data:

TimespanID    StartDate    EndDate
1    2015-01-01    2015-01-02
2    2015-01-05    2015-02-11

Query:

DECLARE @t TABLE (TimespanID int, StartDate DATE, EndDate DATE)
INSERT INTO @t VALUES (1,'1/1/2015','1/2/2015'), (2, '1/5/2015', '2/11/2015')
 
; WITH cte AS (
    SELECT 
        TimespanID,
        StartDate,
        CASE WHEN DATEADD(DAY, 2, StartDate) > EndDate
            THEN EndDate
            ELSE DATEADD(DAY, 2, StartDate)
        END AS EndDate,
        EndDate AS OriginalEndDate
    FROM @t
 
    UNION ALL
 
    SELECT 
        TimespanID,
        DATEADD(DAY, 1, EndDate) AS StartDate,
        CASE WHEN DATEADD(DAY, 3, EndDate) > OriginalEndDate
            THEN OriginalEndDate
            ELSE DATEADD(DAY, 3, EndDate)
        END AS EndDate,
        OriginalEndDate AS OriginalEndDate
    FROM cte
    WHERE DATEADD(DAY, 1, EndDate) <= OriginalEndDate
)
 
SELECT * FROM cte ORDER BY TimespanID

Results:

TimespanID    StartDate    EndDate    OriginalEndDate
1    2015-01-01    2015-01-02    2015-01-02
2    2015-01-05    2015-01-07    2015-02-11
2    2015-01-08    2015-01-10    2015-02-11
2    2015-01-11    2015-01-13    2015-02-11
2    2015-01-14    2015-01-16    2015-02-11
2    2015-01-17    2015-01-19    2015-02-11
2    2015-01-20    2015-01-22    2015-02-11
2    2015-01-23    2015-01-25    2015-02-11
2    2015-01-26    2015-01-28    2015-02-11
2    2015-01-29    2015-01-31    2015-02-11
2    2015-02-01    2015-02-03    2015-02-11
2    2015-02-04    2015-02-06    2015-02-11
2    2015-02-07    2015-02-09    2015-02-11
2    2015-02-10    2015-02-11    2015-02-11

Ex. 5: Retrieving Hierarchy from a Relationship Table

This example takes a hierarchy stored in a table where the ParentID is the only link that can be used to establish hierarchy level. Normally this is a problem because you never know what level the employee is at and how many times you have to join back to the table to retrieve the full hierarchy.

However, this is trivial for a recursive CTE because it will continually self join until the full hierarchy is established.

Note that this example differs from the other examples in that there is no WHERE clause termination check. Instead, the termination happens when the lowest level of the hierarchy is reached meaning there is no lower level employee that can be joined to because no one reports to them. This also means that if the data is bad, there exists the possibility of an infinite loop in the hierarchy.

Sample Data:

PK    EmployeeName    ParentID
1    Mr. CEO    0
2    Andy    1
3    Billy Jean    1
4    Charles    2
5    Danni    2
6    Eden    2
7    Frank    3
8    Geri    5

Query:

DECLARE @t TABLE (PK INT, EmployeeName VARCHAR(10), ParentID INT);
 
INSERT INTO @t VALUES
    (1, 'Mr. CEO', 0),
    (2, 'Andy',1 ),
    (3, 'Billy Jean', 1),
    (4, 'Charles', 2),
    (5, 'Danni', 2),
    (6, 'Eden', 2),
    (7, 'Frank', 3),
    (8, 'Geri', 5)
;
 
; WITH cte AS (
    SELECT
        PK,
        EmployeeName,
        1 AS HierarchyLevel,
        CONVERT(VARCHAR(255), PK) AS HierarchySortString
    FROM @t
    WHERE ParentID = 0
 
    UNION ALL
 
    SELECT
        t.PK,
        t.EmployeeName,
        cte.HierarchyLevel + 1 AS HierarchyLevel,
        CONVERT(VARCHAR(255), HierarchySortString + ',' + CONVERT(VARCHAR(255), t.PK)) AS HierarchySortString
    FROM @t AS t
        INNER JOIN cte
        ON t.ParentID = cte.PK
)
 
SELECT
    PK,
    REPLICATE('+', HierarchyLevel - 1) + EmployeeName AS EmployeeName,
    HierarchyLevel
FROM cte
ORDER BY
    HierarchySortString

Results:

PK    EmployeeName    HierarchyLevel
1    Mr. CEO    1
2    +Andy    2
4    ++Charles    3
5    ++Danni    3
8    +++Geri    4
6    ++Eden    3
3    +Billy Jean    2
7    ++Frank    3

[Canes816]

From the permutations example you posted, it looks like you are using the string length to exit the recursion. In the data that I'm using, I'm trying to get all possible related values, but the relationship could be 1 or 2 (or multiple) levels away.

For example, how could I get the output below, from the table defined here?

Declare @example table (RowID varchar(10), RelID varchar(10))
Insert Into @example Select 'Rec1', 'Rec2'
Insert Into @example Select 'Rec2', 'Rec3'
Insert Into @example Select 'Rec3', 'Rec4'
Insert Into @example Select 'Rec4', 'Rec41'
Insert Into @example Select 'Rec4', 'Rec42'
Insert Into @example Select 'Rec4', 'Rec43'
Insert Into @example Select 'Rec4', 'Rec44'

The output I want to get is the following (along with any other possible "connections"):
Rec1-Rec2
Rec1-Rec3
Rec1-Rec4
Rec1-Rec41
Rec1-Rec42
Rec1-Rec43
Rec1-Rec44