ࡱ> @K?Y |AbjbjWW l==|=]4$t y4C  $!# _yy__ _ _ xN lݒ4k z 0Bitmap Indexes 2: Star Transformations In an earlier article, I described the basic functionality of bitmap indexes, describing in particular their relevance to DSS types of system where data updates were rare, and indexes could be dropped and rebuilt for data loads. In this article we move onwards to one of the more advanced features of bitmap indexes, namely the bitmap star transformation that first appeared in later versions of Oracle 7. In an earlier article I demonstrated the extraordinary effectiveness of bitmap indexes when addressing queries of the type shown in fig. 1. select count(facts) from t1 where eyes = 1 and sex = 1 and hair = 1 and town = 15 and age = 25 and work = 40 ; Figure 1 A query designed for bitmap indexes. If facts was a very large table with single column bitmap indexes on each of the columns eyes, sex, hair, town, age, and work then Oracle could use normal costing techniques to decide that a combination of some (not necessarily all) of these indexes could be used through the mechanism of the bitmap AND to answer the query. Of course I pointed out that whilst such bitmap indexes could be used very effectively for queries, there were serious performance penalties if the indexes were in place when data maintenance was going on. These penalties essentially required you to consider dropping and rebuilding your bitmap indexes as part of your data maintenance procedures. However, there is a rather more significant weakness in this example that means it is not really a good example of genuine end-user requirements. It is often that case that the actual values that we wish to use to query the data are not stored on the main data table. In real systems they tend to be stored in related dimension tables. For example, we might have a table of Towns where code 15 represents Birmingham. The end-user could quite reasonably expect to query the facts table in terms of Birmingham rather than using a meaningless code number. Of course, the query might even be based on a secondary reference table States(where the column state_id is a foreign key in Towns) if we were interested in all the towns in Alabama. This issue is addressed by the Bitmap Star Transformation, a mechanism introduced in Oracle 7 although it's use is still not the default behaviour even in Oracle 9.2 where the two relevant parameters _always_star_transformation star_transformation_enabled still have the default value of FALSE. (Note - the star transformation is not the same thing as the star query that was introduced in earlier versions of Oracle 7 and was dependent on massive, multi-column b-tree indexes). A new feature of Oracle 9.2, the bitmap join index, may also be of benefit in such queries, but the jury is still out on that one; and I plan to describe that mechanism and comment on it in a later feature. The Bitmap Star Transformation - What is a Bitmap Star Transformation, how do you implement it, and how do you know that it is working. The main components are a large fact table and a surrounding collection of dimension tables. A row in the fact table consists of a number of useful data elements, and a set of identifiers - typically short codes. Each identifying column has a bitmap index created over it. An identifying column on the fact table corresponds to one of the dimension tables, and the short codes that appear in that column must be selected from the (declared) primary key of that table. Fig. 2 shows an extract from a suitable set of table definitions. create table states( id number(3,0), name varchar2(30), constraint st_pk primary key(id) ); create table towns( id number(3,0), name varchar2(30), id_state number(3,0) not null references states, constraint to_pk primary key(id) ); create table people( id_town_work number(3,0) not null references towns, id_town_home number(3,0) not null references towns, {other identifying columns} {fact columns} ); create bitmap index pe_work_idx on people(id_town_work); create bitmap index pe_home_idx on people(id_town_home); Figure 2 Part of a star (snowflake) schema. In this example, we have a people table as the central fact table, and a towns table which is actually used twice as a dimension table. I have also included a states table representing the relationship that each town is in a state. This is to illustrate the fact that Oracle can actually recognise a 'snowflake' schema. (See fig. 3).  EMBED Word.Picture.8  Figure 3 Simple Snowflake Schema. You will note that I have declared foreign key referential integrity between the people table and the towns table. There are two points to bear in mind here. First that the presence of the bitmap index is not sufficient to avoid the share lock problem that shows up if you update or delete a parent id - an index created for this purpose has to be a b-tree index. (Of course, in a DSS database such updates are not likely to be a significant issue). Secondly, for reasons that will be discussed in future articles on materialized views and partitioned tables, such foreign key constraints in DSS databases are quite likely to be declared as disabled, not validated, and rely. Having created the tables, loaded them with suitable data, and then enabled the feature by issuing: alter session set star_transformation_enabled = true; we can start to examine the execution plans for queries such as those in figure 4. select {pe.fact columns} from towns wt, towns ht, people pe where wt.name = 'Coventry' and ht.name = 'Birmingham' and pe.id_town_home = ht.id and pe.id_town_work = wt.id ; select wt.name, ht.name, st.name {pe.fact columns} from states st, towns wt, towns ht, people pe where st.name = 'Alabama' and wt.id_state = st.id and ht.name = 'Birmingham' and pe.id_town_home = ht.id and pe.id_town_work = wt.id ; Figure 4 Sample Queries. There are several variations in the gross structure of the execution plan that depend on whether we are using a simple star transformation, or a more complex query. The most important point to note in the execution plan though is the presence of lines like those in fig.5 (which almost a complete plan for the first query in fig. 4). TABLE ACCESS (BY INDEX ROWID) OF PEOPLE BITMAP CONVERSION (TO ROWIDS) BITMAP AND BITMAP MERGE BITMAP KEY ITERATION TABLE ACCESS (FULL) OF TOWNS BITMAP INDEX (RANGE SCAN) OF PE_HOME_IDX BITMAP MERGE BITMAP KEY ITERATION TABLE ACCESS (FULL) OF TOWNS BITMAP INDEX (RANGE SCAN) OF PE_WORK_IDX Figure 5 Baseline execution plan. Reading the plan recursively from top to bottom we see that the path is: Examine the towns table for towns called 'Birmingham', and find the primary key of each such town. For each Birmingham primary key in turn, scan the bitmap index pe_home_idx for the relevant section. Merge the resulting sections into a single large bitmap for the possible target rows of the people table. Repeat the process for 'Coventry' and the pe_work_idx index to produce a second large bitmap. (For more complex schemas, the above step will be repeated, perhaps for every dimension specified in the query, to produced one bitmap per dimension.) AND the two bitmaps together to produce a single bitmap identifying all people rows that match both conditions. Convert the resulting bitmap into a list of rowids, and fetch the rows from the table. Notice how this stage of the operation targets and returns the smallest possible set of people rows with the minimum expenditure of resources. Dimension tables are usually relatively small, so the cost of finding their primary keys is low; the bitmap indexes on the people table are relatively small, so scanning them for each towns key value is quite cheap, and the bitmap AND operation is very efficient. Remember - in many cases the most expensive action in a query is the work of collecting the actual rows from the largest table(s). A mechanism like the bitmap star transformation that manages to identify exactly the bare minimum number of rows from the fact table, with no subsequent discards, can give you a terrific performance gain. Once we have established that the critical section of the plan is appearing, we can worry about the extra work that may have to be done. For example, in the second query in fig. 4 we want columns from the towns table(s), as well as moving out one extra layer to get data from the states table. Because we have started with a star transformation to identify the critical people rows, we should now join this 'intermediate result set' back to the dimension tables with a minimum of extra work. So the questions we need to ask are - do we still see the same pattern of AND'ed bitmaps in the plan, and what can we see that shows us how the extra columns handled. To answer the first question, the inner part of the plan now looks like fig. 6. The same basic structure of the star transformation is clearly visible even though one (highlighted) part of it now includes a join to the states table. This is the critical section of code that ensures we locate the minimum set of people rows that are relevant, and use the minimum resources to get them. TABLE ACCESS (BY INDEX ROWID) OF PEOPLE BITMAP CONVERSION (TO ROWIDS) BITMAP AND BITMAP MERGE BITMAP KEY ITERATION TABLE ACCESS (FULL) OF TOWNS BITMAP INDEX (RANGE SCAN) OF PE_HOME_IDX BITMAP MERGE BITMAP KEY ITERATION NESTED LOOPS TABLE ACCESS (FULL) OF STATES TABLE ACCESS (FULL) OF TOWNS BITMAP INDEX (RANGE SCAN) OF PE_WORK_IDX Figure 6 Core of extended plan. What about the rest of the data though - how does Oracle retrieve the extra columns that have not been required so far. The full plan - simplified by replacing the section shown in fig. 6 by a single line - is likely to be something similar to the one shown fig. 7: NESTED LOOP NESTED LOOP NESTED LOOP {people rows from fig. 6 happens here} TABLE ACCESS (BY INDEX ROWID) OF TOWNS INDEX (UNIQUE SCAN) OF TO_PK (UNIQUE) TABLE ACCESS (BY INDEX ROWID) OF TOWNS INDEX (UNIQUE SCAN) OF TO_PK (UNIQUE) TABLE ACCESS (BY INDEX ROWID) OF STATES INDEX (UNIQUE SCAN) OF ST_PK (UNIQUE) Figure 7 Revisiting the fact tables. The sub-plan shown above simply says - for each row found in the people table get the home town using the primary key, then get the work town by primary key, then get the state by primary key. In effect, the query has been rewritten internally in the form shown in fig. 8, where we can more easily see the first half of the where clause becoming the driving bitmap access clause, and the second half of the clause being used to join back to the dimension tables. select wt.name, ht.name, st.name {pe.fact columns} from states st, towns wt, towns ht, people pe where /* bitmap drivers */ pe.id_town_home in ( select id from towns where ht.name = 'Birmingham' ) and pe.id_town_work in ( select wt.id from states st, towns wt where st.name = 'Alabama' and wt.id_state = st.id ) /* join back */ and ht.id = pe.id_town_home and wt.id = pe.id_town_work and st.id = wt.id_state ; Figure 8 Notional Internal rewrite. As ever, there are numerous variations on a theme. Oracle may be able to restructure b-tree information into bitmap form in memory, so extra conversion steps may appear in the plan. The bitmap star transformation can be applied to partitioned tables, so extra steps relating to partitioning may appear. The path can execute in parallel, introducing extra levels of messy parallel distribution elements in the plan. The join back of the dimension tables could be implemented as a series of hash joins, or sort merge joins instead of nested loop joins. Warnings One important detail to watch out for is that the bitmap star transformation is available only to the Cost Based Optimizer (after all, the Rule Based Optimizer doesn't even recognise bitmap indexes). So if you fail to generate statistics of a suitable quality, the optimizer may very easily switch into an alternative plan - typically a very expensive, multi-stage hash join mechanism. Of course, there is also the critical detail that you can't do the bitmap star transformation without using bitmap indexes, and these are only available with the Enterprise Edition. Another feature to watch out for is that under newer versions of Oracle, a recursive temporary table mechanism may be use to handle the dimension tables. At present tkprof, autotrace, and v$sql_plan have no method of showing you what is going on behind the scenes, so you will need the latest SQL code for reporting the results of an explain plan. For example, the second query of fig. 4 might produce an autotrace plan including lines like those in fig. 9: . . . TEMP TABLE TRANSFORMATION RECURSIVE EXECUTION OF 'SYS_LE_2_0' . . . BITMAP KEY ITERATION TABLE ACCESS (FULL) OF SYS_TEMP_0FD9D6603_333A5B BITMAP INDEX (RANGE SCAN) OF 'PE_WORK_IDX' Figure 9 Temp Table Transformation *extract). You may be able to guess this has something to do with the join between (work) towns and states because those two tables will have vanished from the plan. Bbut without the aid of the latest SQL for reporting the results of explain plan, you won't be able to see that the recursive step is creating and populating a temporary table using SQL like: INSERT INTO SYS.SYS_TEMP_0FD9D6605_333A5B SELECT WT.ID C0, WT.NAME C1, ST.NAME C2 FROM TEST_USER.STATES ST, TEST_USER.TOWNS WT WHERE ST.NAME='Alabama' AND WT.ID_STATE=ST.ID; The same enhanced code for displaying execution paths will also show that, in this case, the generated SQL uses a hash join. (Hint : always check the rdbms/admin directory of your ORACLE_HOME for the scripts utlxpls.sql and utlxplp.sql, which produce outputs for serial and parallel execution plans respectively. These changed quite significantly for Oracle 9.0, and then switched to using a new package called dbms_xplan in Oracle 9.2.) It is possible, by the way, that in some special cases you will want to turn off the temporary table feature - there have been reports of circumstances where the resource cost, particularly of memory or temporary space, becomes unreasonably high. If you hit this case, the star_transformation_enabled parameter has a third value (after true and false) which is temp_disable. This allows bitmap star transformations to take place, but disables the option for generating temporary tables. Conclusion The bitmap star transformation is a very powerful feature for making certain types of query very efficient. However, the dependency on bitmap indexes does require you to have a proper strategy for data loading before you can take advantage of this high-performance query mechanism. You also need to be aware that there are some very new features of explain plan that will require you to update your method for testing execution paths. References Oracle 9i Release 2 Datawarehousing Guide. Chapter 17. Oracle 9i Release 2 Supplied Types and PL/SQL packages Chapter 90 (dbms_xplan). $ORACLE_HOME/rdbms/admin utlxplan.sql utlxpls.sql utlxplp.sql dbmsutil.sql Jonathan Lewis is a freelance consultant with more than 17 years experience of Oracle. He specialises in physical database design and the strategic use of the Oracle database engine, is author of 'Practical Oracle 8I - Designing Efficient Databases' published by Addison-Wesley, and is one of the best-known speakers on the UK Oracle circuit. Further details of his published papers, presentations and seminars can be found at www.jlcomp.demon.co.uk, which also hosts The Co-operative Oracle Users' FAQ for the Oracle-related Usenet newsgroups. 'ftp MN(7NRTWY]_cehnr$ds|[ j   ! $ / 9 s x  # , @ E q x 1S]w%*u5<cih CJOJQJ 56>*CJ566Z'(MNcl|:; &$d%d&d'd/+D&$d%d&d'd/+D o#'(_`01S -01EVj)3FbqtuhPQDEFNafq| 16BMXci~a z { D E b  _`01S &$d%d&d'd/+D&$d%d&d'd/+D -01EVj)3Fbqtu&$d%d&d'd/+D&$d%d&d'd/+DuhP~&$d%d&d'd/+D&$d%d&d'd/+D&$d%d&d'd/+D&$d%d&d'd/+D&$d%d&d'd/+Dhihu-57DJNV 06iu % 6 9 B J g m ~ Y!`!!" ""H"N"p"{"2#8#9#L#f#m###$$% %_%e%%%%&(&,&4&556CJ&j9HA CJOJQJUVhmHnH CJOJQJjCJOJQJURPQDEFNafq|&$d%d&d'd/+D$&$d%d&d'd/+D$ 16BMXci~&$d%d&d'd/+D$&$d%d&d'd/+D$V%5Np  >?5 6 !!""##t$u$%%&&(-(L(Y(i(((((()4)X)))))*****+0+Z+++++#,$,,,---...-.2.>.I.T._.e.{....... /$/    ^V%5Np  >? & F&$d%d&d'd/+D&$d%d&d'd/+D&$d%d&d'd/+D$?5 6 !!""##t$u$%%&&(-(L(Y(i((&$d%d&d'd/+D & F & F & F4&*'8'^'d'''()X)))**++",e,l,{,,,,,,j-p-----////(0/0@0G0001182S2223334444444455555 666J7P7T7Z77799999:::;;<!<&<+<6<B<P<6CJOJQJCJ56CJOJQJ CJOJQJ56X((((()4)X)))))*****+0+Z++&$d%d&d'd/+D&$d%d&d'd/+D&$d%d&d'd/+D++++#,$,,,---...-.2.>.I.T._.e.&3$d%d&d'd/+D$&$d%d&d'd/+D&$d%d&d'd/+De.{....... /$/>/A/U/q////////&3$d%d&d'd/+D$&3$d%d&d'd/+D$&3$d%d&d'd/+D$$/>/A/U/q/////////001t111233@4A455 6 66-6R6X6m66666V8W8c888888888889999::<<<==v>w>>>> ? ? ?&?3???K?X?Y?{A|A   L//001t111233@4A455 6 66-6R6X6m666&=f$d%d&d'd/+D & F666V8W8c888888888889999::<<<==&=f$d%d&d'd/+DP<l<<<<<H=W= >,>X?Y?{A|A656 =v>w>>>> ? ? ?&?3???K?X?Y?{A|A & F+ 0P. A!"#8$8%88/ 0P. A!"#8$8%88 P+ 0P. A!"#8$8%88gDd)VB  S A? 2WBl@ESD`!WBl@ES',J|4sxWkAovRӘТҊVM@ UAh&0 MBC^=DB/ G?@CP*73u7YIfׅf߼} B6W찿zB.'s68 t1ʟ}oa m3b^QdBf2](~Ar"9ɦ RR.{gwJKdL(25N1Ad'ybүm:vӻo[r[kѽGd sj3S3WM0 13Qs/Pzmv&1],4E L]moV)TU/^ +'o B{|U*V0>ne*}g3H?#\;@?, Pg[{n5dCy|NoWGAo YnYn@[nRWEaCal`=l V=603ʪ0+g%ipLF({Nk84q+>²) _Uܤe`h:e}xלe՜57Ys_ip,Cjfq¸r~nEܰ;bN*N]$pXK ՅjX8}&>~ixܭުozk04vms}mT^ndhW:;8F8;(u}A ׋|j '+-ό4rFr\~F)Ꮀ) _UܤmօIME[pCbI-3ʪ-s֕ &W&8~dhh"&p&_GKh?j  !"#$%&'()*+,-./012345689:;<=>AMCDEFGHIJgfOPQRSTUWXYZ[\]_`abcdehjklmnopqrstuvwxyz{Root Entry  Fy84kL@Data 7WordDocument lObjectPoolr4k4k_1095252243 Fr4kr4k1TableBCompObjhObjInfo [$@$NormalmH <A@<Default Paragraph Font#-7O &#-7:O  OOON8(*@ )  (  H  #  N  3   NB  S DNB   S DNB  @ S D N   3  ? n@ P" .p#`0 ZB  S D" ."`0ZB  S D"@/p#`0ZB B S DP"@/"`0H  # A HB @ C DHB  C D HB @ C D \@ 0* P+ A TB B C D* *TB  C D0**TB B C D*P+H  #  % H  #  HB ! C DHB " C DHB $ C DH & # &2 HB '@ C DHB ( C DHB )@ C DB S  ? O)  4(p 4' [ 4&[U 4$  $4"  $4!  @4]@W 4  3 4S 4Sp 4  4 p 43 4  0 P4  0 P4  P4P 4C 4 C 4  4JKPCLP@ |O`@GzTimes New Roman5Symbol3& zArial"h#j#j!~0Jonathan LewisJonathan Lewis   FMicrosoft Word Picture MSWordDocWord.Picture.89qOh+'0 , H T ` lx!Relate article - Partition ViewsroselaJonathan Lewis-ona Normal.dotwObjectPool r4kr4kWordDocumentNSummaryInformation( VDocumentSummaryInformation8^Y ObjbjWW  ==8]  [[[$xb[ z[[[ [[fT =rkw Facts Dim 1 Dim 3 Dim 2 Dim 4 Parent Y Parent X O CJOJQJ jUmH#$*+1289BCLMNO#$*+1289BCLMNN N!]"#$%Oh+'0d   , 8DLT\ssJonathan Lewisona Normal.dotwJonathan Lewis2naMicrosoft Word 8.0@F#@ƟJk@ cnk՜.+,D՜.+,, hp|   j  Title 6> _PID_GUIDAN{DF5BD1B7-44CC-468C-BB3B-8CB45FB897F0}1Tableix$SummaryInformation(DocumentSummaryInformation8 CompObjjJonathan Lewis-366Microsoft Word 8.0r@^X@3@T 8@Tk 0՜.+,D՜.+,` hp  JL Computer Consultancy9Ej !Relate article - Partition Views Title 6> _PID_GUIDAN{D8D308A8-7055-40FA-BCFA-8A24622BF761}  FMicrosoft Word Document MSWordDocWord.Document.89q [8@8NormalCJOJQJhmH nH :@: Heading 1$/.@&5>*0@0 Heading 2@&5>*.. Heading 3@&5nn Heading 47$&$d%d&d'd/+D@&5>*CJOJQJll Heading 57$&$d%d&d'd/+D@&5CJOJQJ<A@<Default Paragraph Font66 Normal Indent 00+0 Endnote TextCJ,@,Header  o#6"6 Footnote Text5222 Double Indent&B&Action5>*."@.Caption xx5.b.program CJOJQJ\-@r\ Macro Text"  ` @ OJQJhmH nH bBb Body Text1&$d%d&d'd/+D CJOJQJ(U@( Hyperlink>*B*8C@8Body Text Indent6 bullet pointp & Fh>T h8V@8FollowedHyperlink>*B* X;|= l -l ^l h4&P<|A!'-4 uP?(+e./6=|A"$%&()+,./0235$/|A#*1h|=:8@0(  B S  ? _1089656015 _1089656108 _1089656196 _1089656695 _1089656714 _1095252224~=@@@@@@~=#+G a c ~ A F jrPW   '>@`bjqit%"+")******#*:*<*\*^*|**********++*+5+8+=+Y+^+a+p+u+z+}++++++g/l/013344555556667768B8:::;;;&;2;3;>;?;J;K;W;~=( NTcglq|9 G M c g 17EGVZjl*-4>GLcgu{chFLPWaeglrw}   '157=CHNSY_chjq~W]- 7 !!%"+"^#d#& &&&e(r()))******#*-*1*3*9*?*D*J*O*U*[*_*d*i*o*|************ ++%+(+E+I+U+X+q+t+++++// 22R2U255::~=Jonathan Lewis5C:\optimising oracle\publication\dbazine\bitmap_2.docJonathan LewisDC:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\AutoRecovery save of bitmap_2.asdJonathan LewisDC:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\AutoRecovery save of bitmap_2.asdJonathan LewisDC:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\AutoRecovery save of bitmap_2.asdJonathan LewisDC:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\AutoRecovery save of bitmap_2.asdJonathan LewisDC:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\AutoRecovery save of bitmap_2.asdJonathan LewisDC:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\AutoRecovery save of bitmap_2.asdJonathan LewisDC:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\AutoRecovery save of bitmap_2.asdJonathan LewisDC:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\AutoRecovery save of bitmap_2.asdJonathan LewisDC:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\AutoRecovery save of bitmap_2.asd|lϞL}xF~$V&,D%t%@ߜR,~nf/s;< e U[1?#s8cy>bB_~e*e.... OJQJo( OJQJo( OJQJo( OJQJo(hh. hhOJQJo(*@hhB*OJQJo(hh.@hhB*OJQJo(@hhB*OJQJo(@hhB*OJQJo(@hhB*OJQJo(@hhB*OJQJo(@hhB*OJQJo(@hhB*OJQJo(@hhB*OJQJo(= ~}|cy>_~ebB/s1?#e U;<s8*e[= @h hOJQJo(@{|=@GzTimes New Roman5Symbol3& zArial?5 zCourier New"CP hgf $jfFn{ 09= .2G!P 2dEk< Relate article - Partition ViewsJonathan LewisJonathan Lewis