[postgis-devel] SPGIST KD-Tree

[Sandro Santilli]

On Mon, Dec 01, 2014 at 10:41:46AM -0800, Paul Ramsey wrote:

> 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)

Do you have that table still around to also test a run against the GiST
index ? Would be interesting to compare performance.

--strk;

 ()  ASCII ribbon campaign  --  Keep it simple !
 /\  http://strk.keybit.net/rants/ascii_mails.txt