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

От: Mischa Sandberg
Тема: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Дата: ,
Msg-id: 1115760957.4281293e0155b@webmail.telus.net
(см: обсуждение, исходный текст)
Ответ на: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  ("Jim C. Nasby")
Ответы: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Mark Lewis)
Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane)
Список: pgsql-general

Скрыть дерево обсуждения

"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, )

Quoting "Jim C. Nasby" <>:

> 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?

You might want to google on "grace hash" and "hybrid hash".

The PG hash join is the simplest possible: build a hash table in memory,
and match an input stream against it.

*Hybrid hash* is where you spill the hash to disk in a well-designed
way. Instead of thinking of it as building a hash table in memory, think
of it as partitioning one input; if some or all of it fits in memory,
all the better. The boundary condition is the same.

The real wizard of hybrid hash has to be Goetz Graefe, who sadly has now
joined the MS Borg. He demonstrated that for entire-table joins, hybrid
hash completely dominates sort-merge. MSSQL now uses what he developed
as an academic, but I don't know what the patent state is.

"Grace hash" is the original implementation of hybrid hash:
  Kitsuregawa, M., Tanaka, H., and Moto-oka, T. (1984).
  Architecture and Performance of Relational Algebra Machine Grace.




В списке pgsql-general по дате сообщения:

От: Alex Turner
Дата:
Сообщение: Re: Adventures in Quest for GUI RAD
От: Alex Turner
Дата:
Сообщение: Re: Hosting options on Postgres - what's best?