On Thu, Jul 05, 2007 at 12:26:45PM +0100, Heikki Linnakangas wrote:
> Kenneth Marshall wrote:
> >I definitely agree with Tom's assessment. If we cannot need to make the
> >hash index as performant as it is in theory, none of the other refinements
> >are worth it. You would need to use BTree if you were concerned about
> >speed. (and who isn't)
>
> I just got an idea.
>
> Hash indexes would take much less space, and be more efficient to
> search, if we only stored the hash of the key in the index. Such index
> tuples would be fixed size, so we could get rid of the overhead of the
> length-field in IndexTuple, as well as the line pointers.
>
> Of course, the key value would need to be rechecked after fetching the
> heap tuple, but that shouldn't be a problem assuming there's few collisions.
>
> Another idea: when searching, we scan the whole bucket page looking for
> matching tuples. If we stored the tuples ordered by hash value within
> page, we could do a binary search instead.
>
> These changes might give hash indexam the edge over b-tree it needs.
>
> --
> Heikki Linnakangas
> EnterpriseDB http://www.enterprisedb.com
>
I was thinking about your idea on my commute yesterday and the new
HOT functionality. The first step would be as you suggested, store
only the hash value and the heap bucket page in the index. The check
for collisions within a hash bucket is essentially the same thing
that we do when searching for the heap tuple visible for a specific
transaction. This would mean, that with a HOT type process, the index
would not need to be updated when a non-indexed field is changed. We
treat them as another tuple in the HOT chain.
This would make typical lookups require 2 disk reads per item, the
first to get the heap location and the second to get the heap page
itself. The next step would be to have the hash function generate
the heap location directly instead of a disk read, then retrieving
an item would be one read. This would also provide for a simple
clustering based on the hash index. I am certain that there are
holes in this ideal, but it would be a logical next step.
Regards,
Ken
