oracle位图索引.pptx

2024/11/17 周日1 What a DBA Needs to Know AboutOracles Bitmap Indexing to Retrieve Data Quickly?Part IVilin RoufchaieCingular WDownload slides:www.nocoug.org2024/11/17 周日2Presentation Assumptions&PrerequisiteslFamiliarity with basic Database and Data Warehouse concepts is requiredlBitmap and Bit Vector will be used interchangeably2024/11/17 周日3Who Is This Presentation For?lData warehouse designers&developerslDBAslPerformance DBAslCapacity Planners2024/11/17 周日4Presentation SummaryPart IlOverview,Characteristics,Structure&Size of a Bitmap IndexlPerformance Considerations of Bitmap IndexinglLogical Layout of Bitmap IndexeslBitmap Index Creation&Storage IssueslQuery Processing&Bitmap Index Access Paths2024/11/17 周日5Presentation SummaryPart IIlStar Schema,Join,&TransformationlStar Optimization,and TransformationlCBO Estimation&Query TransformerlEnabling Star Transformation lStar Transformation Steps2024/11/17 周日6Presentation SummaryPart IIlJoinback EliminationlCase Study&Explain Plan ReviewlTo“Star Query”?OrTo“Star Transform”?lConclusionslAcknowledgements2024/11/17 周日7Indexing Rules-of-ThumblIn building an index know:data selectivity,data distribution,workload,execution plan,proof of utilization.lThere is cost&overhead in building,utilizing,tuning,&maintaining indexes of any sort!lWhat do we expect after paying those cost?2024/11/17 周日8Indexing Rules-of-ThumblPerformance!Orders of magnitude in execution speed?Ideal!lHow about what makes the Business/users happy!lMake sure business expectations are understood&adequate research&tests are done to assess the likelihood of succeeding before committing to something2024/11/17 周日9Indexing Rules-of-ThumblThe index must be beneficial to all SQLs impacted by it across the board-Wholly beneficiallTry Aggregate/Collective tuninglSo we want to build few,efficient indexeslDemand:Low-overhead indexes,requiring less frequent&fast re/builds,&be space-efficient2024/11/17 周日10Overview Of Bitmap IndexinglBitmap indexing is a query execution optimization technique in Data Warehousing environmentslOracle provides OLTP&Data Warehousing in one engine2024/11/17 周日11Overview Of Bitmap Indexingl Oracle Supports Ever-growing Types of Indexes:B*-tree B*-tree ClusterHashReverse KeyFunction-BasedBitmap IndexBitmap Join Index(new in Oracle 9i)2024/11/17 周日12 Characteristics Of Bitmap IndexeslBitmap index entries have Bitmap vectors of 0s and 1s:.lEach 1-bit in the Bitmap corresponds to a rowid inside a table:Bitmap:RID-list:.2024/11/17 周日13Characteristics Of A Bitmap Indexl1-bits correspond to rowids lA mapping function converts the bit position to an actual rowidlA compression function compresses the long sequence of 0s in the BitmaplGood for low-mid-high cardinality columns 2024/11/17 周日14Structure&Size of A Bitmap Index?lIndex entries which contain bitmap/bit-vector,instead of list of rowids(B*-tree)lEach bit in bitmap maps to a rowid inside a tablelBitmap index entry structure:(key,6 byte(start rowid),6 byte(end rowid),bitmap)Sizekey+2*6 byte+bitmap2024/11/17 周日15Structure&Size of A B*tree IndexUncompressed:(key,6 byte rowid1)(key,6 byte rowid5)(key,6 byte rowid15)Size=(key*3+3*6 byte)Compressed:(key,6 byte rowid1,6 byte rowid5,6 byte rowid15)Size=(key+3*6 byte)2024/11/17 周日16B*-tree vs.Bitmap Index Storage2024/11/17 周日17Are all High Cardinality Columns Inappropriate for Bitmap Indexing?Suppose we have CA as index entry(8 clustered occurrences:CA CA CA CA CA CA CA CA TXBitmapped:Size=(key+2*6 byte+bitmap)=key+12+8=key+20Uncompressed B*-tree:Size=(n*key+n*6 byte)=8*key+48=8 key+48Compressed B*-tree:Size=(key +n*6 byte)key+482024/11/17 周日18Are all High Cardinality Columns Inappropriate for Bitmap Indexing?lIndexed a table with:31,029 rows,num_distinct=3879 Column values were clustered:3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4.9 9 9 9 9 9 9 9.15 15 15 15 15 15 15 15.27 27 27 27 27 27 27 27Bitmap,B*tree,and compressed B*-tree indexes were built on this columnBM index Size:167,631 bytesB*-tree index Size:997,619 bytesB*-tree Index Compressed:449,602 bytes2024/11/17 周日19 Oracle Manual:“As a general rule,a degree of cardinality of under 1%makes a good candidate for a bitmap index”2024/11/17 周日20Characteristics Of A Bitmap IndexlBitmap indexes are very space efficient,which allow more entries per leaf block.l A bitmap can hold many bits pointing to many rowids(low cardinality columns)lSignificantly fewer index block processing and disk I/O.lWhen a bitmap index entry is locked,many rows stay locked(in OLTP)l In a B*-tree index,a list of rowids are stored for each index entry in a leaf block and,when an index entry is locked,it will not impact many table rows2024/11/17 周日21Characteristics Of A Bitmap IndexlBitmaps are stored in the leaves of a B-tree index as bitmap segmentslUsed on low/mid/high cardinality datalFast Boolean/Set operations on Bitmap values from different Index entrieslExampleBitmap AND,OR,AND-NOT.2024/11/17 周日22Characteristics Of A Bitmap IndexlBitmap Indexes can be combined with other Bitmap indexes and B-tree indexes in the same access pathlFully UpdateablelParallelism Applied to:All Aspects of Queries&Index Creation2024/11/17 周日23Performance ConsiderationsOf Bitmap IndexinglProblem?lConcurrent DML(updates/inserts/deletes)operations can be problematic lI.e.,not suitable for concurrent OLTP workloadslGranularity of lock on Bitmap index segment=1lEach index segment can hold hundreds of bits One lock per Index segment2024/11/17 周日24Performance ConsiderationsOf Bitmap IndexinglBatched DMLs are done efficiently-Each bitmap index segment is modified by a single statement(not transaction)in one trip,once a segment lock is acquired:insert into table customer(select*from temp_table)2024/11/17 周日25Logical Layout of Bitmap IndexeslOracle implements B-tree structures to store Bitmaps for each indexed keylUp to 30 keys can be specified for each composite indexlBitmaps are broken down into chunks(not exceeding half a database block)lThey are laid out as:.keystart rowidend rowidbitmapB777 10.0 11.7 10001010000110002024/11/17 周日26Logical Layout of Bitmap IndexeslBitmaps are stored in the leaves of B-tree indexes as bitmap segmentslAligned mapping in place between bitmaps and table rows BLOCK10 StartEnd BLOCK 11KeyRowidRowid BitmapRed10.012.7100010010001001000000Blue10.012.7001000001100000010000yellow10.012.7010000100000000000100 Green10.012.7000100000010010001000 BLOCK122024/11/17 周日27Logical Layout of Bitmap Indexesl1st Problem?Insertion of new rows misalign the mapping in place between Bitmaps and table rowslExplanation I?Oracle divides up each block into maximum number of slots:Based on minimum row size,(Minimum row size would be derived from definition of each column in table)2024/11/17 周日28Logical Layout of Bitmap IndexeslOracle map bits to table rows based on maximum number of rows per data blockbits-allocated-per-table-block And not to existing rows in the data blocklExcessive zeros are compressed 2024/11/17 周日29Mapping Bitmaps to Rowids Optimization Explanation II?lPopulate table 1stlalter table XYZ minimize records_per_blockl(see“nominimize”to disable)lBuild bitmap indexes nowlOracle scans table for maximum number of records in any block lOracle restricts the table to this maximum records/blocklFewer bits go to each blockl Potentially smaller bitmap indexes-run a test!2024/11/17 周日30Mapping Bitmaps to Rowids Optimizationl2nd Problem?This approach creates a dependency between table column definition&Bitmaps createdlAltering table definition,changing minimum row length,may result in all bitmap indexes being automatically invalidated,demanding index rebuilds2024/11/17 周日31Creation Of Bitmap indexeslA Bitmap Index may be constructed on one or more columns of a tablelIn Oracle 9,a local bitmap index can be created on a partitioned table2024/11/17 周日32Creation Of Bitmap indexes(1st Salve Set)lFull table scan to fetch values of column(s)lColumn values are fed into bitmap generator to create index entries:lAllocate sufficient space for:create_bitmap_area_size=(db_block_size*0.5)*(num_distinct)+20%2024/11/17 周日33Creation Of Bitmap indexesBitmap CompactionIndex BuildSortBitmap ConstructionTable AccessSecond set ofParallel Salves Initial set ofParallel Salves2024/11/17 周日34Creation Of Bitmap indexes2nd Salve SetlBitmap index entries sorted on:Set:sort_area_sizelIndex entries compaction:to piece together bitmaps of the same key to reach half a database block sizelPlacing index entries into a B-tree structure2024/11/17 周日35Bitmap CompressionlPatented algorithm(GennadyAntoshenkov),Cleverly encoded,hence very low overhead lStorage Policy:Store all 0-bits if next 1-bit is=8 bits:(100000000000001000000001000000000000001)2024/11/17 周日36Query Processing&Bitmap Access MethodslBitmap Index Probe (for:equality and/or range predicates)lBitmap AND(set-based)(Intersection among multiple bitmaps)lBitmap OR (set-based)(Union among multiple bitmaps)2024/11/17 周日37Query Processing&Bitmap Access MethodslBitmap MINUS (set-based)(between two bitmaps)lBitmap COUNT(set-based)lBitmap Merge (bitmap OR on bitmap values)lBitmap Conversion(bitmap conversion to:rowid or count bits)2024/11/17 周日38Equality Predicates select count(*)from customer where region=WESTAdd all counts togetherCount all 1-bits in the bitmaps fetchedFetch the bitmap correspondingto region=west in the bitmap indexAggregationBitmap Conversion(To Count)Bitmap Index Probe(region=WEST)2024/11/17 周日39AND Predicatesselect name from customer where state=GA andgender=FTable Access(By ROWID)Bitmap Conversion(To ROWIDS)Bitmap ANDBitmap Indexstate=GABitmap Index(gender=F)2024/11/17 周日40OR Predicatesselect count(*)from customer where state=FL OR state is NULLAggregationBitmap Conversion(To COUNT)Bitmap ORBitmap Index(state=FL)Bitmap Index(state is NULL)2024/11/17 周日41Not Equal Predicates select count(*)from customer where gender=F and state!=VAAssumption:State is declaredNOT NULLAggregationBitmap Conversion(To COUNT)Bitmap MINUSBitmap Index(state=VA)Bitmap Index(gender=F)2024/11/17 周日42Range Predicatesselect count(*)from customer where gender=F AND age 65BITMAP_MERGE_AREA_SIZE?AggregationBitmap Conversion(To COUNT)Bitmap ANDBitmap MergeBitmap Index(gender=F)Bitmap Index(age 65)2024/11/17 周日43Group By Queriesselect state,count(*)from customer group by statelNo need to sort for groupinglCount 1-bits in each bitmapreturn keylKey&bitmap will be returned in order from bitmapAggregation(Group By Nosort)Bitmap Conversion(To Count)Bitmap Index(Full Scan)2024/11/17 周日44Distinct Queriesselect distinct statefrom customerlOnly the keys will be returned for each bitmap index entrySort(Unique Nosort)Bitmap Index(Full Scan)2024/11/17 周日45Combining Predicatesselect name from customer where income 90000AND gender=FReverse not done!rowids sorted Generates all rowids satisfying the predicateTable Access(By ROWID)Bitmap Conversion(To ROWID)Bitmap ANDBitmap Conversion(From ROWID)Bitmap Index(gender=F)SortB-tree Index(Income 90000)2024/11/17 周日46Star Transformation lWhat makes bitmap indexes so powerful are their ability to combine with same/other types of indexes lSo far we have learned how to combine indexes to retrieve data from a tablelNow we will learn how to combine indexes to rapidly handle joins2024/11/17 周日47What a DBA Needs to Know About Oracles Star Transformation Processing In a Star Schema?Part IIVilin Roufchaie,Cingular WDownload Slides:www.nocoug.org2024/11/17 周日48Presentation SummaryPart IIlStar Schema,Join,&TransformationlStar Optimization,and TransformationlCBO Estimation&Query TransformerlEnabling Star Transformation lStar Transformation Steps2024/11/17 周日49Presentation SummaryPart IIlJoinback EliminationlCase Study&Explain Plan ReviewlTo“Star Query”?Or To“Star Transform”?lConclusionslAcknowledgements2024/11/17 周日50Star Transformation(ST)Star Transformation Is a Cost-Based Query Transformation Aimed at Executing Star Queries EfficientlyIn a Star Schema2024/11/17 周日51Star SchemalIs the Basic design of a data warehouselMade up of:One or more fact tables A few dimension tables2024/11/17 周日52TimesEmployeeProductsCustomersSales2024/11/17 周日53Fact TablelContains all the“quantitative information”that the user wants to see in the result setlForeign keys to dimension tableslNon-key columns contains numeric facts:summarized,analyzed,and reported lNarrow in record widthlUsually huge number of rowslExamples:Sales,Shipment2024/11/17 周日54Dimension TableslContains the“qualitative information”defining how users will analyze fact datalPrimary Key column lNon-key columns contain“descriptive information”about a recordlTherefore wide in record lengthlDenormalized,enhances query performancelExamples:Time,product,employee2024/11/17 周日55What is a Star Join?A join process in which dimension tables Primary Key column values are joined to the fact tables Foreign Key column values in Star Schemas(but the dimension tables are not joined to each other)2024/11/17 周日56Star Transformation Oracle Data Warehousing functions equally apply to:lStar schemasl3rd Normal Form schemaslHybrid schemas2024/11/17 周日57Star Transformation l ST is Powerful feature of Oracle utilizing bitmap indexing to handle Star Joins:ST Handles:l Several dimension tables,l Snowflakes,Viewsl More than a single fact table(example:sales&inventory)lComplex Queries(Inside-out)Predicate constraint on fact column(s)(should build BM index on facts non-key column)lParallelizable (by fact table rowid ranges)2024/11/17 周日58Star Transformation Data Warehousing Capabilities that work with all schema models are:lPartitioninglParallelismlMaterialized Views2024/11/17 周日59Star Transformation(vs.Star Optimization)lGood for large number of dimension tables lThe Fact tables are sparsely/densely populated lIdeal for creating&combining single-column bitmap indexes on fact columns (rather than concatenated indexes)lAppropriate for cases where large number of dimensions would lead to large Cartesian products finding few matching rows in the fact table2024/11/17 周日60(Star Transformation vs.)Star OptimizationlGood for small number of dimension tables(with relatively small number of rows)lFact table should be densely populatedlDoes not work well with sparsely populated factsl Relies on computing a Cartesian product of the dimension tables,based on the WHERE clause predicates l lIn the last stepIn the last step,joins the result set to a fact table via NESTED LOOPS through concatenated B*-tree index access path.2024/11/17 周日61What Does CBO Do?lAt the outset,the CBO DOES take indexing cost into account when evaluating a query.It creates two plans:Regular TransformedlAnd picks the least costly plan to execute the star query2024/11/17 周日62Query Transformer&Plan Generator(CBO)2024/11/17 周日63Enabling and Implementing Star Transformation lSet init.ora parameter:star_transformation_enabled=TRUElCreate:Single-column bitmap indexes on a fact tables dimension keys(foreign-keys)lCreate indexes on dimension tables attribute columns found in a querys WHERE clause(also known as dimensio