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

[Luke Lonergan]

Sam, Mark,

On 12/19/05 3:41 PM, "Sam Vilain" <sam at vilain.net> wrote:

>> To actually use the bitmap you need a map between the bitmap "array"
>> position and blocknumber,itemid (or similar) of the heap relation. I am
>> guessing that is what your "bm_internal_t*" guys do(?).  Is this where
>> the extra space is being used? (the on-disk bm_* are very small, so I
>> guess it is not).

The bm_internal_t* guys are a btree used to store the values and a reference
to the bitmap vectors that go with them.
 
> On Oracle at least, this mapping is only necessary if you are using an
> "index organised table" (I *think* this maps cleanly to the concept of a
> primary unique key in Pg?).
> 
> Otherwise it's just one bit, one row... and that's before adding the
> compression.

This is exactly what we implemented about 3 weeks ago and it shrank the
actual bitmap index a great deal.  We realized that the TID mapping could be
one-one with the position in the bitmap vectors, and where there were gaps,
they would compress away.

The sizes of the bitmap index is still about 10x larger than Oracle's
though, partially because we are using 32-bit runs for the RLE (actually
HRL) part instead of 8-bit runs, but that's not all of it.

We have done some testing to prove out this implementation for very fast
results compared to Postgres B-Tree (Bizgres) and we got comparable
performance to "another commercial database vendor's" implementation.  In
all cases, this bitmap index implementation was faster on query access and
definitely on build-time.

I¹ve attached a gzipped doc file (was PDF, but it was too large for mailing
list) of Ayush¹s test results.  In there, you see successive versions of the
patch, the December results include the new ³no-TID storage² approach and
show the fast results relative to the prior TID-storage approach.

- Luke



-------------- next part --------------
A non-text attachment was scrubbed...
Name: Index creation performance.doc.gz
Type: application/octet-stream
Size: 13076 bytes
Desc: not available
Url : http://pgfoundry.org/pipermail/bizgres-general/attachments/20051220/9e69b45d/Indexcreationperformance.doc.obj