Re: Implementing Bitmap Indexes

On Sat, Jan 29, 2005 at 01:56:12PM +0200, Victor Y. Yegorov wrote:
> 2) Queries, like "where A = 1" or "where A != 2" will require only 1 scan of
>   the index, while "where A < 3" will require 2 stages: 1st create a 
> list of
>   values lesser then 3, 2nd --- do OR of all bitmaps for that values.
>   For high cardinality attributes, this can take a lot of time;
> 
> 3) Each bitmap is only a bitmap, so there should be an array of 
> corresponding
>   ctids pointers. Maybe, some more arrays (pages, don't know).
> 
> For 2)nd --- there are techniques, allowing better performance for "A < 3"
> queries via increased storage space (see here for details:
> http://delab.csd.auth.gr/papers/ADBIS03mmnm.pdf) and increased reaction time
> for simple queries. I don't know, if they should be implemented, may later.

Sorry if this is in the PDF but I didn't want to read 17 pages to find
out... for the example where 1 >= A >= 4, couldn't you just do NOT (A >=
3)? Granted, in this example it wouldn't matter, but it would be faster
to do this if you asked for A < 4. One downside is that you'd also have
to consider the NULL bitmap, if the field is nullable.
-- 
Jim C. Nasby, Database Consultant               decibel@decibel.org 
Give your computer some brain candy! www.distributed.net Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"