SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets


Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets

Author
Message
Lynn Pettis
Lynn Pettis
SSC Guru
SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)

Group: General Forum Members
Points: 90884 Visits: 38945
Combined some of the code from your code in this article with your delimited split routine to solve a problem at work. Inspiration comes from many places.

Have to give it to you Jeff, you are the Mentor of the Year in my book.

Cool
Lynn Pettis

For better assistance in answering your questions, click here
For tips to get better help with Performance Problems, click here
For Running Totals and its variations, click here or when working with partitioned tables
For more about Tally Tables, click here
For more about Cross Tabs and Pivots, click here and here
Managing Transaction Logs

SQL Musings from the Desert Fountain Valley SQL (My Mirror Blog)
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)

Group: General Forum Members
Points: 205759 Visits: 41952
Lynn Pettis (11/28/2012)
Combined some of the code from your code in this article with your delimited split routine to solve a problem at work. Inspiration comes from many places.

Have to give it to you Jeff, you are the Mentor of the Year in my book.


Blush Thanks, Lynn. I really appreciate that. What did you end up doing?

--Jeff Moden

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
Lynn Pettis
Lynn Pettis
SSC Guru
SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)SSC Guru (90K reputation)

Group: General Forum Members
Points: 90884 Visits: 38945
Jeff Moden (11/29/2012)
Lynn Pettis (11/28/2012)
Combined some of the code from your code in this article with your delimited split routine to solve a problem at work. Inspiration comes from many places.

Have to give it to you Jeff, you are the Mentor of the Year in my book.


Blush Thanks, Lynn. I really appreciate that. What did you end up doing?


Needed to sort DD Version Keys (x.x.x, like 2.1.10). The original code had no problems as it didn't have to work with a 2 digit value. When we went to 2.1.10 instead of 2.3.1, it was a problem. The original solution by another DBA used the OLE Automation Procedures to create a regex_replace function. Only problem is that there is a STIG requiring that these procedures be disabled.

I'm sure there may be another solution, but combining the DelimitedSplit8K and the varbinary concatenation from this article I was able to generate a solution that correctly sorted the version keys, including a very unlikely set of numerical elements (x(n).x(n).x(n).x(n).x(n).x(n).x(n).x(n).x(n).x(n).x(n)) where n represents 1 or more digits.

I wouldn't have thought of concatenating varbinary values had I not read this article.

Cool
Lynn Pettis

For better assistance in answering your questions, click here
For tips to get better help with Performance Problems, click here
For Running Totals and its variations, click here or when working with partitioned tables
For more about Tally Tables, click here
For more about Cross Tabs and Pivots, click here and here
Managing Transaction Logs

SQL Musings from the Desert Fountain Valley SQL (My Mirror Blog)
Michael Meierruth
Michael Meierruth
SSCrazy
SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)

Group: General Forum Members
Points: 2230 Visits: 2516
Lynn,
I see you too have run into this 'x.x.x...' problem.
I have run into serveral end user applications where this was used to manage hierarchies. Of course, all 'order by' clauses became useless when one of the x values reached 10.
I solved it by writing a function which converts 'x.x.x...' to two digit values starting at a certain level.
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)

Group: General Forum Members
Points: 205759 Visits: 41952
Lynn Pettis (11/29/2012)
Jeff Moden (11/29/2012)
Lynn Pettis (11/28/2012)
Combined some of the code from your code in this article with your delimited split routine to solve a problem at work. Inspiration comes from many places.

Have to give it to you Jeff, you are the Mentor of the Year in my book.


Blush Thanks, Lynn. I really appreciate that. What did you end up doing?


Needed to sort DD Version Keys (x.x.x, like 2.1.10). The original code had no problems as it didn't have to work with a 2 digit value. When we went to 2.1.10 instead of 2.3.1, it was a problem. The original solution by another DBA used the OLE Automation Procedures to create a regex_replace function. Only problem is that there is a STIG requiring that these procedures be disabled.

I'm sure there may be another solution, but combining the DelimitedSplit8K and the varbinary concatenation from this article I was able to generate a solution that correctly sorted the version keys, including a very unlikely set of numerical elements (x(n).x(n).x(n).x(n).x(n).x(n).x(n).x(n).x(n).x(n).x(n)) where n represents 1 or more digits.

I wouldn't have thought of concatenating varbinary values had I not read this article.


VERY cool. Thanks for posting the usage, Lynn.

--Jeff Moden

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
LordHz
LordHz
Forum Newbie
Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)

Group: General Forum Members
Points: 6 Visits: 21
Jeff, I have been playing with your RebuildNestedSets_MM stored procedure and I have a question. Is it possible to sort the nodes so that the Left and Right bowers are sorted on another field in the employee table? For example on Employee Name. My issue is I have a large hierarchy and I need the nodes in a specific order and looking through your proc it appears to always build/sort on employeeId. So in your article Lynne comes before Bob because her employeeId is 2 and Bob's is 3. However, I would like to change that sort on name so Bob would appear before Lynne. It looks like part of the beauty of your method is the nodes are arranged by employeeId.

If I am missing something obvious, please don't beat me up to much.

-Matthew Erdmann
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)

Group: General Forum Members
Points: 205759 Visits: 41952
LordHz (3/13/2013)
Jeff, I have been playing with your RebuildNestedSets_MM stored procedure and I have a question. Is it possible to sort the nodes so that the Left and Right bowers are sorted on another field in the employee table? For example on Employee Name. My issue is I have a large hierarchy and I need the nodes in a specific order and looking through your proc it appears to always build/sort on employeeId. So in your article Lynne comes before Bob because her employeeId is 2 and Bob's is 3. However, I would like to change that sort on name so Bob would appear before Lynne. It looks like part of the beauty of your method is the nodes are arranged by employeeId.

If I am missing something obvious, please don't beat me up to much.

-Matthew Erdmann


Heh... that's the problem with articles like this. They're not as big as a book. :-D

Someone smarter than me will probably figure out a better way but, yes, you can sort from left to right by level but not after you've built the nested sets. You have to do it before you build the nested sets and you can't use the EmployeeID for the sort path anymore. Instead, you have to sort by alphabetical position and assign new child/parent values to maintain each nodes position in the alphabetic hierarchy while still maintaining the parent/child hierarchy. That sounds real tough to do but it's actually not. You just need to assign a new sequential value to each employee in alphabetical order and then find the match of that new number as the new value for each manager. It does require a couple of extra steps (sorting is always expensive) but the code runs so fast, I don't see what an extra minute or two on a million rows would be much of an inconvenience. And, no... I wouldn't use a self joining CTE for this because that'll get calculated more than once. You need a table to store it in, anyway.

I'll post the code in a couple of minutes.

--Jeff Moden

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)SSC Guru (205K reputation)

Group: General Forum Members
Points: 205759 Visits: 41952
Here's one way. I apologize for not taking the time to make a more optimal solution but it's been a long day and I'm too pooped to pop.

Basically, you need to add an interim table to replace the original Employee table as the source of the recursive CTE to make the sort path. This new table has a SortedChild column to replace the EmployeeID in the sort path calculation and a Parent column to use in the join criteria along with SortedChild.

 SELECT SortedChild  = ROW_NUMBER() OVER (ORDER BY EmployeeName)
, Parent = NULL
, EmployeeID
, ManagerID
, EmployeeName
INTO #SortedEmployee
FROM dbo.Employee
;
GO
CREATE UNIQUE CLUSTERED INDEX IX_SortedEmployee_Composite01
ON #SortedEmployee (EmployeeID);
UPDATE child
SET child.Parent = parent.SortedChild
FROM #SortedEmployee child
JOIN #SortedEmployee parent
ON parent.EmployeeID = child.ManagerID
;
--===== Display what we end up with.
-- This is not a part of the solution
SELECT * FROM #SortedEmployee ORDER BY SortedChild
;



--Jeff Moden

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
LordHz
LordHz
Forum Newbie
Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)

Group: General Forum Members
Points: 6 Visits: 21
Jeff,
I had considered that and was working on something along those lines before I left work. For pure performance reasons, I would create a new sorted node mapping table that would maintain the sorted Id/ParentId pairs and a reference to the original Id/ParentId's. Hadn't gotten past that, so if you have a complete solution I would be grateful. Using your method for updating my nested sets has reduced my rebuild time from 18 seconds to 400 milliseconds (8000 nodes, ~10 levels of depth). The only thing missing is solving this sort issue. It would be simpler if the application I was building this for pulled only one level at a time, since I could sort the nodes however I like. But the spec is for a flat table that shows the entire hierarchy and is sorted on a different field.

Thanks again,
Matthew
LordHz
LordHz
Forum Newbie
Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)Forum Newbie (6 reputation)

Group: General Forum Members
Points: 6 Visits: 21
Jeff,

I implemented your sort solution and it is perfect. Only change I need to make is to update the hierarchy table to support the sortedId/sortedParentId and the original ID/parentID fields.

Thanks for you assistance and knowledge,
Matthew E.
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search