468,743 Members | 2,238 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Share your developer knowledge by writing an article on Bytes.

Recursive Queries in SQL Server

Rabbit
12,515 Expert Mod 8TB
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:
Expand|Select|Wrap|Line Numbers
  1. WITH cte AS ( 
  2.     Base Query
  3.  
  4.     UNION ALL
  5.  
  6.     Recursive Query call back to cte
  7.     WHERE termination check
  8. )
  9.  
  10. 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:
Expand|Select|Wrap|Line Numbers
  1. item    quantity
  2. a    1
  3. b    2
  4. c    3
  5. d    4
  6. e    5
Query:
Expand|Select|Wrap|Line Numbers
  1. DECLARE @t TABLE (item char(1), quantity int)
  2. INSERT INTO @t VALUES ('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)
  3.  
  4. ; WITH cte AS (
  5.     SELECT item, 
  6.         quantity - 1 AS quantityLeft
  7.     FROM @t
  8.  
  9.     UNION ALL
  10.  
  11.     SELECT item, 
  12.         quantityLeft - 1 AS quantityLeft
  13.     FROM 
  14.         cte
  15.     -- termination clause
  16.     WHERE quantityLeft > 0 
  17. )
  18.  
  19. SELECT * FROM cte ORDER BY item;
Results:
Expand|Select|Wrap|Line Numbers
  1. item    quantityLeft
  2. a    0
  3. b    1
  4. b    0
  5. c    1
  6. c    0
  7. c    2
  8. d    3
  9. d    2
  10. d    1
  11. d    0
  12. e    4
  13. e    3
  14. e    2
  15. e    1
  16. 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:
Expand|Select|Wrap|Line Numbers
  1. item
  2. a
  3. b
  4. c
  5. d
  6. e
Query:
Expand|Select|Wrap|Line Numbers
  1. DECLARE @t TABLE (item CHAR(1))
  2. INSERT INTO @t VALUES ('a'), ('b'), ('c'), ('d'), ('e')
  3. DECLARE @maxLen INT
  4. SET @maxLen = (SELECT COUNT(*) FROM @t)
  5.  
  6. -- Combination, order does not matter
  7. ; WITH cte AS (
  8.     SELECT item, 
  9.         CONVERT(VARCHAR(255), item) AS combined
  10.     FROM @t
  11.  
  12.     UNION ALL
  13.  
  14.     SELECT t.item,
  15.         CONVERT(VARCHAR(255), cte.combined + t.item) AS combined
  16.     FROM 
  17.         cte
  18.         INNER JOIN @t t
  19.         ON cte.item < t.item
  20.     WHERE LEN(cte.combined + t.item) <= @maxLen
  21. )
  22.  
  23. SELECT combined FROM cte ORDER BY LEN(combined), combined;
  24.  
  25.  
  26. -- Permutation, order matters
  27. ; WITH cte AS (
  28.     SELECT item, 
  29.         CONVERT(VARCHAR(255), item) AS combined
  30.     FROM @t
  31.  
  32.     UNION ALL
  33.  
  34.     SELECT t.item,
  35.         CONVERT(VARCHAR(255), cte.combined + t.item) AS combined
  36.     FROM 
  37.         cte
  38.         INNER JOIN @t t
  39.         ON cte.combined NOT LIKE '%' + t.item + '%'
  40.     WHERE LEN(cte.combined + t.item) <= @maxLen
  41. )
  42.  
  43. SELECT combined FROM cte ORDER BY LEN(combined), combined;
Combination Results:
Expand|Select|Wrap|Line Numbers
  1. combined
  2. a
  3. b
  4. c
  5. d
  6. e
  7. ab
  8. ac
  9. ad
  10. ae
  11. bc
  12. bd
  13. be
  14. cd
  15. ce
  16. de
  17. abc
  18. abd
  19. abe
  20. acd
  21. ace
  22. ade
  23. bcd
  24. bce
  25. bde
  26. cde
  27. abcd
  28. abce
  29. abde
  30. acde
  31. bcde
  32. 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:
Expand|Select|Wrap|Line Numbers
  1. IDField    fieldName
  2. 1    >>>>>>1.pdf test> >b>c>xyz.pdf bob >hello world.pdf foo >womp womp.pdf>
  3. 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.
Expand|Select|Wrap|Line Numbers
  1. DECLARE @f TABLE (fieldName VARCHAR(255), IDField int)
  2. INSERT INTO @f VALUES('>>>>>>1.pdf test> >b>c>xyz.pdf bob >hello world.pdf foo >womp womp.pdf>', 1)
  3. INSERT INTO @f VALUES('>2.pdf other unnecssary stuff > bar.pdf', 2)
  4.  
  5. ; WITH cte2 AS (
  6.     SELECT 
  7.         IDField,
  8.         --PATINDEX('%.pdf%', fieldName) + 3 AS PDFLocation,
  9.         --SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3)) AS PDFSubstring,
  10.         --REVERSE(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3))) AS PDFSubstringReverse,
  11.         --PATINDEX('%>%', REVERSE(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3)))) AS ReverseSymbolLocationBeforePDF,
  12.         --LEN(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3)))) + 2 AS SymbolLocationBeforePDF,
  13.  
  14.         CONVERT(VARCHAR(255), SUBSTRING(fieldName, 
  15.             LEN(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3)))) + 2, 
  16.             PATINDEX('%.pdf%', fieldName) + 3 - (LEN(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(fieldName, 1, (PATINDEX('%.pdf%', fieldName) + 3)))) + 2) + 1
  17.         )) AS PDFName,
  18.  
  19.         CONVERT(VARCHAR(255), STUFF(fieldName, 1, PATINDEX('%.pdf%', fieldName) + 3, '')) AS strWhatsLeft
  20.     FROM @f
  21.  
  22.     UNION ALL
  23.  
  24.     SELECT 
  25.         IDField,
  26.         --PATINDEX('%.pdf%', strWhatsLeft) + 3 AS PDFLocation,
  27.         --SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3)) AS PDFSubstring,
  28.         --REVERSE(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3))) AS PDFSubstringReverse,
  29.         --PATINDEX('%>%', REVERSE(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3)))) AS ReverseSymbolLocationBeforePDF,
  30.         --LEN(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3)))) + 2 AS SymbolLocationBeforePDF,
  31.  
  32.         CONVERT(VARCHAR(255), SUBSTRING(strWhatsLeft, 
  33.             LEN(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3)))) + 2, 
  34.             PATINDEX('%.pdf%', strWhatsLeft) + 3 - (LEN(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3))) - PATINDEX('%>%', REVERSE(SUBSTRING(strWhatsLeft, 1, (PATINDEX('%.pdf%', strWhatsLeft) + 3)))) + 2) + 1
  35.         )) AS PDFName,
  36.  
  37.         CONVERT(VARCHAR(255), STUFF(strWhatsLeft, 1, PATINDEX('%.pdf%', strWhatsLeft) + 3, '')) AS strWhatsLeft
  38.     FROM cte2
  39.     WHERE strWhatsLeft LIKE '%.pdf%'
  40. )
  41.  
  42. SELECT * FROM cte2 ORDER BY IDField
