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
pgsql-hackers by date
|Next:||From: Tom Lane||Date: 2006-07-28 19:29:47|
|Subject: Re: [HACKERS] pg_regress breaks on msys |
|Previous:||From: Tom Lane||Date: 2006-07-28 19:27:08|
|Subject: Re: Hash indexes (was: On-disk bitmap index patch) |