Re: Nested Sets vs. Nested Intervals
From: Vadim Tropashko <vadimtro_invalid_at_yahoo.com>
Date: 9 Nov 2005 17:56:30 -0800
Message-ID: <1131587790.345387.81280_at_g47g2000cwa.googlegroups.com>
Date: 9 Nov 2005 17:56:30 -0800
Message-ID: <1131587790.345387.81280_at_g47g2000cwa.googlegroups.com>
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