SP-GiST for ranges based on 2d-mapping and quad-tree - Mailing list pgsql-hackers
| From | Alexander Korotkov |
|---|---|
| Subject | SP-GiST for ranges based on 2d-mapping and quad-tree |
| Date | |
| Msg-id | CAPpHfdtnpASc6vZMTJK7gLY1AO-=RNPW+v-TtW62szFKbBEkaQ@mail.gmail.com Whole thread Raw |
| Responses |
Re: SP-GiST for ranges based on 2d-mapping and quad-tree
Re: SP-GiST for ranges based on 2d-mapping and quad-tree Re: SP-GiST for ranges based on 2d-mapping and quad-tree Re: SP-GiST for ranges based on 2d-mapping and quad-tree |
| List | pgsql-hackers |
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.
Attachment
pgsql-hackers by date: