Re: Indexing techniques for hierarchies

From: --CELKO-- <71062.1056_at_compuserve.com>
Date: 21 Dec 2001 11:53:46 -0800
Message-ID: <c0d87ec0.0112211153.6308ad88_at_posting.google.com>

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

There are some tricks with the nested sets model. First, put the tree structure (i.e. organizational chart) and the nodes (i.e. personnel)in separate tables. This makes the rows of the tree structure table very short, so that a lot of them fit onto one data page. For example:

CREATE TABLE Tree
(lft INTEGER NOT NULL,
 rgt INTEGER NOT NULL,
 CHECK (lft < rgt),
 emp_id INTEGER -- null means the job is empty

        REFERENCES Personnel(emp_id)
        ON UPDATE CASCADE
        ON DELETE SET NULL,

 PRIMARY KEY (lft, rgt));

This would give us a unique index on (lft, rgt) which will make the BETWEEN predicate faster. If you want to add an index to emp_id that would also help. However, you could get a covering index with

CREATE TABLE Tree
(lft INTEGER NOT NULL,
 rgt INTEGER NOT NULL,
 CHECK (lft < rgt),
 emp_id INTEGER -- null means the job is empty

        REFERENCES Personnel(emp_id)
        ON UPDATE CASCADE
        ON DELETE SET NULL,

 UNIQUE (lft, rgt, emp_id)); -- unique allows nulls Received on Fri Dec 21 2001 - 20:53:46 CET