X-Original-To: pgsql-general-postgresql.org@localhost.postgresql.org
Received: from localhost (unknown [200.46.204.144])
	by svr1.postgresql.org (Postfix) with ESMTP id BC3CB53363;
	Tue, 10 May 2005 01:25:22 -0300 (ADT)
Received: from svr1.postgresql.org ([200.46.204.71])
	by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024)
	with ESMTP id 61618-03; Tue, 10 May 2005 04:25:14 +0000 (GMT)
Received: from mailbox.samurai.com (mailbox.samurai.com [205.207.28.82])
	by svr1.postgresql.org (Postfix) with ESMTP id D4F3D53921;
	Tue, 10 May 2005 01:25:13 -0300 (ADT)
Received: from localhost (mailbox.samurai.com [205.207.28.82])
	by mailbox.samurai.com (Postfix) with ESMTP id 84C3818CD50;
	Tue, 10 May 2005 00:25:13 -0400 (EDT)
Received: from mailbox.samurai.com ([205.207.28.82])
	by localhost (mailbox.samurai.com [205.207.28.82]) (amavisd-new,
	port 10024)
	with LMTP id 09175-01-7; Tue, 10 May 2005 00:25:11 -0400 (EDT)
Received: from [61.88.101.19] (unknown [61.88.101.19])
	(using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))
	(No client certificate requested)
	by mailbox.samurai.com (Postfix) with ESMTP id 3659B18CD45;
	Tue, 10 May 2005 00:25:09 -0400 (EDT)
Message-ID: <428037A2.4060304@samurai.com>
Date: Tue, 10 May 2005 14:25:06 +1000
From: Neil Conway <neilc@samurai.com>
User-Agent: Debian Thunderbird 1.0.2 (X11/20050331)
X-Accept-Language: en-us, en
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>
In-Reply-To: <4407.1115698257@sss.pgh.pa.us>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Virus-Scanned: by amavisd-new at mailbox.samurai.com
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, hits=0.024 tagged_above=0 required=5 tests=AWL
X-Spam-Level: 
X-Archive-Number: 200505/446
X-Sequence-Number: 77794

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. Handling overflow 
pages would be tricky: perhaps we could store the entries in a given 
page in sorted order, but not try to maintain that order for the hash 
bucket as a whole. This would mean we'd need to do a binary search for 
each page of the bucket, but that would still be a win.

-Neil