pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Tom Lane <tgl@sss.pgh.pa.us>
To: Greg Stark <gsstark@mit.edu>
Cc: Neil Conway <neilc@samurai.com>
Cc: Jim C. Nasby <decibel@decibel.org>
Cc: Christopher Petrilli <petrilli@gmail.com>
Cc: Ying Lu <ying_lu@cs.concordia.ca>
Cc: pgsql-general@postgresql.org
Cc: pgsql-performance@postgresql.org
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Date: Tue, 10 May 2005 22:17:47 -0400
Message-ID: <29017.1115777867@sss.pgh.pa.us> (raw)
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>

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



view thread (36+ messages)  latest in thread

Message-ID: <29017.1115777867@sss.pgh.pa.us>
Permalink:  ../29017.1115777867@sss.pgh.pa.us/
Also on:    postgresql.org/message-id/29017.1115777867@sss.pgh.pa.us

 · 

reply
Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-performance@postgresql.org
  Cc: tgl@sss.pgh.pa.us, gsstark@mit.edu, neilc@samurai.com, decibel@decibel.org, petrilli@gmail.com, ying_lu@cs.concordia.ca, pgsql-general@postgresql.org
  Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
  In-Reply-To: <29017.1115777867@sss.pgh.pa.us>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox