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

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