<div dir="ltr">Thanks for this Peter.<div>Fortunately b-tree opclasses on geom/geog are but rarely used and even more rarely build into actual indexes, since they don't provide any useful spatial searching capability. They are there so that people can use 'group by' and 'order by'. So, I don't think that fixing them to be deterministically ordered should cause any especially bad user-facing effects (by the same token, the fact that they are broken probably hasn't bitten anyone, particularly since they are broken on empties, which also show up rarely in practice).</div><div>Unless anyone has serious concerns, I'll take this on. It's a behaviour change, but one that probably nobody will notice in practice.</div><div>ATB,</div><div>P</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Aug 23, 2016 at 6:43 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">I was unable to create an OSGeo account to post to trac, so I thought<br>
I'd post to the list.<br>
<br>
There seems to be a bug in the geography type's default B-Tree<br>
opclass. In short, it fails to adhere to the transitive law, which is<br>
described here:<br>
<br>
<a href="https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/README#L644" rel="noreferrer" target="_blank">https://github.com/postgres/<wbr>postgres/blob/master/src/<wbr>backend/access/nbtree/README#<wbr>L644</a><br>
<br>
The geography B-Tree opclass does this, which is what is at issue:<br>
<br>
<a href="https://github.com/postgis/postgis/blob/svn-trunk/postgis/geography_btree.c#L260" rel="noreferrer" target="_blank">https://github.com/postgis/<wbr>postgis/blob/svn-trunk/<wbr>postgis/geography_btree.c#L260</a><br>
<br>
There needs to be a consistent rule applied with regard to whether or<br>
not an "empty geography" is less than or greater than any other<br>
possible distinct value that a geography could have. The catch-all<br>
nature of that line's enclosing "if ()" test is what is problematic.<br>
It makes *any* comparison involving an empty geography indicate that<br>
the geography datums are equal, including comparisons where *only one*<br>
geography happens to be empty.<br>
<br>
I think that the fix is to have "empty geometries" continue to be<br>
equal to themselves only. In all other comparisons, they should behave<br>
as either positive or negative infinity (whichever), in order to have<br>
a sane absolute ordering of values that puts empty geometries in their<br>
own portion of the key space.<br>
<br>
A rebuild of all Geography B-Tree indexes should probably be<br>
recommended, once users are on a release with the fix. That would be<br>
the conservative recommendation to make, at least. I've only seen this<br>
problem on 5 databases among a fleet of tens of thousands (not sure<br>
how many of those are actually using PostGIS), so it's probably not<br>
that prevalent. This bug can lead to wrong answers from index scans,<br>
though, and so should be fixed. amcheck [1] is the tool that was used<br>
to find this issue, and could also help those that might need to<br>
REINDEX once the bug is fixed (it could confirm that they're<br>
unaffected).<br>
<br>
Thanks<br>
<br>
[1] <a href="https://github.com/petergeoghegan/amcheck" rel="noreferrer" target="_blank">https://github.com/<wbr>petergeoghegan/amcheck</a><br>
<span class="HOEnZb"><font color="#888888">--<br>
Peter Geoghegan<br>
______________________________<wbr>_________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/postgis-devel" rel="noreferrer" target="_blank">http://lists.osgeo.org/<wbr>mailman/listinfo/postgis-devel</a></font></span></blockquote></div><br></div>