From: | "Dann Corbit" <DCorbit(at)connx(dot)com> |
---|---|
To: | "Alvaro Herrera" <alvherre(at)commandprompt(dot)com>, "Bruno Lavoie" <bruno(dot)lavoie(at)gmail(dot)com> |
Cc: | "PostgreSQL" <pgsql-general(at)postgresql(dot)org> |
Subject: | Re: Indexing columns with low cardinality: persistentbitmap indexes? |
Date: | 2009-01-12 21:47:34 |
Message-ID: | D425483C2C5C9F49B5B7A41F8944154702961F21@postal.corporate.connx.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-general |
> -----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
From | Date | Subject | |
---|---|---|---|
Next Message | Martin Gainty | 2009-01-12 22:44:38 | Re: Indexing columns with low cardinality: persistent bitmap indexes? |
Previous Message | Joshua D. Drake | 2009-01-12 21:39:43 | Re: PgUS 2008 end of year summary |