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



Bitmap Indexes - History and Future


E-mail this post



Remember me (?)



All personal information that you provide here will be governed by the Privacy Policy of Blogger.com. More...





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:



4 Responses to “Bitmap Indexes - History and Future”

  1. Blogger Pete Scott 
    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
  2. Blogger Pete Scott 
    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.
  3. Blogger Radoslav Rusinov 
    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.
  4. Anonymous Anonymous 
    Great Blog, check out this business. This is the Goose that lays you Golden Eggs! canadian home based business

    Enjoy!

Leave a Reply

      Convert to boldConvert to italicConvert to link

 



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

RSS 2.0 Feed

Search This Blog with Google

Search This Blog with Free Find


powered by FreeFind

Search This Blog with Technorati

Previous Posts

Archives

Articles & Presentations

Discover Bulgaria

Oracle News & Blogs Aggregators

Oracle Resources

Remote DBA

Oracle User Groups

Oracle Blogs

Oracle Forums

Security Resources

Professional CV

Blog Statistics

              

              

               Page Rank Checker