<div dir="ltr">Would you believe that ordering by z-order is actually very expensive? Generating a good interleaved key for an arbitrary geometry turns out to be quite expensive<div><br></div><div>- Is it not a point? Generate a point representation. So you're into centroid code.</div><div>- Now you have a point, but it's a collection of double coordinates. To interleave you need integers.</div><div>- OK, just multiply out the doubles so you can capture all the necessary precision in the integer.</div><div>- Oh wait, you don't know what a good scaling factor is. For a geodetic point, it'll be 10,000 or 100,000. For a projected point it might be 10 or 100. How do you know what factor to you? You're doing an SRID lookup probably.</div><div>- OK, finally, you've calculated a centroid, and guessed a good scale factor from the SRID, now you can calculate the interleaved key, and you've got a uint64_t ready to go.</div><div><br></div><div>If you're using the zorder as your sort key, you'll be doing pair-wise tests over and over and over again, so you'll be slamming through this calculation above over and over again. The key really needs to be stored on the serialization, like the bounding box, but now we are wasting storage for things like points...</div><div><br></div><div>All the above is moot if you have a way to generate a zorder key from an arbitrary geometry that works for geometries at all scales. </div><div><br></div><div>(You can skip the expensive centroid code by using a box centroid, that's one. That still leaves figuring out a way to go from double->integer without either stripping useful precision (always multiply by 100) or flattening very disjoint doubles into the same space (just always use the double mantissa). Calculating an interleaved key from two integers is also surprisingly expensive.</div><div><br></div><div>P.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Sep 11, 2017 at 10:19 AM, Paul Ramsey <span dir="ltr"><<a href="mailto:pramsey@cleverelephant.ca" target="_blank">pramsey@cleverelephant.ca</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">You're cruel, cruel, cruel. (And you have a perverse mind to even *conceive* of the sorting-different-kinds-of-<wbr>empty problem)<div>Of course, yes, z-order is v. much something I want to do, but in this run, trying to stay ahead of Regina's release-monster, just avoiding bad index semantics for pgsql is the goal. The non-deterministic nature of different kinds of empty is one I hadn't considered, but I think has to be handled, yay! I'll do that now.</div><span class="HOEnZb"><font color="#888888"><div>P</div></font></span></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Sep 11, 2017 at 7:37 AM, Darafei "Komяpa" Praliaskouski <span dir="ltr"><<a href="mailto:me@komzpa.net" target="_blank">me@komzpa.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">What happens on LINESTRING EMPTY < POINT EMPTY?<br><br>Also, ordering in geohash / z-curve would make many spots where it's used a lot more efficient :)</div><br><div class="gmail_quote"><div dir="ltr">пн, 11 сент. 2017 г. в 17:31, Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca" target="_blank">pramsey@cleverelephant.ca</a>>:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="m_-628764799623409025h5"><div dir="ltr">I took a stab at it in <a href="https://trac.osgeo.org/postgis/ticket/3841" target="_blank">https://trac.osgeo.org/post<wbr>gis/ticket/3841</a><div><br></div><div>Any spelunk into the b-tree side re-raises questions about "what do we mean by equal" and "how should we sort", making we want to tear off the bandages and try again. </div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Sep 10, 2017 at 5:05 PM, Peter Geoghegan <span dir="ltr"><<a href="mailto:pg@bowt.ie" target="_blank">pg@bowt.ie</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Paul,<br>
<span><br>
On Wed, Aug 24, 2016 at 8:25 AM, Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca" target="_blank">pramsey@cleverelephant.ca</a>> wrote:<br>
</span><span>> Thanks for this Peter.<br>
> Fortunately b-tree opclasses on geom/geog are but rarely used and even more<br>
> rarely build into actual indexes, since they don't provide any useful<br>
> spatial searching capability.<br>
<br>
</span>When do you expect to get around to fixing this? With amcheck in<br>
Postgres 10, I would expect more people to notice this.<br>
<br>
Thanks<br>
<span class="m_-628764799623409025m_-9054311596470569916m_-572449859427607851HOEnZb"><font color="#888888">--<br>
Peter Geoghegan<br>
</font></span></blockquote></div><br></div></div></div><span>
______________________________<wbr>_________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br>
</span><a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailma<wbr>n/listinfo/postgis-devel</a></blockquote></div>
<br>______________________________<wbr>_________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailma<wbr>n/listinfo/postgis-devel</a><br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>