Fix for cube picksplit function

Hackers,

Gist picksplit method implementation in cube contrib module contains a bug
in Guttman's split algorithm implementation. It was mentioned before but it
is still not fixed yet. Current implementation doesn't cause incorrect
behavior, but index becomes very bad, because each index scan require to
read significant part of index.

test=# create table test (a cube);
test=# insert into test (select cube(array[random(),random(),random()]) from
generate_series(1,1000000));
test=# create index test_cube_idx on test using gist(a);

Before this patch, index scan of relatively small area requires read of 1235
index pages.

test=# explain (analyze,buffers) select * from test where a <@
cube(array[0.1,0.1,0.1],array[0.15,0.15,0.15]);
QUERY
PLAN

------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on test (cost=88.77..3046.68 rows=1000 width=56) (actual
time=17.497..18.188 rows=120 loops=1)
Recheck Cond: (a <@ '(0.1, 0.1, 0.1),(0.15, 0.15, 0.15)'::cube)
Buffers: shared hit=1354
-> Bitmap Index Scan on test_cube_idx (cost=0.00..88.52 rows=1000
width=0) (actual time=17.428..17.428 rows=120 loops=1)
Index Cond: (a <@ '(0.1, 0.1, 0.1),(0.15, 0.15, 0.15)'::cube)
Buffers: shared hit=1235
Total runtime: 18.407 ms
(7 rows)

Time: 19,501 ms

After this patch, index scan of same area requires read of only 44 index
pages.

test=# explain (analyze,buffers) select * from test where a <@
cube(array[0.1,0.1,0.1],array[0.15,0.15,0.15]);
QUERY
PLAN

----------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on test (cost=76.66..3034.57 rows=1000 width=56) (actual
time=0.828..1.543 rows=120 loops=1)
Recheck Cond: (a <@ '(0.1, 0.1, 0.1),(0.15, 0.15, 0.15)'::cube)
Buffers: shared hit=163
-> Bitmap Index Scan on test_cube_idx (cost=0.00..76.41 rows=1000
width=0) (actual time=0.767..0.767 rows=120 loops=1)
Index Cond: (a <@ '(0.1, 0.1, 0.1),(0.15, 0.15, 0.15)'::cube)
Buffers: shared hit=44
Total runtime: 1.759 ms
(7 rows)

Seg contrib module and pg_temporal project contain same bug. But there are
another fix for them, because there is no need to use Guttman's split
algorithm at all in unidimensional case.
I'm going to add this patch to commitfest.

----
With best regards,
Alexander Korotkov.

On Fri, Oct 29, 2010 at 2:59 PM, Alexander Korotkov
<aekorotkov(at)gmail(dot)com> wrote:
> Gist picksplit method implementation in cube contrib module contains a bug
> in Guttman's split algorithm implementation. It was mentioned before but it
> is still not fixed yet. Current implementation doesn't cause incorrect
> behavior, but index becomes very bad, because each index scan require to
> read significant part of index.

It looks to me like this can be safely back-patched, because it
doesn't affect the contents of index entries already on disk, just the
manner in which we construct new ones.

So I've committed this and back-patched it all the way back to 8.1.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company