<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" style="font-size:12pt;color:#000000;background-color:#FFFFFF;font-family:Calibri,Arial,Helvetica,sans-serif;">
<p style="margin-bottom: 0in">Hi</p>
<p style="margin-bottom: 0in"><br>
</p>
<p style="margin-bottom: 0in">Thanks for testing it. We have used it quite bit and have not seen any scaling problems yet.</p>
<p style="margin-bottom: 0in"><br>
</p>
<p style="margin-bottom: 0in">For a layer with 8 million polygons (about 1 billion points) it takes about one minute to create a content based grid. (Se example further down)</p>
<p style="margin-bottom: 0in"><br>
</p>
<p style="margin-bottom: 0in">We use the && operator to check intersection to avoid loading all data, but what sometimes take time is to compute the extent of the layer. Before I used ST_estimatedExtent (<a href="https://github.com/larsop/content_balanced_grid/commit/66c8267590543951c1b5088ff021cc5b70e0acff" title="https://github.com/larsop/content_balanced_grid/commit/66c8267590543951c1b5088ff021cc5b70e0acff
Cmd+ Klikk eller trykk for å følge koblingen">https://github.com/larsop/content_balanced_grid/commit/66c8267590543951c1b5088ff021cc5b70e0acff</a>)
but that function gives to small extent in some cases. To use the ST_estimatedExtent, we have to use add some more tests to ensure that the extent is big enough, but since we have not seen any need yet its not done either.</p>
<p style="margin-bottom: 0in"><br>
</p>
<p style="margin-bottom: 0in">We usually use this kind of grids to be able to run jobs i parallel with about equal load in each job. To be sure that each polygon is only handled by one job we can use ST_Centroid(or faster first point in exterior ring) and ST_CoveredBy
cell.b<span style="font-size: 12pt;">To be 100% sure you also have to check for ST_Centroid(or first point) on cell borders.</span></p>
<p style="margin-bottom: 0in"><br>
</p>
<p style="margin-bottom: 0in"><br>
</p>
<p align="LEFT" style="margin-bottom: 0in"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt"><font color="#7f0055"><b>SELECT</b></font><font color="#000000">
</font><font color="#000080">count</font><font color="#000000">(q_grid.cell::geometry(geometry,4258))
</font><font color="#7f0055"><b>as</b></font><font color="#000000"> geo </font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt"><font color="#7f0055"><b>FROM</b></font><font color="#000000"> (
</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt"><font color="#7f0055"><b>SELECT</b></font><font color="#000000">(ST_Dump(
</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt"><font color="#000000">cbg_content_based_balanced_grid(ARRAY[</font><font color="#0000ff">'org_ar5.ar5_flate geo'</font><font color="#000000">],4000))</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt"><font color="#000000">).geom
</font><font color="#7f0055"><b>AS</b></font><font color="#000000"> cell) </font>
<font color="#7f0055"><b>AS</b></font><font color="#000000"> q_grid</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">geo
</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#408080"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">------</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">5245</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">(1 row)</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">Time: 62370.532 ms</font></font></font></p>
<p style="margin-bottom: 0in"><br>
</p>
<p align="LEFT" style="margin-bottom: 0in"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt"><font color="#7f0055"><b>SELECT</b></font><font color="#000000">
</font><font color="#000080">count</font><font color="#000000">(*) </font><font color="#7f0055"><b>from</b></font><font color="#000000"> org_ar5.ar5_flate;</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"></font><font face="Monaco, monospace"><font size="2" style="font-size: 11pt"><font color="#000080">count</font><font color="#000000">
</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#408080"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">---------</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">8263246</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">(1 row)</font></font></font></p>
<p style="margin-bottom: 0in"><br>
</p>
<p align="LEFT" style="margin-bottom: 0in"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt"><font color="#7f0055"><b>SELECT</b></font><font color="#000000"> PostGIS_Full_Version();</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">postgis_full_version
</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#408080"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">--------------------------------------------------------------------------------------------------------------------------------------------------------------</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#408080"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">-------------</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">POSTGIS=</font><font color="#008000">"2.2.2 r14797"</font><font color="#000000"> GEOS=</font><font color="#008000">"3.5.0-CAPI-1.9.0
r4084"</font><font color="#000000"> PROJ=</font><font color="#008000">"Rel. 4.8.0, 6 March 2012"</font><font color="#000000"> GDAL=</font><font color="#008000">"GDAL 1.9.2, released 2012/10/08"</font><font color="#000000"> LIBXML=</font><font color="#008000">"2.7.6"</font><font color="#000000">
LIBJSON=</font><font color="#008000">"0.11"</font><font color="#000000"> TOP</font></font></font></p>
<p align="LEFT" style="margin-bottom: 0in"><font color="#000000"><font face="Monaco, monospace"><font size="2" style="font-size: 11pt">OLOGY RASTER</font></font></font></p>
<p style="margin-bottom: 0in"><br>
</p>
<p style="margin-bottom: 0in"><br>
</p>
<p></p>
<p style="margin-bottom: 0in">Lars</p>
<br>
<br>
<div style="color: rgb(0, 0, 0);">
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>Fra:</b> postgis-users <postgis-users-bounces@lists.osgeo.org> på vegne av Jonathan Moules <jonathan-lists@lightpear.com><br>
<b>Sendt:</b> 2. mars 2017 18:41<br>
<b>Til:</b> PostGIS Users Discussion<br>
<b>Emne:</b> Re: [postgis-users] Spatially ordering data</font>
<div> </div>
</div>
<div>
<div style="font-size:10pt; font-family:Verdana,Arial,Helvetica,sans-serif">Thanks for the suggestions. Some thoughts after testing:<br>
<br>
<br>
<b>Darafei</b>: (order by ST_Geohash) Interesting notion, but when implemented the grouping is tenuous at best. If I return 5,000 features they can be spread over 200km (bad) or 6km (good). It'd definitely better clustered than without this, but I was surprised
at how dispersed some of the groups were, and that may be too much for my purposes.<br>
Although I see Paul's answer to this SO question (https://gis.stackexchange.com/questions/188879/clustering-markers-using-quadtree/189296) may help. I've not tested it yet.<br>
<br>
<b>Lars</b>: (content_balanced_grid) The issue here is what happens to features that overlap the grid edges, as I only want to process any given polygon once, and I can't clip them? I'd have to use a ST_Within to only get polygons inside the CBG (which is fine),
but the remaining features would need an ST_Overlaps against the entire grid. I've been running that 30 mins so far on a small sample of my full database, and it's still running, so it definitely won't scale.<br>
<br>
<b>Remi</b>: I was looking for something higher level. Implementing a Quad-Tree in SQL isn't something I'd be comfortable doing. Although if it is simple to do, it may be worth implementing as a feature within PostGIS; I'm sure others would also benefit from
being able to easily spatially sort. I tried googling PostGIS quadtree but didn't find anything so I'm guessing PG doesn't implement this type of index by default.<br>
<br>
Are there any other options? I may consider trying to glue together the two approaches, but that's going to take some thought.<br>
<br>
Thanks,<br>
Jonathan<br>
<div class="zmail_extra">
<div id="1"><br>
---- On Wed, 01 Mar 2017 12:56:58 +0000 <b>Travis Kirstine <traviskirstine@gmail.com></b> wrote ----
<br>
</div>
<blockquote style="border-left:1px solid #0000FF; padding-left:6px; margin:0 0 0 5px">
<div>
<div dir="ltr">
<div>if you go with Remi suggestion you then can cluster the quad tree index to reorder records </div>
<div><br>
</div>
<a href="http://postgis.net/docs/performance_tips.html" target="_blank">http://postgis.net/docs/performance_tips.html</a><br>
<div><br>
</div>
<div><br>
</div>
</div>
<div><br>
<div>On 1 March 2017 at 07:11, Rémi Cura <span><<a href="mailto:remi.cura@gmail.com" target="_blank">remi.cura@gmail.com</a>></span> wrote:<br>
<blockquote style="margin:0 0 0 0.8ex; border-left:1.0px rgb(204,204,204) solid; padding-left:1.0ex">
<div dir="ltr">
<div style="font-family:monospace ,monospace">hey,<br>
</div>
<div style="font-family:monospace ,monospace">the most classical approach would be to construct a
<a href="https://en.wikipedia.org/wiki/Quadtree" target="_blank">quad tree</a>.<br>
</div>
<div style="font-family:monospace ,monospace">You can think of it as a grid that adapts its resolution locally according to the data.<br>
</div>
<div style="font-family:monospace ,monospace">This is also easy to code.<br>
</div>
<div style="font-family:monospace ,monospace"><br>
</div>
<div style="font-family:monospace ,monospace">Cheers,<br>
</div>
<div style="font-family:monospace ,monospace">Rémi-C<br>
</div>
</div>
<div>
<div>
<div><br>
<div>2017-03-01 12:46 GMT+01:00 Darafei "Komяpa" Praliaskouski <span><<a href="mailto:me@komzpa.net" target="_blank">me@komzpa.net</a>></span>:<br>
<blockquote style="margin:0 0 0 0.8ex; border-left:1.0px rgb(204,204,204) solid; padding-left:1.0ex">
<div dir="ltr">Have a look here:<br>
<br>
<a href="http://www.paulnorman.ca/blog/2016/05/improve-your-st-geohash-sorting-with-these-three-simple-tricks/" target="_blank">http://www.paulnorman.ca/blog/2016/05/improve-your-st-geohash-sorting-with-these-three-simple-tricks/</a> <br>
<br>
for simplest case, you can just order by your geom field.</div>
<br>
<div>
<div dir="ltr">ср, 1 мар. 2017 г. в 14:44, Jonathan Moules <<a href="mailto:jonathan-lists@lightpear.com" target="_blank">jonathan-lists@lightpear.com</a>>:<br>
</div>
<blockquote style="margin:0 0 0 0.8ex; border-left:1.0px rgb(204,204,204) solid; padding-left:1.0ex">
<div>
<div><u></u>
<div>
<div style="font-size:10.0pt; font-family:Verdana ,Arial ,Helvetica ,sans-serif">
Hi List,<br>
I've got a database of about 60 million spatial features that I need to run through a process.<br>
<br>
The process can't do all of them at once, so I want to get the data from postgis in spatial chunks of up to say 500,000 features per query.<br>
<br>
The data itself isn't evenly spatially distributed, so gridding won't work either, and I don't see any prospectively useful functions in the reference.<br>
<br>
Non-spatially this would be simple:<br>
<br>
<i>SELECT * FROM my_table ORDER BY some_key ASC LIMIT 500000 OFFSET 0</i><br>
<br>
Does anyone have any suggestions for how to spatially order data with PostGIS?<br>
<br>
Thanks,<br>
Jonathan<br>
</div>
</div>
</div>
</div>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-users" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-users</a></blockquote>
</div>
<br>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-users" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-users</a><br>
</blockquote>
</div>
<br>
</div>
</div>
</div>
<br>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-users" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-users</a><br>
</blockquote>
</div>
<br>
</div>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-users" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-users</a></div>
</blockquote>
<br>
</div>
<br>
</div>
</div>
</div>
</div>
</body>
</html>