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(at)decibel(dot)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?"