[Bizgres-general] A bitmap index access method is available in bizgres CVS tip

[Mark Kirkwood]

Sam Vilain wrote:
> On Mon, 2005-12-19 at 21:25 +1300, Mark Kirkwood wrote:
> 
>>10 value bitmap for 10000000 rows requires 10*10000000/8 = 12500000 (~12Mb).
>>
>>This is quite small (whereas the 10 value bitmap indexes are ~150Mb).
>>
>>To actually use the bitmap you need a map between the bitmap "array" 
>>position and blocknumber,itemid (or similar) of the heap relation. I am 
>>guessing that is what your "bm_internal_t*" guys do(?).  Is this where 
>>the extra space is being used? (the on-disk bm_* are very small, so I 
>>guess it is not).
> 
> 
> On Oracle at least, this mapping is only necessary if you are using an
> "index organised table" (I *think* this maps cleanly to the concept of a
> primary unique key in Pg?).
> 

Hmmm - the big O's docs are *very* light on bitmap implementation 
detail, however they do use a mapping construct - see :

http://www.dbazine.com/oracle/or-articles/jlewis3

Each bitmap block stores a ROWID range that the bitmap run is for (this 
being the mapping), the value the index is for, and the bitmap run 
itself (possibly with run compression).


For a reasonably readable vendor neutral discussion of bitmap indexes 
(and other interesting warehouse ideas) see:

http://www.cs.brown.edu/courses/cs227/Papers/Indexing/O'NeilGraefe.pdf


Cheers

Mark