SP-GiST for ranges based on 2d-mapping and quad-tree

Hackers,

attached patch implements quad-tree on ranges. Some performance results in
comparison with current GiST indexing.
Index creation is slightly slower. Probably, it need some investigation.
Search queries on SP-GiST use much more pages. However this comparison can
be not really correct, because SP-GiST can pin same buffer several times
during one scan. In CPU search queries on SP-GiST seems to be slightly
faster. Dramatical difference in "column <@ const" query is thanks to
2d-mapping.

test=# create index period_idx on period_test using gist (period);
CREATE INDEX
Time: 49141,148 ms

test=# create index period_idx2 on period_test2 using spgist (period);
CREATE INDEX
Time: 59503,215 ms

test=# explain (analyze, buffers) select * from period_test where period &&
daterange('2011-12-10', '2011-12-11');
                                                            QUERY PLAN


----------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on period_test  (cost=471.63..13716.45 rows=11866
width=32) (actual time=107.258..147.139 rows=365451 loops=1)
   Recheck Cond: (period && '[2011-12-10,2011-12-11)'::daterange)
   Buffers: shared read=7636
   ->  Bitmap Index Scan on period_idx  (cost=0.00..468.67 rows=11866
width=0) (actual time=106.697..106.697 rows=365451 loops=1)
         Index Cond: (period && '[2011-12-10,2011-12-11)'::daterange)
         Buffers: shared read=3694
 Total runtime: 160.670 ms
(7 rows)

test=# explain (analyze, buffers) select * from period_test2 where period
&& daterange('2011-12-10', '2011-12-11');
                                                           QUERY PLAN


---------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on period_test2  (cost=414.52..13659.34 rows=11866
width=32) (actual time=88.793..129.608 rows=365451 loops=1)
   Recheck Cond: (period && '[2011-12-10,2011-12-11)'::daterange)
   Buffers: shared hit=7623 read=7687
   ->  Bitmap Index Scan on period_idx2  (cost=0.00..411.55 rows=11866
width=0) (actual time=88.285..88.285 rows=365451 loops=1)
         Index Cond: (period && '[2011-12-10,2011-12-11)'::daterange)
         Buffers: shared hit=7623 read=3745
 Total runtime: 142.971 ms
(7 rows)

test=# explain (analyze, buffers) select * from period_test where period <@
daterange('2011-12-10', '2011-12-11');
                                                        QUERY PLAN


---------------------------------------------------------------------------------------------------
-----------------------
 Bitmap Heap Scan on period_test  (cost=102.06..6140.66 rows=2373 width=32)
(actual time=85.437..85.437 rows=0 loops=1)
   Recheck Cond: (period <@ '[2011-12-10,2011-12-11)'::daterange)
   Buffers: shared read=3694
   ->  Bitmap Index Scan on period_idx  (cost=0.00..101.47 rows=2373
width=0) (actual time=85.431..85.431 rows=0 loops=1)
         Index Cond: (period <@ '[2011-12-10,2011-12-11)'::daterange)
         Buffers: shared read=3694
 Total runtime: 85.493 ms
(7 rows)

test=# explain (analyze, buffers) select * from period_test2 where period
<@ daterange('2011-12-10', '2011-12-11');
                                                        QUERY PLAN


--------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on period_test2  (cost=88.95..6127.54 rows=2373 width=32)
(actual time=18.666..18.666 rows=0 loops=1)
   Recheck Cond: (period <@ '[2011-12-10,2011-12-11)'::daterange)
   Buffers: shared hit=1404
   ->  Bitmap Index Scan on period_idx2  (cost=0.00..88.35 rows=2373
width=0) (actual time=18.660..18.660 rows=0 loops=1)
         Index Cond: (period <@ '[2011-12-10,2011-12-11)'::daterange)
         Buffers: shared hit=1404
 Total runtime: 18.717 ms
(7 rows)


test=# explain (analyze, buffers) select * from period_test where period @>
daterange('2011-08-10', '2011-12-31');
                                                          QUERY PLAN


-------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on period_test  (cost=102.06..6140.66 rows=2373 width=32)
(actual time=56.114..73.785 rows=118097 loops=1)
   Recheck Cond: (period @> '[2011-08-10,2011-12-31)'::daterange)
   Buffers: shared read=4125
   ->  Bitmap Index Scan on period_idx  (cost=0.00..101.47 rows=2373
width=0) (actual time=55.740..55.740 rows=118097 loops=1)
         Index Cond: (period @> '[2011-08-10,2011-12-31)'::daterange)
         Buffers: shared read=1391
 Total runtime: 78.469 ms
(7 rows)


test=# explain (analyze, buffers) select * from period_test2 where period
@> daterange('2011-08-10', '2011-12-31');
                                                          QUERY PLAN


-------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on period_test2  (cost=88.95..6127.54 rows=2373 width=32)
(actual time=31.653..49
.751 rows=118097 loops=1)
   Recheck Cond: (period @> '[2011-08-10,2011-12-31)'::daterange)
   Buffers: shared hit=3093 read=3768
   ->  Bitmap Index Scan on period_idx2  (cost=0.00..88.35 rows=2373
width=0) (actual time=31.282..31.282 rows=118097 loops=1)
         Index Cond: (period @> '[2011-08-10,2011-12-31)'::daterange)
         Buffers: shared hit=3093 read=1034
 Total runtime: 54.288 ms
(7 rows)

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