"Simon Riggs" <[EMAIL PROTECTED]> 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! -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
