Nested Set query suggestions - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2005 Forums

Transact-SQL (2005)

Nested Set query suggestions

Author

Topic

gamartin
Starting Member

1 Post

Posted - 2010-03-29 : 15:52:26

Hi all:

I am planning on using a nested set hierarchy type table to store the hierarchy of tasks for a project management tool. The client wants to have the tasks automatically renumber when tasks get inserted/moved within the tree -- (i.e. 1, 1.1, 1.1.1, 1.1.2, 1.2 ...etc)

Having only worked a little with nested sets, I would appreciate any suggestions on the following:

1) is it practical to calculate the "number" (1.1.2 or whatever) at runtime by walking up the tree for each node to create the unique number or would that impose too much overhead on the server? It is unlikely that any one tree (or project) would have more than 250-300 individual nodes (based on the current system I am replacing).

or

2) would I be better computing the "number" when adding the node and only changing it when the node gets moved around? A node can only be switched with one of it's siblings (not across branches) so it is not that big a move (if that makes any difference)

The main reason for asking is really a performance issue since I assume that I am going to be looking at a recursive function basically to get the full "number" starting from the individual node.

Thanks in advance

Garth

PackRat
Starting Member

26 Posts

Posted - 2010-04-01 : 18:13:17

The code below I adapted from one of my production scripts. It will at least get you a working sequencer.

Whether you store the sequence in the table or generate it on the fly is your call, best to take into consideration your particular scenario. if your sequences are of a known and limited depth and might end up looking like 1.5.9 storing them in the table might not be too bad (can cluster on that key), but if the sequences are potentially long or of n-tier depth calculating them on the fly isn't a bad option either;

1.5.9 doesn't look so bad, but
113202.156478.294732.746354 ... can get to be a bit much when it runs long.

To give credit where credit's due; the solution below is inspired by techniques gleaned from some of Itzik Ben-Gan's articles in SqlMag;

some sample data:


DECLARE @Hierarchy TABLE(ID INT NOT NULL PRIMARY KEY, ParentID INT NULL);
INSERT @Hierarchy
SELECT 10481, 10413	UNION ALL
SELECT 10482, 10413	UNION ALL
SELECT 10483, 10413	UNION ALL
SELECT 10484, 10413	UNION ALL
SELECT 10485, 10413	UNION ALL
SELECT 10486, 10413	UNION ALL
SELECT 10487, 10413	UNION ALL
SELECT 10492, 10413	UNION ALL
SELECT 10493, 10413	UNION ALL
SELECT 10499, NULL	UNION ALL
SELECT 10500, NULL	UNION ALL
SELECT 10501, NULL	UNION ALL
SELECT 10502, NULL	UNION ALL
SELECT 10503, NULL	UNION ALL
SELECT 10508, NULL	UNION ALL
SELECT 10515, NULL	UNION ALL
SELECT 10527, 10497	UNION ALL
SELECT 10528, 10497	UNION ALL
SELECT 10541, NULL	UNION ALL
SELECT 10714, 10498	UNION ALL
SELECT 12676, 10497	UNION ALL
SELECT 12680, 10497	UNION ALL
SELECT 12681, 10418	UNION ALL
SELECT 12682, NULL	UNION ALL
SELECT 10413, NULL	UNION ALL
SELECT 10418, NULL	UNION ALL
SELECT 10468, 10413	UNION ALL
SELECT 10470, 10468	UNION ALL
SELECT 10471, 10470	UNION ALL
SELECT 10473, 10413	UNION ALL
SELECT 10474, 10413	UNION ALL
SELECT 10475, 10413	UNION ALL
SELECT 10476, 10413	UNION ALL
SELECT 10477, 10413	UNION ALL
SELECT 10488, 10413	UNION ALL
SELECT 10489, 10413	UNION ALL
SELECT 10490, 10413	UNION ALL
SELECT 10491, 10413	UNION ALL
SELECT 10497, NULL	UNION ALL
SELECT 10498, NULL	UNION ALL
SELECT 10604, NULL

couple things for fun;


DECLARE @MaxDepth TINYINT, @RootID INT;
SET @MaxDepth=1;
SET @RootID=10413;

the main course;


DECLARE @MaxDepth TINYINT, @RootID INT;
SET @MaxDepth=1;
SET @RootID=NULL; --10413

WITH HierarchyCTE ([ParentID],[ID],[ThreadDepth],[Sequence]) AS 
(
	SELECT 
		  EM.[ParentID]
		, EM.[ID]
		, 0 AS [ThreadDepth]
		, CAST(EM.[ID] AS varbinary(max)) [Sequence]
	FROM @Hierarchy EM
	WHERE (@RootID IS NULL AND EM.[ParentID] IS NULL) 
		OR (@RootID = EM.[ParentID])

	UNION ALL

	SELECT 
		  HierarchyCTE.[ID] [ParentID]
		, EM.[ID]
		, HierarchyCTE.[ThreadDepth]+1 [ThreadDepth]
		,CAST(HierarchyCTE.[Sequence] + CAST(EM.[ID] AS binary(4)) AS varbinary(max)) [Sequence]

	FROM HierarchyCTE INNER JOIN @Hierarchy EM ON HierarchyCTE.[ID]=EM.[ParentID]
	WHERE (@MaxDepth IS NULL OR HierarchyCTE.[ThreadDepth] < @MaxDepth)
) 
	SELECT [ParentID],[ID],[ThreadDepth],[Sequence]
	FROM HierarchyCTE
	ORDER BY [Sequence];

if you need to order the sequence by something other than the simple id you can add to the sequence;

CAST(EM.[DateCol] AS binary(8))+CAST(EM.[ID] AS binary(4))

will order members by date then id, the sequences will become very long at depth, a further deturrent to saving the sequence in the table, but you're granted a lot of flexibilty in the exact row order you end up with - very useful if you need something other than or in addition to id order

_____________________________
wrote this on my TRS-80 COCO4

<PakRat/>

tkizer
Almighty SQL Goddess

38200 Posts

Posted - 2010-04-01 : 18:45:56

I moved the topic from the Script Library forum.

Tara Kizer
Microsoft MVP for Windows Server System - SQL Server
http://weblogs.sqlteam.com/tarad/

Subscribe to my blog

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources