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

Re: Implementing Bitmap Indexes

From: Mike Rylander <mrylander(at)gmail(dot)com>
To: Neil Conway <neilc(at)samurai(dot)com>
Cc: Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Implementing Bitmap Indexes
Date: 2005-01-30 00:40:11
Message-ID: b918cf3d05012916407f4ec3ae@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
On Sun, 30 Jan 2005 11:07:59 +1100, Neil Conway <neilc(at)samurai(dot)com> wrote:
> Mike Rylander wrote:
> > For on-disk bitmap indexes, yes.  I don't see any reason this couldn't
> > be done with GiST
> 
> It might be possible to do it with GiST, but GiST is designed for
> implementing tree-structured indexes; I don't think it's the right tool
> for the job.

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.  I suppose that would make the index
much more efficient for high-cardinality values, no?

-- 
Mike Rylander
mrylander(at)gmail(dot)com
GPLS -- PINES Development
Database Developer
http://open-ils.org

In response to

Responses

pgsql-hackers by date

Next:From: Neil ConwayDate: 2005-01-30 01:15:20
Subject: Re: Implementing Bitmap Indexes
Previous:From: Neil ConwayDate: 2005-01-30 00:07:59
Subject: Re: Implementing Bitmap Indexes

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