Re: Question about rtrees (overleft replacing left in nodes)

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: William White <bwhite(at)frognet(dot)net>
Cc: pgsql-general(at)postgresql(dot)org
Subject: Re: Question about rtrees (overleft replacing left in nodes)
Date: 2004-03-31 17:55:40
Message-ID: 7576.1080755740@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general pgsql-patches

William White <bwhite(at)frognet(dot)net> writes:
> Tom Lane wrote:
>> However, if this is indeed wrong, why have we not heard bug reports
>> stating that rtree indexes don't work?

> Because the positionsel/positionjoinsel estimator functions make it all
> but impossible to invoke index search on r-trees for position operators;

Good point. You can force it by setting enable_seqscan to false, but
otherwise it's unlikely to happen.

> Suggested remediation, if this is reproducible:

> 1. Modify overleft and overright to actually mean "overlap or left" and
> "overlap or right" respectively, which might break existing code, or

> 2. Add two new functions, e.g., "overlap_or_left" and
> "overlap_or_right", and two operators (e.g., "&&||<<" and "&&||>>" ...
> yes, I'm kidding about the ugly operator names), and modify the operator
> class definition to use the new operators instead of the old.

Those seem like our choices, all right.

It seems to me that the operator rtree actually wants is best thought of
as "is not to right of" (resp. "is not to left of"). The reference to
overlapping is misleading, at least when thinking in 2 or more
dimensions, since a box that is completely above or below the reference
box could still "overlap" in the 1-dimensional sense being used here.
So reasonable operator names would be !>> and !<< respectively.

So, as far as fixing rtree goes, I'm in favor of #2.

Independently of rtree considerations, though, ISTM the existing
operators are broken in the sense that they don't meet the advertised
definition, which is "Overlaps or is left of?". In the first place it's
not obvious that this is meant to be thought of in 1-D terms. A person
thinking in 2-D terms might think "a &< b" is supposed to mean "a && b
OR a << b", which is a tighter constraint than the actual 1-D behavior,
since && considers Y overlap as well as X. And even when thinking in 1-D,
"overlaps" has a different meaning than what the code is doing, anyway.

So it's clear that we should also change either the code or the
documentation for the existing operators. If we are going to add new
operators then I'd favor leaving the existing code alone as a
potentially useful behavior, but fixing the documentation. I can't
think of an equally succinct definition of what the operators really do
though. Comments?

BTW, it occurs to me we should add rtree opclasses associated with
Y-dimension tests (is below, etc) ... or should there be more members of
an rtree opclass than there are now?

regards, tom lane

In response to

Responses

Browse pgsql-general by date

  From Date Subject
Next Message Bob.Henkel 2004-03-31 17:58:38 PL/pgSQL
Previous Message Mooney, Ryan 2004-03-31 17:50:25 Re: Large DB

Browse pgsql-patches by date

  From Date Subject
Next Message Tom Lane 2004-03-31 18:03:40 Re: Question about rtrees (overleft replacing left in nodes)
Previous Message William White 2004-03-31 17:42:52 Re: Question about rtrees (overleft replacing left in nodes)