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


Hierarchies in SQL


Hierarchies in SQL

Author
Message
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)

Group: General Forum Members
Points: 207616 Visits: 41965
From the article...
The speed difference and IO difference can be significant on the two. For example, I have a hierarchy in one of my databases with 2,700 nodes in it, going up to six levels deep. If someone at the top of that hierarchy signs in, it takes 11 seconds for my server to resolve the whole hierarchy and determine what data that person has access to (this is a security access hierarchy that controls much of what is displayed to customers on a web site). That’s using the adjacency model. Using a nested sets table, that same hierarchy takes less than 1 millisecond. (This isn’t the one with multiple parents. Different company.)

If this same database didn’t have a lot of updates to the hierarchies, I’d definitely use a straight-up nested sets hierarchy, and have much faster web pages. But it does have a lot of updates, sometimes several per minute, sometimes several at the same time. Each nested sets rebuild takes about 20-30 seconds to finish, and locks the table pretty aggressively while it’s running.


Hi Gus,

I've had reason to revisit this article and the paragraphs above caught my eye, especially the two emphasized areas.

With that in mind, which method are you using to convert the Adjacency List to a Nested Set Model? Is it the familiar "push stack" method from Joe Celko's book/article postings? And was it for the ~2700 rows you mentioned?

Thanks, Gus.

--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
GSquared
GSquared
SSC Guru
SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)

Group: General Forum Members
Points: 55651 Visits: 9730
I don't have access to that code currently, since it's for a prior employer. However, if I remember it correctly, it ended up using the TopParentID mentioned in the article to first find a simple count by that column, did a "running total" type calculation on that (I use a CLR function for that, blindingly fast) to get top level range start and stop values. All of that was very, very fast, like milliseconds. I think it then repeated that for each level till it got zero for @@rowcount, but the lower levels weren't as fast because they had to actually crawl the hierarchy to get the number of nodes beneath each, instead of just a count on TopParentID.

I tried the update method mentioned in Joe's article and found that it was WAY too slow for an in-use database. My update solution was more complex, but much, much faster.

I could improve the process immensely with the difference between what I know now and what I knew when I built it, but that's pretty much true of any code I wrote more than about a month ago. Just some simple Cross Apply inline queries would make the thing much more efficient.

The 2,700 rows was for one hierarchy within a multi-million row table. 11 seconds to resolve anything on a 2,700-row table would imply that I was running it on, maybe a 286 CPU with 2 Meg of RAM? TSR-80? Timex/Sinclair 1000? Not sure how far back I'd have to go to get that bad of performance, even on an adjacency crawl. If I remember correctly, the table had somewhere around 2-million total rows, and 2,700 nodes, 6 levels deep, was the biggest single hierarchy within it.

- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread

"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)SSC Guru (207K reputation)

Group: General Forum Members
Points: 207616 Visits: 41965
Thanks Gus.

--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
amenjonathan
amenjonathan
SSC-Addicted
SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)

Group: General Forum Members
Points: 498 Visits: 434
Just wanted to post back to this thread that I finished my blog post on handling hierarchies in slowly changing dimensions. If I've misquoted anyone (especially Gus) please let me know. Also any feedback if someone knows of a better / faster way.

SCD with hierarchy in key

-------------------------------------------------------------------------------------------------
My SQL Server Blog
GSquared
GSquared
SSC Guru
SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)SSC Guru (55K reputation)

Group: General Forum Members
Points: 55651 Visits: 9730
amenjonathan (1/28/2011)
Just wanted to post back to this thread that I finished my blog post on handling hierarchies in slowly changing dimensions. If I've misquoted anyone (especially Gus) please let me know. Also any feedback if someone knows of a better / faster way.

SCD with hierarchy in key


I read the post, and it looks like it makes sense and would work. Definitely well-written too.

- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread

"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
amenjonathan
amenjonathan
SSC-Addicted
SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)SSC-Addicted (498 reputation)

Group: General Forum Members
Points: 498 Visits: 434
Thanks, Gus.

-------------------------------------------------------------------------------------------------
My SQL Server Blog
Alan.B
Alan.B
SSChampion
SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)

Group: General Forum Members
Points: 12948 Visits: 8000
I know I am a little late here but, Great article Gus.

FYI - the to Celko's article (http://www.intelligententerprise.com/001020/celko.jhtml.) is broke ;-)

-- Alan Burstein



Best practices for getting help on SQLServerCentral
Need to split a string? Try DelimitedSplit8K or DelimitedSplit8K_LEAD (SQL 2012+)
Need a pattern-based splitter? Try PatternSplitCM
Need to remove or replace those unwanted characters? Try PatExclude8K and PatReplace8K.

"I can't stress enough the importance of switching from a 'sequential files' mindset to 'set-based' thinking. After you make the switch, you can spend your time tuning and optimizing your queries instead of maintaining lengthy, poor-performing code. " -- Itzek Ben-Gan 2001
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