[postgis-users] ST_Distance_Sphere too slow

Fri Mar 25 08:08:14 PDT 2011

Another option if your data is all within a relatively local area is to
project your data into a suitable projection for that data (ST_Transform),
create an index on the projected data and then use ST_DWithin which will
automatically do the &&/ST_Expand behind the scenes.  Planar math is much
quicker than spherical math and so the final check on the distance will be
much faster than using ST_Distance_Spheroid.

On Thu, Mar 24, 2011 at 11:44 PM, Stephen Woodbridge <
woodbri at swoodbridge.com> wrote:

> On 3/24/2011 7:35 PM, Julian Perelli wrote:
>
>> 2011/3/24 Stephen Woodbridge<woodbri at swoodbridge.com>:
>>
>>> On 3/24/2011 6:14 PM, Julian Perelli wrote:
>>>
>>>>
>>>> Thanks!
>>>>
>>>> I don't know if st_expand is faster than st_distance_sphere but with
>>>> EXPLAIN I saw 2 seq scan, and with your approach I see now one seq
>>>> scan, and one index scan, so I suppose your approach is much better,
>>>> and I think that it couldn't be better.
>>>>
>>>> Could you explain me why that happens? why now is a index scan where
>>>> before was a seq scan?
>>>>
>>>
>>> Spatial indexes only work on the bbox of the geometry and the&&  is try
>>> if
>>> the two geometry bboxes interact with one another.
>>>
>>> So if you hav geometry A and B then A&&  B compares their bboxes. But in
>>> your case you want to find any two geometries that might be as far apart
>>> as
>>> 300 meters. If A and B are 300 meters apart then their bboxes will not
>>> interact and you will never be able to select them for computing the
>>> distance. But if we expand the bbox of one of the geometries by 300
>>> meters,
>>> then it will interact with the bbox in question and we will check the
>>> distance. If the distance is greater then 300m we will throw it out
>>> anyway.
>>>
>>
>> Ok, I understand now.&&  works with bboxes, and st_expand doesn't have
>> almost any cost.
>>
>
> Right, st_expand only grows the bbox size, so no cost in doing that.
>
>
>
>>> So&&  is a fast select using indexes and bboxes.
>>> The distance is not performed on all the pairs that are obviously too far
>>> apart, and since this is an expense computation this is good.
>>>
>>> Performance is based more on the false index matches that get rejected by
>>> the more costly distance calculation. If there is not a high percentage
>>> of
>>> these then index searchs are extremely fast.>
>>> -Steve
>>>
>>
>> Unfortunately, I have too many overlapping paths, but you are giving
>> me here an idea:
>>
>> I can first see what paths cross each other, and that (I suppose) Is
>> faster than the distance calculation. Then with the rest of the
>> results I can take the distance. (I don't know if the internals on
>> ST_distance do that already, then my idea is useless :P) I'll try it,
>> post the code and say how it goes.
>>
>
> No this will not work, intersects is more costly than distance. Are you
> paths, straight line segments or linstrings with multiple vertices? Are you
> paths fairly random or mostly parallel at a mostly common angle?
>
> 45 degrees lines have a large bbox, but horizontal and vertical lines have
> small bboxes. If you rotate your geometry so most of the paths are
> horizontal or vertical and save it in a temp table and index it, it would
> then probably run much faster even given building the temp table.
>
> -Steve
>
>
>  Thanks!
>>
>>>
>>>  I made a subset table (only 10 paths!!) to test.
>>>> with your SQL it takes 2,8 sec
>>>> with mine it takes 5,0 sec to complete.
>>>>
>>>> with a subset of 100 paths I let it for an hour and it doesn't finished.
>>>> the problem is that it's almost unacceptable, with 1000 paths it will
>>>> take eternity!
>>>> (I think it takes exponential time as the subset grows up because of
>>>> the self join)
>>>>
>>>> maybe is there another way to do this faster... I dont know...
>>>>
>>>> I want to run this just once, to make a table with this temporary
>>>> results for a larger query in my application, so if it takes 12 hours
>>>> to complete this operation, is ok.
>>>>
>>>> 2011/3/24 Stephen Woodbridge<woodbri at swoodbridge.com>:
>>>>
>>>>>
>>>>> I would make sure there is an gist index on path and use a query like:
>>>>>
>>>>>  select
>>>>>    t1.id,
>>>>>    t2.id
>>>>>  from
>>>>>    table t1
>>>>>      inner join table t2
>>>>>        on (t1.path&&    st_expand(t2.path, 300/111120) and t1.id!=
>>>>> t2.id and
>>>>> ST_Distance_Sphere(t1.path, t2.path)<    300);
>>>>>
>>>>> the 300/111120 is to convert 300 meters into approximately degrees. If
>>>>> you
>>>>> are worried about some near misses you can expand it a little more and
>>>>> distance_sphere will filter extras out of the results.
>>>>>
>>>>> -Steve W
>>>>>
>>>>> On 3/24/2011 3:43 PM, Julian Perelli wrote:
>>>>>
>>>>>>
>>>>>> Hello Postgis List!
>>>>>>
>>>>>> I'm trying to get the pair of paths that crosses each other or are 300
>>>>>> meters or less distant from each other, making this SQL.
>>>>>>
>>>>>>   select
>>>>>>     t1.id,
>>>>>>     t2.id
>>>>>>   from
>>>>>>     table t1
>>>>>>       inner join table t2
>>>>>>         on (t1.id!=t2.id and ST_Distance_Sphere(t1.path, t2.path)<
>>>>>>  300);
>>>>>>
>>>>>> it was 14 hours running and it doesn't finish... I have 1200+ rows in
>>>>>> the table, each path has between 100 and 500 points.
>>>>>>
>>>>>> I tried to make an index on the path column, but when I use explain on
>>>>>> the query, it seems that pg doesn't use the index.
>>>>>>
>>>>>> should I increase the memory assigned to pgsql?
>>>>>>
>>>>>> I don't know where to begin, what to do, to make this query faster.
>>>>>> Maybe I have an error and it just hangs up.
>>>>>> It would be nice to know how to debug the query.. to see it running or
>>>>>> something like that. EXPLAIN helps, but not too much.
>>>>>>
>>>>>> Regards!
>>>>>> _______________________________________________
>>>>>> postgis-users mailing list
>>>>>> postgis-users at postgis.refractions.net
>>>>>> http://postgis.refractions.net/mailman/listinfo/postgis-users
>>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> postgis-users mailing list
>>>>> postgis-users at postgis.refractions.net
>>>>> http://postgis.refractions.net/mailman/listinfo/postgis-users
>>>>>
>>>>>  _______________________________________________
>>>> postgis-users mailing list
>>>> postgis-users at postgis.refractions.net
>>>> http://postgis.refractions.net/mailman/listinfo/postgis-users
>>>>
>>>
>>> _______________________________________________
>>> postgis-users mailing list
>>> postgis-users at postgis.refractions.net
>>> http://postgis.refractions.net/mailman/listinfo/postgis-users
>>>
>>>
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>

-- 
************************************
David William Bitner
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20110325/8550ff33/attachment.html>