Path: news.easynews.com!easynews!newsfeed.frii.net!out.nntp.be!propagator-SanJose!in.nntp.be!newsranger.com!www.newsranger.com!not-for-mail
Newsgroups: comp.databases.theory
From: vadim Tropashko <nospam@newsranger.com>
Subject: Indexing techniques for hierarchies
Lines: 32
Message-ID: <%3sU7.5938$XC5.7898@www.newsranger.com>
X-Abuse-Info: When contacting newsranger.com regarding abuse please
X-Abuse-Info: forward the entire news article including headers or
X-Abuse-Info: else we will not be able to process your request
X-Complaints-To: abuse@newsranger.com
NNTP-Posting-Date: Thu, 20 Dec 2001 15:43:39 EST
Organization: http://www.newsranger.com
Date: Thu, 20 Dec 2001 20:43:39 GMT
Xref: easynews comp.databases.theory:19295
X-Received-Date: Thu, 20 Dec 2001 13:43:40 MST (news.easynews.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?