Re: Implementing Bitmap Indexes

On Sat, 29 Jan 2005 18:46:44 +0000, Mike Rylander <mrylander(at)gmail(dot)com> wrote:
> As a side note, wouldn't the in-memory bitmaps pretty much kill the
> need for multicolumn indexes? It seems that they would be able to
> join index scans on the same table, and then there would be no need
> for industrial strength cross-column correlation stats. The planner
> would be able to choose a multi index scan based on multiple single
> column stat entries and completely sidestep the need for precalculated
> cross-column correlations. Am I getting that right?

I'm not too sure of that. Lets imagine big table with two columns,
a and b. If we use multicolumn index (a,b), the search must go through
a tree, find a value, and from there find b value.

With in-memory bitmap, the search would start with index a, all
matching rows would form the bitmap; then the second search
would go through b index, forming another bitmap. Which then
would be ANDed with previous bitmap.
If I am correct, in case of in-memory bitmap PostgreSQL would
have to read more index tuples (the less unique values, the
more tuples to read) which in majority of cases would mean
more work than multicolumn index.

However in-memory bitmap would speed up many other
cases (think: OR), but multicolumn indexes are there to stay. :)

Regards,
Dawid