Opened 12 years ago

Closed 11 years ago

#1841 closed enhancement (invalid)

ST_Distance on PostGIS 2.0 is prohibitively slow

Reported by: andrewxhill Owned by: pramsey
Priority: medium Milestone: PostGIS 2.1.0
Component: postgis Version: 2.0.x
Keywords: st_distance, speed Cc:

Description

Running a query to get a pairwise distance calculation for a table takes very long. I'm using this to generate a distance matrix for use in R.

An example query,

select a.a as g1, b.a as g2, st_distance(a.g, b.g) as d from a join a b on a.a<b.a

Can take minutes on the following data,

st_distance - no spheroids 623 polygons with an average of 625 points each (single ring, shell only)

Attachments (2)

fullset.png (6.3 KB ) - added by strk 12 years ago.
detail.png (21.4 KB ) - added by strk 12 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 by strk, 12 years ago

Syntetized dataset: http://strk.keybit.net/tmp/slowdist.zip

avg/max/min points: 416.5136436597110754 | 582 | 10

Takes over 6 minutes to run this:

select sum(d) from ( select a.a as g1, b.a as g2, st_distance(a.g, b.g) as d from a join a b on a.a<b.a ) as foo;

by strk, 12 years ago

Attachment: fullset.png added

by strk, 12 years ago

Attachment: detail.png added

comment:2 by strk, 12 years ago

full extent of the dataset and detailed view:

comment:3 by nicklas, 12 years ago

This is strange. It seems like a case that should benefit from the new algorithm since 1.5.

I will take a look

comment:4 by nicklas, 12 years ago

Hmm, is this really slow?

This is more than 190000 pairwise distance-calculations. If the run-time is 6 minutes, 360000 ms it is about 2 ms per pair. With, in average 625 points in each polygon, I am not sure it is very slow.

If it would have been a brute force algorithm every distance pair would need 390000 vertex-combinations and almost as many edge-vertex combinations to compute.

I do not have any PostGIS 1.4 installed to time brute force version, but I suspect it will be quite a lot slower.

And I did it in 190000 ms, I love ssd :-)

/Nicklas

comment:5 by robe, 11 years ago

Resolution: invalid
Status: newclosed

This ticket is too vague to be useful. Slow has not been quantified. I'm closing this out.

Note: See TracTickets for help on using tickets.