Recursive Queries Using Common Table Expressions

Recursive Queries Using Common Tabl...

Community Content

In this section

Statistics Annotations (12)

Click here to expand

Collapse All

Language Filter

Other versions are also available for the following:

SQL Server 2005

Recursive Queries Using Common Table Expressions

A common table expression (CTE) provides the significant advantage of being able to reference itself, thereby creating a recursive CTE. A recursive CTE is one in which an initial CTE is repeatedly executed to return subsets of data until the complete result set is obtained.

A query is referred to as a recursive query when it references a recursive CTE. Returning hierarchical data is a common use of recursive queries, for example: Displaying employees in an organizational chart, or data in a bill of materials scenario in which a parent product has one or more components and those components may, in turn, have subcomponents or may be components of other parents.

A recursive CTE can greatly simplify the code required to run a recursive query within a SELECT, INSERT, UPDATE, DELETE, or CREATE VIEW statement. In earlier versions of SQL Server, a recursive query usually requires using temporary tables, cursors, and logic to control the flow of the recursive steps. For more information about common table expressions, see Using Common Table Expressions.

Structure of a Recursive CTE

The structure of the recursive CTE in Transact-SQL is similar to recursive routines in other programming languages. Although a recursive routine in other languages returns a scalar value, a recursive CTE can return multiple rows.

A recursive CTE consists of three elements:

Invocation of the routine.
The first invocation of the recursive CTE consists of one or more CTE_query_definitions joined by UNION ALL, UNION, EXCEPT, or INTERSECT operators. Because these query definitions form the base result set of the CTE structure, they are referred to as anchor members.
CTE_query_definitions are considered anchor members unless they reference the CTE itself. All anchor-member query definitions must be positioned before the first recursive member definition, and a UNION ALL operator must be used to join the last anchor member with the first recursive member.
Recursive invocation of the routine.
The recursive invocation includes one or more CTE_query_definitions joined by UNION ALL operators that reference the CTE itself. These query definitions are referred to as recursive members.
Termination check.
The termination check is implicit; recursion stops when no rows are returned from the previous invocation.

Note
An incorrectly composed recursive CTE may cause an infinite loop. For example, if the recursive member query definition returns the same values for both the parent and child columns, an infinite loop is created. When testing the results of a recursive query, you can limit the number of recursion levels allowed for a specific statement by using the MAXRECURSION hint and a value between 0 and 32,767 in the OPTION clause of the INSERT, UPDATE, DELETE, or SELECT statement. For more information, see Query Hints (Transact-SQL) and WITH common_table_expression (Transact-SQL).

Note

An incorrectly composed recursive CTE may cause an infinite loop. For example, if the recursive member query definition returns the same values for both the parent and child columns, an infinite loop is created. When testing the results of a recursive query, you can limit the number of recursion levels allowed for a specific statement by using the MAXRECURSION hint and a value between 0 and 32,767 in the OPTION clause of the INSERT, UPDATE, DELETE, or SELECT statement. For more information, see Query Hints (Transact-SQL) and WITH common_table_expression (Transact-SQL).

Pseudocode and Semantics

The recursive CTE structure must contain at least one anchor member and one recursive member. The following pseudocode shows the components of a simple recursive CTE that contains a single anchor member and single recursive member.

WITH cte_name ( column_name [,...n] )

(

CTE_query_definition –- Anchor member is defined.

UNION ALL

CTE_query_definition –- Recursive member is defined referencing cte_name.

)

-- Statement using the CTE

SELECT *

FROM cte_name

The semantics of the recursive execution is as follows:

Split the CTE expression into anchor and recursive members.
Run the anchor member(s) creating the first invocation or base result set (T0).
Run the recursive member(s) with Ti as an input and Ti+1 as an output.
Repeat step 3 until an empty set is returned.
Return the result set. This is a UNION ALL of T0 to Tn.

Example

The following example shows the semantics of the recursive CTE structure by returning a hierarchical list of employees, starting with the highest ranking employee, in the Adventure Works Cycles company. A walkthrough of the code execution follows the example.

Transact-SQL

-- Create an Employee table.
CREATE TABLE dbo.MyEmployees
(
    EmployeeID smallint NOT NULL,
    FirstName nvarchar(30)  NOT NULL,
    LastName  nvarchar(40) NOT NULL,
    Title nvarchar(50) NOT NULL,
    DeptID smallint NOT NULL,
    ManagerID int NULL,
 CONSTRAINT PK_EmployeeID PRIMARY KEY CLUSTERED (EmployeeID ASC) 
);
-- Populate the table with values.
INSERT INTO dbo.MyEmployees VALUES 
 (1, N'Ken', N'Sánchez', N'Chief Executive Officer',16,NULL)
