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

Yes, that's the one!

I'm not against using obscure hacks, and there's always going to be a debate about the point at which you even classify something as an obscure hack. The discovery of a new, better way of doing things will start life as an obscure hack and eventually find its way into mainstream use. What I am against, is using obscure hacks without explaining what you're doing in your code. At some point Joe Rookie is going to inherit my code and is going to waste an awful lot of time working out why I'd ever order by @@spid if I haven't commented. I don't know where the line should be drawn regarding what to comment and what not to, but personally, I've always appreciated inheriting code where the original author went to a bit of effort.

Each to their own, but to my mind, I see no difference between ordering by a static variable like @@SPID and a NULL set...both are hacks according to Books Online, which only allows for columns made available by the FROM clause...

@mister.magoo

Yes I totally agree. I was just using the @@spid as an example. My point (that if you're using obscure hacks you should explain what you're doing in your code) applies equally to using NULL in that context.

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

Excellent article; I have used all three types of tree representations before. In one project, we used a materialized path, and I kind of wish I'd thought to use varbinary instead of a hex string. However, I just tested using an index on a materialized path as a hex string using 100000 rows of sample data generated with BuildLargeEmployeeTable, and the results were perhaps not so surprising.

SELECT

ISNULL(EmployeeID, 0) AS EmployeeID,

ISNULL(ManagerID, 0) AS ManagerID,

ISNULL(CONVERT(varchar(8000), sortpath, 2), '') as SortPath

INTO Hierarchy2

FROM Hierarchy

ALTER TABLE Hierarchy2 ADD CONSTRAINT PK_Hierarchy2 PRIMARY KEY CLUSTERED (EmployeeID)

CREATE INDEX SortPath ON Hierarchy2 (SortPath)

SQL Server will use a string index on LIKE operations anchored at the begining, so this:

SELECT * FROM Hierarchy2 WHERE SortPath LIKE '0000000100000002000000130000001F0000003F00000058000000650000009600000935%'

ends up being more than three times more efficient than this:

SELECT * FROM Hierarchy2 WHERE SUBSTRING(SortPath, 65, 8) = '00000935'

Unfortunately, the index only supports the first 900 bytes of the SortPath. Also, since the Nested Sets provide the same benefits (fast ancestor / descendant access and sorting), and since the update to calculate them using the SortPath is going to touch every row anyway, going with the approach you've got looks best. 🙂

I guess since the rebuild is so fast, you also don't need to consider using double-precision floating-point numbers as the bowers (which makes updating the bowers in place a bit more manageable, since you can keep subdividing the ranges up to a certain point).

Keep up the great work!

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.