Digital Symposium Collection 2000

Query Optimization for Selections Using Bitmaps Ming-Chuan Wu   View Paper (PDF)   Return to Selectivities 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 Note: References link to DBLP on the Web. [1] Randal E. Bryant : Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers 35(8) : 677-691(1986) [2] Randal E. Bryant : Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams. Computing Surveys 24(3) : 293-318(1992) [3] Chee Yong Chan , Yannis E. Ioannidis : Bitmap Index Design and Evaluation. SIGMOD Conference 1998 : 355-366 [4] ... [5] Jiang-Hsing Chu , Gary D. Knott : An Analysis of B-trees and their Variants. IS 14(5) : 359-370(1989) [6] Douglas Comer : The Ubiquitous B-Tree. Computing Surveys 11(2) : 121-137(1979) [7] David J. DeWitt , Randy H. Katz , Frank Olken , Leonard D. Shapiro , Michael Stonebraker , David A. Wood : Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984 : 1-8 [8] Joan Feigenbaum , Sampath Kannan , Moshe Y. Vardi , M. Viswanathan : Complexity of Problems on Graphs Represented as OBDDs (Extended Abstract). STACS 1998 : 216-226 [9] Goetz Graefe : Query Evaluation Techniques for Large Databases. Computing Surveys 25(2) : 73-170(1993) [10] Klaus Küspert : Storage Utilization in B*-Trees with a Generalized Overflow Technique. Acta Informatica 19 : 35-55(1983) [11] ... [12] Patrick E. O'Neil : Model 204 Architecture and Performance. HPTS 1987 : 40-59 [13] Patrick E. O'Neil , Goetz Graefe : Multi-Table Joins Through Bitmapped Join Indices. SIGMOD Record 24(3) : 8-11(1995) [14] Patrick E. O'Neil , Dallan Quass : Improved Query Performance with Variant Indexes. SIGMOD Conference 1997 : 38-49 [15] ... [16] Sunita Sarawagi : Indexing OLAP Data. Data Engineering Bulletin 20(1) : 36-43(1997) [17] Leonard D. Shapiro : Join Processing in Database Systems with Large Main Memories. TODS 11(3) : 239-264(1986) [18] Ming-Chuan Wu , Alejandro P. Buchmann : Encoded Bitmap Indexing for Data Warehouses. ICDE 1998 : 220-230 [19] ... [20] ... BIBTEX @inproceedings{DBLP:conf/sigmod/Wu99,   author    = {Ming-Chuan Wu},    editor    = {Alex Delis and                 Christos Faloutsos and                 Shahram Ghandeharizadeh},    title     = {Query Optimization for Selections Using Bitmaps},    booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference                 on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,                 USA},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-084-8},    pages     = {227-238},    crossref  = {DBLP:conf/sigmod/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM