Re: Nested Sets vs. Nested Intervals

Joe,

We have already discussed this. The predicate

O1.lft BETWEEN O2.lft AND O2.rgt

looks simple, but is assymmetric regarding O1 and O2. In the acces path driven from O2 to O1, the O1 set could be found by index range scan. Find the first node in the b-tree satisfying

O1.lft BETWEEN O2.lft AND O2.rgt

then go to the next b-tree leaf, and so on. This is very efficient.

In contrast, the access path driven from O1 to O2 you have either to scan the whole table O2, or use index range scan that would scan an interval with one boundary condition only

O1.lft >= O2.lft

or

O1.lft <= O2.rgt

which would scan large portion of the index. This is (relatively) inefficient. Received on Thu Nov 10 2005 - 02:56:30 CET