I have a gut reaction against that: it makes hash indexes fundamentally subservient to btrees.
I wouldn't say "subservient" -- if there is no ordering defined for the index key, we just do a linear scan.
However: what about storing the things in hashcode order? Ordering uint32s doesn't seem like any big conceptual problem.
Hmm, my memory of the hash code is a bit fuzzy. Do I understand correctly?
- we only use some of the bits in the hash to map from the hash of a key to its bucket
- therefore within a bucket, we can still distinguish most of the non-equal tuples from one another by comparing their full hash values
- if we keep the entries in a bucket (or page, I guess -- per earlier mail) sorted by full hash value, we can use that to perform a binary search
Sounds like a good idea to me. How likely is it that the hash index will be sufficiently large that we're using most of the bits in the hash just to map hash values to buckets, so that the binary search won't be very effective? (At this point many of the distinct keys in each bucket will be full-on hash collisions, although sorting by the key values themselves would still be effective.)
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.
Another benefit is that it would speed up page splits -- there would be no need to rehash all the keys in a bucket when doing the split.
-Neil
---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@xxxxxxxxxxxxxx so that your
message can get through to the mailing list cleanly
