Using Materialized Path to create a paths table

Here are some records

EmployeeId ParentEmployeeId MaterializedPath

1                   <null>                    1.
2                   1                           1.1.
3                   1                           1.2.
4                   2                           1.1.1

etc.

To find the descendants of a node using the materialized path is quite low-cost: an index on MaterializedPath would be usable with the following query

select
Descendant.EmployeeId
from Employee as Ancestor
inner join Employee as Descendant on Descendant.MaterializedPath like Ancestor.MaterializedPath + '%'
where Ancestor.EmployeeId = 1

To find the ancestors however with the following query

select
Ancestor.EmployeeId
from Employee as Descendant
inner join Employee as Ancestor on Descendant.MaterializedPath like Ancestor.MaterializedPath + '%'
where Descendant.EmployeeId = 4

requires a table scan.

This is very expensive for any non-trivial number of nodes where you need to find a node's ancestors.

But if you treat the MaterializedPath as an intermediate result, it is a trival to use it to build a denormalized EmployeeAncestor table, which for the set of data above would be as follows

EmployeeId AncestorEmployeeId

1                 1
2                 1
2                 2
3                 1
3                 2
4                 1
4                 2
4                 4

I.e. there is one record for each of each node's ancestors (including the node itself)

This table is easy to maintain using the same trigger tha maintains the MaterializedPath (although not so easy if you did not maintain the MaterializedPath itself)

The advantage is that it becomes very much cheaper to calculate the ancestors of a node:

select
Ancestor.EmployeeId
from
EmployeeAncestor Descendant
inner join Employee Ancestor on Ancestor.EmployeeId = Descendant.AncestorEmployeeId
where Descendant.EmployeeId = 4

The query to find descendant is similar:

select
Descendant.EmployeeId
from
Employee Ancestor
inner join EmployeeAncestor Descendant on Descendant.AncestorEmployeeId = Ancestor.EmployeeId
where Ancestor.EmployeeId = 1

So it seems to me that the materialized path is not actually a good thing to use to find ancestor/descendant relationships of itself, but by using it to create a simple ancestor node-type table, you can get slightly better performance for finding descendants, and vastly better performance results for ancestors.

Any comments? Received on Thu May 25 2006 - 15:41:55 CEST