Skip site navigation (1) Skip section navigation (2)

Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL

From: Neil Conway <neilc(at)samurai(dot)com>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: "Jim C(dot) Nasby" <decibel(at)decibel(dot)org>,Christopher Petrilli <petrilli(at)gmail(dot)com>,Ying Lu <ying_lu(at)cs(dot)concordia(dot)ca>, pgsql-general(at)postgresql(dot)org,pgsql-performance(at)postgresql(dot)org
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Date: 2005-05-10 04:25:06
Message-ID: 428037A2.4060304@samurai.com (view raw or flat)
Thread:
Lists: pgsql-generalpgsql-performance
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

In response to

Responses

pgsql-performance by date

Next:From: Tom LaneDate: 2005-05-10 04:54:48
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Previous:From: Tom LaneDate: 2005-05-10 04:10:57
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL

pgsql-general by date

Next:From: Jerome MacaranasDate: 2005-05-10 04:35:28
Subject: Re: Need input on postgres used for phpBB
Previous:From: Jerome MacaranasDate: 2005-05-10 04:19:43
Subject: Re: Need input on postgres used for phpBB

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group