Hello,
I'm rather confused about the logic of something in the rtree code, perhaps
someone can provide some insight here. Without loss of generality I'll
use intervals on R (real number line) below, but this would apply to
boxes as well. Note that sup(S) and inf(S) are the upper and lower bound
of interval S, which (if S is the closed interval [min,max]) equals
min and max, respectively.
geo_ops.c defines the overleft operator as (considering intervals, not
boxes)
S &< T iff sup(S) <= sup(T)
whereas the left operator is defined as
S << T iff sup(S) < inf(T)
fine and dandy.
If I understand correctly, in scanning an R-tree (see rtstrat.c) there
appear to be several replacements for these operators that occur at nodes
(as opposed to leaves) in the tree. For example, if searching for an
interval (box) that is the same as T, we check if the node contains T,
because the node's interval contains the leaves' intervals.
Again, fine and dandy.
My concern is this. The left (<<) operator is replaced with overleft (&<)
in tests at a node. However, consider the node N whose leaves L and R
are as follows:
N = [0,3] L = [0,1] R = [2,3]
and a target interval
T = [1.4,1.6]
If I understand correctly, a search for all X << T will test if N &< T.
While it is the case that L << T, it is not the case that N &< T, as
sup(N) > sup(T).
I expect that I'm missing something important in the code. Can someone
let me know what that is, so I'll stop worrying? ;)
Alternatively, if I'm not missing something, either the node-level
replacement must be changed to "N << T or X && T" (which probably
wouldn't work unless one added operators to the geo-ops class), or
the definition of "overleft" should truly include all cases of overlap
(e.g., [0,3] &< [1,2] would be true).
Thank you,
-- Bill
---------------------------(end of broadcast)--------------------------- TIP 5: Have you checked our extensive FAQ?
http://www.postgresql.org/docs/faqs/FAQ.html
