An efficient bitmap encoding scheme for selection queries

ABSTRACT

Bitmap indexes are useful in processing complex queries in decision support systems, and they have been implemented in several commercial database systems. A key design parameter for bitmap indexes is the encoding scheme, which determines the bits that are set to 1 in each bitmap in an index. While the relative performance of the two existing bitmap encoding schemes for simple selection queries of the form “v1 ≤ A ≤ v2” is known (specifically, one of the encoding schemes is better for processing equality queries; i.e., v1 = v2, while the other is better for processing range queries; i.e., v1 < v2), it remains an open question whether these two encoding schemes are indeed optimal for their respective query classes in the sense that there is no other encoding scheme with better space-time tradeoff. In this paper, we establish a number of optimality results for the existing encoding schemes; in particular, we prove that neither of the two known schemes is optimal for the class of two-sided range queries. We also propose a new encoding scheme and prove that it is optimal for that class. Finally, we present an experimental study comparing the performance of the new encoding scheme with that of the existing ones as well as four hybrid encoding schemes for both simple selection queries and the more general class of membership queries of the form “A ∈ {v1, v2, .…, vk}”. These results demonstrate that the new encoding scheme has an overall better space-time performance than existing schemes.

REFERENCES

• Ant93: G. Antoshenkov. Byte Aligned Data Compression. U.S. :Patent No: 142640, October 1993.
• CI98a: C.Y. China and Y.E. Ioannidis. An Efficient Bitmap Encoding Scheme for Selection Querlies. Computer Sciences Department, University of Wisconsin-Madison, 1998. http://www.cs.wisc.edu/~cychan/interval.ps.
• CI98b: 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
• Ede95: H. Edelstein. Faster Data Warehouses. Information We,~k, pages 77-88, December 1995.
• Inf: informix Inc. informix Decision Support Indexing for the Enterprise Data Warehouse. http://www.informix.com/informix/corpinfo/_ zines/whiteidx.htm.
• Jak97: H. Jakobs,~on. Bitmap Indexing in Oracle Data Warehousing.Database seminar at Stanford University. http://wwwdb.stanford.edu/dbseminar/Archive/Fal197/_ slides/oracle/, October 1997.
• OG95: Patrick O'Neil , Goetz Graefe, Multi-table joins through bitmapped join indices, ACM SIGMOD Record, v.24 n.3, p.8-11, Sept. 1995 [doi>10.1145/211990.212001]
• O'N87: Patrick E. O'Neil, Model 204 Architecture and Performance, Proceedings of the 2nd International Workshop on High Performance Transaction Systems, p.40-59, September 28-30, 1987
• O'N97: P. O'Neil. Informix Indexing Support for Data Warehouses. Database Programming and Design, 10(2):38-43, February 1997.
• OQ97: Patrick O'Neil , Dallan Quass, Improved query performance with variant indexes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.38-49, May 11-15, 1997, Tucson, Arizona, United States
• Syb97: Sybase Inc. Sybase IQ Indexes. In Sybase IQ Administration Guide, Sybase IQ Release 11.2 Collection, chapter 5. Sybase Inc., March 1997. http://sybooks.sybase.com/cgi-bin/nphdynaweb/siql1201/iq_admin/1.toc.
• WB98: Ming-Chuan Wu , Alejandro P. Buchmann, Encoded Bitmap Indexing for Data Warehouses, Proceedings of the Fourteenth International Conference on Data Engineering, p.220-230, February 23-27, 1998
• Win99: R. Winter. Indexing Goes a New Direction. Intelligent Enterprise, 2(2):70-73, January 199!).
• WLO+85: H.K.T. Wong, H-F. Liu, F. Olken, D. Rotem, and L. Wong. Bit Transposed Files. In Proceedings of the Intl. Conference on Very Large Data Bases, pages 448-457, Stockholm, 1985.
• WLO+86: H.K.T. Wong, J.Z. Li, F. Olken, D. Rotem, and L. Wong. Bit Transposition for Very Large Scientific and Statistical Databases. Algorithmica, 1(3):289-309, 1986.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

General Terms:
Design, Management, Measurement, Performance, Reliability, Theory