> -----Original Message-----
> From: Bruce Momjian [mailto:pgman@candle.pha.pa.us]
> Sent: Friday, June 21, 2002 6:32 AM
> To: Tom Lane
> Cc: Neil Conway; mloftis@wgops.com; Dann Corbit;
> pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] What is wrong with hashed index usage?
> 
> 
> Tom Lane wrote:
> > Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > >       <para>
> > > !      Because of the limited utility of hash indexes, a 
> B-tree index
> > > !      should generally be preferred over a hash index.  
> We do not have
> > > !      sufficient evidence that hash indexes are actually 
> faster than
> > > !      B-trees even for <literal>=</literal> comparisons. 
>  Moreover,
> > > !      hash indexes require coarser locks; see <xref
> > > !      linkend="locking-indexes">.
> > >       </para>
> > >      </note>  
> > >     </para>
> > > --- 181,189 ----
> > >   </synopsis>
> > >      <note>
> > >       <para>
> > > !      Testing has shown that hash indexes are slower 
> than btree indexes,
> > > !      and the size and build time for hash indexes is 
> much worse. For
> > > !      these reasons, hash index use is discouraged.
> > 
> > This change strikes me as a step backwards.  The existing 
> wording tells
> > the truth; the proposed revision removes the facts in favor 
> of a blanket
> > assertion that is demonstrably false.
> 
> OK, which part of is "demonstrably false"?  I think the old "should
> generally be preferred" is too vague.  No one has come up with a case
> where hash has shown to be faster, and a lot of cases where 
> it is slower.

I agree with Tom.  Maybe it is not true for PostgreSQL that hashed
indexes are better, but for every other database if you are doing single
lookups and do not need to order the items sequentially, hashed indexes
are better.  What this indicates to me is that hashed indexes could
{potentially} be much better implemented for PostgreSQL.

See section 2.4:
http://citeseer.nj.nec.com/cache/papers/cs/21214/http:zSzzSzwww.cs.cmu.e
duzSz~christoszSzcourseszSz826-resourceszSzFOILS-LATEXzSzslides.pdf/inde
xing-multimedia-databases.pdf

See
http://ycmi.med.yale.edu/nadkarni/db_course/NonStd_Contents.htm

See also:
http://www-courses.cs.uiuc.edu/~cs411/RR2_goodpoints.html

From the Oracle Rdb documentation:
1.3.5 Retrieval Methods
Oracle Rdb provides several methods for retrieving or accessing data. In
the physical design of your database, consider that Oracle Rdb can use
one or more of the following methods to retrieve the rows in a table: 

Sequential: locating a row or rows in sequence by retrieving data within
a logical area 
Sorted index lookup with value retrieval: using the database key (dbkey)
for the value from the index to retrieve the row 
Sorted index only: using data values in the index key pertinent to your
query 
Hashed index retrieval: for retrieving exact data value matches 
Dbkey only: retrieving a row through its dbkey 
You determine the retrieval method Oracle Rdb chooses by creating one or
more sorted or hashed indexes. 

Sorted index retrieval provides indexed sequential access to rows in a
table. (A sorted index is also called a B-tree index.) By contrast,
hashed index retrieval, also known as hash-addressing, provides direct
retrieval of a specific row. Retrieval of a row is based on a given
value of some set of columns in the row (called the search key). 

Use a hashed index primarily for random, direct retrieval when you can
supply the entire hashed key on which the hashed index is defined, such
as an employee identification number (ID). For this kind of retrieval,
input/output operations can be significantly reduced, particularly for
tables with many rows and large indexes. 

For example, to retrieve a row using a sorted index that is four levels
deep, Oracle Rdb may need to do a total of five input/output operations,
one for each level of the sorted index and one to retrieve the actual
row. By using a hashed index, the number of input/output operations may
be reduced to one or two because hashed index retrieval retrieves the
row directly. 

Fri, 21 Jun 2002 11:06:50 -0700
"Dann Corbit" <DCorbit@connx.com>
Re: What is wrong with hashed index usage?
Dann Corbit wrote:
> > > This change strikes me as a step backwards.  The existing 
> > wording tells
> > > the truth; the proposed revision removes the facts in favor 
> > of a blanket
> > > assertion that is demonstrably false.
> > 
> > OK, which part of is "demonstrably false"?  I think the old "should
> > generally be preferred" is too vague.  No one has come up with a case
> > where hash has shown to be faster, and a lot of cases where 
> > it is slower.
> 
> I agree with Tom.  Maybe it is not true for PostgreSQL that hashed
> indexes are better, but for every other database if you are doing single
> lookups and do not need to order the items sequentially, hashed indexes
> are better.  What this indicates to me is that hashed indexes could
> {potentially} be much better implemented for PostgreSQL.

Yes, our implementation needs help.  People who know other db's are
probably choosing hash thinking it is as good as btree in our code, and
it isn't.  That's why I wanted the documentation update, and why I am
suggesting the elog(NOTICE).

I have updated the documentation to specifically mention that
PostgreSQL's hashes are slower/similar to btree.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Index: doc/src/sgml/diskusage.sgml
===================================================================
RCS file: /cvsroot/pgsql/doc/src/sgml/diskusage.sgml,v
retrieving revision 1.1
diff -c -r1.1 diskusage.sgml
*** doc/src/sgml/diskusage.sgml	13 Jun 2002 05:15:22 -0000	1.1
--- doc/src/sgml/diskusage.sgml	21 Jun 2002 19:06:03 -0000
***************
*** 22,31 ****
    </para>
  
    <para>
!    You can monitor disk space from two places; from inside
!    <application>psql</> and from the command line using
!    <application>contrib/oid2name</>. Using <application>psql</> you can
!    issue queries to see the disk usage for any table:
  <programlisting>
  play=# SELECT relfilenode, relpages
  play-# FROM pg_class
--- 22,33 ----
    </para>
  
    <para>
!    You can monitor disk space from three places: from
!    <application>psql</> using <command>VACUUM</> information, from
!    <application>psql</> using <application>contrib/dbsize</>, and from
!    the command line using <application>contrib/oid2name</>. Using
!    <application>psql</> on a recently vacuumed (or analyzed) database,
!    you can issue queries to see the disk usage of any table:
  <programlisting>
  play=# SELECT relfilenode, relpages
  play-# FROM pg_class
***************
*** 38,47 ****
    </para>
  
    <para>   
!    Each page is typically 8 kilobytes. <literal>relpages</> is only
!    updated by <command>VACUUM</> and <command>ANALYZE</>. To show the
!    space used by <acronym>TOAST</> tables, use a query based on the heap
!    relfilenode:
  <programlisting>
  play=# SELECT relname, relpages
  play-# FROM pg_class
--- 40,49 ----
    </para>
  
    <para>   
!    Each page is typically 8 kilobytes. (Remember, <literal>relpages</>
!    is only updated by <command>VACUUM</> and <command>ANALYZE</>.) To
!    show the space used by <acronym>TOAST</> tables, use a query based on
!    the heap relfilenode shown above:
  <programlisting>
  play=# SELECT relname, relpages
  play-# FROM pg_class
Index: doc/src/sgml/indices.sgml
===================================================================
RCS file: /cvsroot/pgsql/doc/src/sgml/indices.sgml,v
retrieving revision 1.33
diff -c -r1.33 indices.sgml
*** doc/src/sgml/indices.sgml	21 Jun 2002 16:52:00 -0000	1.33
--- doc/src/sgml/indices.sgml	21 Jun 2002 19:06:04 -0000
***************
*** 181,190 ****
  </synopsis>
     <note>
      <para>
!      Testing has shown hash indexes to be similar or slower than btree
!      indexes, and the index size and build time for hash indexes is much
!      worse. Hash indexes also suffer poor performance under high
!      concurrency. For these reasons, hash index use is discouraged.
      </para>
     </note>  
    </para>
--- 181,191 ----
  </synopsis>
     <note>
      <para>
!      Testing has shown PostgreSQL's hash indexes to be similar or slower
!      than btree indexes, and the index size and build time for hash
!      indexes is much worse. Hash indexes also suffer poor performance
!      under high concurrency. For these reasons, hash index use is
!      discouraged.
      </para>
     </note>  
    </para>
Index: doc/src/sgml/ref/create_index.sgml
===================================================================
RCS file: /cvsroot/pgsql/doc/src/sgml/ref/create_index.sgml,v
retrieving revision 1.33
diff -c -r1.33 create_index.sgml
*** doc/src/sgml/ref/create_index.sgml	21 Jun 2002 16:52:00 -0000	1.33
--- doc/src/sgml/ref/create_index.sgml	21 Jun 2002 19:06:05 -0000
***************
*** 330,339 ****
      the <literal>=</literal> operator.
     </para>
     <para>
!      Testing has shown hash indexes to be similar or slower than btree
!      indexes, and the index size and build time for hash indexes is much
!      worse. Hash indexes also suffer poor performance under high
!      concurrency. For these reasons, hash index use is discouraged.
     </para>
  
     <para>
--- 330,340 ----
      the <literal>=</literal> operator.
     </para>
     <para>
!      Testing has shown PostgreSQL's hash indexes to be similar or slower
!      than btree indexes, and the index size and build time for hash
!      indexes is much worse. Hash indexes also suffer poor performance
!      under high concurrency. For these reasons, hash index use is
!      discouraged.
     </para>
  
     <para>
Fri, 21 Jun 2002 15:06:22 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: What is wrong with hashed index usage?