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 at 06:21 AM in Default

Kimm gravatar image

Kimm
1 1 2

Please post this question in the Default section and not the meta-askssc section.
Apr 21 at 07:13 AM nidheesh.r.pillai
Moved to Default Section.
Apr 21 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 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 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 at 08:51 AM

Squirrel gravatar image

Squirrel
2.1k 1 2 4

(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 at 07:53 AM

Kev Riley gravatar image

Kev Riley ♦♦
52.8k 47 49 76

Kev, the link is bad
May 04 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 at 06:06 AM

Kimm gravatar image

Kimm
1 1 2

(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 at 10:58 PM

Kimm gravatar image

Kimm
1 1 2

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 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 at 09:54 PM

Kimm gravatar image

Kimm
1 1 2

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 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.

New code box

There's a new way to format code on the site - the red speech bubble logo will automatically format T-SQL for you. The original code box is still there for XML, etc. More details here.

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:

x40
x21

asked: Apr 21 at 06:21 AM

Seen: 488 times

Last Updated: May 04 at 12:53 PM