Skip site navigation (1) Skip section navigation (2)

Re: Implementing Bitmap Indexes

From: "Jim C(dot) Nasby" <decibel(at)decibel(dot)org>
To: "Victor Y(dot) Yegorov" <viy(at)mits(dot)lv>
Cc: pgsql-hackers(at)postgresql(dot)org
Subject: Re: Implementing Bitmap Indexes
Date: 2005-01-30 09:57:29
Message-ID: 20050130095729.GJ64304@decibel.org (view raw or flat)
Thread:
Lists: pgsql-hackers
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?"

In response to

pgsql-hackers by date

Next:From: Nicolai TufarDate: 2005-01-30 10:17:35
Subject: Repleacement for src/port/snprintf.c
Previous:From: Oleg BartunovDate: 2005-01-30 07:23:53
Subject: Re: Huge memory consumption during vacuum (v.8.0)

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group