[postgis-tickets] [PostGIS] #3411: Clustering functions not using spatial index

[PostGIS]

#3411: Clustering functions not using spatial index
---------------------+---------------------------
 Reporter:  dbaston  |      Owner:  pramsey
     Type:  defect   |     Status:  new
 Priority:  high     |  Milestone:  PostGIS 2.2.1
Component:  postgis  |    Version:  2.2.x
 Keywords:           |
---------------------+---------------------------
 I was poking around a bit recently, trying to figure out why the
 clustering functions were showing roughly N^2^ runtime performance.  It
 turns out that these functions are not correctly using the GEOS C API for
 creating an STRtree; where the constructor is requesting a node capacity
 for the tree, the code is instead providing the _entire_ capacity of the
 tree.  This renders the tree useless, hence the N^2^ performance.

 I'll commit a fix to use the default JTS node capacity of 10 here.

 Some examples of the performance effect, on my laptop:

 Clustering a set of 24,000 points, that I was using as a test of the
 window API, goes from 8800ms to 130ms.

 Clustering 1.4 million points, which did not finish before (within the
 limits of my patience) now takes 13.5s.

--
Ticket URL: <https://trac.osgeo.org/postgis/ticket/3411>
PostGIS <http://trac.osgeo.org/postgis/>
The PostGIS Trac is used for bug, enhancement & task tracking, a user and developer wiki, and a view into the subversion code repository of PostGIS project.