Optimizing Queries on Compressed Bitmaps

摘要: OptimizingQueriesOnCompressedBitmapsSihem Amer-YahiaAT&T Labs{Researchsihem@research.att.comTheo doreJohnsonjohnsont@research.att.comAbstractBitmap indices are used by DBMS's to accelerate decision supp ort queries.A signi cant advantage ofbitmap is that complex logical selection op erations can b e p erformed very quickly, erformingbit-wiseAND,OR,andNOTop erators.Althoughbitmapindicescanb espaceinecientforhighcardinalityattributes,the space use of compressed bitmapscompares well other indexingmetho ds.Oracle and Sybase IQ two commercial pro ducts make extensive bitmap indices.Our recent research showed there several fast algorithmsfor evaluatingBo oleanop eratorson compressedbitmaps.Dep endingon the natureof erandbitmaps(theirformat, densityandclusterdness) eration (AND, NOT, ...), these algorithms have executiontimes orders magnitude di erent.Cho osing an algorithm for erforming a Bo olean erationhas global ects in query expression, requiring optimization.We present linear timedynamicprogrammingsearch strategy based on cost mo delto optimizequeryexpressionevaluationplans.We alsopresentrewritingheuristicsthat rewritethe queryexpressionto anequivalenonetoencourage etter algorithmsassignments.Our erformance results show optimizerrequiresanegligibl amount time execute, optimized queries execute up three timesfaster than unoptimized real data.1Intro ductionAbitmap indexis bit string which each mapp ed record ID (RID) relation.A thebitmap index set (to 1) if corresp onding RID has prop ertyP(i.e., represents customer thatlives New York), reset 0) otherwise.In typical usage, predicatePis true it hasthe valueafor attributeA.One such predicate asso ciated one unique value ofthe attributeA.The predicates more complex, example bitslice [OQ97] precomputedcomplex [HEP99].Oneadvantageofbitmapindicesisthatcomplexselectionpredicatescanb ecomputedveryquickly,by bit-wiseAND, OR, andNOTop indices.Furthermore, indexableselection involve many attributes.Let's consider some examples, using databasewith schemaCustomer(Name, Livesin, Worksin, Car, Numberofchildren, Hascable, Hasel lular)Supp osethatweanttoselectallcustomerswholivinNewEngland.Thentheselectioncon-ditionisLivesin=\ME"ORin=\VT"in=\NH"in=\MA"in=\CT"ORLivesin=\RI"in=\NY". Since createdfor attributeLivesin, translates into mapping attribute all its ossible values.1