[Bizgres-general] A bitmap index access method is available in bizgres CVS tip

[Luke Lonergan]

Sam, 

> Apparently on Oracle, the value of "low" here is something like 2^20.
> Apparently this is because as the cardinality increases, the 
> compressibility (presumably RLE) of the indexes increases drastically.

Yes, we noticed that.  The ultimate performance of their bitmap
implementation may have less to do with the compressibility than it does
the underlying implementation details.  If you think about it - as the
number of values increases, you have to index into them as well, so you
want a fast access method to the structure that stores values.

We use a Btree to store the values, so you might expect our
implementation to act like a btree in the limit where the cardinality is
the number of values (like a bitmap index on a unique key).  However,
the structure of our implementation may not be that efficient.
 
> Has any work been done to quantify what "low" is ?

Well - this implementation has benefitted from some recent rework that
drastically improved it's performance, coming close to "a popular
commercial database" speeds for cases with the same cardinality on the
order of 2^5, despite the fact that many queries with "popular
commercial databases" can deliver values directly from the index and
Postgres can not do this.

However, we haven't recently done performance testing on cardinality of
2^20, or even functional testing beyond 2^14.  It would be good for
people like yourself to test it's capabilities on cases of interest so
that we can improve it.

- Luke