ࡱ> Root Entry E# F*g;"YWordDocument  E#9FFObjectPool,s O#a1@/;@/; ,SummaryInformation( P*( !"$%&')=+,-./012>456789:;<X?@ABCQRSTUVW#YZ[\ObjInfoSummaryInformation( DocumentSummaryInformation8 CompObjj FMicrosoft Word Document MSWordDocWord.Document.69qing the two columns type of property and no. of bedrooms as in Fig. 1 (flat, 2) (detached house, 4) (detached house, 3) (cottage, 1) (semi-detached 3) (semi-detached 2) (flat, 1) (semi-detached 3) (detached house, 3) (semi-detached 3) Fig 1 Table of property data To build a bitmap index on the TYPE column we note that there are four different values used for TYPE, so we builRoot Entry E# F`g;"YWordDocument  E#9FFObjectPool,s O#a1@/;@/; ,SummaryInformation( P*(+,-./012>456789:;<?@ABCEFGHIJKLMNOQRSTUVWDܥhc $eb)Fb&<<=====R?R?R?R?R?R?b?(R?ER????????}CCCC#C D EKFXFPE!=?????E*A==??YES 0 0 0 0 0 1 0 0 0 0 0 0 1 1 YES 0 0 1 0 0 1 YES 0 0 1 0 YES 1 1 YES 0 0 0 1 0 0 1 1 YES 0 0 Fig 3. Samples of ANDs and Ors Some Test results. To find out how well Oracles bitmaps work, I built a 13 column table of which one column was data/padding, and the other columns were calculated to test the effectiveness of bitmaps. Different columns had cardinalities 2 (i.e. only two values allowed in the column) 10, 100, and 1000. The clustering factor ranged from non-existent, through repetitions of 50, to repetitions of 500. For example a column named TEN_50 was allowed to have only the values 0 to 9 in it, but reading down the table you would see 50 0s, then 50 1s and so on up to 50 9s then back to 0s. To indicate their cardinality and clustering, the columns were named: two_1, two_50, two_500 ten_1, ten_50, ten_500 c_1, c_50, c_500 m_1, m_50, m_500 The table held 8,000,000 rows, and had a size of 750 MB. To make best use of bitmaps, I set the following init.ora parameters. create_bitmap_area_size = 8388608 bitmap_merge_area_size = 4194304 b_tree_bitmap_plans = TRUE v733_plans_enabled = TRUE compatibility = 7.3.2 It is only the compatibility option that needs to be set. The other options affect performance and the possible choice of execution paths. The speed with which bitmap indices can be built is also affected by the sort_area_size, which was set to (relatively small) default of 64K. Building Bitmaps The table shows the time taken in minutes to build indices on each of the columns, the sizes of the indices, and the amount of space in the TEMP tablespace needed whilst building.  EMBED Excel.Sheet.5  An interesting comparison is the cost of building an ordinary b-tree index on the M_500 column which is the most appropriate column in the table for normal indexing. For the purposes of this build, I set the sort_area_size to 8MB with the following result: Time: 33 mins 46 secs Size: 126 MB Sort Space: 158 MB We can draw four conclusions from these results. bitmaps are significantly smaller than b-tree indices. The total space for all 12 bitmaps was less than the space for the single b-tree bitmaps on clustered data can be stored much more efficiently than bitmaps on non-clustered data. the cost of building lots of bitmaps is not really prohibitive. low cardinality is relative - our bitmaps on columns with 1,000 different values are still very small. Each value represents only 0.1% of the total number of rows in the table, and it is this fraction that is more important that the absolute number of different values in the column. Using Bitmaps: I ran various queries to determine the execution paths of queries, and the time cost of bitmaps - the variations, and the clever tricks that Oracle plays could easily fill a couple more articles but the most significant thing was the very first query I ran: select padding from bit_test where m_2 = 0 and m_50 = 0 and m_500 = 0; Out of the 8,000,000 rows in the table, there were 16 meeting the condition. Oracle got them in just 0.88 seconds. This surprised me so much I rebooted the machine and ran the query from a cold database startup - it still took only 1.03 seconds. This was so amazing that I rebuilt the table with 2 columns that were allowed 1,000 values of randomly distributed data. With these columns bitmapped, (30 MB per bitmap this time) it took only 0.5 seconds to return a result for: select padding from bit_test where col1 = N1 and col2 = N2; The other feature of bitmap indices was the way in which Oracle would use as many indices as needed to satisfy the query efficiently. The first example above used only the M_500 and M_50 indices as these were the best indices (narrowing the table access down to 800 rows), and the M_2 index was unlikely to improve matters much. By comparison, the query: select padding from bit_test where two_2 = 0 and two_50 = 0 and two_500 = 0 and ten_2 = 0 and ten_50 = 0 and ten_500 = 0; used*A*A*A?=?=?}C# e;>>====?}C*AS*AMake a little bit go a long way. In my last article, I mentioned bitmap indices as a possible solution to the problem of acquiring a small number of rows from a very large table. This resulted in a few people contacting me to ask for more details: so her՜.+,0HPpx  JL Computer ConsultancyC !Relate article - Partition ViewsOh+'0 4@ h t  ܥhc 4eb)Fb&<<=====R?R?R?R?R?R?b?(R?ER????????vCxCxCxC#C D EPFXFPE-=?????E*A==??*A*A*A?=?=?vC*g;>>====?vC*AL*AMake a little bit go a long way. In my last article, I mentioned bitmap indices as a possible solution to the problem of acquiring a small number of rows from a very large table. This resulted in a few people contacting me to ask for more details: so here is a brief summary of the what, why and how of bitmap indices in Oracle . Any examples in this article are based on Oracle 7.3.2.3 running on HP-UX 10.20 A Challenge. A (hypothetical) building society has about 5,000,000 customers, and amongst other details their customer database records the following details: Size of mortgage (to nearest 1,000 ) Value of property (to nearest 1,000 ) Year mortgage acquired Type of property Number of bedrooms etc. . How can you define the database in such a way that it is possible to run efficient queries to identify things like: All mortgages for more than 300,000 taken out in 1992 on 5-bed detached houses You may identify a few frequently occurring queries and build multi-column indices that allow them to be addressed fairly efficiently, but this takes a lot of space and you wont be able to cover all the possible options. This is where bitmap indices can be useful, and this article is a brief discussion of what they are, how they work, and what they cost in Oracle. What is a bitmap index ? Take as an example a ten row subset of the building society data, showing the two columns type of property and no. of bedrooms as in Fig. 1 (flat, 2) (detached house, 4) (detached house, 3) (cottage, 1) (semi-detached 3) (semi-detached 2) (flat, 1) (semi-detached 3) (detached house, 3) (semi-detached 3) Fig 1 Table of property data To build a bitmap index on the TYPE column we note that there are four different values used for TYPE, so we build a second table with 4 columns one for each type, and in each column we put a 1 or 0 to show which TYPE appears at that location in the base table (See Fig. 2). Then, of course, we have to figure out a way of storing and using this table of 1s and 0s efficiently. flat semi cott detached 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 Fig 2. Example of a bitmap index There are two problems that Fig. 2 highlights, both of which are raised in the Oracle manuals: First, the notional size of a bitmap is number of used values multiplied by number of rows in table. Clearly you should only create a bitmap index on a column (or set of columns) with a low cardinality. But how low is low ? More on this later. Secondly, if you update a column that is bitmap indexed, two columns of the bitmap have to be locked briefly whilst a bit is set in one and cleared in the other. Although Oracles physical implementation aims to minimise the impact this has on concurrency, bitmap indices should not be used on columns with high update rates. Relational purists may, of course, complain that bitmaps work only if the rows in the base table have an implied order that allows the bitmaps to line up with the table. As an example of using bitmaps, Fig. 3 shows the action for the two queries: find all three bed semis find a flat or 2 bedrooms AND for semi-detached and 3 bedrooms OR for flat or 2 bedrooms semi 3 beds 3-bed-semi Flat 2 beds Flat/2 beds 0 0 1 1 !Relate article - Partition ViewseeeeeeJonathan Lewis Normal.dotJonathan Lewis141Microsoft Word for Windows 95@1V@bn@\m@(Q;՜.+,08@ `h p JL Computer Consultancy Sheet1  e is a brief summary of the what, why and how of bitmap indices in Oracle . Any examples in this article are based on Oracle 7.3.2.3 running on HP-UX 10.20 A Challenge. A (hypothetical) building society has about 5,000,000 customers, and amongst other details their customer database records the following details: Size of mortgage (to nearest 1,000 ) Value of property (to nearest 1,000 ) Year mortgage acquired Type of property Number of bedrooms etc. . How can you define the database in such a way tDocumentSummaryInformation8_926624672 F@/;;Ole PIC L  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~hat it is possible to run efficient queries to identify things like: All mortgages for more than 300,000 taken out in 1992 on 5-bed detached houses You may identify a few frequently occurring queries and build multi-column indices that allow them to be addressed fairly efficiently, but this takes a lot of space and you wont be able to cover all the possible options. This is where bitmap indices can be useful, and this article is a brief discussion of what they are, how they work, and what they cost in Oracle. What is a bitmap index ? Take as an example a ten row subset of the building society data, showing the two columns type of property and no. of bedrooms as in Fig. 1 (flat, 2) (detached house, 4) (detached house, 3) (cottage, 1) (semi-detached 3) (semi-detached 2) (flat, 1) (semi-detached 3) (detached house, 3) (semi-detached 3) Fig 1 Table of property data To build a bitmap index on the TYPE column we note that there are four different values used for TYPE, so we build a second table with 4 columns one for each type, and in each column we put a 1 or 0 to show which TYPE appears at that location in the base table (See Fig. 2). Then, of course, we have to figure out a way of storing and using this table of 1s and 0s efficiently. flat semi cott detached 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 Fig 2. Example of a bitmap index There are two problems that Fig. 2 highlights, both of which are raised in the Oracle manuals: First, the notional size of a bitmap is number of used values multiplied by number of rows in table. Clearly you should only create a bitmap index on a column (or set of columns) with a low cardinality. But how low is low ? More on this later. Secondly, if you update a column that is bitmap indexed, two columns of the bitmap have to be locked briefly whilst a bit is set in one and cleared in the other. Although Oracles physical implementation aims to minimise the impact this has on concurrency, bitmap indices should not be used on columns with high update rates. Relational purists may, of course, complain that bitmaps work only if the rows in the base table have an implied order that allows the bitmaps to line up with the table. As an example of using bitmaps, Fig. 3 shows the action for the two queries: find all three bed semis find a flat or 2 bedrooms AND for semi-detached and 3 bedrooms OR for flat or 2 bedrooms semi 3 beds 3-bed-semi Flat 2 beds Flat/2 beds 0 0 1 1 !">?eEFvw  #$ % 2 F [ o p E#%E#E#8%8888888888888888888%8E#E#E#E#E#E#E#E#E#E#E#E#@ h*   ) 2 : B J R Z b j r z { CD>?[\wxyz 0888E#E#E#E#E#E#E#E#E#E#E#E#88888 888888888E#E#E#E#E#E#E#E#@ @ +0ATgxSTUVp;<^kl  E#E#E#E#E#E#E#E#88%8888888888888888888888888888888%8, OP<=}~88888888888888888 888%88888888%88888h  4.  4.!de 1"2"9""""" ####F$G$A%B%N%%%%%888888888888888888888 888%8888888888888%8888h)Book T META  3PRINT CompObj f%&$&B&&&'''((()(*(b)8%8%8%8@8888E#E#  4 WorksheetsOh+'008L`x jonathan jonathanMicrosoft Excel FMicrosoft Excel WorksheetBiff5Excel.Sheet.59q&     ,V,,,V,,,,V,VVVVVV,V,V,V,,,V,,,,,,,,,V,,,,,,,,V,,V,VV,V,V,V,,,,V,,,,,,,V,,,,,,,V,,,,V,VVVVVV,V,,VV,V,V,V,VVV,VVVVVVVVVVVV,VVVVVVV,VVVVVVV,VVVVVV,V,,,V,,,,V,VVVVVV,V,V,V,V,,,V,,,,V,VVVVVV,V,V,V,V,,,V,,,,V,VVVVVV,V,V,V%%%,,,444<<<DDDMMMVVV___iiirrr}}}45'  ' ' - -44- !4-'- Arial b~wk~wWw --"System  -'-- Arial b~wk~wWw - ArialC b~wk~wWwC  ---'-- 4 2  Index 2 . Time Taken % 2 R Index Size   2 v Sort Space --'-- - 2 8 TWO_2S*!2 8.09:26S 2 8R5.5 MB  #2 8v5.4 MB  #2 l TWO_50*!2 l.08:540 2 lR3.25 MB  #2 lv3.2 MB  #2 TWO_500*!2 .08:490 2 R2.75 MB  #2 v2.7 MB  #2  TEN_2B2 .15:44B 2 R22 MBB #2 v25 MBB #2 < TEN_502 <.09:160 2 <R3.5 MB  # 2 <v4 MB #2 p TEN_5002 p.09:010 2 pR2.75 MB  # 2 pv3 MB # 2  C_2B2 .17:26 2 R21.5 MB  #2 v25 MBM # 2  C_502 .09:36 2 R3.5 MB  # 2 v4 MB #2 @ C_5002 @.09:21 2 @R2.75 MB  # 2 @v4 MB # 2  M_2B#2 .20:35 2 R21.5 MB  #2 v43 MBM # 2  M_50#2 .09:48  2 R4 MB # 2 v4 MB #2  M_500#2 .09:21  2 R3 MB # 2 v3 MB #2 x Total  2 xR96 MB #--'-- - -4' 3B==<X@"1Arial1Arial1Arial1Arial1Arial1$     3e,V,,,V,,,,V,VVVVVV,V,V,V,,,V,,,,,,,,,V,,,,,,,,V,,V,VV,V,V,V,,,,V,,,,,,,V,,,,,,,V,,,,V,VVVVVV,V,,VV,V,V,V,VVV,VVVVVVVVVVVV,VVVVVVV,VVVVVVV,VVVVVV,V,,,V,,,,V,VVVVVV,V,V,V,V,,,V,,,,V,VVVVVV,V,V,V,V,,,V,,,,V,VVVVVV,V,V,V%%%,,,444<<<DDDMMMVVV___iiirrr}}}45'  ' 3e-  -e- !e-3- !3-'- 3e -e- !d-""e- !d"-33e- !d3-DDe- !dD-UUe- !dU-ffe- !df-wwe- !dw-e- !d-e- !d-e- !d-e- !d-e- !d-e- !d-e- !d-e- !d-e- !d-!!e- !d!-22e- !d2-Y3Y- !2Y-3- !2- 3 - !2 -d3d- !2d- -e- !e-'- 3eArial b~wk~wWw --"System  -'-- 3eArial vb~wk~wWw v - Arial b~wk~wWw -  2 Index2 \ Time Taken 2  Index Size 2  Sort Space  -2 TWO_2 2 \09:262 5.5 MB 2 5.4 MB 2 #TWO_50 2 #\08:542 #3.25 MB 2 #3.2 MB 2 4TWO_500 2 4\08:492 42.75 MB 2 42.7 MB 2 VTEN_2 2 V\15:442 V22 MB 2 V25 MB 2 gTEN_50 2 g\09:162 g3.5 MB 2 g4 MB 2 xTEN_500 2 x\09:012 x2.75 MB 2 x3 MB 2 C_2B 2 \17:262 21.5 MB 2 25 MB 2 C_50 2 \09:362 3.5 MB 2 4 MB 2 C_500 2 \09:212 2.75 MB 2 4 MB 2 M_2B 2 \20:352 21.5 MB 2 43 MB 2 M_50 2 \09:48 2 4 MB 2 4 MB 2 M_500 2 \09:21 2 3 MB 2 3 MB 2 "Total2 "96 MB - -4'K @ Normal ]a c$@$ Heading 1$U^@ Heading 2U^@ Heading 3U"A@"Default Paragraph Font$@$ Normal Indent0 +@ Endnote Textc @ Header o#$@"$ Footnote TextU"O2" Double IndentOBActionU^TObTprogram8 4]cArial""#,##0;\-""#,##0""#,##0;[Red]\-""#,##0""#,##0.00;\-""#,##0.00!""#,##0.00;[Red]\-""#,##0.003*0_-""* #,##0_-;\-""* #,##0_-;_-""* "-"_-;_-@_-*)'_-* #,##0_-;\-* #,##0_-;_-* "-"_-;_-@_-;,8_-""* #,##0.00_-;\-""* #,##0.00_-;_-""* "-"??_-;_-@_-2+/_-* #,##0.00_-;\-* #,##0.00_-;_-* "-"??_-;_-@_-                + ) , *  ! !  ( @!8 @ Sheet1 3  dMbP?_*+%,&APage &PMOfficejetpB A4 ''''" d??U}   Gwfw   @ @ @D@ Index Time Taken Index Size Sort Space TWO_2}'}'?5.5 MB5.4 MBTWO_50?3.25 MB3.2 MBTWO_500-؂-؂?2.75 MB2.7 MB TEN_2OO? 22 MB 25 MBTEN_50a ` ?3.5 MB 4 MBTEN_500` ` ?2.75 MB 3 MB C_2 >>? 21.5 MB 25 MB C_50~ D@ 3.5 MB 4 MB C_500 ? 2.75 MB 4 MB  M_2 qq? 21.5 MB 43 MB M_50#"""""? 4 MB 4 MB M_500? 3 MB 3 M$ ,SGIJEFHE@FEB> Md" L$!">?eEFvw  #$ % 2 F [ o p E#%E#E#8%8888888888888888888%8E#E#E#E#E#E#E#E#E#E#E#E#@ h*   ) 2 : B J R Z b j r z { CD>?[\wxyz 0888E#E#E#E#E#E#E#E#E#E#E#E#88888 888888888E#E#E#E#E#E#E#E#@ @ +0ATgxSTUVp;<^kl  E#E#E#E#E#E#E#E#88%8888888888888888888888888888888%8, OP<=}~88888888888888888 888%88888888%88888h  4.  4.!de 1"2"9""""" ####F$G$A%B%N%%%%%888888888888888888888 888%8888888888888%8888h)%&$&B&&&'''((()(*(b)8%8%8%8@8888E#E#  4 K @ Normal ]a c$@$ Heading 1$U^@ Heading 2U^@ Heading 3U"A@"Default Paragraph Font$@$ Normal Indent0 +@ Endnote Textc @ Header o#$@"$ Footnote TextU"O2" Double IndentOBActionU^TObTprogram8 4]cy )%b&b))))*"*G*f**k y l=U )%b&* 0 %b)b&: T Z !,&.<S^t 0 9 !#!$$F&a&d&SJonathan Lewis,C:\USERS\jonathan\winword\oracle\bitmaps.docJonathan Lewis,C:\USERS\jonathan\winword\oracle\bitmaps.docJonathan Lewis,C:\USERS\jonathan\winword\oracle\bitmaps.docJonathan Lewis,C:\USERS\jonathan\winword\oracle\bitmaps.docJonathan Lewis,C:\USERS\jonathan\winword\oracle\bitmaps.docJonathan Lewis,C:\USERS\jonathan\winword\oracle\bitmaps.docJonathan Lewis,C:\USERS\jonathan\winword\oracle\bitmaps.docJonathan Lewis3C:\USERS\jonathan\winword\oracle\Relate bitmaps.docJonathan Lewis%C:\USERS\jonathan\website\bitmaps.docJonathan Lewis%C:\USERS\jonathan\website\bitmaps.doc@OfficejetLPT1:winspoolOfficejetOfficejetpB A4l\DRIVERS\W32X #''''OfficejetpB A4tem32;C:\WINNT #''''a&b&@@a)RTimes New Roman Symbol &Arial5Courier NewCG Times P h J1Ɠ iC!P P Relate article - Partition ViewsJonathan LewisJonathan Lewismple of using bitmaps, Fig. 3 shows the action for the two queries: find all three bed semis find a flat or 2 bedrooms AND for semi-detached and 3 bedrooms OR for flat or 2 bedrooms semi 3 beds 3-bed-semi Flat 2 beds Flat/2 beds 0 0 1 1 all 6 indices to try and restrict the table access to the required 8,000 rows. The result came out in 1 minute 4 seconds - compared to 6 minutes 56 for a full tablescan. You may recall that with B-tree indices Oracle does not merge more than 5 indices on a single table: this doesnt apply with bitmap indices. All the indices used in this second query range from bad to appalling in b-tree terms - the best ones return 800,000 rows from the table - yet because our query can merge several bitmapped columns we can still get a reasonable turn-around time. Traps: Are there any pitfalls to using bitmap indices ? I dont really know yet as all my work has been done in the lab, and not against real client data. I did find one anomaly. The query: select * from bit_test; used a bitmap scan, rather than a tablescan to acquire the rows. This might introduce a surprise overhead when scanning a large table. There are some indications that users of bitmaps will end up grabbing more memory than other processes. (The default bitmap_merge_area_size is 4MB, which seems a bit large.) The only other thing to be wary of is using bitmaps against partitioned views - they do work, and they could work very well but - there is a brief note in my 8.02 Beta manuals that bitmap indices will not work against version 8 partitioned tables. Conclusion: Although I have not yet stress-tested bitmap indices in a user environment, I am amazed at how well they have responded in the tests I carried out. The main benefits are: They are quick to build They are small Good indices work very well Oracle can combine lots of bad indices to get a result quickly. Remember the key point - a single bitmap is not particularly useful, it is the ability to combine several bitmaps that brings the greatest benefits. I am looking forward to working on a site where they may be appropriate. However, given the v733 init.ora parameter I have mentioned in this article, I personally would be a little cautious of implementing them in a production system until version 7.3.3 of Oracle. Jonathan Lewis is a freelance consultant with 11 years experience of Oracle. He specialises in physical database design and the strategic use of the Oracle database engine, but spends most of his time resolving performance issues. He can be contacted on 0973-188785, or e-mailed at jonathan@jlcomp.demon.co.uk 88.A88#88.A88 88.A88#88.A88 88.A88#88.A8888.A88#88.A8888.A88!F " ) * 8 9 @ A F G L M T U Z [ d e p q t u ?AZ]vw-/01369;ABMNS]^fghjmps{|UV<]c^UU]cUVU^V] >>>(>a&b&@@>@a)RTimes New Roman Symbol &Arial5Courier NewCG Times CP h J1Ɠ iC!P P Relate article - Partition ViewsJonathan LewisJonathan Lewis