Problem With Recursive CTE

Magoo's code seems to do the trick for leaf-node detection. I decided to go "Full Monty" so that other "questions" could be asked of the hierarchy.

First, here's the test data... notice the bit of a change I made (at the very bottom of the next code window) to show some extra utility in the code that follows it.

--===== Always do experiments in a nice, safe place that everyone has just to be sure.

USE TempDB

;

--===== Conditionally drop the test table to make reruns in SSMS easier.

-- This is NOT a part of the solution.

--===== Conditionally drop temp tables to make reruns easier in SSMS

IF OBJECT_ID('TempDB..#ProductAssembly','U') IS NOT NULL DROP TABLE #ProductAssembly;

--===== Create and populate the test table

CREATE TABLE #ProductAssembly

(

Product NVARCHAR(20),

Component NVARCHAR(20)

)

;

INSERT INTO dbo.ProductAssembly

(Product, Component)

SELECT 'Part A','Part Z' UNION ALL

SELECT 'Part B','Part Z' UNION ALL

SELECT 'Part C','Part Z' UNION ALL

SELECT 'Part D','Part Z' UNION ALL

SELECT 'Part Z','Part Y' UNION ALL

SELECT 'Part D','Part X' UNION ALL

SELECT 'Part D','Part W' UNION ALL

SELECT 'Part Z','Part G'

UNION ALL SELECT 'Part A', 'Part D' --<< Added this little nuance

You'll need this "very odd" splitter function which doesn't actually split anything. It breaks each instance of a hierarchical path into all of the paths it took to get to that given line item so we can figure out how many nodes are in each subpath and THAT's critical to the Set-Based method I use. As complicated as it looks, it's Nasty Fast...

CREATE FUNCTION dbo.SplitCommonPath

-- Jeff Moden - 31 May 2011

--===== Define I/O parameters

(@pString NVARCHAR(4000), @pDelimiter NCHAR(1))

RETURNS TABLE WITH SCHEMABINDING AS

RETURN

--===== "Inline" CTE Driven "Tally Table" produces values from 0 up to 10,000...

-- enough to cover NVARCHAR(4000)

WITH E1(N) AS (

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1

), --10E+1 or 10 rows

E2(N) AS (SELECT 1 FROM E1 a, E1 b), --10E+2 or 100 rows

E4(N) AS (SELECT 1 FROM E2 a, E2 b), --10E+4 or 10,000 rows max

cteTally(N) AS (--==== This provides the "base" CTE and limits the number of rows right up front

-- for both a performance gain and prevention of accidental "overruns"

SELECT TOP (ISNULL(DATALENGTH(@pString)/2,0)) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E4

),

cteStart(N) AS (--==== This returns N+1 (starting position of each "element" just once for each delimiter)

SELECT t.N FROM cteTally t WHERE SUBSTRING(@pString,t.N,1) = @pDelimiter

)

--===== Do the actual split.

-- CommonPath always contains 1 less node

SELECT CommonPath = SUBSTRING(@pString, 1 ,s.N)

FROM cteStart s

;

Now, we go on to converting the Adjacency List to a Hierarchical Path. This code also builds the missing "Top Level" node and the related top level parts that "report" to it.

--===== Declare and populate an obviously named variable for what to finpe.

DECLARE @SearchFor NVARCHAR(20);

SELECT @SearchFor = 'ALL'; -- or can be a single part

--===== Conditionally drop temp tables to make reruns easier in SSMS

IF OBJECT_ID('TempDB..#HierarchyWork' ,'U') IS NOT NULL DROP TABLE #HierarchyWork;

IF OBJECT_ID('TempDB..#FinalHierarchy','U') IS NOT NULL DROP TABLE #FinalHierarchy;

--===== Build a working table to include the missing "top level" so we can convert the

-- Adjacency List to a Hierarchical Path

------- Copy all existing data into a new table on the fly

SELECT Product, Component

INTO #HierarchyWork

FROM #ProductAssembly

UNION ALL

------- Create the missing top level and copy it, as well.

