GEOMETRY type is not "hashable"

[vince]

It seems the GEOMETRY type is not hashable, which prevents recursive WITH clauses to work with the UNION keyword:

WITH RECURSIVE path (id, the_geom, z) AS (SELECT id, the_geom, z_min AS z FROM "bâti" WHERE z_min = (SELECT MAX(z_min) FROM "bâti") UNION SELECT "bâti".id, "bâti".the_geom, z FROM path, "bâti" WHERE ST_Distance ("bâti".the_geom, path.the_geom) < 20 AND "bâti".z_min > path.z - 10) SELECT * FROM path;
ERROR:  could not implement recursive UNION
DETAIL:  All column datatypes must be hashable.

Using UNION ALL instead of UNION works, but produces duplicates.

I have no clue on how to make the GEOMETRY type hashable, but if it is just providing a hash function, it might maybe worth it?

[pramsey]

What PgSQL version are you on?

[vince]

9.0.3

psql -V
psql (PostgreSQL) 9.0.3
contains support for command-line editing

Is it tied somehow to PostGreSQL?

[mcayland]

Unfortunately structures containing IEEE-754 floating point numbers cannot be marked HASHABLE because of the "negative zero" problem. There is an explanation of this here: ​http://www.virtualdub.org/blog/pivot/entry.php?id=259.

I suspect that this will have to be marked as a "won't fix"

[vince]

How does PostGreSQL cope with float/double numbers?

[mcayland]

It seems there is an explicit check for zero added into the floating point hash function. However, in the case of PostGIS we'd have to take a copy of the geometry, isolate the floating point numbers within it, fix the zero values, hash it and destroy the copy. That's quite a lot of tricky work to do in order to make this work.

If someone can show that making geometry hashable is a big win then I would consider a patch, but it's going to need a fair bit of work.

[vince]

Of course I can't alone state that. I was attempting to implement some kind of steepest descent algorithm into a single recursive SQL query; was thinking also about identifying areas potentially liable to flooding by growing iteratively around water polygons until a certain z was reached. I guess this is far to be a major use of PostGIS.

There is, of course, a workaround: do not include the geometry column in the result table (the one that grows iteratively), and, at each stage, perform a join between the result table and the table containing geometry info (using a primary key, for example). The query is more complex but, if, as you say, writing a hash function is tricky and maybe also cumbersome, it might even be more efficient to go that way.

Anyhow, thanks a lot for your input and time.

[chodgson]

Wouldn't it be just as valid to hash based on the bounding box? That's down to only 4 zero-checks. Might not be as efficient for special cases handling gridded data or similar (but would still work), but would work fine in the general cases where you have no reason to expect any two random geometries to have the same bounding box.

[strk]

I just hit this issue. Can't we have a special "hash" function outputting a geohash ?

[pramsey]

I hit it too. I ended up working around it by just hashing on the EWKB (bytea) and casting that back and forth. Seems silly to do that (it worked) when we could have a bad geometry hash instead.

[pramsey]

I'm finding it hard to care about the issue mentioned in Mark's article. Basically, if I'm reading it right, it means that our hashing would provide a different value for:

POINT(0 0) and POINT(-0 0)

So if you tried to test equality with the hash function, you'd be told they aren't equal. And if you did a SELECT 'POINT(0 0)' UNION SELECT POINT(-0 0) you'd get back two rows instead of one.

This seems like hardly a deathly issue, and I being too cowboy here? We're already consuming POINT(NaN NaN) for infrastructural purposes, and not allowing convenient CTE recursion (in all cases) because we might accidentally duplicate 0 and -0 cases? Seem like nose cutting and face spiting.

[pramsey]

Oh ha ha, turns out something is already happening…

pramsey=# select 'POINT(0 0)'::geometry UNION SELECT 'POINT(0 0)'::GEometry;
                  geometry                  
--------------------------------------------
 010100000000000000000000000000000000000000
(1 row)

pramsey=# select 'POINT(0 0)'::geometry UNION SELECT 'POINT(-0 0)'::GEometry;
                  geometry                  
--------------------------------------------
 010100000000000000000000000000000000000000
(1 row)

pramsey=# select 'POINT(-0 0)'::geometry UNION SELECT 'POINT(0 0)'::GEometry;
                  geometry                  
--------------------------------------------
 010100000000000000000000800000000000000000
(1 row)

[pramsey]

This is looking harder than ever…

​http://postgresql.nabble.com/Hashable-custom-types-tp5801576p5857261.html

[pramsey]

Just a final note before punting (read the link given above for full details). In order to get a proper hashing behaviour, we need the = operator to be defined in both btree and hash opclasses, with the same symbol and the same semantics. Basically that means going away from bbox equality in the old btree ops. Perhaps moving the btree over to geohash comparisons for < and > (to get a semi-rational ORDER BY) and maybe a topological equality or a vertex-level equality for '='.

[robe]

Milestone renamed

[pramsey]

Now that b-tree uses geometry_cmp on the exact value, we can use it for hashability too.

[pramsey]

In 16058:

Make geometry a hashable type, allowing recursive CTEs
to use geometry in their signatures.
Closes #1014

[pramsey]

In 16059:

Equality test failed on points with same coordinates
and differing SRIDs, resulting in incorrect hashing.
Amazingly, this problem existed in *both* the btree
function and the new hash machinery (and it was the
btree machinery that was actually called for the
UNION operation).
References #1014