To: Neil Conway <neilc@samurai.com>
Cc: "Jim C. Nasby" <decibel@decibel.org>,
	Christopher Petrilli <petrilli@gmail.com>,
	Ying Lu <ying_lu@cs.concordia.ca>, pgsql-general@postgresql.org,
	pgsql-performance@postgresql.org
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL 
In-reply-to: <428037A2.4060304@samurai.com> 
References: <427F6853.90308@cs.concordia.ca> <427F757A.8000407@samurai.com>
	<59d991c405050908271b55e673@mail.gmail.com>
	<427F8321.5030702@samurai.com> <20050509163423.GH35026@decibel.org>
	<427F9211.2090008@samurai.com> <20050509165133.GJ35026@decibel.org>
	<427FFCD3.1010803@samurai.com> <4407.1115698257@sss.pgh.pa.us>
	<428037A2.4060304@samurai.com>
Comments: In-reply-to Neil Conway <neilc@samurai.com>
	message dated "Tue, 10 May 2005 14:25:06 +1000"
Date: Tue, 10 May 2005 00:54:48 -0400
Message-ID: <6686.1115700888@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Neil Conway <neilc@samurai.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