<div dir="ltr">Hey,<br><br> - get all the coordinates in the bounding box. may be better to have float, not double bbox - two 32bit floats can be packed into single 64-bit int;<br> - cast them into integer from ieee754 representation - thus you get (sign,exponent,fraction) tuple packed into integer. <br>for the syntax, have a look at pack_float in gist penalty.<br> - treat 2D bbox as 4-dimensional point.<br> - bit-interleave all the (x1, y1, x2, y2) dimensions, say by morton_encode(morton_encode(x1, y1), morton_encode(x2,y2));<br>for reference, <a href="https://github.com/gojuno/hexgrid-pgsql/blob/master/sql/morton.sql">https://github.com/gojuno/hexgrid-pgsql/blob/master/sql/morton.sql</a><br> - if it were 2df box and you managed to pack it into 128bit of data, you lost nothing. if you didn't, lose bits starting from the end.<br><br>PS: also, what will GEOMETRYCOLLECTION(LINESTRING EMPTY, POINT EMPTY) < GEOMETRYCOLLECTION(POINT EMPTY, LINESTRING EMPTY) be?</div><br><div class="gmail_quote"><div dir="ltr">пн, 11 сент. 2017 г. в 21:28, Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca">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 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><div dir="ltr"><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-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="m_-4918356224400990928HOEnZb"><font color="#888888"><div>P</div></font></span></div><div class="m_-4918356224400990928HOEnZb"><div class="m_-4918356224400990928h5"><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_-4918356224400990928m_-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/postgis/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_-4918356224400990928m_-628764799623409025m_-9054311596470569916m_-572449859427607851HOEnZb"><font color="#888888">--<br>
Peter Geoghegan<br>
</font></span></blockquote></div><br></div></div></div><span>
_______________________________________________<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/mailman/listinfo/postgis-devel</a></blockquote></div>
<br>_______________________________________________<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/mailman/listinfo/postgis-devel</a><br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
_______________________________________________<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/mailman/listinfo/postgis-devel</a></blockquote></div>