Skip site navigation (1) Skip section navigation (2)

Re: incorrect index behaviour with rtree on box values

From: Bruce Momjian <pgman(at)candle(dot)pha(dot)pa(dot)us>
To: andrew(at)supernews(dot)com
Cc: pgsql-bugs(at)postgresql(dot)org
Subject: Re: incorrect index behaviour with rtree on box values
Date: 2005-02-14 23:22:50
Message-ID: 200502142322.j1ENMoR19542@candle.pha.pa.us (view raw or flat)
Thread:
Lists: pgsql-bugs
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(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> > Andrew - Supernews <andrew+nonews(at)supernews(dot)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(at)candle(dot)pha(dot)pa(dot)us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

In response to

pgsql-bugs by date

Next:From: GillesDate: 2005-02-15 02:03:01
Subject: Unicode characters greater than U+10000
Previous:From: Tom LaneDate: 2005-02-14 19:20:28
Subject: Re: Bug in ALTER LANGUAGE ... RENAME TO ...;

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group