Re: Implementing Bitmap Indexes

Mike Rylander wrote:
> For the initial example where the index is implemented as a set of
> unique keys from the table and a bitmap for each key this would look a
> unique index, but with an extra datum at at each index node to hold
> the bitmap for that key.  If implemented that way an augmented B-Tree
> structure would work fine.  At least that's how I would imagine an
> on-disk bitmap index would work.

It might _work_, I just don't see the point. Given an attribute of a 
heap relation that has N distinct values and T tuples, you need to store

- N bitmaps, each of T bits (before compression)
- T ctids
- a way to map from a bit in one of the bitmaps to a heap tuple
- a way to decide which bitmap(s) to use for a given index scan

I don't see why it's a win to organize this data in a tree. Why not 
store the ctids in a simple array? You then know that bit K of any 
bitmap refers to entry K of the ctid array. You'd also need some meta 
data to figure out which bitmap to use for a given scankey, but it 
should be pretty easy to do that efficiently.

-Neil