Re: Hashable custom types

On Fri, Apr 25, 2014 at 04:47:49PM -0700, Paul Ramsey wrote:
> When trying to write a recursive CTE using the PostGIS geometry type,
> I was told this:
>
> ERROR: could not implement recursive UNION
> DETAIL: All column datatypes must be hashable.

This leads to an interesting question, which is why does our
implementation require this. I'm guessing it's a performance
optimization.

Quoth src/backend/executor/nodeRecursiveunion.c:

/*
* To implement UNION (without ALL), we need a hashtable that stores tuples
* already seen. The hash key is computed from the grouping columns.
*/

As hashing can only approximately guarantee uniqueness (pigeonhole
principle, blah, blah), is there some other similarly performant
mechanism for tracking seen tuples that might work at least in cases
where we don't have a hash function for the data type? Some kind of
tree, perhaps, or does that require too many other things (total
ordering, e.g.)?

Cheers,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david(dot)fetter(at)gmail(dot)com
iCal: webcal://www.tripit.com/feed/ical/people/david74/tripit.ics

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate