Re: Hash index todo list item

Kenneth Marshall wrote:
> Continuing this train of thought.... While it would make sense for larger
> keys to store the hash in the index, if the key is smaller, particularly
> if it is of fixed size, it would make sense to store the key in the index
> instead. This would have the benefit of allowing use of the hash index
> in non-lossy mode albeit with a slight increase in complexity.
>
I suspect there is no value in designing a hash implementation to work
well for a context where a btree index would already perform equally well.

If there are too few hash buckets, performance is not O(1). For a hash
index to function better than btree, I believe focus should be spent on
the O(1) case, which means ensuring that enough hash buckets are used to
provide O(1).

All of these must match: 1) Hash value, 2) Key value, 3) Tuple visibility.

In the optimum O(1) scenario, each existing key will map to a hash
bucket that contains ~1 entry. For this case, there is no value to
having the key stored in the index row, as 3) Tuple visibility, will
still require access to the table row. In this optimum scenario, I do
not believe anything of value is saved by storing the key in the index
row. The loss, however, is that the hash index data structures become
more complex, and would likely require support for variable length data.
The resulting increase in hash index size and code complexity would
reduce performance.

Just an opinion.

Cheers,
mark

--
Mark Mielke <mark(at)mielke(dot)cc>