Click here to Skip to main content
12,357,063 members (74,809 online)
Click here to Skip to main content
Articles » Database » Database » SQL » Downloads

Stats

190K views
1.2K downloads
62 bookmarked
Posted

Improve hierarchy performance using nested sets

, 17 May 2003
This article describes how to use nested sets to improve performance of hierarchies within SQL Server and other relational databases
-- Create the SQL Table
CREATE TABLE Employee
	(
		EmployeeID	INT		IDENTITY(1, 1)	NOT NULL,
		ParentID		INT				NULL,
		JobTitle		VARCHAR(50)			NOT NULL,
		FirstName		VARCHAR(50)			NOT NULL,	
		PRIMARY KEY(EmployeeID),
		FOREIGN KEY (ParentID) REFERENCES Employee (EmployeeID)
	)

GO

-- And populate the data:
SET IDENTITY_INSERT Employee ON -- Set identity insert ON so we can insert the employee ID
SET NOCOUNT ON

INSERT INTO Employee (EmployeeID, ParentID, JobTitle, FirstName) VALUES (1, NULL, 'Managing Director', 'Bill')
-- Employees under Bill
INSERT INTO Employee (EmployeeID, ParentID, JobTitle, FirstName) VALUES (2, 1, 'Customer Services', 'Angela')
INSERT INTO Employee (EmployeeID, ParentID, JobTitle, FirstName) VALUES (3, 1, 'Development Manager', 'Ben')
-- Employess under angela
INSERT INTO Employee (EmployeeID, ParentID, JobTitle, FirstName) VALUES (4, 2, 'Assistant 1', 'Henry')
INSERT INTO Employee (EmployeeID, ParentID, JobTitle, FirstName) VALUES (5, 2, 'Assistant 2', 'Nicola')
-- Employees under ben
INSERT INTO Employee (EmployeeID, ParentID, JobTitle, FirstName) VALUES (6, 3, 'Snr Developer', 'Kerry')
INSERT INTO Employee (EmployeeID, ParentID, JobTitle, FirstName) VALUES (7, 3, 'Assistant', 'James')
-- Emplyees under kerry
INSERT INTO Employee (EmployeeID, ParentID, JobTitle, FirstName) VALUES (8, 6, 'Jrn Developer', 'Tim')
SET NOCOUNT OFF

SET IDENTITY_INSERT Employee OFF

-- Alter the employee table to include the left and right extent values
ALTER TABLE Employee ADD [LeftExtent] INT NULL
ALTER TABLE Employee ADD [RightExtent] INT NULL

GO


-- Create the stack table
DECLARE @tmpStack TABLE 
	(
		ID INT IDENTITY(1, 1), 
		EmployeeID INT NOT NULL, 
		LeftExtent INT NULL, 
		RightExtent INT NULL
	)

-- what we do is start from a parent, in this instance
-- we want to start from the very top which is the NULL parent
DECLARE @parentid AS INTEGER
SET @parentid = NULL 

-- our counter is the variable used to set the left and right extent
DECLARE @counter AS INTEGER
SET @counter = 1

-- what we do is go check the parentid for children, if it has children we push
-- it into the stack and move on to the next child
DECLARE @id AS INTEGER
DECLARE @oldid AS INTEGER

SET NOCOUNT ON

WHILE 1 = 1
BEGIN
SET @id = NULL

	-- get the first row which is a child of @partentid, which has not already
	-- been pushed onto the stack
	INSERT INTO @tmpStack
		(
			EmployeeID, 
			LeftExtent
		)
	SELECT TOP 1 EmployeeID, @counter 
	FROM Employee 
	WHERE ISNULL(ParentID, 0) = ISNULL(@parentid,0) 
	AND EmployeeID NOT IN (SELECT EmployeeID FROM @tmpStack)



	-- just check we are getting the right identity value
	-- this value does not get reset once its reas so we need to see if its the same
	-- as the older one
	SET @id = SCOPE_IDENTITY()
	IF ISNULL(@id, 0) = ISNULL(@oldid, 0)
		SET @id = NULL
		ELSE
	BEGIN
		SET @oldid = @id
		SET @counter = @counter + 1
	END


	-- if we have children (i.e if this operation inserted a row, then we carry on
	IF @id IS NULL
	BEGIN
		-- no rows left, which means we want to pop the last item
		SELECT TOP 1 @id = ID FROM @tmpStack
		WHERE RightExtent IS NULL ORDER BY ID DESC
		
		-- there are no items left to pop, so exit the procedure
		IF @id IS NULL
			BREAK

		UPDATE @tmpStack
		SET RightExtent = @counter
		WHERE ID = @id

		SET @counter = @counter + 1 

		SELECT @parentid = ParentID 
		FROM Employee WHERE EmployeeID = (SELECT EmployeeID FROM @tmpStack WHERE ID = @id)
	END
	ELSE
	BEGIN
		-- this is easy enough, move on to the next level
		-- we want the parent id of the item just inserted 
		SELECT @parentid = EmployeeID FROM @tmpStack WHERE ID = @id
	END
END

-- And update all the Items in Hier_Dept
-- in the original hierarchy table
UPDATE e
SET LeftExtent = ts.LeftExtent,
RightExtent = ts.RightExtent
FROM Employee e
INNER JOIN @tmpStack ts
ON ts.EmployeeID = e.EmployeeID

GO

-- If Left is between parent left and parent right then the node is a child
SELECT * FROM Employee 
	CROSS JOIN (
			SELECT [LeftExtent], [RightExtent] 
			FROM Employee WHERE Firstname = 'Ben'
		) AS Parent
WHERE Employee.[LeftExtent] BETWEEN Parent.[LeftExtent] and Parent.[RightExtent]

-- All Leaf nodes (an item with any children) can be identified by Left = Right - 1
SELECT * FROM Employee WHERE [LeftExtent] = [RightExtent] - 1

-- Which level of the hierarchy are the employees on
SELECT COUNT(P2.EmployeeID) AS level, 
	P1.FirstName,
	P1.LeftExtent ,
	P1.RightExtent
FROM Employee AS P1
INNER JOIN Employee AS P2 
	ON (P1.LeftExtent BETWEEN P2.LeftExtent AND P2.RightExtent)
GROUP BY P1.FirstName, P1.LeftExtent, P1.RightExtent
ORDER BY Level ASC

-- Counting the employees of a manager
SELECT p1.FirstName,
	COUNT(p2.EmployeeID) Employees
 FROM Employee p1
INNER JOIN Employee p2
	ON (p2.LeftExtent BETWEEN p1.LeftExtent AND p1.RightExtent AND p2.LeftExtent <> p1.LeftExtent)
GROUP BY p1.FirstName
ORDER BY Employees DESC 

GO


DROP TABLE Employee


By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

James Simpson
United Kingdom United Kingdom
No Biography provided

You may also be interested in...

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160621.1 | Last Updated 18 May 2003
Article Copyright 2003 by James Simpson
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid