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
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)

Group: General Forum Members
Points: 213781 Visits: 41977
Jason-299789 (11/13/2012)
A very nice article jeff, Its given me a few Ideas on how to change one of the Hierarchy builders I have, just need to find the down time to test it.

Looking forward to future installments.



Thank you for the feedback, Jason. The article mentioned in the "p.s." comes out on Thursday, 15 November ( 2 days from now).

I'd be interested in knowing what your ideas are, if you have the time.

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

Group: General Forum Members
Points: 213781 Visits: 41977
mister.magoo (11/13/2012)
Jeff Moden (11/12/2012)
Just like the old cartoon, I've got to say... "Ah, Magoo! You've done it again!"

Here are the run results using the same machine I used in testing for the article for a million nodes using your fine addition.

Building the initial table and SortPath...
There are 1000000 rows in dbo.Hierarchy
Cumulative Duration = 00:00:14:420
Building the Nested Sets...
1000000 rows have been updated to Nested Sets
If the rowcounts don't match, there may be orphans.
Cumulative Duration = 00:00:42:023
Building the indexes...
Cumulative Duration = 00:00:47:330
===============================================
RUN COMPLETE
===============================================



In whole numbers, that a rock solid 13% improvement. Well done, Magoo!

My only question now is, is it the "Identity Hack" that did it or is it the fact that you used a While Loop to replacce the rCTE (and we've previously proven that such loops will frequenctly beat rCtEs). I'll give it a try tomorrow.

Speaking of that, tomorrow is only a half hour a way so I need to hit the hay or the people at work are going to have to put up with a really cranky ol' DBA tomorrow. :-P Thanks again for the code, Magoo.

To the best of my knowledge, the identity has no effect on speed directly, but it allows us to "remember" a value between statements without using a variable, which in turn means the while loop can operate with just one statement... That is where the advantage is gained.
If you have to perform operations in the while loop to manipulate a variable it becomes costly.

The result of doing the inserts in this way is a series of set based inserts with no extra overhead.


Ah... I missed that completely last night. Thanks, Magoo. I've been meaning to do a deeper dive on your "Identity Hack" since the first time you brought it up on the forums. I definitely need to take a closer look.

As a side bar, you should write a "spackle" article on the subject. As my boss wwould say, it's a "spec-hacular" trick.

--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
Theo Ekelmans
Theo Ekelmans
Ten Centuries
Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)

Group: General Forum Members
Points: 1058 Visits: 802
Stick???

I'd say this article is more like a bat; and a really good tool to hammer this example into the minds of some data model dudez i need work with to develop an SNMP MIB database Smile

Thanks for sharing !!!

Theo
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)SSC Guru (213K reputation)

Group: General Forum Members
Points: 213781 Visits: 41977
Theo Ekelmans (11/13/2012)
Stick???

I'd say this article is more like a bat; and a really good tool to hammer this example into the minds of some data model dudez i need work with to develop an SNMP MIB database Smile

Thanks for sharing !!!

Theo


Heh... if you like what can be done with a bat, then you'll really like the 16# sledge hammer you'll find in the followup article on hierarchies coming out this Thursday (15 Nov 2012), Theo. It shows another bit of "black arts" magic that preaggregates the million node hierarchy to provide most of the answers to questions that you might ever ask of a hierarchy and it only takes 8 seconds longer.

Thanks for the feedback, Theo. I'd also be interested in a more detailed version of what you're doing for your SNMP MIB database. It sounds like a great deal of fun!

--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
Theo Ekelmans
Theo Ekelmans
Ten Centuries
Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)Ten Centuries (1.1K reputation)

Group: General Forum Members
Points: 1058 Visits: 802
LOL, gimme thor class hammer!!!

The project i'm working on is a roof of concept SNMP MIB database, that is so fast it can do (near)realtime SNMP data packet to SQL data conversion

Just in case your new to the extensible SNMP MIB tree:

If E-mail addresses were OIDs... user@ordina.org would have been something like: user@ordina.enterprises.private.internet.dod.org.iso
or in non-translated notation: user@99999.1.4.1.6.3.1

except that we write the top-most part at the left: 1.3.6.1.4.1.99999.117.115.101.114

An OID is just a unique key (within one managed device) for one piece of information Ensures vendors don't have conflicting OIDs

OID corresponds to a label .1.3.6.1.2.1.1.5 => sysName (in windows this is the servername)

The complete (translated) path: .iso.org.dod.internet.mgmt.mib-2.system.sysName

The info needed to get from one to an other is "mib (database) files", that are supplied with each new device / software version.

The provided MIB files all have a part of the ginormous jigsaw MIB tree, and that needs to be searched between 500 to 20.000 times a minute.

Fun project indeed Smile
cs_troyk
cs_troyk
SSCrazy
SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)SSCrazy (2.1K reputation)

Group: General Forum Members
Points: 2130 Visits: 973
Excellent article, Jeff! I look forward to Thursday's installment.

I've played around with mixing these two representations of hierarchies before, but had never gotten past the performance issues, so it's great to have a new approach to try. It seems that I keep inheriting db implementations that contain at least one hierarchy in them, so having more choices for dealing with them is a very good thing!

For those that are willing to give up a little in terms of understandability (which can be dealt with via abstractions, anyway), and who are working with fairly constrained hierarchy sizes, take some time to investigate the matrix path encoding technique that Tropashko describes. You can think of it as a "best of both worlds" approach to the problem that doesn't have the heavy recalculation requirements. I was also able to obtain favorable performance results for many of the descendant- and ancestor-type queries. If nothing else, it will expand your db math skillset:-D

And finally, for those with some disk space to burn, you might consider materializing the transitive closure of the hierarchy. This can really net you some performance if you have a large hierarchy that is used primarily for reads (the materialization is a rather expensive process).

-TroyK



Igor Micev
Igor Micev
SSChampion
SSChampion (10K reputation)SSChampion (10K reputation)SSChampion (10K reputation)SSChampion (10K reputation)SSChampion (10K reputation)SSChampion (10K reputation)SSChampion (10K reputation)SSChampion (10K reputation)

Group: General Forum Members
Points: 10280 Visits: 5157
Hi Jeff,
Simply brilliant!

Thanks
IgorMi

Igor Micev,
My blog: www.igormicev.com
Michael Meierruth
Michael Meierruth
SSCrazy
SSCrazy (2.3K reputation)SSCrazy (2.3K reputation)SSCrazy (2.3K reputation)SSCrazy (2.3K reputation)SSCrazy (2.3K reputation)SSCrazy (2.3K reputation)SSCrazy (2.3K reputation)SSCrazy (2.3K reputation)

Group: General Forum Members
Points: 2324 Visits: 2516
Jeff,

In the code for generating the tally table, you use this syntax:
row_number() over (order by (select null))

I have never see this before. But it works. What is this '(select null)' trick all about?

PS
Very, very neat article!
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