Home Forums Article Discussions Article Discussions by Author Discuss Content Posted by Jeff Moden Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets RE: Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets

  • November 15, 2012 at 11:18 pm

    #1559625

    GSquared (11/15/2012)

    Since I was out a few days, I missed this article till today.

    Interesting methodology.

    Testing it on my workstation, I got 45 seconds for a million-row hierarchy, 30 nodes deep.

    On 10k rows, 21 deep, took 593 milliseconds.

    Methods I posted in my article in August took 3 milliseconds at 10k rows, 29 seconds at 1M rows, same data. I'm using HierarchyIDs the same way you use your SortBy column. When I modified to Varbinary(max) instead of HiearchyID, it stays under 10 milliseconds for 10k rows, but goes up to 49 seconds for 1M rows, using those methods.

    In the Varbinary(max) version, 70-75% of the run-time was generating the breadcrumb path (SortBy), and 25-30% in generating the Nested Sets from it.

    Per my tests, HierarchyID will only easily go to a depth of a little more than 400 levels, so my methods won't work precisely on really deep hierarchies. Anything less than 400 levels, I'd still stick with HierarchyID, and seriously think about upgrading to a supported version of SQL Server if you can't use them. Not always possible, but it is worth it if you can.

    Didn't get a chance to try yours out with a hierarchy table with n-top levels, instead of just 1, as per the comments in your code. Wanted to make sure I was using the same testing methodology, so didn't play with your test-hierarchy-generator, in order to try these kinds of permutations.

    Of course, I'm not entirely sure why you'd use both breadcrumbs and nested sets. If you're already breadcrumbing, you can query that directly and avoid nested sets completely. Same performance as nested sets, in most cases, unless your path is really, really long (since it's a binary sort, until it goes over 8000 datalength; indexes do binary sorts very, very well).

    Thanks for the feedback, Gus. The bread crumbing was just to make the calculation of the Nested Sets easy and could actually be removed from the final table. I left it there for two reasons... 1) as a training artifact and 2) beccause just like you say, there's a use in those breadcrumbs that will be demmonstrated in part 2.

    So far as upgrading to 2008 or better to make use of the HierarchyID datatype goes, some people just don't have that option.

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

    Change is inevitable... Change for the better is not.

    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)