Improve hierarchy performance using nested sets

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