CTE Performance on Recursive Queries

Hierarchy structures are widely used in data model and SQL Server implementation for real world entities like manageremployee relation, organizational structures, regional structures etc. In order to get all the descendants for a node in the hierarchy, we need to recursively query the children of the node, and the children of the children, and so on until we reach the leaf level. In SQL Server 2000, this is achieved by loops traversing all the levels under the node. SQL 2005 provides the new feature Common Table Expression (CTE), which can be used to solve this request.

Introduction

When CTE is used in recursive query, it consists of at least one anchor member and one recursive member, e.g., in the following sample that gets all the employees under the "Vice President of Production",

• [1] is the anchor member that queries the record for "Vice President of Production";
• [2] is the recursive member by referencing the CTE name AllEmps;
• [3] is the execution of the CTE;

USE AdventureWorks;
GO
WITH AllEmps (ManagerID, EmployeeID, ManagerTitle, EmpTitle, [Level])
AS
(
--[1]
SELECT E.ManagerID, E.EmployeeID, F.Title, E.Title, 0 AS [Level]
FROM HumanResources.Employee AS E,HumanResources.Employee AS F
WHERE E.Title='Vice President of Production' AND E.ManagerID=F.EmployeeID
UNION ALL
--[2]
SELECT E.ManagerID, E.EmployeeID, A.EmpTitle, E.Title, A.Level + 1
FROM HumanResources.Employee AS E
INNER JOIN AllEmps AS A ON E.ManagerID = A.EmployeeID
)
-- [3]
SELECT ManagerID, EmployeeID, ManagerTitle, EmpTitle, [Level]
FROM AllEmps
ORDER BY [Level],ManagerTitle,EmpTitle
GO

Though CTE provides a simple and neat solution for recursive queries in SQL 2005, we need to know its performance implication before we migrate existing code.

Performance Test

Hierarchy structures can be level intensive, i.e. the tree has many levels with fewer children under each node, or sub-node intensive, i.e. the tree has fewer levels with many children under each node. Tests are performed for these two extreme scenarios.

Test Environment

• Hardware: Desk top PC with P4 1.60GHz CPU, 1GB RAM, 200GB IDE hard drive without software or hardware RAID.
• Software: SQL server 2005 developer edition with SP2 on Windows 2003 Standard Edition;
• Table schema and the stored procedures (script):

The script creates one table and stored procedures used by the test. The table schema is as follow:

CREATE TABLE dbo.Groups
 ( GroupID int identity NOT NULL,
 GroupName nvarchar(100),
 ParentGroupID int NULL,
 [Description] nvarchar(150)
 )
ALTER TABLE dbo.Groups ADD CONSTRAINT PK_Groups PRIMARY KEY CLUSTERED (GroupID)
CREATE INDEX IX_Groups_ParentGroupID ON dbo.Groups (ParentGroupID)

The stored procedures used for descendants queries are dbo.GetDescendantsCTE and dbo.GetDescendantsLoop, which query all the descandant groups for a given group by CTE and loop respectively.

The stored procedures used for ancestors queries are dbo.GetAncestorsCTE and dbo.GetAncestorsLoop, which query all the ancestor groups for a given group by CTE and loop respectively.

Test Case Design

Tests to query descendants:

For each test case, nodes of different levels in the tree are selected and its descendants are queried by the two stored procedures respectively.

Test to query ancestors:

Test Results

• Test 1: Run CTETestPopulateData1.txt to populate test data, run all the test 1

  queries in CTETestByCTE.txt and CTETestByLoop.txt.

• Test 2: Run CTETestPopulateData2.txt to populate test data, run all the test 2

  queries in CTETestByCTE.txt and CTETestByLoop.txt.

• Test 3: Run CTETestPopulateData3.txt to populate test data, run all the test 3

  queries in CTETestByCTE.txt and CTETestByLoop.txt.

Results are shown in the following table and chart.

The results indicate that CTE is much slower than loop. When the number of children increases under each node, the performance of CTE gets worse quickly.

The following images are the actual execution plans of the recursive part for both methods. The plans do not give any clue to their performance difference. However, both plans have expensive key lookup operator due to the index seek operator in the plans.

To investigate whether key lookup on CTE and loop recursive queries has different behavior, I created two new stored procedures (dbo.GetDescendantsCTE2 and dbo.GetDescendantsLoop2) to keep only the key column GroupID of the index and [Level] in the CTE and the table variable. Other output columns are retrieved by join the CTE (table variable) with the table in the select statement, where clustered index seek is used:

SELECT G.GroupID, G.ParentGroupID, G.GroupName, P.GroupName AS ParentGroupName, D.[Level]
FROM Descendants D INNER JOIN dbo.Groups G ON D.GroupID=G.GroupID
LEFT JOIN dbo.Groups P ON G.ParentGroupID=P.GroupID
ORDER BY [Level],ParentGroupID,GroupID

Run CTETestPopulateData2.txt to populate test data, and run the "Test4" in both CTETestByCTE.txt and CTETestByLoop.txt. The following is the new recursive part execution plan for CTE. Both plans for CTE and loop eliminated the key lookup operator.

The results are showed below. The performance of both methods is improved by removing the key lookup.

In the query ancestor test, run CTETestPopulateData2.txt to populate the data, and run the "Test5" in both CTETestByCTE.txt and CTETestByLoop.txt. The result shows that performance of CTE is as good as, if not better than, traditional loop methods. I didnt test trees with more than 10 levels.

A test (script not included) to query descendants on a 10 level tree with one child per node shows that the performance of CTE and loop is also comparable.

Conclusion

CTE is a neat way to implement recursive queries. However its performance is generally more than 50% slower than the recursive query by the traditional loop method if recursive part of the query returns more than 1 record for each node like the query for descendants of a node in a tree. When the number of children under a node is increasing, the performance of CTE degrades even more quickly in the mentioned scenario.

If the recursive part returns one record for each node, e.g. queries for ancestors of a node in a tree, the performance of CTE is comparable as loop method.

In the recursive part of a CTE or loop method, if index seek is used in the execution plan, only including columns covered by indexes of the tables involved in the recursive query can improve performance.

Before migrating the recursive queries to CTE in your database, you need to understand the scenarios how data is queried and how heavy the recursive query load is in your system. In a busy OLTP system, 10ms degradation for highly concurrent calls can become bottleneck of the whole server.