Secondary bitmap indexes with vertical and horizontal partitioning

ABSTRACT

Traditional bitmap indexes are utilized as a special type of primary or clustered indexes where the queries are answered by performing fast logical operations supported by hardware. Answers are mapped to the physical data by using the row id of each tuple. Bitmaps represent the i-th tuple in the original table with the i-th bit position of the index. Run-length compression is used to reduce the size of the bitmaps and it has been shown that ordered data is significantly better compressed. However, for large-scale and dynamic datasets it is infeasible to keep the data always sorted. Partitioning can be used to keep the data in smaller and manageable chunks, where a different bitmap index is built for each chunk. We propose a novel bitmap index design with partitioning which serves as basis for non-clustered bitmap indexes. Individual bitmaps are not stored, only an Existence Bitmap (EB) for the existing ranks of the full table is maintained. This approach improves update performance of sorted bitmaps and does not require maintaining a heap as the underlying table, nor the same ordering for all the partitions. A one dimensional index is used over the ranks to map the bits in the EB to the physical order of the data, which allows queries to run even faster. The proposed approach, called ranked Non-Clustered Bitmaps (rNCB), is compared against traditional bitmaps using FastBit and shows significant performance gains.

REFERENCES

• 1: http://mlearn.ics.uci.edu/MLRepository.html.
• 2: Sihem Amer-Yahia , Theodore Johnson, Optimizing Queries on Compressed Bitmaps, Proceedings of the 26th International Conference on Very Large Data Bases, p.329-338, September 10-14, 2000
• 3: G. Antoshenkov, Byte-aligned bitmap compression, Proceedings of the Conference on Data Compression, p.476, March 28-30, 1995
• 4: Gennady Antoshenkov , Mohamed Ziauddin, Query processing and optimization in Oracle Rdb, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.229-237, December 1996 [doi>10.1007/s007780050026]
• 5: R. Bayer and E. M. McCreight. Organization and maintenance of large ordered indices. Acta Inf., 1:173--189, 1972.
• 6: Chee-Yong Chan , Yannis E. Ioannidis, Bitmap index design and evaluation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.355-366, June 01-04, 1998, Seattle, Washington, United States
• 7: Chee-Yong Chan , Yannis E. Ioannidis, An efficient bitmap encoding scheme for selection queries, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.215-226, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 8: H. Edelstein. Faster data warehouses. Information Week, December 1995.
• 9: I. Inc. Informix decision support indexing for the enterprise data warehouse. http://www.informix.com/informix/corpinfo/-zines/whiteidx.htm.
• 10: S. Inc. Sybase IQ Indexes, chapter 5: Sybase IQ Release 11.2 Collection. Sybase Inc., March 1997.
• 11: David Johnson , Shankar Krishnan , Jatin Chhugani , Subodh Kumar , Suresh Venkatasubramanian, Compressing large boolean matrices using reordering techniques, Proceedings of the Thirtieth international conference on Very large data bases, p.13-23, August 31-September 03, 2004, Toronto, Canada
• 12: Theodore Johnson, Performance Measurements of Compressed Bitmap Indices, Proceedings of the 25th International Conference on Very Large Data Bases, p.278-289, September 07-10, 1999
• 13: Theodore Johnson, Performance Measurements of Compressed Bitmap Indices, Proceedings of the 25th International Conference on Very Large Data Bases, p.278-289, September 07-10, 1999
• 14: Nick Koudas, Space efficient bitmap indexing, Proceedings of the ninth international conference on Information and knowledge management, p.194-201, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354819]
• 15: Elizabeth O'Neil , Patrick O'Neil , Kesheng Wu, Bitmap Index Design Choices and Their Performance Implications, Proceedings of the 11th International Database Engineering and Applications Symposium, p.72-84, September 06-08, 2007 [doi>10.1109/IDEAS.2007.19]
• 16: P. O'Neil. Informix and indexing support for data warehouses, 1997.
• 17: Ali Pinar , Tao Tao , Hakan Ferhatosmanoglu, Compressing Bitmap Indices by Data Reorganization, Proceedings of the 21st International Conference on Data Engineering, p.310-321, April 05-08, 2005 [doi>10.1109/ICDE.2005.35]
• 18: David Salomon, Data Compression, SpringerVerlag, 2004
• 19: Mike Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Sam Madden , Elizabeth O'Neil , Pat O'Neil , Alex Rasin , Nga Tran , Stan Zdonik, C-store: a column-oriented DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 20: K. Wu. Fastbit: an efficient indexing technology for accelerating data-intensive science. J. Phys.: Conf. Ser., 16:556--560, 2005.
• 21: Kesheng Wu , Ekow J. Otoo , Arie Shoshani, A performance comparison of bitmap indexes, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502689]
• 22: Kesheng Wu , Ekow J. Otoo , Arie Shoshani, Compressing Bitmap Indexes for Faster Search Operations, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.99-108, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029710]