[postgis-devel] Bug in default B-Tree operator class for geography

[Peter Geoghegan]

I was unable to create an OSGeo account to post to trac, so I thought
I'd post to the list.

There seems to be a bug in the geography type's default B-Tree
opclass. In short, it fails to adhere to the transitive law, which is
described here:

https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/README#L644

The geography B-Tree opclass does this, which is what is at issue:

https://github.com/postgis/postgis/blob/svn-trunk/postgis/geography_btree.c#L260

There needs to be a consistent rule applied with regard to whether or
not an "empty geography" is less than or greater than any other
possible distinct value that a geography could have. The catch-all
nature of that line's enclosing "if ()" test is what is problematic.
It makes *any* comparison involving an empty geography indicate that
the geography datums are equal, including comparisons where *only one*
geography happens to be empty.

I think that the fix is to have "empty geometries" continue to be
equal to themselves only. In all other comparisons, they should behave
as either positive or negative infinity (whichever), in order to have
a sane absolute ordering of values that puts empty geometries in their
own portion of the key space.

A rebuild of all Geography B-Tree indexes should probably be
recommended, once users are on a release with the fix. That would be
the conservative recommendation to make, at least. I've only seen this
problem on 5 databases among a fleet of tens of thousands (not sure
how many of those are actually using PostGIS), so it's probably not
that prevalent. This bug can lead to wrong answers from index scans,
though, and so should be fixed. amcheck [1] is the tool that was used
to find this issue, and could also help those that might need to
REINDEX once the bug is fixed (it could confirm that they're
unaffected).

Thanks

[1] https://github.com/petergeoghegan/amcheck
-- 
Peter Geoghegan