,(273, N'Brian', N'Welcker', N'Vice President of Sales',3,1)
,(274, N'Stephen', N'Jiang', N'North American Sales Manager',3,273)
,(275, N'Michael', N'Blythe', N'Sales Representative',3,274)
,(276, N'Linda', N'Mitchell', N'Sales Representative',3,274)
,(285, N'Syed', N'Abbas', N'Pacific Sales Manager',3,273)
,(286, N'Lynn', N'Tsoflias', N'Sales Representative',3,285)
,(16,  N'David',N'Bradley', N'Marketing Manager', 4, 273)
,(23,  N'Mary', N'Gibson', N'Marketing Specialist', 4, 16);

Transact-SQL

USE AdventureWorks2008R2;
GO
WITH DirectReports (ManagerID, EmployeeID, Title, DeptID, Level)
AS
(
-- Anchor member definition
    SELECT e.ManagerID, e.EmployeeID, e.Title, edh.DepartmentID, 
        0 AS Level
    FROM dbo.MyEmployees AS e
    INNER JOIN HumanResources.EmployeeDepartmentHistory AS edh
        ON e.EmployeeID = edh.BusinessEntityID AND edh.EndDate IS NULL
    WHERE ManagerID IS NULL
    UNION ALL
-- Recursive member definition
    SELECT e.ManagerID, e.EmployeeID, e.Title, edh.DepartmentID,
        Level + 1
    FROM dbo.MyEmployees AS e
    INNER JOIN HumanResources.EmployeeDepartmentHistory AS edh
        ON e.EmployeeID = edh.BusinessEntityID AND edh.EndDate IS NULL
    INNER JOIN DirectReports AS d
        ON e.ManagerID = d.EmployeeID
)
-- Statement that executes the CTE
SELECT ManagerID, EmployeeID, Title, DeptID, Level
FROM DirectReports
INNER JOIN HumanResources.Department AS dp
    ON DirectReports.DeptID = dp.DepartmentID
WHERE dp.GroupName = N'Sales and Marketing' OR Level = 0;
GO

Example Code Walkthrough

The recursive CTE, DirectReports, defines one anchor member and one recursive member.

The anchor member returns the base result set T0. This is the highest ranking employee in the company; that is, an employee who does not report to a manager.

Here is the result set returned by the anchor member:

ManagerID EmployeeID Title                         Level
--------- ---------- ----------------------------- ------
NULL      1          Chief Executive Officer        0

The recursive member returns the direct subordinate(s) of the employee in the anchor member result set. This is achieved by a join operation between the Employee table and the DirectReports CTE. It is this reference to the CTE itself that establishes the recursive invocation. Based on the employee in the CTE DirectReports as input (Ti), the join (MyEmployees.ManagerID = DirectReports.EmployeeID) returns as output (Ti+1), the employees who have (Ti) as their manager. Therefore, the first iteration of the recursive member returns this result set:
```
ManagerID EmployeeID Title                         Level
--------- ---------- ----------------------------- ------
1         273        Vice President of Sales       1
```

The recursive member is activated repeatedly. The second iteration of the recursive member uses the single-row result set in step 3 (containing EmployeeID 273) as the input value, and returns this result set:

ManagerID EmployeeID Title                         Level
--------- ---------- ----------------------------- ------
273       16         Marketing Manager             2
273       274        North American Sales Manager  2
273       285        Pacific Sales Manager         2

The third iteration of the recursive member uses the result set above as the input value, and returns this result set:

ManagerID EmployeeID Title                         Level
--------- ---------- ----------------------------- ------
16        23         Marketing Specialist          3
274       275        Sales Representative          3
274       276        Sales Representative          3
285       286        Sales Representative          3

The final result set returned by the running query is the union of all result sets generated by the anchor and recursive members.

Here is the complete result set returned by the example:

ManagerID EmployeeID Title                         Level
--------- ---------- ----------------------------- ------
NULL      1          Chief Executive Officer       0
1         273        Vice President of Sales       1
273       16         Marketing Manager             2
273       274        North American Sales Manager  2
273       285        Pacific Sales Manager         2
16        23         Marketing Specialist          3
274       275        Sales Representative          3
274       276        Sales Representative          3
285       286        Sales Representative          3

Reference

WITH common_table_expression (Transact-SQL)

Query Hints (Transact-SQL)

INSERT (Transact-SQL)

UPDATE (Transact-SQL)

DELETE (Transact-SQL)

EXCEPT and INTERSECT (Transact-SQL)

Concepts

Using Common Table Expressions

Tags

: Add a tag

Community Content

Add new content

Annotations

Error using Recursive CTE, use of MAXRECURSION hint

manub22 | Edit | Show History

