Sunday, February 12, 2006

How To: Hierarchal Lookups Without a Cursor

Reporting on hierarchal tables (Child/Parent relationship) tables can be a huge time bottleneck when using an iterative cursor process. Here is a speedy way to look up hierarchal information.

Original Hierarchal Table
Traditionally hierarchal tables self reference its own primary key and giving it a parent role name. Example:

PersonID (PK) , Name (Attributes) , ParentPersonID (Self Ref. Person.PersonID FK)
1 , John Doe , NULL
2 , Tom Doe , 1
3 , Jill Doe , 1
4 , Harry Doe , 2
5 , Jim Smith , NULL

Hierarchal Index Table
The key is building an index table that maps a parent to every child, grand child, great grand child, etc... and assign the generation it belongs to in relationship. Example:

AncestoryID (Person.PersonID PK, FK), ChildID (Person.PersonID PK, FK), GenerationLevel1 (John Doe) , 1 (John Doe), 0
1 (John (Doe), 2 (Tom Doe), 1
1 (John Doe), 3 (Jill Doe), 1
1 (John Doe), 4 (Harry Doe), 2
2 (Tom Doe), 2 (Tom Doe), 0
2 (Tom Doe), 4 (Harry Doe), 1
3 (Jill Doe),2 (Jill Doe), 0
4 (Harry Doe), 4 (Harry Doe), 0
5 (Jim Smith), 5 (Jim Smith), 0

Index Usage
With the aid of the hierarchal index you will not need a cursor for your reports. Example:

-- Get all Progeny (Children, Grand Children, etc…)
Select Person.Name, Parent.Name, Index.GenerationLevel
From PersonHierarchyIndex
Join Person
On Person.PersonID = PersonHierarchyIndex.ChildID
And ParentHierarchyIndex.AncestoryID = 1 -- (John Doe)

Join Person Parent
On Parent.PersonID = PersonHierarchyIndex.AncestoryID

Index Population
The following example uses the new feature in 2005 SQL Server. We populate the Index using a recursive query using a CTE (Common Table Expression). It is used to build the index at the time of creating or modifying the hierarchy. Most hierarchies are slowly changing domain data. With that in mind it makes sense to take the cost of building the index at the time when the domain changes rather then at the time of selecting from the hierarchy to create your reports.

Use this function to then insert into the PersonHierarchyIndex table:

-- Recursive Query using Common Table Expression
CREATE Function dbo.BuildPersonHierarchyIndex () RETURNS Table

WITH AncestoryTree (PPID, PID, PersonID, ParentPersonID, DirectChild, GenerationLevel)
AS (SELECT PPID = Person.ParentPersonID, PID = Person.PersonID, Person.PersonID, Person.ParentPersonID , DirectChild = 1, GenerationLevel = 1
FROM Person
SELECT AncestoryTree.PPID, AncestoryTree.PID, Person.PersonID, Person.ParentPersonID, DirectChild = 0, GenerationLevel = AncestoryTree.GenerationLevel + 1
FROM Person
JOIN AncestoryTree
ON AncestoryTree.ParentPersonID = Person.PersonID
WHERE Person.PersonID <> Person.ParentPersonID)
SELECT PersonID = AncestoryTree.PID, AncestoryTree.ParentPersonID, AncestoryTree.DirectChild, AncestoryTree.GenerationLevel
FROM AncestoryTree
SELECT PersonID, PersonID, 0, 0
FROM Person

--OPTION (MAXRECURSION 200) -- Default is 100: Make sure the recursion limit is set high enough

No comments: