Re: Indexing columns with low cardinality: persistentbitmap indexes?

> -----Original Message-----
> From: pgsql-general-owner(at)postgresql(dot)org [mailto:pgsql-general-
> owner(at)postgresql(dot)org] On Behalf Of Alvaro Herrera
> Sent: Monday, January 12, 2009 12:41 PM
> To: Bruno Lavoie
> Cc: PostgreSQL
> Subject: Re: [GENERAL] Indexing columns with low cardinality:
> persistentbitmap indexes?
>
> Bruno Lavoie escribió:
> > Hello,
> >
> > I have a column with a small number of distinct values, indexing this
> > one with a standard BTree is useless. How do I can index this column
> > efficiently? I searched and it seems that pg doesn't support the
> > creation of persistent bitmap indexes...
>
> It doesn't.
>
> > Is that feature planned in next releases of pg?
>
> There are some efforts to get it done, but don't hold your breath (it
> won't be in 8.4 either, as it has major problems currently.)

Here is an interesting experiment:

Application of Bitmap Index to Information Retrieval. K. Fujioka, Y. Uematsu, and M. Onizuka. WWW 2008
Source: [ACM]
Synopsis: This paper proposes a hierarchical structure called HS-bitmap index to represent document-term matrix. The authors implemented their data structure on PostgreSQL and observed it to perform better than an inverted index. A short-coming might be that HS-bitmap index takes more space than the inverted index even after compression.
Note this work makes use of PostgreSQL but is unrelated to the on-going work of implementing bitmap index in PostgreSQL.

http://portal.acm.org/citation.cfm?doid=1367497.1367680

Here is the research page where I found the above:
http://www-users.cs.umn.edu/~kewu/annotated.html