Error: The statement terminated. The maximum recursion 100 has been exhausted before statement completion.

Check this link: http://sqlwithmanoj.wordpress.com/2011/12/23/recursive-cte-maximum-recursion-100-has-been-exhausted/

Tags

: Add a tag

Flag as ContentBug

Simpler Example

Hector Protector ... Thomas Lee | Edit | Show History

This one has no unnecessary joins and the table aliases have meaning.

USE HYP_STUDIO_STAR_SCHEMA;
GO
WITH cteBU (Parent, Child, Alias, Level) -- BU stands for Business Unit
-- Anchor member definition
SELECT ANCHOR.BU_PARENT, ANCHOR.BU_CHILD, ANCHOR.BU_ALIAS, 0 AS Level
FROM dbo.DIM_BUSINESS_UNIT AS ANCHOR WHERE ANCHOR.BU_PARENT = 'Business Unit'
UNION ALL
-- Recursive member definition
SELECT RECURSE.BU_PARENT, RECURSE.BU_CHILD, RECURSE.BU_ALIAS,
Level + 1
FROM dbo.DIM_BUSINESS_UNIT AS RECURSE
INNER JOIN cteBU AS cteANCHOR
ON RECURSE.BU_PARENT = cteANCHOR.Child)
-- Statement that extracts using the CTE
SELECT Child "Business Unit", Parent, Alias
FROM cteBU
OPTION (Maxrecursion 10000) -- this isn't required; I believe default is 100
GO

Tags

: Add a tag

Flag as ContentBug

Why Joins

transformer78 ... Thomas Lee | Edit | Show History

Although it is a good example but too many unnecessary JOINS has messed the whole concept. I can achieve the same result with

WITH DirectReports (ManagerID, EmployeeID, Title, DeptID, Level)
(-- Anchor member definition
SELECT e.ManagerID, e.EmployeeID, e.Title, e.Deptid,
0 AS Level
FROM dbo.MyEmployees e
WHERE e.ManagerID IS NULL
UNION ALL
-- Recursive member definition
SELECT e.ManagerID, e.EmployeeID, e.Title, e.Deptid,
Level + 1
FROM dbo.MyEmployees AS e
INNER JOIN DirectReports AS
ON e.ManagerID = d.EmployeeID)
-- Statement that executes the CTE
SELECT ManagerID, EmployeeID, Title, Level
FROM DirectReports

I have just pasted it here so that anyone else does not frustrate with the use of JOINS in this example. a very good article is at http://www.simple-talk.com/sql/t-sql-programming/sql-server-cte-basics/ if anybody interested.

cheers

Tags

: Add a tag

Flag as ContentBug

Good Example

Joshua Ramirez | Edit | Show History

Maybe it's been improved, but I liked the example and the explanation. Nice job on this one.

Tags

: Add a tag

Flag as ContentBug

CTE recursion

manub22 | Edit | Show History

Examples of creating Number &;; Date sequences, Factorial &;; Fibonacci series by using recursive CTE.
Link: http://sqlwithmanoj.wordpress.com/2011/05/23/cte-recursion-sequence-dates-factorial-fibonacci-series/

Tags

: Add a tag

Flag as ContentBug

A CTE similar to the one given, but more realistic

Mihnea Rădulescu | Edit | Show History

use AdventureWorks;
go

with cteEmployeeLevel (EmployeeID, EmployeeName, EmployeeTitle, EmployeeLevel, ManagerName)
as
(
   select Employee.EmployeeID,
           EmployeeContact.LastName + ' ' + EmployeeContact.FirstName,
           Employee.Title,
           0,
           ManagerContact.LastName + ' ' + ManagerContact.FirstName
   from HumanResources.Employee as Employee
       left join HumanResources.Employee Manager on Employee.ManagerID = Manager.EmployeeID
       inner join Person.Contact as EmployeeContact on Employee.ContactID = EmployeeContact.ContactID
       left join Person.Contact as ManagerContact on Manager.ContactID = ManagerContact.ContactID
   where Employee.ManagerID is null
   union all
   select Employee.EmployeeID,
           EmployeeContact.LastName + ' ' + EmployeeContact.FirstName,
           Employee.Title,
           EmployeeLevel + 1,
           ManagerContact.LastName + ' ' + ManagerContact.FirstName
   from HumanResources.Employee as Employee
       inner join HumanResources.Employee Manager on Employee.ManagerID = Manager.EmployeeID
       inner join Person.Contact as EmployeeContact on Employee.ContactID = EmployeeContact.ContactID
       inner join Person.Contact as ManagerContact on Manager.ContactID = ManagerContact.ContactID
       inner join cteEmployeeLevel on Employee.ManagerID = cteEmployeeLevel.EmployeeID
)
select EmployeeName, EmployeeTitle, EmployeeLevel, ManagerName
from cteEmployeeLevel
order by EmployeeLevel asc;
go

