Re: bitmap indexes - performance

On Thu, Jul 1, 2010 at 9:23 AM, Leonardo F <m_lists(at)yahoo(dot)it> wrote:
> Using as a starting point the old bitmap patch in:
>
> http://archives.postgresql.org/message-id/20081101000154.GO27872@fune
>
>
> I re-applied and re-worked the patch to see what kind of improvements over
> btrees bitmaps actually provided.
>
> Using a 20M rows table of 10/100/1000 random values, I've found that:
>
> 1) bulk index creation time is roughly 6 times better
> 2) index size is 6-15 times smaller (depending on column cardinality)
> 3) there's almost no difference in query times (but I have to make more
> tests)
> 4) I can't say anything about the insertion performance, but I guess
> bitmap will perform way worse than btree
>
> Are these improvements (index creation time, index size) worth enough
> to keep on working on this?
>
> I mean: given that bitmaps don't give any benefits in query times, but
> only benefits related to disk size and bulk index creation times, and
> will have horrible performance for insertions/deletions: would this job be
> worthed?
>
> In case it is: I will try to clean up the patch and post it...
>
>
> As a side note: I guess that most of the bitmap indexes performance
> improvements in the SELECT area are already implemented in postgres
> in the bitmapand/or and bitmap scan stuff? I couldn't find any docs that
> say that bitmap indexes are faster for selects, unless of course they
> are ANDed/ORed together (which is something postgres already does
> for regular btree indexes)

Hmm... no performance improvement? That's not encouraging.

The index being smaller ought to by itself provide some performance
improvement if, say, the smaller index can fit in cache and the larger
one can't. With a 6-15x size difference, that's presumably not an
implausible scenario. But I guess the real point is to be able to AND
and OR bitmap indices on multiple columns. Not sure if this
implementation supports that or not (I haven't read the patch) and how
the performance compares to doing Bitmap Heap Scan -> BitmapAnd ->
Bitmap Index Scan with btree indices.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company