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

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).

--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.