{"id":1800,"date":"2014-04-28T00:00:00","date_gmt":"2014-04-28T00:00:00","guid":{"rendered":"https:\/\/test.simple-talk.com\/uncategorized\/the-performance-of-traversing-a-sql-hierarchy\/"},"modified":"2021-06-03T16:44:07","modified_gmt":"2021-06-03T16:44:07","slug":"the-performance-of-traversing-a-sql-hierarchy","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/performance-sql-server\/the-performance-of-traversing-a-sql-hierarchy\/","title":{"rendered":"The Performance of Traversing a SQL Hierarchy"},"content":{"rendered":"<div id=\"pretty\">\n<h1>The Performance of Traversing a SQL Hierarchy<\/h1>\n<p>It is well known, and blogged to death, that the way to traverse a hierarchy that is stored in a T-SQL table as an adjacency list, is to use a recursive Common Table Expression (rCTE). But what if there was a faster way of traversing an adjacency list? Would you use it?<\/p>\n<p>The adjacency list approach to saving a hierarchy is quite common and can represent:<\/p>\n<ul>\n<li>Reporting levels between managers and their successive employees.<\/li>\n<li>A parts hierarchy, particularly the case of parts in a kit with the kit\/assembly having multiple levels. Another example is parts succession, where older parts are replaced by newer ones.<\/li>\n<li>A Bill of Materials (BOM).<\/li>\n<\/ul>\n<p>Today we&#8217;ll look at various ways a hierarchy represented as an adjacency list can be traversed and compare the elapsed times for each method.<\/p>\n<h2>Data Setup &#8211; A Simple Hierarchy as an Adjacency List<\/h2>\n<p>Let&#8217;s create an adjacency list (<strong>ManagersDirectory<\/strong>) and insert a simple hierarchy into it.<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\tCREATE TABLE dbo.ManagersDirectory\r\n\t(\r\n\t\u00a0\u00a0\u00a0 ManagerID\u00a0\u00a0 INT\r\n\t\u00a0\u00a0\u00a0 ,EmployeeID INT\r\n\t\u00a0\u00a0\u00a0 ,CONSTRAINT md_pk1 PRIMARY KEY (ManagerID, EmployeeID)\r\n\t);\r\n\tGO\r\n\t\r\n\tINSERT INTO dbo.ManagersDirectory\r\n\t-- Level 1 elements\r\n\tSELECT 1, 10 UNION ALL SELECT 1, 20 UNION ALL SELECT 1, 30\r\n\t-- Level 2 elements\r\n\tUNION ALL SELECT 10, 100 UNION ALL SELECT 10, 101 UNION ALL SELECT 10, 102\r\n\tUNION ALL SELECT 20, 200 UNION ALL SELECT 20, 201 UNION ALL SELECT 20, 202\r\n\tUNION ALL SELECT 30, 300 UNION ALL SELECT 30, 301 UNION ALL SELECT 30, 302\r\n\t-- Level 3 elements\r\n\tUNION ALL SELECT 100, 1000 UNION ALL SELECT 100, 1001 UNION ALL SELECT 100, 1002\r\n\tUNION ALL SELECT 200, 2000 UNION ALL SELECT 200, 2001 UNION ALL SELECT 200, 2002\r\n\tUNION ALL SELECT 300, 3000 UNION ALL SELECT 300, 3001 UNION ALL SELECT 300, 3002\r\n\tUNION ALL SELECT 101, 1003 UNION ALL SELECT 101, 1004 UNION ALL SELECT 101, 1005\r\n\tUNION ALL SELECT 201, 2003 UNION ALL SELECT 201, 2004 UNION ALL SELECT 201, 2005\r\n\tUNION ALL SELECT 301, 3003 UNION ALL SELECT 301, 3004 UNION ALL SELECT 301, 3005\r\n\tUNION ALL SELECT 102, 1006 UNION ALL SELECT 102, 1007 UNION ALL SELECT 102, 1008\r\n\tUNION ALL SELECT 202, 2006 UNION ALL SELECT 202, 2007 UNION ALL SELECT 202, 2008\r\n\tUNION ALL SELECT 302, 3006 UNION ALL SELECT 302, 3007 UNION ALL SELECT 302, 3008;\r\n\t\r\n\tSELECT ManagerID, EmployeeID\r\n\tFROM dbo.ManagersDirectory;\r\n<\/pre>\n<p>The final <strong>SELECT<\/strong> returns all 39 elements we&#8217;ve created in our adjacency list. We put a primary key on the most common place you&#8217;d expect to find one: <strong>ManagerID<\/strong> and <strong>EmployeeID<\/strong>.<\/p>\n<p>Pictorially, this hierarchy looks like this (three children reporting to each parent):<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/imported\/1980-13a87884-0fa3-4171-94b9-3e6a34447f97.png\" alt=\"1980-13a87884-0fa3-4171-94b9-3e6a34447f9\" \/><\/p>\n<h2>Traverse the Hierarchy Using a Traditional rCTE<\/h2>\n<p>When we generate the traversal, we add a level counter and a string that represents the manager-to-employee reporting relationship for this hierarchy. It uses the same rCTE that you&#8217;ve seen many times before. You&#8217;ll have to excuse me for complaining about everyone rehashing this over and over, while I&#8217;m doing the same, but hopefully in the end I&#8217;ll add a little value.<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t \tDECLARE @TopLevel INT = 1\u00a0\u00a0\u00a0 -- Top level manager (node)\r\n\t\u00a0\u00a0\u00a0 ,@NumLevels\u00a0\u00a0 INT = 3;\u00a0\u00a0 -- Depth of the hiearchy to traverse\r\n\t\r\n\tWITH HierarchyTraaversal AS\r\n\t(\r\n\t\u00a0\u00a0\u00a0 -- rCTE anchor: retrieve the top level node\r\n\t\u00a0\u00a0\u00a0 SELECT [Level]=1, ManagerID, EmployeeID\r\n\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ,MgrEmp=CAST(ManagerID AS VARCHAR(8000)) + '\/' + CAST(EmployeeID AS VARCHAR(8000))\r\n\t\u00a0\u00a0\u00a0 FROM dbo.ManagersDirectory\r\n\t\u00a0\u00a0\u00a0 WHERE ManagerID = @TopLevel\r\n\t\u00a0\u00a0\u00a0\u00a0 \r\n\t\u00a0\u00a0\u00a0 UNION ALL\r\n\t\u00a0\u00a0\u00a0 \r\n\t\u00a0\u00a0\u00a0 -- rCTE recursion: retrieve the following nodes\r\n\t\u00a0\u00a0\u00a0 SELECT [Level]+1, a.ManagerID, a.EmployeeID\r\n\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ,MgrEmp=MgrEmp + '\/' + CAST(a.EmployeeID AS VARCHAR(8000))\r\n\t\u00a0\u00a0\u00a0 FROM dbo.ManagersDirectory a\r\n\t\u00a0\u00a0\u00a0 JOIN HierarchyTraaversal b ON b.EmployeeID = a.ManagerID\r\n\t\u00a0\u00a0\u00a0 WHERE [Level] &lt; @NumLevels --+ 1\r\n\t)\r\n\tSELECT [Level], ManagerID, EmployeeID, MgrEmp\r\n\tFROM HierarchyTraaversal\r\n\tORDER BY [Level], ManagerID, EmployeeID;\r\n<\/pre>\n<p>This produces the fairly familiar results (39 rows), abbreviated below:<\/p>\n<pre>\t\tLevel\u00a0\u00a0 ManagerID\u00a0\u00a0 EmployeeID\u00a0 MgrEmp\r\n\t\t1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 10\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\/10\r\n\t\t1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 20\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\/20\r\n\t\t1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 30\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\/30\r\n\t\t2\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 10\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 100\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\/10\/100\r\n\t\t2\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 10\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 101\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\/10\/101\r\n\t\t&lt;snip&gt;\r\n\t\t3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 301\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 3005\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\/30\/301\/3005\r\n\t\t3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 302\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 3006\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\/30\/302\/3006\r\n\t\t3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 302\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 3007\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\/30\/302\/3007\r\n\t\t3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 302\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 3008\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\/30\/302\/3008\u00a0 \r\n\t\t<\/pre>\n<h2>A Non-traditional Hierarchy Traversal in T-SQL<\/h2>\n<p>It has been said that T-SQL only supports recursion through a recursive CTE. Or does it? Let&#8217;s see if we can persuade SQL Server to let us create a recursive FUNCTION:<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t\t\t CREATE FUNCTION dbo.HierarchyTraversal\r\n\t\t\t (\r\n\t\t\t \u00a0\u00a0\u00a0 @Levels\u00a0\u00a0\u00a0\u00a0\u00a0 INT\r\n\t\t\t \u00a0\u00a0\u00a0 ,@TopLevel\u00a0\u00a0 INT\r\n\t\t\t )\r\n\t\t\t RETURNS @H TABLE \r\n\t\t\t (\r\n\t\t\t \u00a0\u00a0\u00a0 [Level] INT\r\n\t\t\t \u00a0\u00a0\u00a0 ,ManagerID INT\r\n\t\t\t \u00a0\u00a0\u00a0 ,EmployeeID INT\r\n\t\t\t \u00a0\u00a0\u00a0 ,MgrEmp\u00a0 VARCHAR(8000)\r\n\t\t\t ) \r\n\t\t\t AS BEGIN\r\n\t\t\t \u00a0\u00a0\u00a0 IF @Levels &gt; 0\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 INSERT INTO @H\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 -- The top level manager\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT 1, ManagerID, EmployeeID\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ,CAST(ManagerID AS VARCHAR(8000)) + '\/' + CAST(EmployeeID AS VARCHAR(8000)) \r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM dbo.ManagersDirectory\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WHERE ManagerID = @TopLevel\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0  \r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 UNION ALL\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0  \r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 -- The remainder of the hierarchy\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT [Level]+1, a.ManagerID, a.EmployeeID\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ,MgrEmp + '\/' + CAST(a.EmployeeID AS VARCHAR(8000))\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM dbo.ManagersDirectory a\r\n\t\t\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 JOIN dbo.HierarchyTraversal(@Levels-1, @TopLevel) b ON b.EmployeeID = a.ManagerID;\r\n\t\t\t \u00a0\u00a0\u00a0 RETURN\r\n\t\t\t END\r\n\t<\/pre>\n<p>Note where we reference <strong>dbo.Hierarchy<\/strong><strong>Traversal<\/strong> (the FUNCTION we are creating) in the JOIN. Thanks to the miracle of deferred name resolution we gleefully receive the message back from SQL Server Management Studio (SSMS) that our &#8220;Command(s) completed successfully.&#8221;<\/p>\n<p>When we run this FUNCTION to traverse our adjacency list:<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t\tSELECT [Level], ManagerID, EmployeeID, MgrEmp\r\n\t\tFROM dbo.HierarchyTraversal(@NumLevels, @TopLevel)\r\n\t\tORDER  BY [Level], ManagerID, EmployeeID;\r\n\t<\/pre>\n<p>We behold with wonder that the returned results are identical to those returned by the rCTE!<\/p>\n<p>Note that the FUNCTION cannot be given the property WITH SCHEMABINDING, nor can it be an in-line Table Valued FUNCTION (TVF). It only works with a multi-line TVF. Another limitation is that if you ever exceed 32 levels, this function is going to throw an error.<\/p>\n<h2>The Method of Repeating JOINs<\/h2>\n<p>Another way to do this is with a series of repeating JOINs, using UNION ALL operators to combine each successive level. For our tiny hierarchy, this can be achieved as follows:<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t\t-- Manager level node and its children\r\n\t\tSELECT [Level]=1, ManagerID, EmployeeID\r\n\t\t\u00a0\u00a0\u00a0 ,MgrEmp=CAST(ManagerID AS VARCHAR(8000)) + '\/' + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(EmployeeID AS VARCHAR(8000))\r\n\t\tFROM dbo.ManagersDirectory a1\r\n\t\tWHERE a1.ManagerID = @TopLevel\r\n\t\tUNION ALL\r\n\t\t-- Children of the manager level node plus those children\r\n\t\tSELECT [Level]=2, a2.ManagerID, a2.EmployeeID\r\n\t\t\u00a0\u00a0\u00a0 ,MgrEmp=CAST(a1.ManagerID AS VARCHAR(8000)) + '\/' + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(a2.ManagerID AS VARCHAR(8000)) + '\/' + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(a2.EmployeeID AS VARCHAR(8000))\r\n\t\tFROM dbo.ManagersDirectory a1\r\n\t\tJOIN dbo.ManagersDirectory a2 ON a1.EmployeeID = a2.ManagerID\r\n\t\tWHERE a1.ManagerID = @TopLevel \r\n\t\tUNION ALL\r\n\t\t-- Final levels\r\n\t\tSELECT [Level]=3, a3.ManagerID, a3.EmployeeID\r\n\t\t\u00a0\u00a0\u00a0 ,MgrEmp=CAST(a1.ManagerID AS VARCHAR(8000)) + '\/' + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(a2.ManagerID AS VARCHAR(8000)) + '\/' + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(a3.ManagerID AS VARCHAR(8000)) + '\/' + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(a3.EmployeeID AS VARCHAR(8000))\r\n\t\tFROM dbo.ManagersDirectory a1\r\n\t\tJOIN dbo.ManagersDirectory a2 ON a1.EmployeeID = a2.ManagerID\r\n\t\tJOIN dbo.ManagersDirectory a3 ON a2.EmployeeID = a3.ManagerID\r\n\t\tWHERE a1.ManagerID = @TopLevel;\r\n\t<\/pre>\n<p>This too returns the same results as our prior attempts. Of course, it only works if you reconstruct the query based on the number of levels you want to traverse, unless you construct the query with dynamic SQL.<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t\tDECLARE @SQL\u00a0\u00a0\u00a0 NVARCHAR(MAX) = N''\r\n\t\t\u00a0\u00a0\u00a0 ,@SQLParms\u00a0 NVARCHAR(MAX) = N'@TopLevel INT'\r\n\t\t\u00a0\u00a0\u00a0 ,@J\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 INT = 1\r\n\t\t\u00a0\u00a0\u00a0 ,@J1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 VARCHAR(2)\r\n\t\t\u00a0\u00a0\u00a0 ,@RC\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 INT;\r\n\t\t\r\n\t\tWHILE @J &lt;= @NumLevels + 1\r\n\t\tBEGIN\r\n\t\t\u00a0\u00a0\u00a0 -- This character string version of @J is used frequently in later string concatenations\r\n\t\t\u00a0\u00a0\u00a0 SELECT @J1 = CAST(@J AS VARCHAR);\r\n\t\t\r\n\t\t\u00a0\u00a0\u00a0 -- The Tally table must return enough numbers to handle the number of desired levels.\r\n\t\t\u00a0\u00a0\u00a0 -- @NumLevels was set earlier to 3.\r\n\t\t\u00a0\u00a0\u00a0 WITH Tally (n) AS\r\n\t\t\u00a0\u00a0\u00a0  (\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT 1+ROW_NUMBER() OVER (ORDER BY (SELECT NULL))\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM (VALUES(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0)) a(n)\r\n\t\t\u00a0\u00a0\u00a0 )\r\n\t\t\u00a0\u00a0\u00a0 SELECT @SQL = @SQL + 'SELECT [Level]=' + @J1 + ', a' + @J1 + '.ManagerID, a' + @J1 + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 '.EmployeeID' + CHAR(10) + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 '\u00a0\u00a0\u00a0 ,MgrEmp=CAST(a1.ManagerID AS VARCHAR(8000)) + ''\/'' + ' + CHAR(10) +\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ISNULL((\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT '\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(a' + CAST(n AS VARCHAR) + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 '.ManagerID AS VARCHAR(8000)) + ''\/'' +' + CHAR(10)\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM Tally\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WHERE n BETWEEN 2 AND @J\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FOR XML PATH(''), TYPE\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ).value('.', 'NVARCHAR(4000)'), '') +\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 '\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(a' + @J1 + '.EmployeeID AS VARCHAR(8000))' + CHAR(10) +\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 -- Used in our performance test harness to suppress display of the final results\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 -- CASE @J WHEN 1 THEN 'INTO #Temp3' + CHAR(10) ELSE '' END +\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 'FROM dbo.ManagersDirectory a1' + CHAR(10) +\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ISNULL((\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT 'JOIN dbo.ManagersDirectory a' + CAST(n AS VARCHAR) + ' ON a' + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(N-1 AS VARCHAR) + '.EmployeeID = a' + CAST(N AS VARCHAR) + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 '.ManagerID' + CHAR(10)\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM Tally\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WHERE n BETWEEN 2 AND @J\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FOR XML PATH, TYPE\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ).value('.', 'NVARCHAR(4000)'), '') +\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 'WHERE a1.ManagerID = @TopLevel ' + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CASE WHEN @J &lt; @NumLevels + 1 THEN CHAR(10) + 'UNION ALL' + CHAR(10) ELSE '' END;\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \r\n\t\t\u00a0\u00a0\u00a0 SELECT @J = @J + 1;\r\n\t\tEND\r\n\t\t\r\n\t\tPRINT @SQL;\r\n\t\t-- EXEC sp_executesql @SQL, @SQLParms, @TopLevel = @TopLevel;\r\n\t\t\r\n<\/pre>\n<p>A look at the printed SQL query should show that it is identical to the first but will grow in size and complexity depending on the number of levels (<strong>@<\/strong><strong>NumLevels<\/strong>) you&#8217;ve set. Note the line we commented out in the middle, which we&#8217;ll use in our test harness later to dump the results to a temporary table when we do our timings.<\/p>\n<h2>The Set-based Loop<\/h2>\n<p>Since any recursive CTE can always be rewritten as a set-based loop, even though I don&#8217;t particularly like loops, we&#8217;ll give it a go nonetheless.<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t\t-- The first select is equivalent to the anchor leg of the rCTE.\r\n\t\t-- It creates the temporary table we'll store results for each iteration of the loop.\r\n\t\tSELECT [Level]=ISNULL(1, 0)\r\n\t\t\u00a0\u00a0\u00a0 ,ManagerID=ISNULL(ManagerID, 0)\r\n\t\t\u00a0\u00a0\u00a0 ,EmployeeID=ISNULL(EmployeeID, 0)\r\n\t\t\u00a0\u00a0\u00a0 ,MgrEmp=CAST(ManagerID AS VARCHAR(8000)) + '\/' + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(EmployeeID AS VARCHAR(8000))\r\n\t\tINTO #Temp1\r\n\t\tFROM dbo.ManagersDirectory a1\r\n\t\tWHERE a1.ManagerID = @TopLevel\r\n\t\t\r\n\t\t-- Add a PRIMARY KEY to hopefully make the later JOIN a bit more efficient\r\n\t\tALTER TABLE #Temp1 ADD CONSTRAINT t_pk PRIMARY KEY ([Level], ManagerID, EmployeeID);\r\n\t\t\r\n\t\tDECLARE @I INT = 2;\r\n\t\t\r\n\t\tWHILE @I &lt; @NumLevels + 1\r\n\t\tBEGIN\r\n\t\t\u00a0\u00a0\u00a0 -- Insert each successive level into the temporary table.\r\n\t\t\u00a0\u00a0\u00a0 INSERT INTO #Temp1\r\n\t\t\u00a0\u00a0\u00a0 SELECT @I, b.ManagerID, b.EmployeeID\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ,MgrEmp=MgrEmp + '\/' + CAST(b.EmployeeID AS VARCHAR(8000))\r\n\t\t\u00a0\u00a0\u00a0 FROM #Temp1 a\r\n\t\t\u00a0\u00a0\u00a0 JOIN dbo.ManagersDirectory b ON a.EmployeeID = b.ManagerID\r\n\t\t\u00a0\u00a0\u00a0 WHERE [Level] = @I - 1\r\n\t\t\u00a0\u00a0\u00a0 -- This is explained below.\r\n\t\t\u00a0\u00a0\u00a0 OPTION (RECOMPILE);\r\n\t\t\u00a0\u00a0\u00a0\u00a0 \r\n\t\t\u00a0\u00a0\u00a0 SELECT @I = @I + 1;\r\n\t\tEND\r\n\t\t\r\n\t\tSELECT [Level], ManagerID, EmployeeID, MgrEmp\r\n\t\tFROM #Temp1\r\n\t\tORDER BY [Level], ManagerID, EmployeeID;\r\n\t<\/pre>\n<p>Once again, a check against our expected results shows they match. Note that, since we&#8217;re using #Temp1 to JOIN back to the <strong>ManagersDirectory<\/strong> table, having an index (the primary key) on the temporary table should improve the performance over the case where we have only a heap.<\/p>\n<p>All of the queries we&#8217;ve shown so far, including the CREATE for our function, and the next one are in the attached resource file: <strong><em>01 Example Queries.sql<\/em><\/strong>.<\/p>\n<p>You may have noticed the <strong>OPTION (RECOMPILE) <\/strong>on the query within the loop. We were concerned about parameter sniffing impacting the performance of the query. So, of course, we tested that using <strong><em>02 Loop With and Without RECOMPILE.sql<\/em><\/strong> and concluded that the query generally runs faster with the <strong>OPTION <\/strong>than without it. You can try it yourself at various levels to confirm our conclusion.<\/p>\n<h2>The WHILE Loop Revisited<\/h2>\n<p>Since we&#8217;ve taken our WHILE loop on a test drive, let&#8217;s drive it all the way to Memphis and see if we can meet Elvis.\u00a0 As perversely absurd as that sounds, the question that follows may seem even more so.\u00a0 Is it possible that our WHILE loop hierarchy traversal may be impacted by the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Halloween_Problem\">Halloween Problem<\/a>?\u00a0 I first learned about this and the SQL Optimizer&#8217;s Halloween protection in <a href=\"http:\/\/mvp.microsoft.com\/en-us\/mvp\/Itzik%20Ben-Gan-6819\">SQL MVP<\/a> Itzik Ben-Gan&#8217;s article: <a href=\"http:\/\/sqlmag.com\/t-sql\/identifying-subsequence-in-sequence-part-1\">Identifying a Subsequence in a Sequence, Part 1<\/a>, where he implemented a method of avoiding SQL&#8217;s Halloween protection in his third solution.\u00a0 I found the problem interesting, so I was testing that solution and was frankly amazed at the lightning speed that it processed his ten million rows of test data, literally trouncing the first set-based solutions that I could come up with.\u00a0 The similarity of what he was doing (INSERTs into an indexed temporary table within the loop) got me to thinking that it may be applicable here.\u00a0 \u00a0So I read the outstanding articles he recommended by <a href=\"http:\/\/mvp.microsoft.com\/en-us\/mvp\/Paul%20White-4032572\">SQL MVP<\/a> Paul White, who clearly showed that Halloween protection can impact INSERTs (and DELETEs and MERGEs) in addition to UPDATEs. \u00a0More reading led me to another article by Itzik Ben-Gan: <a href=\"http:\/\/sqlmag.com\/t-sql\/divide-and-conquer-halloween\">Divide and Conquer Halloween<\/a>, where he addressed the hierarchy traversal problem directly.\u00a0<\/p>\n<p>His solution modified to our requirements is shown below with two changes: 1) I added the <strong>OPTION(RECOMPILE)<\/strong> because I did a little pre-performance testing and it seemed to be marginally better and 2) his solution always traverses the entire hierarchy while I&#8217;d like mine to only go as deep as I tell it to (using <strong>@<\/strong><strong>NumLevels<\/strong>).<\/p>\n<p>First we must create two indexed temporary tables.<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t\tCREATE TABLE #Temp3\r\n\t\t(\r\n\t\t\u00a0\u00a0\u00a0 [Level] INT\r\n\t\t\u00a0\u00a0\u00a0 ,ManagerID\u00a0 INT\r\n\t\t\u00a0\u00a0\u00a0 ,EmployeeID INT\r\n\t\t\u00a0\u00a0\u00a0 ,MgrEmp VARCHAR(8000)\r\n\t\t\u00a0\u00a0\u00a0 ,CONSTRAINT t3_pk PRIMARY KEY([Level], ManagerID, EmployeeID)\r\n\t\t);\r\n\t\t\r\n\t\tCREATE TABLE #Temp4\r\n\t\t(\r\n\t\t\u00a0\u00a0\u00a0 [Level] INT\r\n\t\t\u00a0\u00a0\u00a0 ,ManagerID\u00a0 INT\r\n\t\t\u00a0\u00a0\u00a0 ,EmployeeID INT\r\n\t\t\u00a0\u00a0\u00a0 ,MgrEmp VARCHAR(8000)\r\n\t\t\u00a0\u00a0\u00a0 ,CONSTRAINT t4_pk PRIMARY KEY([Level], ManagerID, EmployeeID)\r\n\t\t);\r\n\t<\/pre>\n<p>We then populate the two temporary tables, avoiding the SQL Optimizer&#8217;s need to provide Halloween protection by alternating our <strong>INSERT<\/strong>s between the two temporary tables.<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t\t-- Insert the parent level\r\n\t\tINSERT INTO #Temp3\r\n\t\tSELECT [Level]=ISNULL(1,0), ManagerID=ISNULL(ManagerID,0), EmployeeID=ISNULL(EmployeeID,0)\r\n\t\t\u00a0\u00a0\u00a0 ,MgrEmp=CAST(ManagerID AS VARCHAR(8000)) + '\/' + \r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CAST(EmployeeID AS VARCHAR(8000))\r\n\t\tFROM dbo.ManagersDirectory2 a1\r\n\t\tWHERE a1.ManagerID = @TopLevel;\r\n\t\t\r\n\t\tWHILE @I &lt; @NumLevels + 1\r\n\t\tBEGIN\r\n\t\t\u00a0\u00a0\u00a0 -- Insert each successive level into the temporary table.\r\n\t\t\u00a0\u00a0\u00a0 IF @I % 2 = 0\r\n\t\t\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0-- Even iterations go into #Temp4\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 INSERT INTO #Temp4\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT @I, b.ManagerID, b.EmployeeID\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ,MgrEmp=MgrEmp + '\/' + CAST(b.EmployeeID AS VARCHAR(8000))\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM #Temp3 a\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 JOIN dbo.ManagersDirectory2 b ON a.EmployeeID = b.ManagerID\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WHERE [Level] = @I - 1\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OPTION (RECOMPILE);\r\n\t\t\u00a0\u00a0\u00a0 ELSE\r\n\t\t\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0-- Odd iterations go into #Temp3\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 INSERT INTO #Temp3\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT @I, b.ManagerID, b.EmployeeID\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ,MgrEmp=MgrEmp + '\/' + CAST(b.EmployeeID AS VARCHAR(8000))\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM #Temp4 a\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 JOIN dbo.ManagersDirectory2 b ON a.EmployeeID = b.ManagerID\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WHERE [Level] = @I - 1\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OPTION (RECOMPILE);\r\n\t\t\u00a0\u00a0\u00a0\u00a0 \r\n\t\t\u00a0\u00a0\u00a0 SELECT @I = @I + 1;\r\n\t\tEND\r\n\t<\/pre>\n<p>Now we just need to combine the results stored into our two temporary tables to obtain our hierarchy traversal.<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t\t-- Combine the results to get the hierarchy traversal\r\n\t\tSELECT [Level], ManagerID, EmployeeID, MgrEmp\r\n\t\tFROM #Temp3\r\n\t\tUNION ALL\r\n\t\tSELECT [Level], ManagerID, EmployeeID, MgrEmp\r\n\t\tFROM #Temp4\r\n\t\tORDER BY [Level], ManagerID, EmployeeID;\r\n\t\t\r\n<\/pre>\n<p>Since Itzik Ben-Gan and Paul White are both so much more eloquent and technically skilled than me, we&#8217;ll leave the explanation of detecting, and why avoiding, Halloween protection is a good thing.<\/p>\n<h2>A Bigger Test Harness<\/h2>\n<p>After learning rather quickly that generating a large test harness for an adjacency list can be quite annoying, we finally managed to do so as follows. This extends the hierarchy adding three nodes to each prior node for each iteration of the <strong>WHILE<\/strong> loop.<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t\t-- Remove our small hierarchy table and add a column we'll use to generate more levels\r\n\t\tTRUNCATE TABLE dbo.ManagersDirectory;\r\n\t\tALTER TABLE dbo.ManagersDirectory ADD [Level] INT;\r\n\t\tGO\r\n\t\t\r\n\t\t-- The first entry is the top level parent plus three children\r\n\t\tINSERT INTO dbo.ManagersDirectory\r\n\t\tSELECT 1, 2, 1 UNION ALL SELECT 1, 3, 1 UNION ALL SELECT 1, 4, 1;\r\n\t\t\r\n\t\tDECLARE @Level INT = 1;\r\n\t\t\r\n\t\tWHILE @Level &lt;= 13\r\n\t\tBEGIN\r\n\t\t\u00a0\u00a0\u00a0 INSERT INTO dbo.ManagersDirectory (ManagerID, EmployeeID, [Level])\r\n\t\t\u00a0\u00a0\u00a0 SELECT EmployeeID, ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) +\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 -- Next employee numbers will just be integers from ROW_NUMBER() above added to this.\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0  (SELECT MAX(EmployeeID) FROM dbo.ManagersDirectory)\r\n\t\t\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ,@Level + 1\r\n\t\t\u00a0\u00a0\u00a0 FROM dbo.ManagersDirectory a\r\n\t\t\u00a0\u00a0\u00a0 -- This small tally table generates 3 nodes for each previous level's entry\r\n\t\t\u00a0\u00a0\u00a0 CROSS JOIN (SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3) b(n)\r\n\t\t\u00a0\u00a0\u00a0 WHERE [Level] = @Level;\r\n\t\t\r\n\t\t\u00a0\u00a0\u00a0 SELECT @Level = @Level + 1;\r\n\t\tEND\r\n\t\t\r\n\t\t-- Remove the column we added to facilitate creation of the test harness.\r\n\t\tALTER TABLE dbo.ManagersDirectory DROP COLUMN [Level];\r\n\t\t\r\n\t\tSELECT COUNT(*) \r\n\t\tFROM dbo.ManagersDirectory;\r\n\t\t\r\n<\/pre>\n<p>Be patient when you run the above script because it does take a little longer to run that the prior ones (about 3.5 minutes). To construct our hierarchy, we needed to add a Level column which we later drop off to restore the adjacency list to its original structure. The final <strong>SELECT<\/strong> tells us that our table now contains 7,174,452 rows.<\/p>\n<p>To test the performance of this new method, we&#8217;ll run through traversals of the hierarchy from 5 to 13 levels using a batch that we&#8217;ll execute 9 times. The <strong>#Results<\/strong> table will capture the results for each execution of the batch. The <strong>#Sequence <\/strong>table is used to simulate a SQL 2012 <strong>SEQUENCE<\/strong> object, since we&#8217;re running our test in SQL Server 2008 R2.<\/p>\n<pre class=\"theme:ssms2012 lang:tsql\">\t\tCREATE TABLE #Results\r\n\t\t(\r\n\t\t\u00a0\u00a0\u00a0 Levels\u00a0\u00a0\u00a0\u00a0\u00a0 INT\r\n\t\t\u00a0\u00a0\u00a0 ,Reccount\u00a0\u00a0 INT\r\n\t\t\u00a0\u00a0\u00a0 ,Method\u00a0\u00a0\u00a0\u00a0 VARCHAR(10)\r\n\t\t\u00a0\u00a0\u00a0 ,ElapsedMS\u00a0 INT\r\n\t\t);\r\n\t\tGO\r\n\t\t\r\n\t\tCREATE TABLE #Sequence\r\n\t\t(\r\n\t\t\u00a0\u00a0\u00a0 [Counter]\u00a0\u00a0 INT\r\n\t\t);\r\n\t\t\r\n\t\tINSERT INTO #Sequence\r\n\t\tSELECT 4;\r\n\t\tGO\r\n\t<\/pre>\n<p>The batch will start at level five, because below that all of the methods are pretty swift. The rest of the test harness is rather lengthy so we won&#8217;t include it here, however you can find it in the attached resources as: <strong><em>0<\/em><\/strong><strong><em>3<\/em><\/strong><strong><em> Performance Test Harness.sql<\/em><\/strong><\/p>\n<p>After the final run of the timing batch (takes about 16 minutes), the results from our <strong>#Results<\/strong> table (reformatted) are shown below for elapsed time in milliseconds. <strong>Red<\/strong> font indicates the worst performing solution at the level while <strong>green<\/strong> font (often tied) represents the fastest solution.<\/p>\n<table>\n<tbody>\n<tr>\n<td>\n<p class=\"MsoNormal\"><b> Elapsed (ms)<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> rCTE<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> rFCN<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> dSQL<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> sbLP<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> sbLPwR<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> LAHP<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> LAHPwR<\/b><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p class=\"MsoNormal\"><b> 5 Levels<br \/>\n1092 Rows<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 16<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">63<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">63<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">30<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 76<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">46<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 16<\/b><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p class=\"MsoNormal\"><b> 6 Levels<br \/>\n3279 Rows<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">46<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">33<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 30<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 123<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">80<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">60<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">46<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p class=\"MsoNormal\"><b> 7 Levels<br \/>\n9840 Rows<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 160<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 93<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">123<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">123<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">96<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">110<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 93<\/b><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p class=\"MsoNormal\"><b> 8 Levels<br \/>\n29523 Rows<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 503<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">313<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 170<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">296<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">230<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">296<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">200<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p class=\"MsoNormal\"><b> 9 Levels<br \/>\n88572 Rows<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 1280<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">983<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">593<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">576<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 563<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">596<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 563<\/b><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p class=\"MsoNormal\"><b> 10 Levels<br \/>\n265719 Rows<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 3780<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">3113<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">1763<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">1853<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">1763<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">1843<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 1400<\/b><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p class=\"MsoNormal\"><b> 11 Levels<br \/>\n797160 Rows<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 11443<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">9630<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">5520<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">7913<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">6660<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 4573<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">4616<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p class=\"MsoNormal\"><b> 12 Levels<br \/>\n2391483 Rows<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 35300<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">29790<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">17510<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">17020<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">17336<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">21740<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 15646<\/b><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p class=\"MsoNormal\"><b> 13 Levels<br \/>\n7174452 Rows<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 108113<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">104420<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">57950<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">52563<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">81153<\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\"><b> 50156<\/b><\/p>\n<\/td>\n<td>\n<p class=\"MsoNormal\">52643<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Each of our methods are abbreviated as:<\/p>\n<ul>\n<li><strong>rCTE<\/strong> &#8211; The traditional recursive CTE approach<\/li>\n<li><strong>rFCN<\/strong> &#8211; The non-traditional recursive FUNCTION approach<\/li>\n<li><strong>dSQL<\/strong> &#8211; The dynamic SQL constructed from repeated JOINs and UNION ALL<\/li>\n<li><strong>sbLP<\/strong> &#8211; The set-based WHILE loop<\/li>\n<li><strong>sbLPwR<\/strong> &#8211; The set-based WHILE loop with RECOMPILE option<\/li>\n<li><strong>LAHP<\/strong> &#8211; The set-based WHILE loop avoiding Halloween protection<\/li>\n<li><strong>LAHPwR<\/strong> &#8211; The set-based WHILE loop avoiding Halloween protection with RECOMPILE option<\/li>\n<\/ul>\n<p>Note that you can probably drop the <strong>OPTION(<\/strong><strong>RECOMPILE)<\/strong> whenever your intention is to traverse the entire hierarchy to its full depth.<\/p>\n<p>The results are clearly illustrated when you graph them as a percentage of the worst performing solution, which is usually the rCTE.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/imported\/1980-9da4e504-a22c-46c4-b8ff-923d147fdb20.png\" alt=\"1980-9da4e504-a22c-46c4-b8ff-923d147fdb2\" \/><\/p>\n<h2>Conclusions<\/h2>\n<p>When traversing the hierarchy we constructed between eight and thirteen levels deep, the set-based WHILE loop avoiding Halloween protection with RECOMPILE option (LAHPwR) is most often the elapsed time winner. Perhaps surprisingly, the non-traditional recursive function seems to do just a little better than the rCTE between six and twelve levels. It is exactly tied with the set-based loop at seven levels. The repeated <strong>JOIN<\/strong>s method seems contra-indicated across the board (except at six levels) because there&#8217;s always a faster performing solution available.<\/p>\n<p>We present these results with a caveat. This is that, depending on your hierarchy one or the other results may be faster for you. Our enlarged hierarchy was exactly balanced; specifically each node had exactly three nodes growing from it. You may find that when only a few of your branches extend out to the higher depths, one of the other approaches may be more suitable for traversal. They also show that sometimes a well-constructed, set-based loop can out-perform the traditional recursive CTE approach.<\/p>\n<p>While adjacency lists for storing hierarchies are quite prevalent, there are other methods that offer opportunities for high performance depending on the requirements of the results from the hierarchies. Nested sets, closure tables and the data mart concept proposed by SQL MVP Jeff Moden in his Hierarchies on Steroids &#8211; Parts <a href=\"http:\/\/www.sqlservercentral.com\/articles\/Hierarchy\/94040\/\">One<\/a> and <a href=\"http:\/\/www.sqlservercentral.com\/articles\/T-SQL\/94570\/\">Two<\/a> all have different advantages depending on circumstance. Perhaps we&#8217;ll explore these alternatives in future submissions.<\/p>\n<p>Writing fast SQL is facilitated by knowing what code patterns perform well under various circumstances. We have provided you with several code patterns in this article that you can use to traverse your adjacency list hierarchies, so that you can decide which is best for your particular case.<\/p>\n<h2>Further Reading<\/h2>\n<ul class=\"reference-list\">\n<li><a href=\"http:\/\/www.simple-talk.com\/content\/article.aspx?article=1065\">Binary Trees in SQL<\/a> By Joe Celko<\/li>\n<li><a href=\"http:\/\/www.sqlservercentral.com\/articles\/Hierarchy\/94040\/\">Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets<\/a> by Jeff Moden<\/li>\n<li><a href=\"http:\/\/www.sqlservercentral.com\/articles\/T-SQL\/94570\/\">Hierarchies on Steroids #2: A Replacement for Nested Sets Calculations<\/a> be Jeff Moden<\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Halloween_Problem\">Halloween Problem<\/a> (Wikipedia)<\/li>\n<li><a href=\"http:\/\/sqlmag.com\/t-sql\/identifying-subsequence-in-sequence-part-1\">Identifying a Subsequence in a Sequence, Part 1<\/a> by <a href=\"http:\/\/sqlmag.com\/author\/itzik-ben-gan\">Itzik Ben-Gan<\/a><\/li>\n<li><a href=\"http:\/\/sqlmag.com\/t-sql\/divide-and-conquer-halloween\">Divide and Conquer Halloween by <\/a><a href=\"http:\/\/sqlmag.com\/author\/itzik-ben-gan\">Itzik Ben-Gan<\/a><\/li>\n<\/ul>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Dwain Camps show that, depending on the  size and characteristics of some hierarchical data, six different methods of traversal can each be the fastest at some point. He illustrates convincingly that It is dangerous to generalize from just one set of test data, and it is foolish to assume that, just because SQL code looks neat, it will perform well.&hellip;<\/p>\n","protected":false},"author":221942,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[143529],"tags":[4206,4150],"coauthors":[6800],"class_list":["post-1800","post","type-post","status-publish","format-standard","hentry","category-performance-sql-server","tag-performance","tag-sql"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1800","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/221942"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=1800"}],"version-history":[{"count":7,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1800\/revisions"}],"predecessor-version":[{"id":91203,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1800\/revisions\/91203"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=1800"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=1800"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=1800"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=1800"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}