Hierarchies (trees) in SQL Server 2005

re: Hierarchies (trees) in SQL Server 2005

Roger Bucks — Thu, 16 Feb 2006 02:40:16 GMT

There seems to be another mechanism for this in SQL Server 2005 (I found the link to it http://www.sqlservercentral.com/columnists/sSampath/recursivequeriesinsqlserver2005.asp)
Unfortunately I have not had a chance to try this out. Have you experimented with this technique?

re: Hierarchies (trees) in SQL Server 2005

AnthonyBloesch — Thu, 16 Feb 2006 02:54:35 GMT

This is the adjacency approach mentioned in the post. They use recursive CTE queries also.
In early betas of SQL Server 2005, recursive CTE queries generated poor query plans so I did this calculation with a stored procedure. However, now recursive CTE queries generate good query plans so I use CTE queries.

re: Broken image links

Chui — Thu, 16 Feb 2006 03:15:53 GMT

Images referring to your file system my friend

file://Tkzaw-pro-14/Mydocs3/ABloesch/My%20Documents/Projects/Blog/Tree%

re: Hierarchies (trees) in SQL Server 2005

Roger Bucks — Thu, 16 Feb 2006 03:24:37 GMT

Thanks for the update.
Do you have a sample of the CTE query that you might use in the example you give above?
(To understand how the performance figures were obtained, is it possible to link to/display the SQL used?)

re: Hierarchies (trees) in SQL Server 2005

Cel;ko — Mon, 06 Mar 2006 06:01:18 GMT

Someone quoted your blog on an SQL Sever newsgroup that an adjacency list tbel is just fine. I took a quick peek at the blog. So here Ia m for details.

You seemed to be measring loading time, without telling us the fomat of the data. If you are loading (superior, subordinate) pairs without any cycle and gap checking. You did do FULL checking on EACH edge of the graph? No cycles? Do you have a solution to an NP-Complete Problem? Or a proof it is impossible? Ghod, you will be famous!!

I have 20+ years of SQL in 177+ produccts and when I wrote my code, it sucked rocks. Show what you do for data integrity. I am amazed because you did better than I have been able to do in 10+ years of trying!!

How many thousand summary queries in a tree of depth 5, 10 and 20 levels did you do in the models? What ere the numbers?

If you do the adjacency list model done right, you have to insert (in_node, out_node) pairs and then check the ENTIRE schema for cycles with a TRIGGER every time. Then you have to look for gaps to assure it is one tree. And finally check that "# of nodes = (# of edges) - 1"

This is not an option -- it is vital. I am waiting for $1000/day contract to come thru with an insurance company that forgot these constraints [Opps!! we are dead! and since we do not expect a right answer, it is always 42:)]

Test methods 20 levels deep and 20 levels across -- the schema for a 747 airplane parts explosion. Really.

re: Hierarchies (trees) in SQL Server 2005

shanzy — Fri, 23 Jun 2006 07:24:33 GMT

wonderful article!!

A question:

Where I can found the Class (namespace) Hierarchy Chart for .net 2.0? Just like the MFC Hierarchy Chart in MSDN2001? Is it

available from microsoft or MSDN? Can you give me a link?

Thank you very much!!

re: Hierarchies (trees) in SQL Server 2005

Misha — Thu, 05 Oct 2006 13:20:42 GMT

Do you have any data on the relative speed of the recursive CTE vs (your old) stored procedure versions of the adjacency model?

Have you tried a materialised ancestor version of the adjacency model (using either triggers or indexed views)?

Can you publish the code used in the tests?

re: Hierarchies (trees) in SQL Server 2005

Chandrashekar Kollipara — Sun, 28 Jan 2007 18:25:10 GMT

When you post such an article on msdn.com there should be considerable amount of test data that would proove what you put forward. I have been working in this area for last 10 years and agree with Celko 100%. Please dont misguide people if you cant guide them to the correct path

re: Hierarchies (trees) in SQL Server 2005

Cesar — Sat, 31 Mar 2007 08:35:21 GMT

I know it is too late to ask, but where is the data to test your experiment?

re: Hierarchies (trees) in SQL Server 2005

dan — Wed, 26 Nov 2008 05:06:28 GMT

To the person making comments that sound a bit nasty, and mentioning NP-Complete. it may come as a surprise to you, but not everyone releases everything they have, and there are indeed some solutions out there you have not heard of.

re: Hierarchies (trees) in SQL Server 2005

mbuzina — Thu, 05 Feb 2009 11:41:18 GMT

I am missing the classical datawarehouse approach. I know it is mostly focused on querying, but in my personal experiance, the insert performance is not too bad, depending on the model of inserts.

I have successfully used a combination of adjencency with a cache table for holding all relationships. I would have the following cache table

emp_cache

descendant,ancestor,distance

2,2,0

1,1,0

1,2,1

3,3,0

3,2,1

4,4,0

4,3,1

4,2,2

5,5,0

5,3,1

5,2,1

Additionally I would add a depth column to the base table, which allows a quicker computation of the distance value inside the trigger maintaining the cache and have the cache table indexed (depending on your query patterns). Inserting, updateing & deleting is done exactly as with adjacency, which makes sure there are no loops at all. Querying will use the cache table (& depth column). Querying the cache is quite natural to sql.

I used this to handle a cost center structure which was 17 levels deep and handled approx. 15.000 nodes.

re: Hierarchies (trees) in SQL Server 2005

Yoseph — Fri, 03 Apr 2009 12:37:27 GMT

When using Nested set, if you want to retrieve all the tree (root node and all of its descendants), all you need to do is: SELECT * FROM tree ORDER BY left ASC. The process of generating the tree is supposed to be handled by your application. So the query needed is only 1, not 6072.

You can see the implementation of this tree in PHP ORM framework (Propel) ->

http://propel.phpdb.org/trac/wiki/Users/Documentation/1.3/Tree/NestedSet

Here is some code of the implementation of retrieving tree:

public static function retrieveTree(PropelPDO $con = null)

{

$c = new Criteria(TreePeer::DATABASE_NAME);

$c->addAscendingOrderByColumn(self::LEFT_COL);

EXECUTE QUERY:

SELECT * FROM tree ORDER BY lft ASC

$stmt = TreePeer::doSelectStmt($c, $con);

if (false !== ($row = $stmt->fetch(PDO::FETCH_NUM))) {

$root = new Tree();

$root->hydrate($row);

$root->setLevel(0);

$tree = self::hydrateDescendants($root, $stmt);

$stmt->closeCursor();

return $tree;

}

return false;

}

Note: only 1 query is executed.

re: Hierarchies (trees) in SQL Server 2005

Niclas — Fri, 08 May 2009 01:31:43 GMT

Hi there,

I have a problem which i wonder if you could point me in direction how to solve.

I have a tree structure where each node have a "rating" column (int). For "composite" nodes, nodes with children the rating column should take the value of the max value of all its children. What kind of structure do i represent such a tree best in?

re: Hierarchies (trees) in SQL Server 2005

OrbMan — Thu, 10 Sep 2009 15:23:48 GMT

The high value for all descendents of the path model makes me think the path column was not indexed - can you confirm whether it was or not?

re: Hierarchies (trees) in SQL Server 2005

Jon — Mon, 16 Nov 2009 11:28:06 GMT

I don't know this Celko. Wikipedia says:

He is often corrected by product experts including a number of the SQL Server MVP's which lead to protracted discussions which more often than not he comes out losing.

All I know is he is a brag who's not helping average programmers... I have 20+ experience and paid $1000s of a day. Ashol. Same with you Chandrashekar. I bet you dont even know what you are saying.