Re: incorrect index behaviour with rtree on box values

This has been saved for the 8.1 release:

    http://momjian.postgresql.org/cgi-bin/pgpatches2

---------------------------------------------------------------------------

Andrew - Supernews wrote:
> On 2005-01-25, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> > Andrew - Supernews <andrew+nonews@supernews.com> writes:
> >> The problem is that the semantics of the &< and &> operators for the box
> >> type are not what rtree needs for the "OverLeft" and "OverRight" slots of
> >> the operator class.
> >
> > This was observed nearly a year ago, see this thread:
> > http://archives.postgresql.org/pgsql-general/2004-03/msg01135.php
> >
> > but apparently no one cares enough to fix it.  Are you volunteering?
>
> Possibly. I don't feel comfortable with changing anything specific to the
> geometric operators, since (a) I don't actually use them (I discovered
> this issue when adding rtree support to a type of my own) and (b) the
> compatibility implications are obvious. But I think there is a solution
> that involves only changes to the rtree strategy code.
>
> Looking at the earlier discussion: it seems to have ended with the
> conclusion that &< should mean "does not extend to the right of", which
> matches the current implementation for box, but not for some other types.
>
> So for box values, we seem (and someone please correct me if I'm wrong) to
> have the following semantics:
>
> a << b   - a is strictly left of b, i.e. a.right < b.left
> a &< b   - a is no further right than b, i.e. a.right <= b.right
> a &> b   - a is no further left than b, i.e. a.left >= b.left
> a >> b   - a is strictly right of b, i.e. a.left > b.right
>
> For rtree to work as apparently intended, it needs four more operators,
> to use for inner nodes when the scan operator is one of the above four.
> However, a small modification to the way that the internal scan key is
> initialised should eliminate the requirement to explicitly specify these
> operators, which strikes me as the solution which preserves maximum
> compatibility.  The four operators required are:
>
>   NOT (a &> b)      (used when the scan operator is (a << b))
>   NOT (a >> b)      (used when the scan operator is (a &< b))
>   NOT (a << b)      (used when the scan operator is (a &> b))
>   NOT (a &< b)      (used when the scan operator is (a >> b))
>
> (This won't fix rtree on contrib/seg or contrib/cube, but those appear to be
> broken already since they have different, and equally incorrect, definitions
> of &> and &<. Fixing those would require slightly more complex operators,
> such as NOT (a &> b OR a >> b) and so on. The more complex operators would
> work for box too, so it might be worth using them anyway, but I don't yet
> understand the scan key handling well enough to know if these can be
> constructed rather than supplied in the opclass.)
>
> Proof:
>
> Let V be the scan key, i.e. the value we are searching for in the index.
> Let U be a union over a set of values.
> Let X be some value for which X OP V holds.
>
> Consider an internal node entry with union U. We require that the following
> holds: if U contains some value X where X OP V holds, then U OP' V must be
> true. (But not the converse; U OP' V may be true even if no such X exists in
> U. However, we wish it to be false as much as possible for efficiency.)
>
> When OP is << :
>
> X << V, therefore X.right < V.left, therefore X.left < V.left
> therefore NOT (X &> V)
>
> If U contains X, then U &> V is true iff U.left >= V.left
>
> U.left <= min(E.left) for all elements E of U, and therefore for X if X in U
>
> So if X in U, then U.left <= X.left < V.left, and therefore NOT (U &> V)
>
> When OP is &< :
>
> X &< V, therefore X.right <= V.right, therefore X.left <= V.right
> therefore NOT (X >> V), and similar reasoning for U containing X as above.
>
> --
> Andrew, Supernews
> http://www.supernews.com - individual and corporate NNTP services
>
> ---------------------------(end of broadcast)---------------------------
> TIP 7: don't forget to increase your free space map settings
>

--
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073