Re: B-Heaps

On Fri, 18 Jun 2010, Robert Haas wrote:
> On Tue, Jun 15, 2010 at 8:23 AM, Matthew Wakeling  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