Tags

: Add a tag

Flag as ContentBug

Simpler example based on given example - no joins!!

lghost | Edit | Show History

$0CREATE TABLE A ( ID int, Name varchar(12), ParentID int)$0 $0-- drop table A$0 $0-- Delete from A$0 $0select * From A$0 $0$0 $0 $0Insert into A (ID,Name,ParentID) values(1,'Greg',0)$0 $0Insert into A (ID,Name,ParentID) values(2,'Bill',0)$0 $0Insert into A (ID,Name,ParentID) values(3,'Amy',1)$0 $0Insert into A (ID,Name,ParentID) values(4,'Red',1)$0 $0Insert into A (ID,Name,ParentID) values(5,'Paul',4)$0 $0Insert into A (ID,Name,ParentID) values(6,'Forest',4)$0 $0Insert into A (ID,Name,ParentID) values(7,'Jade',3)$0 $0Insert into A (ID,Name,ParentID) values(8,'Mary',6)$0 $0Insert into A (ID,Name,ParentID) values(9,'Peter',6)$0 $0Insert into A (ID,Name,ParentID) values(10,'Joseph',6)$0 $0Insert into A (ID,Name,ParentID) values(11,'Juan',6)$0 $0Insert into A (ID,Name,ParentID) values(12,'Barbara',2)$0 $0Insert into A (ID,Name,ParentID) values(13,'Sue',2)$0 $0Insert into A (ID,Name,ParentID) values(14,'Steve',13)$0 $0Insert into A (ID,Name,ParentID) values(15,'Norma',14)$0 $0Insert into A (ID,Name,ParentID) values(16,'Monty',14)$0 $0Insert into A (ID,Name,ParentID) values(17,'Quame',14)$0 $0select * From A$0 $0$0 $0 $0WITH DirectReportsOfGreg (ManagerID, EmployeeID, EmployeeName, Level)$0 $0AS$0 $0( $0 $0-- Anchor$0 $0SELECT ParentID,ID, Name, 0 Level FROM A WHERE Name = 'Greg'$0 $0UNION ALL$0 $0-- Recursive Member Definition$0 $0SELECT ParentID,ID, a.Name, Level+1 FROM A $0 $0INNER JOIN DirectReportsOfGreg as b on A.ParentID = b.EmployeeID$0 $0)$0 $0$0 $0 $0-- Statement that executes the CTE$0 $0SELECT * FROM DirectReportsOfGreg $0 $0ORDER BY LEVEL$0 $0select * From A$0

Tags

: Add a tag

Flag as ContentBug

Good Information!

Deepthi Siripurapu | Edit | Show History

This is really useful when we have to loop through data in a table and particularly looping through each character of a value in the column. This helps us in writing loop queries in a single select statement!

Tags

: Add a tag

Flag as ContentBug

Not behaving as described

ThomasOfSouthBend | Edit | Show History

Consider, for Adventuirework db:
With OrgChart(EmployeeId, ContactId, ManagerId, Title ) AS
(
    SELECT EmployeeID, ContactID, ManagerID, [Title] From HumanResources.Employee Where managerid is null
    Union All
    SELECT e.EmployeeId, e.ContactId, e.ManagerId, e.Title
    From HumanResources.Employee e
        inner join OrgChart o on e.ManagerID = o.EmployeeID
)
SELECT EmployeeId, ContactId, ManagerId, Title From OrgChart
option(Maxrecursion 1)

At recursion 1, the Top manager and 6 immediate - 2nd level - subordinates returned. So far so good. With Maxrecursion 2, only subordinates of one 2nd level manager are returned. It is not until Maxrecursion 3 that subordinates of the other level 2 managers are selected. There are other anomalies as well. What is wrong with recursion?

Tags

: Add a tag

Flag as ContentBug

Simplest example

elvedrano | Edit | Show History

To get you started, here's the simplest cte recursion example I could think of:

WITH cte
AS (
SELECT -- anchor member
1 AS n
UNION ALL
SELECT -- recursive member
n + 1
FROM
cte
WHERE
-- terminator
n < 50)
SELECT
*
FROM
cte

Tags

: Add a tag

Flag as ContentBug

Bad Example

Kevin Earley | Edit | Show History

Ditto for #2 below...

Tags

: contentbug (x) Add a tag

Bad example

Hansjörg1 | Edit | Show History

Why have an example for recursive queries that contains a join? This is simply confusing and makes
reading the example harder. Better example: a single table that references itself e.g. Region (RegionID, RegionName, ParentRegionID) with
data from continents and countries.

Tags

: contentbug (x) Add a tag