Opened 4 years ago

Closed 4 years ago

#3411 closed defect (fixed)

Clustering functions not using spatial index

Reported by: dbaston Owned by: dbaston
Priority: high Milestone: PostGIS 2.2.1
Component: postgis Version: 2.2.x
Keywords: Cc:

Description

I was poking around a bit recently, trying to figure out why the clustering functions were showing roughly N2 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 N2 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.

Change History (2)

comment:1 Changed 4 years ago by dbaston

Owner: changed from pramsey to dbaston
Status: newassigned

comment:2 Changed 4 years ago by dbaston

Resolution: fixed
Status: assignedclosed

Corrected in trunk at r14530, 2.2 at r14531

Note: See TracTickets for help on using tickets.