Re: B-Heaps

On Fri, 18 Jun 2010, Robert Haas wrote:
> On Tue, Jun 15, 2010 at 8:23 AM, Matthew Wakeling <matthew(at)flymine(dot)org> wrote:
>> Absolutely, and I said in
>> http://archives.postgresql.org/pgsql-performance/2010-03/msg00272.php
>> but applied to the Postgres B-tree indexes instead of heaps.
>
> This is an interesting idea. I would guess that you could simulate
> this to some degree by compiling PG with a larger block size. Have
> you tried this to see whether/how much/for what kind of workloads it
> helps?

To a degree, that is the case. However, if you follow the thread a bit
further back, you will find evidence that when the index is in memory,
increasing the page size actually decreases the performance, because it
uses more CPU.

To make it clear - 8kB is not an optimal page size for either fully cached
data or sparsely cached data. For disc access, large pages are
appropriate, on the order of 256kB. If the page size is much lower than
that, then the time taken to fetch it doesn't actually decrease much, and
we are trying to get the maximum amount of work done per fetch without
slowing fetches down significantly.

Given such a large page size, it would then be appropriate to have a
better data structure inside the page. Currently, our indexes (at least
the GiST ones - I haven't looked at the Btree ones) use a simple linear
array in the index page. Using a proper tree inside the index page would
improve the CPU usage of the index lookups.

One detail that would need to be sorted out is the cache eviction policy.
I don't know if it is best to evict whole 256kB pages, or to evict 8kB
pages. Probably the former, which would involve quite a bit of change to
the shared memory cache. I can see the cache efficiency decreasing as a
result of this, which is the only disadvantage I can see.

This sort of thing has been fairly well researched at an academic level,
but has not been implemented in that many real world situations. I would
encourage its use in Postgres.

Matthew

--
Failure is not an option. It comes bundled with your Microsoft product.
-- Ferenc Mantfeld