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 1D40F533AA;
	Tue, 10 May 2005 23:18:13 -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 14114-02; Wed, 11 May 2005 02:18:04 +0000 (GMT)
Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130])
	by svr1.postgresql.org (Postfix) with ESMTP id 669CA53D7D;
	Tue, 10 May 2005 23:18:03 -0300 (ADT)
Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1])
	by sss.pgh.pa.us (8.13.1/8.13.1) with ESMTP id j4B2HlQc029018;
	Tue, 10 May 2005 22:17:48 -0400 (EDT)
To: Greg Stark <gsstark@mit.edu>
Cc: Neil Conway <neilc@samurai.com>, "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: <87ll6mr5y8.fsf@stark.xeocode.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> <6686.1115700888@sss.pgh.pa.us>
	<878y2nsj7i.fsf@stark.xeocode.com> <9871.1115733198@sss.pgh.pa.us>
	<87wtq7q8zk.fsf@stark.xeocode.com> <25690.1115754605@sss.pgh.pa.us>
	<87ll6mr5y8.fsf@stark.xeocode.com>
Comments: In-reply-to Greg Stark <gsstark@mit.edu>
	message dated "10 May 2005 19:56:15 -0400"
Date: Tue, 10 May 2005 22:17:47 -0400
Message-ID: <29017.1115777867@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, hits=0.007 tagged_above=0 required=5 tests=AWL
X-Spam-Level: 
X-Archive-Number: 200505/534
X-Sequence-Number: 77882

Greg Stark <gsstark@mit.edu> writes:
> Tom Lane <tgl@sss.pgh.pa.us> writes:
>> No, not at all, because searching such an index will require a tree
>> descent, thus negating the one true advantage of hash indexes.  

> The hash index still has to do a tree descent, it just has a larger branching
> factor than the btree index.

There is *no* tree descent in a hash index: you go directly to the
bucket you want.

If the bucket spans more than one page, you pay something, but this
strikes me as being equivalent to the case of multiple equal keys
spanning multiple pages in a btree.  It works, but it's not the design
center.

> btree indexes could have a special case hack to optionally use a large
> branching factor for the root node, effectively turning them into hash
> indexes.

No, because you'd still have to fetch and search the root node.

			regards, tom lane