From: Greg Stark <gsstark@mit.edu>
To: Tom Lane <tgl@sss.pgh.pa.us>
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: 10 May 2005 02:12:17 -0400
Message-ID: <878y2nsj7i.fsf@stark.xeocode.com> (raw)
In-Reply-To: <6686.1115700888@sss.pgh.pa.us>
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>
Tom Lane <tgl@sss.pgh.pa.us> writes:
> However: what about storing the things in hashcode order? Ordering uint32s
> doesn't seem like any big conceptual problem.
>
> I think that efficient implementation of this would require explicitly
> storing the hash code for each index entry, which we don't do now, but
> it seems justifiable on multiple grounds --- besides this point, the
> search could avoid doing the data-type-specific comparison if the hash
> code isn't equal.
It seems that means doubling the size of the hash index. That's a pretty big
i/o to cpu tradeoff.
What if the hash index stored *only* the hash code? That could be useful for
indexing large datatypes that would otherwise create large indexes. A good
hash function should have a pretty low collision rate anyways so the
occasional extra i/o should more than be outweighed by the decrease in i/o
needed to use the index.
--
greg
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: gsstark@mit.edu, tgl@sss.pgh.pa.us, 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: <878y2nsj7i.fsf@stark.xeocode.com>
* 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