Strategies for processing ad hoc queries on large data warehouses

ABSTRACT

As data warehousing applications grow in size, existing data organizations and access strategies, such as relational tables and B-tree indexes, are becoming increasingly ineffective. The two primary reasons for this are that these datasets involve many attributes and the queries on the data usually involve conditions on small subsets of the attributes. Two strategies are known to address these difficulties well, namely vertical partitioning and bitmap indexes. In this paper, we summarize our experience of implementing a number of bitmap index schemes on vertically partitioned data tables. One important observation is that simply scanning the vertically partitioned data tables is often more efficient than using B-tree based indexes to answer ad hoc range queries on static datasets. For these range queries, compressed bitmap indexes are in most cases more efficient than scanning vertically partitioned tables. We evaluate the performance of two different compression schemes for bitmap indexes stored is various ways. Using the compression scheme called Word-Aligned Hybrid Code (WAH) to store the bitmaps in plain files shows the best overall performance for bitmap indexes. Tests indicate that our bitmap index strategy based on WAH is not only efficient for attributes of low cardinality, say, <100, but also for high-cardinality attributes with 200,000 or more distinct values.

REFERENCES

• 1: 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
• 2: G. Antoshenkov. Byte-Aligned Bitmap Compression. Technical Report, Oracle Corp., 1994. U.S. Patent number 5,363,098.
• 3: 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]
• 4: Rudolf Bayer, The Universal B-Tree for Multidimensional Indexing: general Concepts, Proceedings of the International Conference on Worldwide Computing and Its Applications, p.198-209, March 10-11, 1997
• 5: 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
• 6: 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
• 7: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 8: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 9: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 10: 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
• 11: M. Jürgens and H.-J. Lenz. Tree Based Indexes vs. Bitmap Indexes - a Performance Study. International Journal of Cooperative Information Systems, 10(3):355--376, 2001.
• 12: V. Markl and R. Bayer. Processing Relational OLAP Queries with UB-Trees and Multidimensional Hierarchical Clustering. In Proceedings of DMDW 2000, June 5--6, 2000.
• 13: 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
• 14: 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
• 15: A. Shoshani , L. M. Bernardo , H. Nordberg , D. Rotem , A. Sim, Multidimensional Indexing and Query Coordination for Tertiary Storage Management, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.214, July 28-30, 1999 [doi>10.1109/SSDM.1999.787637]
• 16: Kurt Stockinger , Dirk Düllmann , Wolfgang Hoschek , Erich Schikuta, Improving the Performance of High-Energy Physics Analysis through Bitmap Indices, Proceedings of the 11th International Conference on Database and Expert Systems Applications, p.835-845, September 04-08, 2000
• 17: Kurt Stockinger, Bitmap Indices for Speeding Up High-Dimensional Data Analysis, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.881-890, September 02-06, 2002
• 18: 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]
• 19: K. Wu, E. J. Otoo, A. Shoshani, and H. Nordberg. Notes on Design and Implementation of Compressed Bit Vectors. Technical Report LBNL/PUB-3161, Lawrence Berkeley National Laboratory, Berkeley, CA, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Performance