Friday, January 19, 2007

Bitmap Indexes


A small introduction:

Bitmap indexes are tailored to data warehouses.
In its simplest form, a bitmap index on an index consists of one vector of bits (i.e., bitmap) per attribute value, where the size of each bitmap is equal to the number of records in the indexed relation. For example, if the attribute is day of the week, then there would be seven bitmap vectors for that attribute, one for each day. The bitmap vector corresponding to Monday would have a 1 at position i if record i contains Monday in the day-of-week attribute. This approach is called a value-list index.

The bitmap index has an interesting history. According to the book: Database Systems -– The Complete Book from Jeffrey Ullman (Professor of Computer Science at Stanford University):

There was a company called Nucleus, founded by Ted Glaser that patented the idea and developed a DBMS in which the bitmap index was both the index structure and the data representation. The company failed in the late 1980'’s, but the idea has recently incorporated into several major commercial database systems.

But according to other sources: Data Warehouse Tuning: What'’s Different About Data Warehouses

These indexes have already been used in some commercial products to speed up query processing: the main early example was Model 204, a prerelational DBMS from Computer Corporation of America.

and VLDB Vision - How the VLDB scene has changed

Bitmap indexes were introduced to the market in the 1970s by Computer Corporation of America (www.cca-int.com) in Model 204, a DBMS for the mainframe. Still around and still delivering astonishingly good performance in predicate evaluation and other areas, Model 204 undoubtedly features the most mature, and probably the best integrated, implementation of bitmap indexes. Of all the database engines on the market, it alone was designed to use bitmap indexes from the beginning.

Computer Corporation of America (CCA) was founded in 1965. More info about the company you can read on its company'’s home page. More info about the “204 model” you can read here:
Model 204: High Performance, High Volume Data Management Solution for Today's Enterprises

The first published work on the bitmap indexes were "“Model 204 architecture and performance”" from Patrick O'’Neil in 1987 year. Unfortunately there is no link for free download of this fundamental paper.

There is a very interesting scientific paper from the same author - Patrick O'’Neil (Professor at the Department of Computer Science, University of Massachusetts at Boston) and Dallan Quass from Stanford University: Improved Query Performance with Variant Indexes

In the above paper you can read the extension of the idea for bitmap indexes. This paper has examined two new index structures: Bit-Sliced indexes and Projection indexes. Indexes like these were used previously in commercial systems, SybaseIQ and MODEL 204, but never examined in print.
It is a matter of time to see will they be implemented in the other commercial databases.

Again from this article I have found the following info about the invention of bitmap indexes:

Bitmap indexes were first developed for database use in the Model 204 product from Computer Corporation of America.

Another interesting finding related to the “bitmap indexes” subject is a patent of Oracle Corporation from 2001 year: Supporting bitmap indexes on primary B+tree like structures (Short Description, Detailed Description).
In the detailed description document you can find another quoted important patents (with links) about indexes.

Source: dba-blog.blogspot.com