Neil Conway <neilc@samurai.com> writes:
> Tom Lane wrote:
>> On the other hand, once you reach the target index page, a hash index
>> has no better method than linear scan through all the page's index
>> entries to find the actually wanted key(s)
> I wonder if it would be possible to store the keys in a hash bucket in
> sorted order, provided that the necessary ordering is defined for the
> index keys -- considering the ubiquity of b+-trees in Postgres, the
> chances of an ordering being defined are pretty good.
I have a gut reaction against that: it makes hash indexes fundamentally
subservient to btrees. We shouldn't bring in concepts that are outside
the basic opclass abstraction.
However: what about storing the things in hashcode order? Ordering uint32s
doesn't seem like any big conceptual problem.
I think that efficient implementation of this would require explicitly
storing the hash code for each index entry, which we don't do now, but
it seems justifiable on multiple grounds --- besides this point, the
search could avoid doing the data-type-specific comparison if the hash
code isn't equal.
There is evidence in the code that indexes used to store more info than
what we now think of as a "standard" index tuple. I am not sure when
that went away or what it'd cost to bring it back, but it seems worth
looking into.
regards, tom lane