Re: Save Hash Indexes

On Friday, November 1, 2013, ktm(at)rice(dot)edu wrote:

> On Fri, Nov 01, 2013 at 01:31:10PM +0000, Dimitri Fontaine wrote:
> > Hi,
> >
> > Here's an idea: when a user ask for an Hash Index transparently build a
> > BTree index over an hash function instead.
> >
> > Advantages:
> >
> > - it works
> > - it's crash safe
> > - it's (much?) faster than a hash index anyways
> >
> > Drawbacks:
> >
> > - root access concurrency
> > - we need a hash_any function stable against pg_upgrade
> >
> > After talking about it with Heikki, we don't seem to find ways in which
> > the root access concurrency pattern would be visible enough to matter.
> >
> > Also, talking with Peter Geoghegan, it's unclear that there's a use case
> > where a hash index would be faster than a btree index over the hash
> > function.
> >
> > Comments?
> > --
> > Dimitri Fontaine
> > http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support
> >
>
> Hi Dimitri,
>
> This use of a function index as a "safe" hash index has been the substitute
> for a while. Check the previous threads. It is not a true substitute
> because
> a hash index is O(1) for lookups but a btree is O(log n) so hash indexes
> have
> an advantage for very large numbers on entries. In fact a recent post
> compared
> both the btree substitute and the current hash index and for large indexes
> the
> hash allowed 2X the lookups than the equivalent btree, which is what you
> would
> expect. The use-case is exactly for very large tables/indexes where the
> index
> does not fit in memory, to say nothing of the data itself.
>
> Regards,
> Ken
>
> Hi,

I agree too.Theoretically, hash tables are constant time lookup while btree
are logarithmic. There may be cases where we may get better performance
with btree, but replacing hash indexes with them completely is not really a
good idea,IMHO.

Is the motivation behind this idea drawn from workloads where btree perform
better, or are you trying to fix issues with hash indexes?

> --
> Sent via pgsql-hackers mailing list (pgsql-hackers(at)postgresql(dot)org<javascript:;>
> )
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>

--
Regards,

Atri
*l'apprenant*