Fixing r-tree semantics - Mailing list pgsql-hackers

I looked into the r-tree breakage discussed in this thread:
http://archives.postgresql.org/pgsql-general/2004-03/msg01135.php

The executive summary: r-tree index opclasses contain four two-dimensional
operators, which behave correctly, and four one-dimensional operators
which do not.  There is a basic logic error in the handling of the 1-D
operators.  One could also legitimately ask why the opclasses don't cover
both directions (X and Y) for 1-D inquiries.  The same problems exist in
the contrib/rtree_gist implementation, because it just copied the r-tree
logic without inquiring too closely into it :-(

We currently have built-in opclasses for types "box" and "polygon", both
of which are fundamentally 2-D objects.  The 2-D operators that the r-tree
opclasses handle are:~=    same (ordinary equality)&&    overlaps~    contains@    is contained by
with pretty much the intuitive definitions of these things.  The 1-D
operators in the opclasses are<<    left        l.max_x < r.min_x>>    right        l.min_x > r.max_x&<    overleft
l.max_x<= r.max_x&>    overright    l.min_x >= r.min_x
 
(I'm not here to argue about whether these definitions are right in
detail, particularly about the equality cases; that's the way it's been
since Berkeley and I'm not proposing to change them.)

Now the problem is that given a query box, say "index_col << some_box",
the rtree code has to decide whether to descend to a child page of the
index tree based on what is in the parent index page's entry for the
child --- and what is there is the union, or minimum combined bounding
box, of the boxes or polygons in the child.  So the test for descending
is not the same as the test for whether a leaf index entry actually
matches the query.  Fine ... but somebody got this wrong long ago.
If you think about it, the criterion for descending during a << (left)
search is properlyunion_box.min_x < query.min_x
If this is true, there might be boxes within the union that satisfy
the << requirement (box.max_x < query.min_x); if it is not true then
there clearly can be no such boxes.  So, given the available operators,
the correct test for descending is "!overright".  But the actual test
being done, according to rtstrat.c, is "overleft".  This causes the search
to fail to search child pages that should be searched (and probably also
to waste time searching pages that shouldn't be searched).  The observed
result is, not surprisingly, that the indexscan fails to find some rows
it should find.

In the same way, the correct descent tests for the other operators areoverleft:    !rightright:
!overleftoverright:   !leftoverlaps:    overlapssame:        containscontains:    containscontained:    overlaps
 
rtstrat.c gets the first three of these wrong, but the last four cases
covering the 2-D operators are correct.

This analysis explains why we've not heard more complaints about such a
fundamental breakage: the cases most people care about, when using an
r-tree, are 2-D inquiries.  And what's more, the default selectivity
estimates for 1-D inquiries are so low that the index never got used.
In 8.1 this will change, because a bitmap index scan looks attractive
to the planner even at rather low selectivity --- which means that we
are probably going to hear more complaints, if we don't fix it.

Fixing the existing operators seems relatively straightforward; there will
need to be some extension to rtstrat.c to represent "NOT this operator"
as well as "this operator", but that's not hard.  I plan to do this, and
make the corresponding fixes in contrib/rtree_gist as well.


What needs more discussion is that it seems to me to make sense to extend
the standard opclasses to handle the four Y-direction operators comparable
to the X-direction operators that are already there, that is "above",
"below", "overabove", and "overbelow".  The polygon type has none of these
operators at the moment.  Box has<^    below        l.max_y <= r.min_y>^    above        l.min_y >= r.max_y
but not the overlap variants.

If you compare these to the X-direction versions:<<    left        l.max_x < r.min_x>>    right        l.min_x >
r.max_x
there are two obvious discrepancies: the names aren't very similar and
the equality cases are handled differently.

We could incorporate the existing box_above and box_below operators into
an r-tree opclass if we defined overabove and overbelow to not match on
the equality case:    overbelow    l.max_y < r.max_y    overabove    l.min_y > r.min_y
However, it seems just plain weird to me to have different edge-case
behaviors in the X and Y directions.  So I don't much care for that.
I would prefer that the operators added to the opclasses act the same
in both directions.

We could avoid any backwards-compatibility complaints if we left
those two operators alone (maybe redocumenting them as "below or touching"
and "above or touching", though these descriptions are a bit misleading)
and invented four new operators to be the Y-direction opclass members,
say<<^    below        l.max_y < r.min_y>>^    above        l.min_y > r.max_y&<^    overbelow    l.max_y <= r.max_y&>^
 overabove    l.min_y >= r.min_y
 
This has a lot to recommend it: backwards compatibility and operator names
that line up with the X-direction case.  On the other hand, it'll confuse
people to have operators that are so close in function, and having one be
indexable and the other not seems like a gotcha.

Plan C would be to just change the above and below operators, on the
grounds that it is an obvious typo that they don't match left and right
to begin with.  We have made greater changes in the behavior of geometric
operators in the past, so this isn't an obviously bogus choice.

Not quite sure what to do, but I'd like to do something with it.
Thoughts?
        regards, tom lane