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