Re: plans for bitmap indexes?

From: Gavin Sherry <swm(at)linuxworld(dot)com(dot)au>
To: Josh Berkus <josh(at)agliodbs(dot)com>
Cc: pgsql-hackers(at)postgresql(dot)org
Subject: Re: plans for bitmap indexes?
Date: 2004-10-19 23:46:30
Message-ID: Pine.LNX.4.58.0410200938180.9866@linuxworld.com.au
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Tue, 19 Oct 2004, Josh Berkus wrote:

> Tom,
>
> > I've been taking "bitmap" to be a rather handwavy way of saying "a
> > compact representation of sets of CTIDs that is readily amenable to
> > being ANDed and ORed with other sets".
>
> Well, actually I think we're talking about two different features:
>
> 1) a way to use more than one index per operation;
> 2) a more compact and thus faster index representation

For those interested, how this generally works is that for every distinct
value in the column being indexed, a bitmap of unique row identifiers (ie,
tids) is created. With compression, this can greatly reduce the size of
indexes on a large number of rows with a small number of distinct values
(a situation in which we're highly likely to use seq scan index of index
in Postgres).

For qualifications like: bitmapcol1 AND/OR bitmapcol2, we can use bitmap
and/or respectively. Of course, this is all in theory.

Bitmap indexes can suffer concurrency issues, depending on the granularity
of locking.

> You gave the impression that (1) could be implemented with regular BTree
> indexes in an earlier e-mail. Would that be very hard to do?
>
> > The whole thing starts to look like a self-adaptive
> > interpolation between our present indexscan and seqscan techniques,
> > which takes a lot of pressure off the planner to correctly guess the
> > number of matching rows in advance.
>
> This would be way cool.

I think there's a lot of be gained by the technique above as an
alternative to our current access methods. Its just a feeling however, I
haven't prototyped this.

Thanks,

Gavin

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Simon Riggs 2004-10-20 00:03:14 Re: plans for bitmap indexes?
Previous Message Peter Eisentraut 2004-10-19 23:37:08 Re: CSS