Re: [PATCH]-hash index improving

"Simon Riggs" <simon(at)2ndquadrant(dot)com> writes:

> On Thu, 2008-07-17 at 16:37 -0700, Dann Corbit wrote:
>
>> Large table unique index equality search should be very fast with hashed
>> index (and the only place where any advantage will be seen). Hashed
>> indexes are useless for any search besides equality and gain more and
>> more when the levels of the b-tree index increase.
>
> I think a comparison with a btree using a functional index should be
> shown.

To do that you'll have to think about the use cases you think hash should win
on.

For cpu-bound databases with small indexes there might be a win if you can
avoid the binary search of all the elements on a page. (Have we modified btree
to do that or does it still scan sequentially on the leaf pages?)

For i/o-bound databases with very large indexes there should be an opportunity
where btree lookups are O(logn) and hash lookups can in theory be O(1).

However to get O(1) hash lookups need to do extra work at insert time. If they
don't expand the hash as necessary then they end up just being a linear
speedup to whatever lookup algorithm is used to scan the buckets. That isn't
going to win over btree which is already doing a binary search.

The extra work on insert time is O(nlogn) amortized, but I'm not sure
good amortized performance is good enough for Postgres. Users are unhappy when
they're average performance is good but 1/1000 inserts thrashes their i/o
rewriting the whole index...

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's 24x7 Postgres support!