Results:
Expand|Select|Wrap|Line Numbers
  1. IDField    PDFName    strWhatsLeft
  2. 1    1.pdf     test> >b>c>xyz.pdf bob >hello world.pdf foo >womp womp.pdf>
  3. 1    xyz.pdf     bob >hello world.pdf foo >womp womp.pdf>
  4. 1    hello world.pdf     foo >womp womp.pdf>
  5. 1    womp womp.pdf    >
  6. 2    2.pdf     other unnecssary stuff > bar.pdf
  7. 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:
Expand|Select|Wrap|Line Numbers
  1. TimespanID    StartDate    EndDate
  2. 1    2015-01-01    2015-01-02
  3. 2    2015-01-05    2015-02-11
Query:
Expand|Select|Wrap|Line Numbers
  1. DECLARE @t TABLE (TimespanID int, StartDate DATE, EndDate DATE)
  2. INSERT INTO @t VALUES (1,'1/1/2015','1/2/2015'), (2, '1/5/2015', '2/11/2015')
  3.  
  4. ; WITH cte AS (
  5.     SELECT 
  6.         TimespanID,
  7.         StartDate,
  8.         CASE WHEN DATEADD(DAY, 2, StartDate) > EndDate
  9.             THEN EndDate
  10.             ELSE DATEADD(DAY, 2, StartDate)
  11.         END AS EndDate,
  12.         EndDate AS OriginalEndDate
  13.     FROM @t
  14.  
  15.     UNION ALL
  16.  
  17.     SELECT 
  18.         TimespanID,
  19.         DATEADD(DAY, 1, EndDate) AS StartDate,
  20.         CASE WHEN DATEADD(DAY, 3, EndDate) > OriginalEndDate
  21.             THEN OriginalEndDate
  22.             ELSE DATEADD(DAY, 3, EndDate)
  23.         END AS EndDate,
  24.         OriginalEndDate AS OriginalEndDate
  25.     FROM cte
  26.     WHERE DATEADD(DAY, 1, EndDate) <= OriginalEndDate
  27. )
  28.  
  29. SELECT * FROM cte ORDER BY TimespanID
