[postgis-devel] SPGIST KD-Tree

[Paul Ramsey]

OK, I finally have an actually proof of the concept of using spgist with geometry. This only works with a patched postgresql from Oleg & Teodor that includes a ‘compress’ option for spgist. This feature will only arrive in PostgreSQL at 9.5, so it’s going to be a long wait for real spgist and geometry. My fault for not testing spgist more/sooner when it first arrived.

Since kd-trees make the most sense for points, the index build for this opclass cans out if you try and build against some other object. It would be possible to set up a quad-tree that could handle all object types, using a fifth node on each inner node to hold the ‘boundary crossers’. If the number of boundary crossers was sufficiently high, though, the index efficiency could be affected.

Here’s the postgresql branch

https://github.com/pramsey/postgres/tree/spgistcompress

Here’s the postgis branch (you have to manually load the gserialized_spgist_2d.sql file to get the bindings)

https://github.com/pramsey/postgis/tree/spgist-kdtree

Here’s what it looks like running,

pramsey=# CREATE TABLE somepoints AS 
pramsey-#   SELECT 
pramsey-#     generate_series AS id,
pramsey-#     st_setsrid(st_makepoint(random()*10000, random()*10000),26910) AS geom
pramsey-#   FROM generate_series(1,1000000);
SELECT 1000000

pramsey=# EXPLAIN ANALYZE 
pramsey-#     SELECT * FROM somepoints 
pramsey-#     WHERE 'LINESTRING(5898 7990, 6198 8290)'::geometry && geom;
                                                     QUERY PLAN                                                     
--------------------------------------------------------------------------------------------------------------------
 Seq Scan on somepoints  (cost=0.00..26161.62 rows=253626 width=36) (actual time=0.625..543.586 rows=894 loops=1)
   Filter: ('01020000000200000000000000000AB740000000000036BF40000000000036B840000000000031C040'::geometry && geom)
   Rows Removed by Filter: 999106
 Planning time: 0.107 ms
 Execution time: 543.779 ms
(5 rows)

pramsey=# CREATE INDEX splx ON somepoints using spgist (geom spgist_geometry_kdtree_ops);                                    
CREATE INDEX

pramsey=# EXPLAIN ANALYZE                                                                                                    
    SELECT * FROM somepoints 
    WHERE 'LINESTRING(5898 7990, 6198 8290)'::geometry && geom;
                                                          QUERY PLAN                                                          
------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on somepoints  (cost=6734.28..19544.28 rows=200000 width=36) (actual time=0.870..7.955 rows=894 loops=1)
   Recheck Cond: ('01020000000200000000000000000AB740000000000036BF40000000000036B840000000000031C040'::geometry && geom)
   Heap Blocks: exact=851
   ->  Bitmap Index Scan on splx  (cost=0.00..6684.28 rows=200000 width=0) (actual time=0.571..0.571 rows=894 loops=1)
         Index Cond: ('01020000000200000000000000000AB740000000000036BF40000000000036B840000000000031C040'::geometry && geom)
 Planning time: 0.230 ms
 Execution time: 8.112 ms
(7 rows)



-- 
Paul Ramsey
Senior Strategist / Evangelist | Boundless
pramsey at boundlessgeo.com
250-885-0632
@boundlessgeo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20141201/b1706011/attachment.html>