2

I have what would seem to be a simple problem but the solutions I have tried to date have left me wanting in the execution areas. Speeds seem fine on small (<10000) data sets but quickly take more and more time as the counts go up.

In SQL Server 2008 R2 I have a table with four columns in it: Id, ParentId, ControlNum, ParentControlNum.

The Id and ParentId information is filled in. An Id always has a value, the ParentId is null if the row has no parent, otherwise its the the value of an Id within the table that represents the parent row.

The issue is that the Id and ParentIds are all over the place. All of the Ids are added to the table then they are processed to add the children. This is a set part of the problem and is not something that can be changed.

What I need to be able to do is to generate the ControlNum values in order obeying the Parent Child relationship. My current logic uses a bit of C# and SQL SELECT/UPDATE commands to accomplish this, but as mentioned performance is a great concern.

In Pseudo-Code

Select all Id's where the parent Id is null (All root entries)
Foreach (Id)
   GenerateControlNum(Id, CurrentCounterValue, CurrentCounterValue)

GenerateControlNum(Id, CurrentCounterValue, ParentCounterValue)
    Set Id's ControlNum to CurrentCounterValue
    Set Id's ParentControlNum to CurrentCounterValue

    Increment CurrentCounterValue

    Select All Id's where ParentId == Id (All my direct children)
    Foreach (ChildId)
        GenerateControlNum(ChildId, CurrentCounterValue, Id's ControlNum);

Baseline is trying to make this execute faster, idealy completely in SQL would be preffered. I am trying along the lines of a CTE populated with the RootIds and then going through them with a MERGE statement but I can just not seem to get the counter value to work properly for setting the ControlNum values.

Is this even possible in SQL or is this too much of a procedural type of processing?

Example Table Data from how it currently runs: BEFORE

ID                                      ParentId                                ControlNum  ParentControlNum
8C821027-A6F9-E011-AB48-B499BAE13A62    756F981E-A6F9-E011-AB48-B499BAE13A62    0           NULL
D7DB6033-A6F9-E011-AB48-B499BAE13A62    756F981E-A6F9-E011-AB48-B499BAE13A62    0           NULL
D2E36033-A6F9-E011-AB48-B499BAE13A62    C9E36033-A6F9-E011-AB48-B499BAE13A62    0           NULL
8FE66033-A6F9-E011-AB48-B499BAE13A62    58E66033-A6F9-E011-AB48-B499BAE13A62    0           NULL
37EC6033-A6F9-E011-AB48-B499BAE13A62    2FEC6033-A6F9-E011-AB48-B499BAE13A62    0           NULL
41EC6033-A6F9-E011-AB48-B499BAE13A62    2FEC6033-A6F9-E011-AB48-B499BAE13A62    0           NULL 
DDED6033-A6F9-E011-AB48-B499BAE13A62    BCED6033-A6F9-E011-AB48-B499BAE13A62    0           NULL
DC69981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    0           NULL
166A981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    0           NULL
4D6A981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    0           NULL
856A981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    0           NULL
F56A981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    0           NULL
2E6B981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    0           NULL
666B981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    0           NULL
9D6B981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    0           NULL

AFTER

ID                                      ParentId                                ControlNum  ParentControlNum
8C821027-A6F9-E011-AB48-B499BAE13A62    756F981E-A6F9-E011-AB48-B499BAE13A62    22          21
D7DB6033-A6F9-E011-AB48-B499BAE13A62    756F981E-A6F9-E011-AB48-B499BAE13A62    24          21
D2E36033-A6F9-E011-AB48-B499BAE13A62    C9E36033-A6F9-E011-AB48-B499BAE13A62    58          57
8FE66033-A6F9-E011-AB48-B499BAE13A62    58E66033-A6F9-E011-AB48-B499BAE13A62    69          68
37EC6033-A6F9-E011-AB48-B499BAE13A62    2FEC6033-A6F9-E011-AB48-B499BAE13A62    86          85
41EC6033-A6F9-E011-AB48-B499BAE13A62    2FEC6033-A6F9-E011-AB48-B499BAE13A62    88          85
DDED6033-A6F9-E011-AB48-B499BAE13A62    BCED6033-A6F9-E011-AB48-B499BAE13A62    95          94
DC69981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    0           0
166A981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    1           1
4D6A981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    2           2
856A981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    3           3
F56A981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    4           4
2E6B981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    5           5
666B981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    6           6
9D6B981E-A6F9-E011-AB48-B499BAE13A62    NULL                                    7           7

The data set I have is 104 entries right now so this is just the first 15. The objects with out parents are at the bottom, those are examples of root entries and have their control number and parent control number set to the same value. At the top of the table we see a few objects that have the same parents and so have matching parent control numbers and fairly close control numbers themselves (there must be row between ControlNum 22 and 24 also from parent 21 for example. same for the 86 to 88 jump, they are just not in the table next to each other).

Hope this makes it more clear.

EDIT: More clarity based on the answer given by Mikael

Below are ControlNum values displayed in the hierarchy based on their Id and ParentId information. Normally these would be listed 1, 2, 3 ... 8 but its easier not to clutter up the display with (child of) messages all over.

1
  4
    7
    8
  5
2
  6
3

What I need is

1
  2
    3
    4
  5
6
  7
8

This is why recursion has been the way that I have been going is I need to assign a ControlNum to the root object, and then the next object needs to be its first child followed by that objects children and so on before going on to the next root object.

I guess what I am saying is this is a breadth first and what I am in need of is a depth first.

Improve this question
2
  • Can you add some sample data? What it looks like before the update and what it should look like after the update. It is not clear to me what you mean by "generate the ControlNum values in order obeying the Parent Child relationship" Commented Oct 22, 2011 at 21:23
  • @MikaelEriksson Sample data with a bit of an explanation added. Commented Oct 22, 2011 at 21:43

1 Answer 1

Reset to default
3

Not sure I get all of your requirement but here is a start. Tell me if it does what you want or if the numbers are not generated correctly.

;with C as
(
  select ID,
         ParentID,
         ControlNum,
         ParentControlNum,
         row_number() over(order by ParentID, ID) - 1 as rn
  from YourTable
)  
update C1
set ControlNum = C1.rn,
    ParentControlNum = case when C1.ParentID is null 
                         then C1.rn
                         else C2.rn 
                       end
from C as C1
  left outer join C as C2
    on C1.ParentID = C2.ID

Run it on SE-Data with slightly modified input: https://data.stackexchange.com/stackoverflow/q/115625/

Version 2

First a recursive CTE R,that builds a string to be used as order by when generating values for ControlNum. After that it is pretty much the same as above.

;with R as
(
  select ID,
         ParentID,
         cast(ID as varchar(max)) as Sort
  from YourTable
  where ParentID is null
  union all
  select T.ID,
         T.ParentID,
         R.Sort+cast(T.ID as varchar(max))
  from YourTable as T
    inner join R
      on R.ID = T.ParentID
),
C as
(
  select ID,
         ParentID,
         row_number() over(order by Sort) - 1 as rn
  from R
)  
update T
set ControlNum = C1.rn,
    ParentControlNum = case when C1.ParentID is null 
                         then C1.rn
                         else C2.rn 
                       end
from YourTable as T
  inner join C as C1
    on T.ID = C1.ID
  left outer join C as C2
    on T.ParentID = C2.ID

Test here: https://data.stackexchange.com/stackoverflow/q/115626/

Note: I guess this is a one time thing you will do with some data because you will have a hard time adding new nodes and at the same time uphold the numbering like this. If you for instance add a new child node to the first node you will have to assign all ControlNum += 1 for all nodes "below" and reassign all ParentControlNum.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

This is a large step in the right direction. It is not entirely solving my issue however and I have extended my question to be more explicit.
This is indeed a once over for final ordering of the data before processing. This does work but is a bit slower, presumably because of the string compare. I am pondering the possibility of taking the data given from the first version, ordering it by the ParentControlNum and then using row_number() on the results.. Anywho, just thoughts for future progression. Thank you again for a working answer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.