Message-ID: <428046CC.4090601@samurai.com>
Date: Tue, 10 May 2005 15:29:48 +1000
From: Neil Conway <neilc@samurai.com>
User-Agent: Debian Thunderbird 1.0.2 (X11/20050331)
MIME-Version: 1.0
To: Tom Lane <tgl@sss.pgh.pa.us>
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
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> <6686.1115700888@sss.pgh.pa.us>
In-Reply-To: <6686.1115700888@sss.pgh.pa.us>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Tom Lane wrote:
> I have a gut reaction against that: it makes hash indexes fundamentally
> subservient to btrees.

I wouldn't say "subservient" -- if there is no ordering defined for the 
index key, we just do a linear scan.

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

Hmm, my memory of the hash code is a bit fuzzy. Do I understand correctly?

- we only use some of the bits in the hash to map from the hash of a key 
to its bucket

- therefore within a bucket, we can still distinguish most of the 
non-equal tuples from one another by comparing their full hash values

- if we keep the entries in a bucket (or page, I guess -- per earlier 
mail) sorted by full hash value, we can use that to perform a binary search

Sounds like a good idea to me. How likely is it that the hash index will 
be sufficiently large that we're using most of the bits in the hash just 
to map hash values to buckets, so that the binary search won't be very 
effective? (At this point many of the distinct keys in each bucket will 
be full-on hash collisions, although sorting by the key values 
themselves would still be effective.)

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

Another benefit is that it would speed up page splits -- there would be 
no need to rehash all the keys in a bucket when doing the split.

-Neil