Re: [PATCHES] Bitmapscan changes

Hannu Krosing wrote:
> Ühel kenal päeval, K, 2007-03-14 kell 10:22, kirjutas Heikki
> Linnakangas:
>> Clustered indexes have roughly the same performance effect and use cases 
>> as clustered indexes on MS SQL Server, and Index-Organized-Tables on 
>> Oracle, but the way I've implemented them is significantly different. On 
>> other DBMSs, the index and heap are combined to a single b-tree 
>> structure. The way I've implemented them is less invasive, there's no 
>> changes to the heap for example, and it doesn't require moving live tuples.
> 
> Do you keep visibility info in the index ?

No.

> If there is no visibility data in index, then I can't see, how it gets
> the same performance effect as Index-Organized-Tables, as lot of random
> heap access is still needed.

Let me illustrate the effect in the best case, with a table that 
consists of just the key:

Normal b-tree:

Root -> leaf -> heap

aaa -> aaa -> aaa       bbb -> bbb       ccc -> ccc
ddd -> ddd -> ddd       eee -> eee       fff -> fff
ggg -> ggg -> ggg       hhh -> hhh       iii -> iii

Clustered b-tree:

Root -> heap

aaa -> aaa       bbb       ccc
ddd -> ddd       eee       fff
ggg -> ggg       hhh       iii

The index is much smaller, one level shallower in the best case. A 
smaller index means that more of it fits in cache. If you're doing 
random access through the index, that means that you need to do less I/O 
because you don't need to fetch so many index pages. You need to access 
the heap anyway for the visibility information, as you pointed out, but 
the savings are coming from having to do less index I/O.

How close to the best case do you get in practice? It depends on your 
schema, narrow tables or tables with wide keys gain the most, and on the 
clusteredness of the table.

--   Heikki Linnakangas  EnterpriseDB   http://www.enterprisedb.com