Re: plans for bitmap indexes?

On T, 2004-10-26 at 18:42, Greg Stark wrote:
> Hannu Krosing <hannu@tm.ee> writes:
> 
> > I repeat here my earlier proposal of making the bitmap indexes
> > page-level and clustering data automatically on AND of all defined
> > bitmap indexes. 
> 
> The problem with page-level bitmaps is that they could be much less effective.
> Consider a query like 'WHERE foo = ? AND bar = ? AND baz = ?" where each of
> those matches about 1% of your tuples. If you have 100 tuples per page then
> each of those bitmaps will find a tuple in about half the pages. So the
> resulting AND will find about 1/8th of the pages as candidates. In reality the
> number of pages it should have to fetch should be more like 1 in a million.
> 
> The other problem is that for persist on-disk indexes they require more work
> to update. You would have to recheck every other tuple in the page to
> recalculate the bit value instead of just being able to flip one bit.

Read again ;)

the per-page clustering would make sure that all the tuples would be on
1 (or on a few) pages.

and what comes to updating the index, you have to do it only once per
100 pages ;)

----------------
Hannu