SELECT DISTINCT

'Top Level', Product

FROM #ProductAssembly

WHERE Product NOT IN (SELECT Component FROM #ProductAssembly)

UNION ALL

SELECT ' ', 'Top Level'

;

--===== Create the Hierarchical Path model and some

-- extra columns to create a Nested Sets model.

WITH

ctePartsExplosion AS

(

SELECT Component, Product, RelativeLevel = 1,

HierarchicalPath = CAST(Component+ N'/' AS NVARCHAR(4000))

FROM #HierarchyWork

WHERE (@SearchFor <> 'ALL' AND Component = @SearchFor)

OR (@SearchFor = 'ALL' AND Product = ' ')

UNION ALL

SELECT h.Component, h.Product, RelativeLevel = pe.RelativeLevel + 1,

HierarchicalPath = CAST(pe.HierarchicalPath + h.Component + N'/' AS NVARCHAR(4000))

FROM #HierarchyWork h

INNER JOIN ctePartsExplosion pe ON h.Product = pe.Component

) --=== We put it all into a Temp Table because we'll need to address the

-- Final Hierarchy table more than once which would cause a CTE to

-- execute more than once making the code twice as slow.

SELECT NodeNumber = ISNULL(ROW_NUMBER() OVER (ORDER BY HierarchicalPath),0),

LeftBower = CAST(NULL AS INT),

RightBower = CAST(NULL AS INT),

NodeCount = CAST(1 AS INT),

Component,

Product = ISNULL(Product,''),

RelativeLevel = CAST(RelativeLevel AS TINYINT),

IsLeafLevel = CAST(NULL AS TINYINT),

HierarchicalPath

INTO #FinalHierarchy

FROM ctePartsExplosion

;

Then we convert the Hierarchical Path to Nested Sets...

--===== Declare a variable to remember the Left Bower

-- of a line item in a Nested Set to calculate the

-- Right Bower from.

DECLARE @LeftBower INT

;

--===== Convert the Hierarchical Path to a Nested Sets

WITH

cteCountNodes AS

( --=== Count the number of "downline" nodes for each line item

-- based on the number of occurances for each "common path".

SELECT split.CommonPath,

NodeCount = COUNT(*)

FROM #FinalHierarchy fh

CROSS APPLY dbo.SplitCommonPath(fh.HierarchicalPath, N'/') split

GROUP BY split.CommonPath

) --=== This bit of computational heaven creates the "Bowers" for the

-- Nested Sets and determines if a line item is at the Leaf Level.

UPDATE fh

SET NodeCount = cn.NodeCount,

@LeftBower = LeftBower = (fh.NodeNumber * 2) - fh.RelativeLevel,

RightBower = ((cn.NodeCount-1) * 2) + @LeftBower + 1,

IsLeafLevel = CASE WHEN cn.NodeCount > 1 THEN 0 ELSE 1 END

FROM #FinalHierarchy fh

INNER JOIN cteCountNodes cn

ON fh.HierarchicalPath = cn.CommonPath

;

Here's what the final hierarchy ends up looking like...

Do an Internet search for "Nested Sets" to find out more about how to use them and how very fast and flexible they are. There's a whole lot more you can do with them other than just calculating leaf-levels.

This, obviously, doesn't take long to run at all. The advantage of having this stuff stored in a table (you'll have to convert the Temp Table I created to a real table) is that you're not calculating the same thing over and over. You calculate it once and won't need to calculate it again until you make a change in the ProductAssembly table. Shoot. You could even run the hierarchical code to create the final hierarchy table as part of a Trigger on the ProductAssembly code.

If you have any questions, please don't hesitate to ask. (Except for the "Bower" columns which form the Nested Set, all the columns have some fairly obvious names).

Jeff/Magoo,

Thanks both for your suggestions; I've very quickly tested Magoo's code against my sample data and it does return the expected results. I'm going to need a bit of time though to look at Jeff's code because I'm not familiar with nested sets but I will look into it!

Thanks again 🙂

You bet. Thank you for the feedback.