Indexing techniques for hierarchies

From: vadim Tropashko <nospam_at_newsranger.com>
Date: Thu, 20 Dec 2001 20:43:39 GMT
Message-ID: <%3sU7.5938$XC5.7898_at_www.newsranger.com>

After familiarising myself with different ways to represent hierarchy in the db I wonder how different methods fare from the performance perspective. Consider, for example, Joe Celko's nested sets. Could the query

<exerpt>

1. An employee and all their Supervisors, no matter how deep the tree.

SELECT P2.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P1.emp = :myemployee;
</exerpt>

tuned to be fast on very large tree? If we have an indexes on lft and rgt columns, neither p2.lft > p1.lft nor p1.lft < P2.rgt would be selective.

2. The employee and all subordinates.

SELECT P2.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P2.emp = :myemployee;

On the contrary, this query is quick with index range scan.

Interestingly, recursive query (either Oracle proprietory "connect by", or SQL99 recursive SQL) is fast in both cases, assuming that we indexed both id and parent_id columns, and that we extract small portion of the tree.

Is there a body of literature :-) to refer to? Received on Thu Dec 20 2001 - 21:43:39 CET