
I don't understand what overlap_{left,right} are supposed to mean.

In general what seems to be missing from the documentation of operator
strategies and support functions is what invariants between them are required.

Can I just make up a meaning for overlap_{left,right}? That's what other
r-tree indexable data types seem to do. Does it have to be consistent in some
with the definitions for left/right? What about with the definitions for
overlapping? contains/contained by? What does it mean to be consistent with
them?

-- 
greg


17 Sep 2004 11:38:01 -0400
Greg Stark <gsstark@mit.edu>
R-Tree operators
Greg Stark <gsstark@mit.edu> writes:
> I don't understand what overlap_{left,right} are supposed to mean.

In this thread:
http://archives.postgresql.org/pgsql-general/2004-03/msg01135.php
we had decided that the rtree stuff is not only poorly documented
but actively broken.  I had thought that Bill White was going to do
some work on the problem, but we've not heard back from him ...

			regards, tom lane

Fri, 17 Sep 2004 12:18:57 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: R-Tree operators 

Tom Lane <tgl@sss.pgh.pa.us> writes:

> Greg Stark <gsstark@mit.edu> writes:
> > I don't understand what overlap_{left,right} are supposed to mean.
> 
> In this thread:
> http://archives.postgresql.org/pgsql-general/2004-03/msg01135.php
> we had decided that the rtree stuff is not only poorly documented
> but actively broken.  I had thought that Bill White was going to do
> some work on the problem, but we've not heard back from him ...

Well that's regarding existing the rtree operator classes for existing
geometric types. What I'm wondering is what invariants I have to maintain if
I'm defining a new operator class.

I'm starting to get a better idea of what's going on here though. Is it the
case that the operators in the operator class are only used when actually
doing an index scan? For building the index it uses the support functions
(union,intersection,size)?

Part of the confusion here is that left,right,overleft,overright only make
sense for 1-dimension cases like intervals. For more dimensions it seems they
make little sense at all. I would be happy if I could just leave them out. As
long as the rtree code can still build the index fine using the support
functions and just not handle access patterns using them I'll be fine.

-- 
greg


17 Sep 2004 17:35:46 -0400
Greg Stark <gsstark@mit.edu>
Re: R-Tree operators
Greg Stark <gsstark@mit.edu> writes:
> I'm starting to get a better idea of what's going on here though. Is it the
> case that the operators in the operator class are only used when actually
> doing an index scan?

Not even that, really.  The operator class is what the planner uses to
detect that a WHERE clause is potentially implementable by an indexscan:
if you have "var OP pseudoconstant" where OP is an operator in the
opclass of an index on VAR, then this is indexscannable.  The indexscan
plan just says to the index AM "here's the WHERE clause, do something
with it".  It's entirely possible that the index AM will never execute
the operator from the WHERE clause directly --- it could rely entirely
on the support functions.  (For example, btree could obviously do
everything it needs to do by examining the results of the
3-way-comparator support function.  I think there are one or two places
where it finds it convenient to use the actual WHERE-clause operator's
implementation function, but in the main it uses the support function.)
On the other hand the index AM is also allowed to transpose things and
substitute use of one operator for another --- so no, you can't just
partially implement an opclass and expect it to work.

I'm not familiar enough with the rtree AM to lay out for you how those
general comments apply to rtree in particular, but that should give you
the lay of the land.  I do recall that rtree does some operator
substitution to obtain the correct tests to use at upper tree levels.

The behavior of the opclass operator members absolutely does have to be
consistent with the support functions, which means that yes there are
very specific semantic requirements on what each one does relative to
the support functions and other members of its opclass.  In the thread
I pointed you to, we had made some progress on understanding just what
rtree expects the semantics to be, but none of that has gotten
transposed into the code or docs yet.

> Part of the confusion here is that left,right,overleft,overright only make
> sense for 1-dimension cases like intervals.

See the thread.  I had personally always assumed that rtree was for 2-D
objects, but it seems like this aspect of the opclass definition handles
just one dimension.  I'd like to see that improved.  Or if it's
fundamental, we need to provide pairs of rtree opclasses for
horizontally and vertically aligned inquiries ...

			regards, tom lane

Fri, 17 Sep 2004 17:51:43 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: R-Tree operators 