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)

                                                        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;