Query optimization for selections using bitmaps

ABSTRACT

Bitmaps are popular indexes for data warehouse (DW) applications and most database management systems offer them today. This paper proposes query optimization strategies for selections using bitmaps. Both continuous and discrete selection criteria are considered. Query optimization strategies are categorized into static and dynamic. Static optimization strategies discussed are the optimal design of bitmaps, and algorithms based on tree and logical reduction. The dynamic optimization discussed is the approach of inclusion and exclusion for both bit-sliced indexes and encoded bitmap indexes.

REFERENCES

• 1: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 2: Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
• 3: 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
• 4: C.-Y. Chan, Y.E. Ioannidis, Bitmap Index Design and Evaluation, CS Dept., Univ. of Wisconsin-Madison, http ://www. cs. wisc. edu/~ cychan/paperl Ol .ps, 1997.
• 5: J.-H. Chu, An analysis of B-trees and their variants, Information Systems, v.14 n.5, p.359-370, 1989 [doi>10.1016/0306-4379(89)90001-X]
• 6: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 7: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 8: J. Feigenbaum, S. Kannan, M.Y. Vardi, M. Viswanathan, Complexity of Problems on Graphs Represented as OBDDs, AT&T Technical Report: 97.1.1, 1996.
• 9: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 10: K. Kiispert, Storage Utilization in B*-Trees with a Generalized Overflow Technique, Acta Informatica, 19, 1983.
• 11: E.J. McCIuskey, Minimisation of Boolean functions, Bell System Technical Journal, 35(6), 1956.
• 12: 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
• 13: 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]
• 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: W.V. Quine, The Problem of Simplifying Truth Functions, American Mathematical Monthly, 59(8), 1952.
• 16: S. Sarawagi, Indexing OLAP Data, Bulletin of the Technical Committee on Data Eng., Vol. 20, No. 1, Mar 1997.
• 17: Leonard D. Shapiro, Join processing in database systems with large main memories, ACM Transactions on Database Systems (TODS), v.11 n.3, p.239-264, Sept. 1986 [doi>10.1145/6314.6315]
• 18: 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
• 19: M.C. Wu, Query Optimization .for Selections using Bitmaps, Tech. Report, DVS98-2, DVS1, CS Dept, Technische Universitiit Darmstadt, 1998.
• 20: K.L. Wu, P.S. Yu, Range-Based Bitmap Indexing for High Cardinality Attributes with Skew, Research Report, IBM Watson Research Center, May 1996.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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

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