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

От: Jim C. Nasby
Тема: Re: [GENERAL] "Hash index" vs. "b-tree index" (PostgreSQL
Дата: ,
Msg-id: 20050510172652.GF31103@decibel.org
(см: обсуждение, исходный текст)
Ответ на: Re: [GENERAL] "Hash index" vs. "b-tree index" (PostgreSQL  (Tom Lane)
Ответы: Re: [GENERAL] "Hash index" vs. "b-tree index" (PostgreSQL  (Mischa Sandberg)
Список: 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, )

On Tue, May 10, 2005 at 11:49:50AM -0400, Tom Lane wrote:
> "Jim C. Nasby" <> writes:
> > What's the challange to making it adaptive, comming up with an algorithm
> > that gives you the optimal bucket size (which I would think there's
> > research on...) or allowing the index to accommodate different bucket
> > sizes existing in the index at once? (Presumably you don't want to
> > re-write the entire index every time it looks like a different bucket
> > size would help.)
>
> Exactly.  That's (a) expensive and (b) really hard to fit into the WAL
> paradigm --- I think we could only handle it as a REINDEX.  So if it
> were adaptive at all I think we'd have to support multiple bucket sizes
> existing simultaneously in the index, and I do not see a good way to do
> that.

I'm not really familiar enough with hash indexes to know if this would
work, but if the maximum bucket size was known you could use that to
determine a maximum range of buckets to look at. In some cases, that
range would include only one bucket, otherwise it would be a set of
buckets. If you found a set of buckets, I think you could then just go
to the specific one you need.

If we assume that the maximum bucket size is one page it becomes more
realistic to take an existing large bucket and split it into several
smaller ones. This could be done on an update to the index page, or a
background process could handle it.

In any case, should this go on the TODO list?

> Allowing a bucket size to be specified at CREATE INDEX doesn't seem out
> of line though.  We'd have to think up a scheme for index-AM-specific
> index parameters ...
--
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-performance по дате сообщения:

От: Mischa Sandberg
Дата:
Сообщение: Re: [GENERAL] "Hash index" vs. "b-tree index" (PostgreSQL
От: Greg Stark
Дата:
Сообщение: Re: [GENERAL] "Hash index" vs. "b-tree index" (PostgreSQL