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.
range_spgist_quad-0.2.patch.gz
Description: GNU Zip compressed data
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers