But I didn't study it. It might be the large geometry had most of it points turned away from the other geometries. That would gain todays code a lot.<br>I will look at it later.<br><br>That is actually probably tje case since the large polygon is probably including a shore line with many points turning away from the geometries not next to the see<br><br>/Nicklas<br><br>Sent from my Sony Xperia™ smartphone<br><br>---- Paul Ramsey wrote ----<br><br>Very interesting. I'm surprised/sad that with the big geometry case<br>the tree doesn't outperform. I was hoping the complexity overhead<br>would be washed out by the size. However, maybe some profiling now<br>would help find other areas of efficiency to makes things better.<br><br>P.<br><br>On Fri, Dec 22, 2017 at 12:11 PM, Nicklas Avén<br><<a href="mailto:nicklas.aven@jordogskog.no">nicklas.aven@jordogskog.no</a>> wrote:<br>> Copy here from irc<br>><br>> I have done some small tests<br>><br>> I get identical results when testing <a href="tel:1000000">1000000</a> distance calculations in<br>> 1:<a href="tel:50000">50000</a> Norwegian areal map<br>><br>><br>> For that geometry in your ticket your code totally outperforms bothe<br>> brute force and the other algorithm<br>><br>> But for more real data as you said it is slower<br>> I get about double time for ST_DistanceRectTree compared to ST_Distance<br>> with average of 64 vertex points in the geometries<br>><br>> I also put a large geometry as first argument and the first 1000<br>> geometries in the Norwegian dataset as second argument. The large<br>> geometry have approx <a href="tel:190000">190000</a> points<br>><br>> Still double time for ST_DistanceRectTree<br>> approx 10 sec for ST_Distance and 19 sec for ST_DistanceRectTree<br>> Then the other geometry has 39 points in average<br>><br>> If there s no low hanging fruits for making it faster, I agree that we<br>> should find the breaking points where it is faster and differentiate in<br>> some way<br>><br>> It will not be possible to do 100 % since the performance of the<br>> current code depends also on the distance between the geometries<br>><br>> Well, maybe an expanded box is worth the effort to find what is close<br>> enough<br>><br>> Something like anything inside a box expanded 5 times and x number of<br>> points goes the tree distance route, and maybe most important all<br>> overlapping bboxes<br>><br>><br>> /Nicklas<br>><br>><br>> On Fri, <a href="tel:2017-12-22">2017-12-22</a> at 06:<a href="tel:43 -0800">43 -0800</a>, Paul Ramsey wrote:<br>>> On Fri, Dec 22, 2017 at 5:46 AM, Nicklas Avén<br>>> <<a href="mailto:nicklas.aven@jordogskog.no">nicklas.aven@jordogskog.no</a>> wrote:<br>>> > Sounds very good.<br>>> ><br>>> > And I think it is worth to sacrify 10 % speed in some occations for<br>>> > the<br>>> > predictability.<br>>> ><br>>> > And caching the tree must be a very good thing.<br>>> ><br>>> > When you say 100x faster, do you then mean in cases like the one in<br>>> > the<br>>> > ticket?<br>>><br>>> No 100x faster for objects of that size (thousands of edges), but<br>>> without the total awfulness. A set of 10 comparisons that take 14s in<br>>> aggregate for current take 140ms for the tree.<br>>><br>>> > If so, it isn't primary the amount of vertes points that is the<br>>> > bottle<br>>> > neck for todays code but other things like distance between the<br>>> > geometries and if there is a lot of vertex points in the part of<br>>> > the<br>>> > border that is hard for the algorithm to filter on (the part facing<br>>> > the<br>>> > other geometry, specially concave cases)<br>>> ><br>>> > But I think it doesn't matter if todays code performs on pair or<br>>> > even<br>>> > better in some cases. Predictability is more important.<br>>><br>>> I'm less sanguine. Lots-of-small-pairings is a more common case than<br>>> a<br>>> few large ones, so we have to not lose performance in that baseline<br>>> case.<br>>><br>>> P<br>>><br>>> ><br>>> > I will give it a test run if the code is ready for that.<br>>> ><br>>> > /Nicklas<br>>> ><br>>> ><br>>> ><br>>> > On Fri, <a href="tel:2017-12-22">2017-12-22</a> at 05:<a href="tel:35 -0800">35 -0800</a>, Paul Ramsey wrote:<br>>> > > So, I now have tree distance code that seems to work, thanks to<br>>> > > this<br>>> > > little bug, which caused me to find the error in my tree code.<br>>> > > I'd<br>>> > > given up on it, figured the tree approach was a dead end.<br>>> > ><br>>> > > <a href="https://github.com/pramsey/postgis/tree/svn-trunk-distance">https://github.com/pramsey/postgis/tree/svn-trunk-distance</a><br>>> > ><br>>> > > In very limited testing, I see it running quite a bit faster<br>>> > > (100x)<br>>> > > than the existing code on large objects, but slightly slower on<br>>> > > small<br>>> > > objects (10%). I was thinking on merging it to trunk but as a<br>>> > > completely independent function for now (ST_DistanceRectTree())<br>>> > > so<br>>> > > that it can be tested and the functional limits of it determined.<br>>> > > Then<br>>> > > we can discuss how we want to integrate it into generic<br>>> > > ST_Distance(),<br>>> > > maybe with a object size test, or maybe as a cached approach<br>>> > > (skipping<br>>> > > the tree built step in cases with repeated inputs would probably<br>>> > > be a<br>>> > > win).<br>>> > ><br>>> > > Thoughts?<br>>> > ><br>>> > > P<br>>> > ><br>>> > ><br>>> > > On Fri, Dec 22, 2017 at 4:15 AM, PostGIS <<a href="mailto:trac@osgeo.org">trac@osgeo.org</a>> wrote:<br>>> > > ><br>>> > > > Comment (by nicklas):<br>>> > > ><br>>> > > >  I agree.<br>>> > > ><br>>> > > >  But worst case is different for different methods.<br>>> > > >  The example Paul provided here is among the worst cases for<br>>> > > > the<br>>> > > > algorithm<br>>> > > >  we use now (when bboxes doesn't overlap, then it falls back to<br>>> > > > brute<br>>> > > >  force)<br>>> > > ><br>>> > > >  If the shoreline of both geometries would have been convex it<br>>> > > > would have<br>>> > > >  been quite a lot faster, but now one is concave and all points<br>>> > > > in<br>>> > > > the<br>>> > > >  concave part needs to be tested more or less.<br>>> > > ><br>>> > > >  So for this case that is a pain for that algorithm it loses<br>>> > > > the<br>>> > > > battle<br>>> > > >  with about 1.08 (79 sec vs 85 sec)<br>>> > > ><br>>> > > >  But for the case with the same geometries further away it wins<br>>> > > > by<br>>> > > > using<br>>> > > >  approx 0.04 of the time brute force method uses. And with the<br>>> > > > case<br>>> > > > when we<br>>> > > >  turn the other side of the geometries against each other it<br>>> > > > wins<br>>> > > > by using<br>>> > > >  approx <a href="tel:0.0005">0.0005</a> of the brute force method.<br>>> > > ><br>>> > > >  So in this case I think the 8 % worse result in some cases is<br>>> > > > ok.<br>>> > > > BUT, the<br>>> > > >  problem is that it is unpredictable. Users will like Paul<br>>> > > > think<br>>> > > > that<br>>> > > >  something is wrong.<br>>> > > ><br>>> > > >  But we have lived with this code now since 2010 and I don't<br>>> > > > think<br>>> > > > there<br>>> > > >  have been many posts on the list about that issue. But I have<br>>> > > > hit<br>>> > > > that<br>>> > > >  wall a few times myself making queries much slower than I<br>>> > > > expect.<br>>> > > > And it<br>>> > > >  can be very frustrating when testing a sample to get an idea<br>>> > > > of<br>>> > > > the query<br>>> > > >  time and then it takes 100 times longer.<br>>> > > ><br>>> > > > --<br>>> > > > Ticket URL: <<a href="https://trac.osgeo.org/postgis/ticket/3949#comment">https://trac.osgeo.org/postgis/ticket/3949#comment</a><br>>> > > > :9><br>>> > > > PostGIS <<a href="http://trac.osgeo.org/postgis/&gt">http://trac.osgeo.org/postgis/&gt</a>;<br>>> > > > The PostGIS Trac is used for bug, enhancement & task tracking,<br>>> > > > a<br>>> > > > user and developer wiki, and a view into the subversion code<br>>> > > > repository of PostGIS project.<br>>> > ><br>>> > > _______________________________________________<br>>> > > postgis-devel mailing list<br>>> > > <a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a><br>>> > > <a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><br>>> ><br>>> > _______________________________________________<br>>> > postgis-devel mailing list<br>>> > <a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a><br>>> > <a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><br>>><br>>> _______________________________________________<br>>> postgis-devel mailing list<br>>> <a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a><br>>> <a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><br>> _______________________________________________<br>> postgis-devel mailing list<br>> <a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a><br>> <a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><br>_______________________________________________<br>postgis-devel mailing list<br><a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a><br><a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a>