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

[Luke Lonergan]

Mark,

On 12/21/05 1:57 PM, "Mark Kirkwood" <markir at paradise.net.nz> wrote:

> Now clearly the confusion here is because I have not really got my head
> around the Bizgres bitmap implementation yet (tho, Jie has provided some
> pointers, and I'm reading the code today). If you have a nice
> description of the algorithm you used, then that would be much appreciated!

The bitmap compression in a nutshell:

There were two versions we came up with - one stores a content value (0 or
1) for a run in the data words, the other stores the content value in the
header word.  I'll describe the one I *think* Jie implemented, which stores
the content value in the data word.

There is a header word that describes the next <word_size> words, where
<word_size> is in bits.  For example, the word size we currently use is 32
bits, so each header word describes the following <32> words of content.  In
the header, each <Nth> bit determines whether the <Nth> data word contains a
literal bitmap of <word_size> bits (0) or if the <Nth> data word contains a
compressed run length description consisting of the first bit (0|1) that
describes the content value and the next <word_size>-1 bits are an integer
that describes how many bits of that value are present.

In the alternate version, the header word contains 2-bit pairs, the first
bit determines literal|compressed and the second bit is the data value.

- Luke