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

From: Jim C. Nasby
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Date: ,
Msg-id: 20050510153245.GA31103@decibel.org
(view: Whole thread, Raw)
In response to: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Neil Conway)
Responses: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane)
Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Mischa Sandberg)
List: pgsql-general

Tree view

"Hash index" vs. "b-tree index" (PostgreSQL 8.0)  (Ying Lu, )
 Re: "Hash index" vs. "b-tree index" (PostgreSQL 8.0)  (Neil Conway, )
  Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL 8.0)  (Christopher Petrilli, )
   Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Neil Conway, )
    Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  ("Jim C. Nasby", )
     Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Neil Conway, )
      Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  ("Jim C. Nasby", )
       Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Neil Conway, )
        Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane, )
         Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Neil Conway, )
          Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane, )
           Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Neil Conway, )
           Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Greg Stark, )
            Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane, )
             Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Greg Stark, )
              Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane, )
               Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Greg Stark, )
                Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane, )
         Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  ("Jim C. Nasby", )
          Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane, )
           Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  ("Jim C. Nasby", )
        Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  ("Jim C. Nasby", )
         Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane, )
         Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Mischa Sandberg, )
          Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Mark Lewis, )
           Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Mischa Sandberg, )
            Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Bruce Momjian, )
             Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Mischa Sandberg, )
              Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Bruce Momjian, )
               Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Mischa Sandberg, )
             Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Neil Conway, )
              Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Bruce Momjian, )
          Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane, )
           Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Mischa Sandberg, )
       Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Bruce Momjian, )
 Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane, )
  Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Neil Conway, )
 Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Greg Stark, )

On Tue, May 10, 2005 at 10:14:11AM +1000, Neil Conway wrote:
> Jim C. Nasby wrote:
> >> No, hash joins and hash indexes are unrelated.
> >I know they are now, but does that have to be the case?
>
> I mean, the algorithms are fundamentally unrelated. They share a bit of
> code such as the hash functions themselves, but they are really solving
> two different problems (disk based indexing with (hopefully) good
> concurrency and WAL logging vs. in-memory joins via hashing with spill
> to disk if needed).

Well, in a hash-join right now you normally end up feeding at least one
side of the join with a seqscan. Wouldn't it speed things up
considerably if you could look up hashes in the hash index instead? That
way you can eliminate going to the heap for any hashes that match. Of
course, if limited tuple visibility info was added to hash indexes
(similar to what I think is currently happening to B-tree's), many of
the heap scans could be eliminated as well. A similar method could also
be used for hash aggregates, assuming they use the same hash.
--
Jim C. Nasby, Database Consultant               
Give your computer some brain candy! www.distributed.net Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"


pgsql-general by date:

From: Christopher Murtagh
Date:
Subject: Re: Trigger that spawns forked process
From: Mischa Sandberg
Date:
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL