incorrect index behaviour with rtree on box values

Testcase:

create table boxtest (a box);
create index boxtest_idx on boxtest using rtree (a);

create function gen_data() returns void as '
  begin for i in 1..200 loop
    insert into boxtest
     values (box(point((i*2-1)::float,0),point((i*2)::float,1)));
  end loop;
  return;
end;' language plpgsql;

select gen_data();
analyze boxtest;

set enable_seqscan = true;
select * from boxtest where a << '(3,0),(3,1)'::box;
set enable_seqscan = false;
select * from boxtest where a << '(3,0),(3,1)'::box;

Those two selects at the end should clearly return the same result, a
single row. In fact, what happens is that the second returns no rows at
all; I tested this on 7.4.6, but others have confirmed this on everything
from 7.3 to latest.

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. Specifically, what rtree needs is this:

  if X << K or X &< K
  then for all A where A is a union of values including X,
  then A &< K

(the designation "&<" is of course arbitrary, what matters is what operator
is placed in the applicable slot of the opclass. Same goes for >> and &>.)

This is because rtree converts (see rtstrat.c) the original "Left" operator
to an "OverLeft" when comparing against internal nodes of the index, which
contain values which are the union of all values in their subtree. In the
testcase, the top node of the tree contains as its first entry a union
value of the form (184,1),(1,0), which the scan then rejects since
(184,1),(1,0) &< (3,0),(3,1) is false.

I can see three possible approaches to fixing this:

1) change the semantics of &< and &> to match rtree's expectations

2) replace &< and &> in the opclass with operators that behave as rtree
expects (this will have the side effect of rendering &< and &> un-indexable)

3) change rtree's behaviour in some way.

--
Andrew, Supernews
http://www.supernews.com - individual and corporate NNTP services