Skip site navigation (1) Skip section navigation (2)

Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Neil Conway <neilc(at)samurai(dot)com>
Cc: "Jim C(dot) Nasby" <decibel(at)decibel(dot)org>,Christopher Petrilli <petrilli(at)gmail(dot)com>,Ying Lu <ying_lu(at)cs(dot)concordia(dot)ca>, pgsql-general(at)postgresql(dot)org,pgsql-performance(at)postgresql(dot)org
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Date: 2005-05-10 04:54:48
Message-ID: 6686.1115700888@sss.pgh.pa.us (view raw or flat)
Thread:
Lists: pgsql-generalpgsql-performance
Neil Conway <neilc(at)samurai(dot)com> writes:
> Tom Lane wrote:
>> On the other hand, once you reach the target index page, a hash index
>> has no better method than linear scan through all the page's index
>> entries to find the actually wanted key(s)

> I wonder if it would be possible to store the keys in a hash bucket in 
> sorted order, provided that the necessary ordering is defined for the 
> index keys -- considering the ubiquity of b+-trees in Postgres, the 
> chances of an ordering being defined are pretty good.

I have a gut reaction against that: it makes hash indexes fundamentally
subservient to btrees.  We shouldn't bring in concepts that are outside
the basic opclass abstraction.

However: what about storing the things in hashcode order?  Ordering uint32s
doesn't seem like any big conceptual problem.

I think that efficient implementation of this would require explicitly
storing the hash code for each index entry, which we don't do now, but
it seems justifiable on multiple grounds --- besides this point, the
search could avoid doing the data-type-specific comparison if the hash
code isn't equal.

There is evidence in the code that indexes used to store more info than
what we now think of as a "standard" index tuple.  I am not sure when
that went away or what it'd cost to bring it back, but it seems worth
looking into.

			regards, tom lane

In response to

Responses

pgsql-performance by date

Next:From: Neil ConwayDate: 2005-05-10 05:29:48
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Previous:From: Neil ConwayDate: 2005-05-10 04:25:06
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL

pgsql-general by date

Next:From: Neil ConwayDate: 2005-05-10 05:29:48
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Previous:From: Jerome MacaranasDate: 2005-05-10 04:35:28
Subject: Re: Need input on postgres used for phpBB

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group