Skip site navigation (1) Skip section navigation (2)

Re: Hash indexes (was: On-disk bitmap index patch)

From: "Jim C(dot) Nasby" <jnasby(at)pervasive(dot)com>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, Hannu Krosing <hannu(at)skype(dot)net>,Luke Lonergan <LLonergan(at)greenplum(dot)com>, mark(at)mark(dot)mielke(dot)cc,Bruce Momjian <bruce(at)momjian(dot)us>, Jie Zhang <jzhang(at)greenplum(dot)com>,Gavin Sherry <swm(at)linuxworld(dot)com(dot)au>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: Hash indexes (was: On-disk bitmap index patch)
Date: 2006-07-28 19:27:46
Message-ID: 20060728192746.GU66525@pervasive.com (view raw or flat)
Thread:
Lists: pgsql-hackers
On Fri, Jul 28, 2006 at 03:14:33PM -0400, Alvaro Herrera wrote:
> Jim C. Nasby wrote:
> 
> > What I'm getting at is that I've never seen any explanation for the
> > theoretical use cases where a hash index would outperform a btree. If we
> > knew what kind of problems hash indexes were supposed to solve, we could
> > try and interest people who are solving those kinds of problems in
> > fixing hash indexes.
> 
> The btree index needs to descend potentially many pages before getting
> to the leaf page, where the actual index is stored.  The hash index can
> get at the "leaf" node in --supposedly-- one fetch.  Btree is O(logN) to
> get a single key, while hash is O(1).  Our problem lies in the
> constants; for btree they are smaller than for hash, so in practice
> that O(logN) is always smaller than O(1).
> 
> I've heard other database systems manage to have hash indexes that are
> actually faster than btree, so either (1) our btree absolutely rocks, or
> (2) their hash implementations are better (probably both).

In that case, perhaps this is something Greenplum might be interested
in, since it might fit nicely between bitmap and btree indexes.
-- 
Jim C. Nasby, Sr. Engineering Consultant      jnasby(at)pervasive(dot)com
Pervasive Software      http://pervasive.com    work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf       cell: 512-569-9461

In response to

Responses

pgsql-hackers by date

Next:From: Tom LaneDate: 2006-07-28 19:29:47
Subject: Re: [HACKERS] pg_regress breaks on msys
Previous:From: Tom LaneDate: 2006-07-28 19:27:08
Subject: Re: Hash indexes (was: On-disk bitmap index patch)

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group