Re: WIP: Fast GiST index build

I've tried index tuples sorting on penalty function before buffer relocation
on split. But it was without any success. Index quality becomes even worse
than without sorting.
The next thing I've tried is buffer relocation between all neighbor buffers.
Results of first tests is much more promising. Number of page accesses
during index scan is similar to those without fast index build. I'm going to
hold on this approach.

test=# create index test_idx on test using gist(v);
NOTICE: Level step = 1, pagesPerBuffer = 406
CREATE INDEX
Time: 10002590,469 ms

test=# select pg_size_pretty(pg_relation_size('test_idx'));
pg_size_pretty
----------------
6939 MB
(1 row)

test=# explain (analyze, buffers) select * from test where v <@
'(0.903,0.203),(0.9,0.2)'::box;
QUERY PLAN

---------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on test (cost=4366.78..258752.22 rows=100000 width=16)
(actual time=1.412..2.295 rows=897 loops=1)
Recheck Cond: (v <@ '(0.903,0.203),(0.9,0.2)'::box)
Buffers: shared hit=1038
-> Bitmap Index Scan on test_idx (cost=0.00..4341.78 rows=100000
width=0) (actual time=1.311..1.311 rows=897 loops=1)
Index Cond: (v <@ '(0.903,0.203),(0.9,0.2)'::box)
Buffers: shared hit=141
Total runtime: 2.375 ms
(7 rows)

test=# explain (analyze, buffers) select * from test where v <@
'(0.503,0.503),(0.5,0.5)'::box;

QUERY PLAN

---------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on test (cost=4366.78..258752.22 rows=100000 width=16)
(actual time=2.113..2.972 rows=855 loops=1)
Recheck Cond: (v <@ '(0.503,0.503),(0.5,0.5)'::box)
Buffers: shared hit=1095
-> Bitmap Index Scan on test_idx (cost=0.00..4341.78 rows=100000
width=0) (actual time=2.016..2.016 rows=855 loops=1)
Index Cond: (v <@ '(0.503,0.503),(0.5,0.5)'::box)
Buffers: shared hit=240
Total runtime: 3.043 ms
(7 rows)

------
With best regards,
Alexander Korotkov.