Bitmap Indexes - History and Future - Radoslav Rusinov's Oracle Blog

My experience, findings and thoughts in my daily work with Oracle products

Bitmap Indexes - History and Future

Published Wednesday, September 07, 2005 by Radoslav Rusinov | E-mail this post

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.

Labels: Indexes

4 Responses to “Bitmap Indexes - History and Future”

Pete Scott on 1:19 PM
Radoslav
It's a slight simplification that there is one bitmap per distinct value with Oracle. Oracle creates a bitmap entry for a contiguous range of rowids, Jonathan Lewis wrote about this some while ago in DBAZINE
Pete Scott on 1:23 PM
Opps - published that too quickly!

Continued...
Multiple entries per distinct key may kick in at around 24,000 rows.

Other vendors have implemented bitmap indexes in their products but often they are 'dynamic' indexes created by fast scanning conventional b-tree indexes.
Radoslav Rusinov on 2:07 PM
Hi, Peter
Thank you for this clarification.
For everyone who is interested, the link for the Jonathan's article is: http://www.dbazine.com/oracle/or-articles/jlewis3
It is very detailed as always.
According to other DBMS vendors, as far as I know, DB2 still didn't have permanent bitmap indexes. They are using dynamic bitmap indexes that they build during query processing and uses them during query execution.
It is one of the main differences shown in the competitive analysis between Oracle and DB2 according the performance:
http://www.oracle.com/technology/deploy/performance/withDB2.html
I don't know details about other vendors.
Anonymous on 11:16 AM
Great Blog, check out this business. This is the Goose that lays you Golden Eggs! canadian home based business

Enjoy!

About me

» I'm Radoslav Rusinov
» From Sofia, Bulgaria
» Employer TechnoLogica Ltd.
» I am working as a Database Consultant in Sofia, Bulgaria. My main professional interests are in the database area and especially in the Oracle RDBMS, including database design, development, security and administration.
» The views expressed on this blog are my own and do not necessarily reflect the views of my employing company and its affiliates
» My profile