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

От: Tom Lane
Тема: Re: [GENERAL] "Hash index" vs. "b-tree index" (PostgreSQL
Дата: ,
Msg-id: 6686.1115700888@sss.pgh.pa.us
(см: обсуждение, исходный текст)
Ответ на: Re: [GENERAL] "Hash index" vs. "b-tree index" (PostgreSQL  (Neil Conway)
Ответы: Re: [GENERAL] "Hash index" vs. "b-tree index" (PostgreSQL  (Neil Conway)
Re: [GENERAL] "Hash index" vs. "b-tree index" (PostgreSQL  (Greg Stark)
Список: pgsql-performance

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

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

Neil Conway <> writes:
> Tom Lane wrote:
>> On the other hand, once you reach the target index page, a hash index
>> has no better method than linear scan through all the page's index
>> entries to find the actually wanted key(s)

> I wonder if it would be possible to store the keys in a hash bucket in
> sorted order, provided that the necessary ordering is defined for the
> index keys -- considering the ubiquity of b+-trees in Postgres, the
> chances of an ordering being defined are pretty good.

I have a gut reaction against that: it makes hash indexes fundamentally
subservient to btrees.  We shouldn't bring in concepts that are outside
the basic opclass abstraction.

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.

There is evidence in the code that indexes used to store more info than
what we now think of as a "standard" index tuple.  I am not sure when
that went away or what it'd cost to bring it back, but it seems worth
looking into.

            regards, tom lane


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

От: Alex Stapleton
Дата:
Сообщение: Partitioning / Clustering
От: Matt Olson
Дата:
Сообщение: Prefetch