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: (view raw or whole 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    work: 512-231-6117
vcard:       cell: 512-569-9461

In response to


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-2015 The PostgreSQL Global Development Group