Opened 5 years ago

Closed 2 months ago

#4469 closed defect (fixed)

ST_ConcaveHull Runtime

Reported by: tsw Owned by: pramsey
Priority: critical Milestone: PostGIS GEOS
Component: postgis Version: 2.5.x -- EOL
Keywords: Cc:


A concave hull query with the attached data set under Postgresql 9.4 / PostGIS 2.2 / Geos 3.5.0 runs in under a second.

The same query using the same data on Postgresql 9.6 / PostGIS 2.5.2 / GEOS 3.7.1 is still running after 30 minutes.

I've also attached a perf top screen shot to help people identify the possible source of the problem.

Attachments (2) (70.6 KB ) - added by tsw 5 years ago.
Data set used to generate error
Screenshot from 2019-08-02 11-25-34.png (224.5 KB ) - added by tsw 5 years ago.
screenshot of perf top while query is running

Download all attachments as: .zip

Change History (9)

by tsw, 5 years ago

Attachment: added

Data set used to generate error

by tsw, 5 years ago

screenshot of perf top while query is running

comment:1 by robe, 5 years ago

Milestone: PostGIS 2.5.3PostGIS GEOS

I think we ruled this is most likely a GEOS issue related to union changes for geometries possibly this

so flipping to GEOS milestone.

comment:3 by tsw, 5 years ago

Discussions on GEOS Issue 982 suggests that my own testing was incomplete so this may in fact be a PostGIS issue.

dbaston commented: " FWIW, if I run ST_ConcaveHull(geom, 0.99) using GEOS master against

PostGIS trunk, the query takes forever. If I run it using GEOS master against the ST_ConcaveHull implementation from PostGIS 2.3.10 it completes instantly."

Version 0, edited 5 years ago by tsw (next)

comment:4 by tsw, 5 years ago

I've further tested this today and calls to public.ST_UnaryUnion in ST_Concave hull don't make any difference as they are only applied to polygon geometries, and in this case, lines are the problem.

HOWEVER, the ST_UnaryUnion call made at the end of _st_concavehull added in response to issue 3638 is the source of this problem. If this is commented out the query runs instantly. Not sure if there is another way to address 3638, but this change causes the slowdown I document here.

Last edited 5 years ago by tsw (previous) (diff)

comment:5 by komzpa, 5 years ago

Good news, this form of that line returns instantly for me and will allow concave hull to still cover a polygon:

var_resultgeom := public.ST_Union(ST_CollectionExtract(param_inputgeom, 3), var_resultgeom);

Bad news, it's not returning a concave hull - lines are hanging outside of it.

comment:6 by mdavis, 2 months ago

Concave Hull has now been implemented natively in GEOS (version 3.11 and above). This case now works with good performance.

comment:7 by mdavis, 2 months ago

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.