On Sat, Sep 08, 2007 at 05:14:09PM -0400, Mark Mielke wrote:
> 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
>
I agree that we should focus on the O(1) area. The value of storing the
actual value, possibly as an option, is that the key check can be done
in the index without requiring a heap lookup to check the actual value
which would be a benefit for a unique index. I agree that supporting
variable length data would complicate the index and reduce performance.
I am not willing to assume that ~1 entry per hash bucket is necessarily
what we want, at least without some testing. It seems reasonable that
with the performance differences between L1/L2/L3 cache, main memory,
and the disk subsystem a higher load factor would result in better
overall system performance by reducing cache line misses and improving
hardware pre-fetch efficiency. Along with the hypothetical performance
wins, the hash index space efficiency would be improved by a similar
factor. Obviously, all of these ideas would need to be tested in
various workload environments. In the large index arena, 10^6 to 10^9
keys and more, space efficiency will help keep the index manageable
in todays system memories.
Please keep the ideas and comments coming. I am certain that a synthesis
of them will provide an implementation with the performance characteristics
that we are seeking.
Regards,
Ken
> --
> Mark Mielke <mark@mielke.cc>
>