question

Kimm avatar image
Kimm asked

How do I sequence number a recursive CTE top to bottom?

I have a recursive cte which I need to turn in to a flat file recordset AND MAINTAIN THE ORDER TOP TO BOTTOM AND KEEP TRACK OF WHICH ITEMS REPORT TO EACH LEVLEL BY THE ORDER NUMBER. Data Item Parent A null B null C A D A E C F C G F H G recursing the data above Should return Index Parent Item 1 0 A 2 0 B 3 1 C 4 1 D 5 3 E 6 3 F 7 6 G 8 7 H This should not be that tough but I can't figure it out. Row_number() resets at each level of the recursion. I tried a function accessing a table of numbers but function won't accept cursor arguments or dynamic sql so it would only work for 1 user at a time which is unacceptable. I actually made it work using the format below and indenting 3 decimal places at each level but it is limited to 999 items in each recursion and only about 11 levels of recursion plus it is just an ugly hack. Index Parent 1.10000000000000000000000000000000000 1.00000000000000000000000000000000000 1.10100000000000000000000000000000000 1.10000000000000000000000000000000000 1.10100100000000000000000000000000000 1.10100000000000000000000000000000000 1.10100100100000000000000000000000000 1.10100100000000000000000000000000000 1.10100100200000000000000000000000000 1.10100100000000000000000000000000000 1.10100100300000000000000000000000000 1.10100100000000000000000000000000000 1.10100100400000000000000000000000000 1.10100100000000000000000000000000000 1.10100100400100000000000000000000000 1.10100100400000000000000000000000000 Global or static variables would make this easy.c'mon Microsoft. Any ideas greatly appreciated.
cterecursion
4 comments
10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Please post this question in the Default section and not the meta-askssc section.
0 Likes 0 ·
Moved to Default Section.
0 Likes 0 ·
Kimm, can you format the sample data & expected result part of your question ? It is rather hard to read and identify what goes to which column. EDIT [Never mind. I think i have figured it out]
0 Likes 0 ·
This site works by voting. Please indicate all helpful answers by clicking on the thumbs up next to those answers. If any one answer lead to a solution, please indicate this by clicking on the check mark next to that answer.
0 Likes 0 ·
Squirrel avatar image
Squirrel answered
; with data as ( select Item = 'A', Parent = null union all select Item = 'B', Parent = null union all select Item = 'C', Parent = 'A' union all select Item = 'D', Parent = 'A' union all select Item = 'E', Parent = 'C' union all select Item = 'F', Parent = 'C' union all select Item = 'G', Parent = 'F' union all select Item = 'H', Parent = 'G' ), rcte as ( select [Seq] = 1, [Parent] = convert(char(1), NULL), [Item] = [Item] from data where Parent is null union all select [Seq] = r.[Seq] + 1, [Parent] = convert(char(1), r.[Item]), [Item] = d.[Item] from rcte r inner join data d on r.[Item] = d.[Parent] ), cte as ( select Seq, [Index] = row_number()over (order by Seq, Item), Parent, Item from rcte ) select c.[Index], Parent = isnull(p.[Index], 0), c.Item from cte c left join cte p on c.[Parent] = p.Item Index Parent Item -------------------- -------------------- ---- 1 0 A 2 0 B 3 1 C 4 1 D 5 3 E 6 3 F 7 6 G 8 7 H (8 row(s) affected)
10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Kimm avatar image
Kimm answered
Sqirrel, you are awesome for taking the time to do this, I learned a lot from just what you did. Unfortunately it did not solve my problem (which I see I did not adequately explain). I cannot sort on the level, which, effectively your solution did. I need to sort the TREE. Also, there is an order sequence built in at each level which must be honored. Below is a sample set of data that can be used with your solution, and below it is the desired output. As you will see it not only fails to sort the tree but does not provide the correct parent either if you add an ORDER BY (i.e. , ROW_NUMBER() over(ORDER BY ORDERBY) as OB). I deliberately made some of the OREDRBY so the Items were NOT alphanumeric as it is certain that they will not be in the real data. As I see it the only way to get the numbers correct is to somehow include a ROW_NUMBER() based on the ORDERBY field at each level. Note: I DON'T CARE if the index numbers are sequential or even Alphanumeric as long as the sort order and the parents are correct. Data: ; with data as ( select Item = 'A', Parent = null, ORDERBY = 2 union all select Item = 'C', Parent = null, ORDERBY = 1 union all select Item = 'C2', Parent = null, ORDERBY = 3 union all select Item = 'B', Parent = 'A', ORDERBY = 1 union all select Item = 'D', Parent = 'C2', ORDERBY = 2 union all select Item = 'E', Parent = 'C2', ORDERBY = 1 union all select Item = 'F', Parent = 'C', ORDERBY = 1 union all select Item = 'G', Parent = 'F', ORDERBY = 1 union all select Item = 'H', Parent = 'G', ORDERBY = 1 union all select Item = 'H1', Parent = 'G', ORDERBY = 2 union all select Item = 'H2', Parent = 'G', ORDERBY = 3 ), And the desired output: Index Parent Item 1 0 C 2 1 F 3 2 G 4 3 H 5 3 H1 6 3 H2 7 0 A 8 7 B 9 0 C2 10 9 D 11 9 E Note this is the TREE for the part. It might better be visualized this way: 1 0 C 2 1 F 3 2 G 4 3 H 5 3 H1 6 3 H2 7 0 A 8 7 B 9 0 C2 10 9 D 11 9 E
10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Kev Riley avatar image
Kev Riley answered
I've been working with a lot of hierarchical data recently, and I've found these articles from Jeff Moden immensely useful : http://www.sqlservercentral.com/articles/Hierarchy/94040/ http://www.sqlservercentral.com/articles/T-SQL/94570/ Using a concept from there, here's a solution that handles up to 1000 levels deep. The solution is also provided in a step-by-step cte way to try and help explain what is going on, but I'm sure some of this could be optimized ; with initialdata as ( select Item = 'A', Parent = null, ORDERBY = 2 union all select Item = 'C', Parent = null, ORDERBY = 1 union all select Item = 'C2', Parent = null, ORDERBY = 3 union all select Item = 'B', Parent = 'A', ORDERBY = 1 union all select Item = 'D', Parent = 'C2', ORDERBY = 2 union all select Item = 'E', Parent = 'C2', ORDERBY = 1 union all select Item = 'F', Parent = 'C', ORDERBY = 1 union all select Item = 'G', Parent = 'F', ORDERBY = 1 union all select Item = 'H', Parent = 'G', ORDERBY = 1 union all select Item = 'H1', Parent = 'G', ORDERBY = 2 union all select Item = 'H2', Parent = 'G', ORDERBY = 3 ), data as ( select row_number()over(order by parent, orderby) as Seq, item, parent, orderby from initialdata ), cteBuildPath AS ( SELECT anchor.Seq, anchor.Item, anchor.Parent, anchor.OrderBy, SortPath = CAST(CAST(anchor.Seq AS BINARY(4)) AS VARBINARY(4000)) --Up to 1000 levels deep. FROM data AS anchor WHERE Parent IS null UNION ALL SELECT recur.Seq, recur.Item, recur.Parent, recur.orderby, SortPath = CAST(cte.SortPath + CAST(Recur.Seq AS BINARY(4)) AS VARBINARY(4000)) FROM data AS recur INNER JOIN cteBuildPath AS cte ON cte.Item = recur.Parent ), orderedresults as ( select row_number()over(order by sortpath) as [index], * from cteBuildPath ) select [index], isnull((select [index] from orderedresults or2 where or2.Item = or1.Parent),0) as ParentIndex, Item from orderedresults or1
2 comments
10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Kimm avatar image
Kimm answered
Kev, Thanks so much! You code works great and gave me some great ideas! I adapted your code to my application and it worked perfectly. Unfortunately it took 9 seconds to run on a 550 item BOM that was 4 levels deep. My own solution was virtually instant. But you got me unstuck from the idea of using a decimal number. I switched to varchar(4000) which should give me about a 1000 level BOM and 9999 items per BOM - more than enough. I also found that by modifying your ending select I could even get the numbers back to regular sequence numbers with your 'orderedresults'. I couldn't have done that in a million years. but I found it takes about a little over twice as long so if the actual numbers are not important then it is probably best to just do a straight SELECT. Which I have included but remmed. I also renamed things so they make more sense for me with what I am doing My code is below. THANKS ALL FOR YOUR HELP! ; with data as ( select Item = 'A', Parent = null, ORDERBY = 2 union all select Item = 'C', Parent = null, ORDERBY = 1 union all select Item = 'C2', Parent = null, ORDERBY = 3 union all select Item = 'B', Parent = 'A', ORDERBY = 1 union all select Item = 'D', Parent = 'C2', ORDERBY = 2 union all select Item = 'E', Parent = 'C2', ORDERBY = 1 union all select Item = 'F', Parent = 'C', ORDERBY = 1 union all select Item = 'G', Parent = 'F', ORDERBY = 1 union all select Item = 'H', Parent = 'G', ORDERBY = 1 union all select Item = 'H1', Parent = 'G', ORDERBY = 2 union all select Item = 'H2', Parent = 'G', ORDERBY = 3 ), BuildTree AS ( SELECT TopLvl.Item, --TopLvl.Parent, Cast(1 AS varchar(4000)) AS Parent, TopLvl.OrderBy, --SortPath = CAST(CAST(TopLvl.Seq AS BINARY(4)) AS VARBINARY(4000)) --Up to 1000 levels deep. cast((ROW_NUMBER() OVER (ORDER BY TopLvl.Parent, TopLvl.OrderBy ) + .1) as varchar(4000)) AS SortPath FROM data AS TopLvl WHERE Parent IS null UNION ALL SELECT Branches.Item, --Branches.Parent, BuildTree.SortPath AS Parent, Branches.orderby, --SortPath = CAST(BuildTree.SortPath + CAST(Branches.Seq AS BINARY(4)) AS VARBINARY(4000)) cast(BuildTree.SortPath + STR(ROW_NUMBER() OVER (ORDER BY BuildTree.Parent, BuildTree.orderby ), 4) as varchar(4000)) AS SortPath FROM data AS Branches INNER JOIN BuildTree ON BuildTree.Item = Branches.Parent ) --SELECT SortPath As [Index], Parent, Item FROM BuildTree ORDER BY SortPath --USE THIS SELECT LINE IF YOU JUST NEED THE SORT AND A PARENT, NOT THE NUMBERS IT IS TWICE AS FAST AS THE BELOW. , orderedresults as ( select row_number()over(order by sortpath) as [index], * from BuildTree ) select [index], isnull((select [index] from orderedresults or2 where or2.SortPath = or1.Parent),0) as ParentIndex, Item from orderedresults or1
1 comment
10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Kimm, thank Jeff Moden for the hierarchy code! Yes the performance of nested CTEs like that probably isn't the best, but I wanted to be able for you to 'see' the steps - and that seems to have worked!
0 Likes 0 ·
Kimm avatar image
Kimm answered
Kev, This is the part I don't understand. Is this another recursion? Does this only work because we started with a WITH or can this be done anywhere? orderedresults as ( select row_number()over(order by sortpath) as [index], * from BuildTree ) select [index], isnull((select [index] from orderedresults or2 where or2.SortPath = or1.Parent),0) as ParentIndex, Item from orderedresults or1
1 comment
10 |1200

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

orderedresults is another cte, using the previous cte 'BuildTree' as a source - not really another recursion. The select following the cte definition uses the cte. So yes, this is because we started with a WITH.
0 Likes 0 ·

Write an Answer

Hint: Notify or tag a user in this post by typing @username.

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.