x

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.

more ▼

asked Apr 21, 2014 at 06:21 AM in Default

avatar image

Kimm
1 1 1 3

Please post this question in the Default section and not the meta-askssc section.

Apr 21, 2014 at 07:13 AM nidheesh.r.pillai

Moved to Default Section.

Apr 21, 2014 at 08:25 AM Dave_Green ♦

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]

Apr 21, 2014 at 08:38 AM Squirrel

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.

Apr 23, 2014 at 10:00 AM Grant Fritchey ♦♦
(comments are locked)
10|1200 characters needed characters left

5 answers: sort voted first
 ; 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)
 
more ▼

answered Apr 21, 2014 at 08:51 AM

avatar image

Squirrel
2.7k 1 4 7

(comments are locked)
10|1200 characters needed characters left

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
more ▼

answered Apr 22, 2014 at 07:53 AM

avatar image

Kev Riley ♦♦
63.8k 48 61 81

Kev, the link is bad

May 04, 2014 at 12:53 PM Squirrel
(comments are locked)
10|1200 characters needed characters left

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
 
more ▼

answered Apr 22, 2014 at 06:06 AM

avatar image

Kimm
1 1 1 3

(comments are locked)
10|1200 characters needed characters left

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
 
more ▼

answered Apr 22, 2014 at 10:58 PM

avatar image

Kimm
1 1 1 3

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!

Apr 23, 2014 at 07:13 AM Kev Riley ♦♦
(comments are locked)
10|1200 characters needed characters left

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
 
more ▼

answered Apr 23, 2014 at 09:54 PM

avatar image

Kimm
1 1 1 3

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.

Apr 24, 2014 at 06:58 AM Kev Riley ♦♦
(comments are locked)
10|1200 characters needed characters left
Your answer
toggle preview:

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

SQL Server Central

Need long-form SQL discussion? SQLserverCentral.com is the place.

Topics:

x54
x22

asked: Apr 21, 2014 at 06:21 AM

Seen: 1995 times

Last Updated: May 04, 2014 at 12:53 PM

Copyright 2016 Redgate Software. Privacy Policy