Обсуждение: 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.
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@gmail.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