Skip site navigation (1)
Skip section navigation (2)
## Re: incorrect index behaviour with rtree on box values

### In response to

### pgsql-bugs by date

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

- Re: incorrect index behaviour with rtree on box values at 2005-01-26 14:54:41 from Andrew - Supernews

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