Re: Hash index use presently(?) discouraged since 2005: revive or bury it?

On Sun, Sep 18, 2011 at 9:59 AM, Stefan Keller <sfkeller(at)gmail(dot)com> wrote:
> Merlin and Jeff,
>
> General remark again:It's hard for me to imagine that btree is
> superior for all the issues mentioned before. I still believe in hash
> index for primary keys and certain unique constraints where you need
> equality search and don't need ordering or range search.

It is -- but please understand I'm talking about int32 tree vs hash.
Hashing as a technique of course is absolutely going to cream btree
for all kinds of data because of the advantages of working with
decomposed data -- we are all taught that in comp-sci 101 :-). The
debate here is not about the advantages of hashing, but the specific
implementation of the hash index used.

Postgres's hash index implementation used to be pretty horrible -- it
stored the pre-hashed datum in the index which, while making it easier
to do certain things, made it horribly slow, and, for all intents and
purposes, useless. Somewhat recently,a lot of work was put in to fix
that -- the index now packs the hash code only which made it
competitive with btree and superior for larger keys. However, certain
technical limitations like lack of WAL logging and uniqueness hold
hash indexing back from being used like it really should be. In cases
where I really *do* need hash indexing, I do it in userland.

create table foo
(
a_long_field text;
);
create index on foo(hash(a_long_field));

select * from foo where hash(a_long_field) = hash(some_value) and
a_long_field = some_value;

This technique works fine -- the main disadvantage is that enforcing
uniqueness is a PITA but since the standard index doesn't support it
either it's no great loss. I also have the option of getting
'uniqueness' and being able to skip the equality operation if I
sacrifice some performance and choose a strong digest. Until the hash
index issues are worked out, I submit that this remains the go-to
method to do this.

Now, my point here is that I've noticed that even with the latest
optimizations btree seems to still be superior to the hash indexing by
most metrics, so that:
create table foo
(
an_int_field int;
a_long_field text;
);

create index on foo(an_int_field);
create index on foo using hash(a_long_field);

On performance grounds alone, the btree index seems to be (from my
very limited testing) a better bet. So I'm conjecturing that the
current hash implementation should be replaced with a formalization of
the userland technique shown above -- when you request a hash index,
the database will silently hash your field and weave it into a btree.
It's a hybrid: a hashed btree. To truly demonstrate if the technique
was effective though, it would have to be coded up -- it's only fair
to compare if the btree based hash is also double checking the value
in the heap which the standard hash index must do.

The other way to go of course is to try and fix up the existing hash
index code -- add wal logging, etc. In theory, a customized hash
structure should be able to beat btree all day long which argues to
continue in this direction.

@ jeff:
>The way you created the table, I think the rows are basically going to be
in order in the table, which means the btree index accesses are going to
visit the same block over and over again before going to the next block.

This does not explain the behavior. Yeah -- it may take longer but
your computer should not be sitting idle during create index
operations :-). Unfortunately, I was not able to reproduce it on
linux. I have to bite the bullet and get the mingw up if I want to
try and diagnose -- perhaps it is stalling in the semop calls.

merlin