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

Re: Implementing Bitmap Indexes

From: Neil Conway <neilc(at)samurai(dot)com>
To: Mike Rylander <mrylander(at)gmail(dot)com>
Cc: Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Implementing Bitmap Indexes
Date: 2005-01-30 01:15:20
Message-ID: 41FC3528.4090205@samurai.com (view raw or flat)
Thread:
Lists: pgsql-hackers
Mike Rylander wrote:
> For the initial example where the index is implemented as a set of
> unique keys from the table and a bitmap for each key this would look a
> unique index, but with an extra datum at at each index node to hold
> the bitmap for that key.  If implemented that way an augmented B-Tree
> structure would work fine.  At least that's how I would imagine an
> on-disk bitmap index would work.

It might _work_, I just don't see the point. Given an attribute of a 
heap relation that has N distinct values and T tuples, you need to store

- N bitmaps, each of T bits (before compression)
- T ctids
- a way to map from a bit in one of the bitmaps to a heap tuple
- a way to decide which bitmap(s) to use for a given index scan

I don't see why it's a win to organize this data in a tree. Why not 
store the ctids in a simple array? You then know that bit K of any 
bitmap refers to entry K of the ctid array. You'd also need some meta 
data to figure out which bitmap to use for a given scankey, but it 
should be pretty easy to do that efficiently.

-Neil

In response to

Responses

pgsql-hackers by date

Next:From: Mike RylanderDate: 2005-01-30 01:48:32
Subject: Re: Implementing Bitmap Indexes
Previous:From: Mike RylanderDate: 2005-01-30 00:40:11
Subject: Re: Implementing Bitmap Indexes

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