Results:
Expand|Select|Wrap|Line Numbers
  1. TimespanID    StartDate    EndDate    OriginalEndDate
  2. 1    2015-01-01    2015-01-02    2015-01-02
  3. 2    2015-01-05    2015-01-07    2015-02-11
  4. 2    2015-01-08    2015-01-10    2015-02-11
  5. 2    2015-01-11    2015-01-13    2015-02-11
  6. 2    2015-01-14    2015-01-16    2015-02-11
  7. 2    2015-01-17    2015-01-19    2015-02-11
  8. 2    2015-01-20    2015-01-22    2015-02-11
  9. 2    2015-01-23    2015-01-25    2015-02-11
  10. 2    2015-01-26    2015-01-28    2015-02-11
  11. 2    2015-01-29    2015-01-31    2015-02-11
  12. 2    2015-02-01    2015-02-03    2015-02-11
  13. 2    2015-02-04    2015-02-06    2015-02-11
  14. 2    2015-02-07    2015-02-09    2015-02-11
  15. 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:
Expand|Select|Wrap|Line Numbers
  1. PK    EmployeeName    ParentID
  2. 1    Mr. CEO    0
  3. 2    Andy    1
  4. 3    Billy Jean    1
  5. 4    Charles    2
  6. 5    Danni    2
  7. 6    Eden    2
  8. 7    Frank    3
  9. 8    Geri    5
Query:
Expand|Select|Wrap|Line Numbers
  1. DECLARE @t TABLE (PK INT, EmployeeName VARCHAR(10), ParentID INT);
  2.  
  3. INSERT INTO @t VALUES
  4.     (1, 'Mr. CEO', 0),
  5.     (2, 'Andy',1 ),
  6.     (3, 'Billy Jean', 1),
  7.     (4, 'Charles', 2),
  8.     (5, 'Danni', 2),
  9.     (6, 'Eden', 2),
  10.     (7, 'Frank', 3),
  11.     (8, 'Geri', 5)
  12. ;
  13.  
  14. ; WITH cte AS (
  15.     SELECT
  16.         PK,
  17.         EmployeeName,
  18.         1 AS HierarchyLevel,
  19.         CONVERT(VARCHAR(255), PK) AS HierarchySortString
  20.     FROM @t
  21.     WHERE ParentID = 0
  22.  
  23.     UNION ALL
  24.  
  25.     SELECT
  26.         t.PK,
  27.         t.EmployeeName,
  28.         cte.HierarchyLevel + 1 AS HierarchyLevel,
  29.         CONVERT(VARCHAR(255), HierarchySortString + ',' + CONVERT(VARCHAR(255), t.PK)) AS HierarchySortString
  30.     FROM @t AS t
  31.         INNER JOIN cte
  32.         ON t.ParentID = cte.PK
  33. )
  34.  
  35. SELECT
  36.     PK,
  37.     REPLICATE('+', HierarchyLevel - 1) + EmployeeName AS EmployeeName,
  38.     HierarchyLevel
  39. FROM cte
  40. ORDER BY
  41.     HierarchySortString
Results:
Expand|Select|Wrap|Line Numbers
  1. PK    EmployeeName    HierarchyLevel
  2. 1    Mr. CEO    1
  3. 2    +Andy    2
  4. 4    ++Charles    3
  5. 5    ++Danni    3
  6. 8    +++Geri    4
  7. 6    ++Eden    3
  8. 3    +Billy Jean    2
  9. 7    ++Frank    3
Dec 7 '15 #1
1 4443
Canes816
3 2Bits
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
1 Week Ago #2

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

9 posts views Thread by JP SIngh | last post: by
2 posts views Thread by Perttu Pulkkinen | last post: by
1 post views Thread by David Fitzjarrell | last post: by
2 posts views Thread by Anand Krishnan | last post: by
3 posts views Thread by NatRoger | last post: by
2 posts views Thread by Jim Devenish | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.