ࡱ> jI( /./ 0`DArialsRomantt+ 0"DGaramondRomantt+ 0 DTimes New Romantt+ 00DWingdingsRomantt+ 0@DTahomagsRomantt+ 0"PDSymbolgsRomantt+ 0`DVerdanasRomantt+ 0"pDMiriamsRomantt+ 0@0.  @n?" dd@  @@`` <C,, ()  ,, 5 ()    21   >>..** -|H{XHJv303H" 1+^=Ax{zz   #  0e0e     A@ AjJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||s " 0e@        @ABC DEEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abN E5%  N E5%  N F   5%    !"?N@ABC DEFFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `ab ff@8uv?O ʚ;B}1ʚ;g4BdBd 0ppp@ <4dddd@w 0t+ g4;d;d 0p@ pp<4BdBd@w 0t+H <4!d!d@w 0t+___PPT10DTimes New Romantt 0DMiriamew Romantt 0 ___PPT92<:,?*+ SIGMOD 2006O  =-9Automatic Physical Design Tuning: Workload as a Sequence.:!(.(pSanjay Agrawal, Microsoft Research Eric Chu, University of Wisconsin-Madison Vivek Narasayya, Microsoft ResearchqqU) Automatic Physical Design Tuning DB applications more complex and varied. Considerable time spent on tuning. Reduce cost of ownership of RDBMS. Automatically recommend physical design. Supported by DB vendors. Database Engine Tuning Advisor, Microsoft Design Advisor, IBM SQL Access Advisor, OracleLo)Yo)Yl3(Microsoft Database Engine Tuning Advisor))&  "Workload as a Sequence: MotivationData warehousing Query by day, update at night. Set: No index recommended when update costs outweigh benefits. Sequence: May exploit benefits of indexes without incurring update costs. Insert  create and  drop of indexes to workload. Exploit order of statements.^ZZQZ?JQ;Set VS SequenceSet-based Recommendation is robust to changes in order of statement arrival. Can miss good recommendations compared to sequenced-based approach. Outputs are different Set: what indexes to create or drop? Sequence: what indexes to create or drop and where?t PPPYP CDX Model Workload as a SequenceYMotivation Problem Definition Optimal Algorithm Disjoint Sequences Greedy-SEQ Experiments&Z <e/Problem Setting$Cost(Si,Ci)  cost of executing Si with Ci. TC(C1, C2)  transition cost Sequence execution cost SNk=1((Cost(Sk,Ck) + TC(Ck-1,Ck)) + TC (CN,CN+1)b1      - H 9.Problem DefinitionGiven: Database D, workload W = [S1, & , SN], initial configuration C0, and storage bound M. Find configurations C1, C2, & , CN+1 such that Minimize sequence execution cost: SNk=1((Cost(Sk,Ck) + TC(Ck-1,Ck)) + TC (CN,CN+1) Storage of Ci d" M, for all i.U."1 ""                  ",9 Search SpaceGiven N statements and M indexes Sequence-based tuning 2M distinct configurations for each statement. 2M(N+1) possible execution sequences. Set-based tuning 2M configurations.7U7.m4Model Workload as a Sequence_Motivation Problem Definition Optimal Algorithm Disjoint Sequences Greedy Heuristic Experiments&`0 'Optimal Algorithm for Single-Index Case((&zNode costs: Cost(Si, { }) and Cost(Si,{I}). Edge costs: 0, IC, and ID. Cost of shortest path includes node and edge costs.{     $ ,  S >General Case  Multiple IndexesAt each stage, enumerate all possible configurations from the set of indexes. Algorithm linear in the number of nodes and edges of DAG. However, number of nodes in DAG is exponential in the number of indexes. M indexes => O(N*2M) nodes and O(N*2M) edges.bP.P   <Optimal Solution d.Search-Space PruningITechniques to reduce number of nodes: Cost-based Pruning Leverages shortest-path solutions of individual indexes. Prunes configurations at each stage without loss of optimality. Disjoint Sequences Divide-and-conquer approach. Splits the input sequence and candidate index set. Greedy-SEQ Guarantees a polynomial number of nodes.&ZZ9Z@ZZZ4Z Z)Z&9@  ) n5Model Workload as a Sequence_Motivation Problem Definition Optimal Algorithm Disjoint Sequences Greedy Heuristic Experiments&`0 Exploiting Disjoint SequencesbTwo sequences X and Y are disjoint if they do not share any statements AND indexes. Disjoint sequences are common E.g., server hosts multiple applications that touch different databases. Approach: Split workload into disjoint sequences. Solve each sequence independently. Merge to get final solution. Idea: DAG for each disjoint sequence has fewer nodes.rI h6PI F5.'Efficiency Gain with Disjoint Sequences((& b-8Merge solutions of W1, W2, and W3: No storage violationsb9     g0*Merge in the presence of storage violation++&*Suppose storage bound allows only 1 index.++J$Solution with Split and Merge. o6Model Workload as a Sequence_Motivation Problem Definition Optimal Algorithm Disjoint Sequences Greedy Heuristic Experiments&`C =Greedy ApproachGoal: Explore a polynomial number of good configurations. Run shortest path over the DAG constructed with these configurations. Solution close to optimal. Greedy-SEQ: adaptation of existing greedy technique for the sequence model.^HZzHZHZLHZzL j2 Greedy-SEQkSteps of Greedy-SEQ: Get optimal solution for each index. Record configurations. Initialize current best to be the lowest-cost solution seen so far. Improve current best by combining with other solutions and resetting current best. Record new configurations of current best. Repeat until no more improvement. Run shortest-path over configurations collected. fHZnZ"HZ3nZ"3 i1$Combining Two Single-Index Solutions%%! y9$Combining Two Single-Index Solutions%%! :Greedy-SEQ: Greedy Approach]Get optimal solution for each index. Record configurations. Initialize current best to be the lowest-cost solution seen so far. Improve current best by combining with other solutions and resetting current best. Record new configurations of current best. Repeat Step 3 until no more improvement. Run shortest-path over configurations collected. nnZ)HZ3nZ)0End-to-End Solution p7Model Workload as a Sequence_Motivation Problem Definition Optimal Algorithm Disjoint Sequences Greedy Heuristic Experiments`T > Sequence VS Set-based approaches% improvement relative to the optimal set-based solution. Sequence is better in the presence of updates and/or storage bound is low.Zb%Greedy-SEQ VS ExhaustivezGreedy-SEQ s much faster with minimal degradation in quality.2u8 Effectiveness of Split and Merge.!! ConclusionSequence model allows more optimization opportunities than set model. Model the problem as finding the shortest path over a DAG. Heuristics give nearly optimal solutions with much better performance./d 02 3 8:;=?KNY"c*f+h,q-r.s/t0v1z2{3|4}5~6789;<   0` 3333ff3` 3333f33ff3` "3333̙ff3` Kf3̙` &e̙3g3f` f333̙po7` ___f3̙;/f9` ff3Lm` ff3LmNLm>?" dd@*?nAd@q<nAqFLK#M n?" dd@   @@``PR    M`2p>> &(    H? ?" `}  X Click to edit Master title style!!  @  H? ?" `  RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S    6 #" `] `}  ^*     6 #" ``   d*       6h #" `] `}  d*       C @ABCDE FjJ@3"0`B  s *DjJ"0 `0H  0޽h ? ff3LmNLm___PPT10i.  +D=' = @B + Edge u 0  (    H(? ?"@ ( X Click to edit Master title style!!    Hx(? ?"  ( [#Click to edit Master subtitle style$$    6( #" `] `} ( ^*     6( #" `]}  ( d*       6( #" `] `} ( d*       C @ABCDE F8c@3"@B  s *DjJ"  ,$ 0H  0޽h ? ff3LmNLm___PPT10i.  +ityD=' = @B +u 0 zr  (    0p, P   , P*    0h ,    , R*  d  c $ ?  ,  0|#,  0 , RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6(, _P  , P*    6x-, _  , R*  H  0޽h ? 3380___PPT10.H|sU5  (    0  P    X*   0     Z*   6  _P   X*   6p _   Z* H  0޽h ? 3380___PPT10.5~Srv  0  *(  r  S D(`~ ( x  c $|( @ ( H  0޽h ? 33___PPT10u..E|+D=' = @B + u" 0 p `0(  `x ` c $[, 0  , x ` c $\, ` , H ` 0޽h ? ___f3̙;/f9___PPT10i.H|PE+D=' = @B + u2 0 \(  x  c $Xb,   ,   Z ??\    Z ?? pP   Tg, ??b  VQuery Optimizer (extended) 0 2  Tk, ??P @  TMicrosoft SQL Server 20050 2vb  N?? 0B   fD??  R   Z??@    Z ??     T|p, ??>i  \Database Engine Tuning Advisor"0(2B    `D??  2    ` ?? i   Tr, ??p D  JRecommendation 0 2  C xw, 1?? @  Z What-if , 0 2   S ~ 1??`   C x( 1??@P T Applications*0 2 B  c D8c??pB  3 rD8c?? B @ 3 rD8c?? B  3 rD8c??  B  C xD8c?? 2   ` ??i`  T, ?? DWorkload 0 2 B  BDjJ?"0@NNN?N` E  H,,G}5HR jJ?"6@`NNN?N ,$D 0 [Set of queries, updates(0s  TZ؈,GHo jJ?"6@`NNN?N ,$D 0 }9Set of indexes, materialized views, horizontal partitions(:07H  0޽h ?/  3333t l ___PPT10L +ډӹDP ' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(DX' =%(D|' =A@BBBB0B%(D' =1:B#ff0000*z3>!Bstyle.color= `B<*D|' =A@BBBB0B%(D' =1:B#ff0000*z3>!Bstyle.color= `B<*:++0+0 ++0+0 ++0+0 ++0+0 +l  u 0L0   P, (  r  S ,   ,   S , ` <$@ 0 ,   S x,"` op @0 Bl x 0 ,x 0,$D 0ZB  s *D  NB  S D x NB  S D"x # NB  S D x   S ,"` 0 DUpdates Night0  S T,"`- 0 B Queries Day 0   S t,"` 0 J Queries Day" 0 NB  S D}x ~ <l  0  + 0 ,$D  0  S ,"` p  DCreate Indexes06b B  } -   S  ,"` 0  DCreate Indexes0  S ,"` p  B Drop Indexes 0 6b B   I 6b B   e H  0޽h ? ff3LmNLm___PPT10..M|0Q+D' = @B DY' = @BA?%,( < +O%,( < +D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*1%(D' =-g6B fade*<3<*1D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*,%(D' =-g6B fade*<3<*,D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*1p%(D' =-g6B fade*<3<*1pD' =%(Dy' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =4@BBBB%()))D' =1:Bvisible*o3>+B#style.visibility<*+%(D' =+4 8?\CB#ppt_xBCB#ppt_xB*Y3>B ppt_x<*+D' =+4 8?dCB0-#ppt_h/2BCB#ppt_yB*Y3>B ppt_y<*+D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =-g6B fade*<3<*pD' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-g6B fade*<3<* +  u 0 "  @(  r  S , `  , r  S , `  ,   S ,"`  ? Updates  0   S ,"`-  >Queries  0   S &"`   G Queries " 0 8 @ `  @N  0   @ 0   C ,"` p  DCreate Indexes0(b B } -   C (,"` 0  DCreate Indexes0  C ,"` p  B Drop Indexes 0 (b  B  I (b  B  e    C , "`o` @0 ZB   s *DNB  S D h NB  S D"h #NB  S D h NB  S D}h ~H  0޽h ? ff3LmNLm___PPT10i._C+D=' = @B +} u  0 @$(  r  S , `  , r  S l, `& , H  0޽h ? ff3LmNLm___PPT10i.J|+D=' = @B +1 u+ 0 zr (  r  S pY( `  (   S Z( `<$ 0 (   <[( jJ?"6@ NNN?N ,$ 0 :Workload: S = [S1, S2, & , SN]^0 2   ll @ @,$D 0   <d( jJ?"6@ NNN?N p DS2&0(2   <i( jJ?"6@ NNN?N DS1&0(2   <g( jJ?"6@ NNN?N   DS3&0(2   <r( jJ?"6@ NNN?N@ DSN&0(24l  ,$@ 0B  BDjJ?"0@NNN?N```B  <DjJ?"0@NNN?NppB  <DjJ?"0@NNN?NB  <DjJ?"0@NNN?NB   <DjJ?"0@NNN?NP P B B BDjJ?"0@NNN?N ``B  <DjJ?"0@NNN?N` `x  <y( jJ?"6@ NNN?N@ ,$ 0 HSi {Select, Insert, Delete, Update}6%0 2"ll  ,$D 0  <t( jJ?"6@ NNN?N@ DC1&0(2  <D( jJ?"6@ NNN?N DC2&0(2  <( jJ?"6@ NNN?N@  DC3&0(2  <( jJ?"6@ NNN?N DCN&0(2tl    ,$D 0  <<( jJ?"6@ NNN?N  HCN+1(0(2   <8( jJ?"6@ NNN?N0 DC0&0(2H  0޽h ? ff3LmNLm___PPT10.6` + eD' = @B D}' = @BA?%,( < +O%,( < +DN' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D ' =%(DP ' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*,%(D' =-g6B fade*<3<*,D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*,I%(D' =-g6B fade*<3<*,ID8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Ib%(D' =-g6B fade*<3<*IbD8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*b%(D' =-g6B fade*<3<*b++0+0 ++0+0 ++0+0 +} u* 0 $$(  $r $ S G `}  G r $ S G  `V G H $ 0޽h ? ff3LmNLm___PPT10i.i|p)+D=' = @B +} u 0 ($(  (r ( S G `}  G r ( S G ` G H ( 0޽h ? ff3LmNLm___PPT10i.k|J+D=' = @B + u- 0 0(  x  c $G `  G x  c $G `& G H  0޽h ? ff3LmNLm___PPT10i.J|+D=' = @B +B u 0 7{4d     (  4r 4 S DfG `  G  4 S DgG@ `<$ 0 G z w u4 ,$@ 0 (4 S hiG(4"` NSOURCE,0G62 *4  @]w +4 S @nG+4"` 9{ }0  h4# ,$D 0+@ +% g4+%62 B4  +% C4 S rGC4"`` P 9{ }0 D4 S hlGD4"` ] DESTINATION6 0 GO   _4# `p,$D  0 F4 S 4{GF4"`p I0,0GTB G4 c $D @TB H4 c $D l I4 S  GI4"` 0 vIc>0GO   q4#  ,$D  0 K4 S GK4"` p I0,0G M4 S ؉GM4"`  ^Id@0GOTB N4 c $D@ TB O4 c $Dp TB P4 c $DSK TB Q4 c $Dp  R4 S DGR4"`0  xIc@0GO S4 S GS4"`  I0,0G  f4# `pk,$D  0TB U4 c $D ;0TB V4 c $D  W4 S ؠGW4 "`PA ^Id@0GO X4 S GX4 "` q I0,0GXl RUb  {4RUb ,$@ 0"T RRb  v4# RRb 62 -4  RD .4 S G.4"`\R 9{ }062 /4  `Rb  04 S ȯG04"` !  9{I}0 Z4 S tGZ4"`U NS100 l  y8  o4#  8 ,$D 0"T  ,h  e4#  y8 62 74    , 84 S $G84 "`@u 9{ }062 94    h  :4 S dG:4 "`@5  9{I}0 [4 S G[4"` < NSN00 z   P  t4  P ,$@ 062 24     34 S PG34"` N`  9{ }062 44    P  54 S @G54"` 2  9{I}0 \4 S G\4"` @  NS200  ]4 BxG]4 ??"` @ ,$ 0 h"DAG for single index, N statements*#0H"8l  P  z4 P ,$D  0ZB x4 s *D P ZB y4 s *D P H 4 0޽h ? ff3LmNLmm$e$___PPT10E$.p|U!+rD#' = @B Dd#' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*]4%(D' =-g6B fade*<3<*]4DA' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*{4%(D' =-g6B fade*<3<*{4D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*t4%(D' =-g6B fade*<3<*t4D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*o4%(D' =-g6B fade*<3<*o4D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*4,%(D' =-g6B fade*<3<*4,D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*u4%(D' =-g6B fade*<3<*u4D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*h4%(D' =-g6B fade*<3<*h4D| ' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*_4%(D' =-g6B fade*<3<*_4D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*q4%(D' =-g6B fade*<3<*q4D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*z4%(D' =-g6B fade*<3<*z4D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*f4%(D' =-g6B fade*<3<*f4D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*4,G%(D' =-g6B fade*<3<*4,GD' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*4G{%(D' =-g6B fade*<3<*4G{+p+0+40 ++0+]40 +D/ u 0 ":G<@(  <r < S 8G `  G  < S G `0<$ 0 G  < 6` DS1&   < 6h ` DS2&   < 6  @` DSN&  l2 < 6"`  < Bp SC114   l2  < 6"`   < B p SC124   l2  < 6"`   < B4 p SC1N4   l2 < 6"`   < B0   SC014   l2 < 6"`   < 6X$0   SC024   l2 < 6"`  < 6)0  SC0N4   l2 < 6"` < B/ SCF14   l2 < 6"`  < BH4  SCF24   l2 < 6"`  < B9  SCFN4    < B? SCi14   l2 < 6"`  < 6D  SCi24   l2  < 6"`  !< B4J  mCiN4   XB "< 0DXB #< 0DXB $< 0Dd XB %< 0DMNXB &< 0DMNXB '< 0D>?XB (< 0D  XB )< 0D67XB *< 0DXB +< 0DXB ,< 0DXB -< 0D> ?XB .< 0DM NXB /< 0D6 7XB 0< 0D  RB 1< s *D XB 2< 0D ?XB 3< 0DM MXB 4< 0D' (XB 5< 0D ?XB 6< 0D  0 XB 9< 0DXB :< 0D{e l2 ;< 6"`0W << 6(W `CN+1&  l2 =< 6"` >< 6L\ DC0&  l2 C< 6"`( G< <` jJ?"6@ NNN?N`0,$ 0 J EXHAUSTIVE$ 0(2 H < 0޽h ? ff3LmNLm___PPT10.| -+u#BD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<N%(D' =-g6B fade*<3<*<ND' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<N%(D' =-g6B fade*<3<*<ND' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*G<%(D' =-g6B fade*<3<*G<D(' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<%(D' =-g6B fade*<3<*<D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<%(D' =-g6B fade*<3<*<+p+0+<0 ++0+G<0 +  u9 0 !  P  (   x   c $w `   F   S X99?0F p6[    p6[ T    #  }[ h2   s *fMMM"` c   Hz,t,t fMMM NRecommendation$0ATB   c $D  TB   c $D  T @<&  # `1   Nh,t,t fMMM"`@& Candidate set of structuresf0 CCCC Ch   s *fMMM"`@<   H,t,t fMMM"` @S  eSolve sequence using EXHAUSTIVE* 0Ch   s *fMMM"``P h   s *fMMM"`p6 T pL.  # LN   N,t,t fMMMp . USequence, Constraints$0Ah2   s *fMMM"`pLTB   c $D @ H   0޽h ? ff3LmNLm___PPT10i.}04+D=' = @B +} u3 0 p$(  r  S  `   r  S l0 `  H  0޽h ? ff3LmNLm___PPT10i.(+D=' = @B + u. 0 0(  x  c $' `   x  c $, `&  H  0޽h ? ff3LmNLm___PPT10i.J|+D=' = @B +j u 0  DP(  Dr D S |1 `}    D S |20 `<$ 0  H D 0޽h ? ff3LmNLmRJ___PPT10*.|b)+[W_D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*DT%(D' =-g6B fade*<3<*DTD(' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*DTr%(D' =-g6B fade*<3<*DTrD8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Dr%(D' =-g6B fade*<3<*DrD ' =%(DP ' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =-g6B fade*<3<*DD8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =-g6B fade*<3<*DD8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =-g6B fade*<3<*DD8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D-%(D' =-g6B fade*<3<*D-D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D-c%(D' =-g6B fade*<3<*D-c+8+0+D0 +;7 u 0 ) ) 0׼      ((  r  S PI `   l 0p ͼ0p,$D 0D@ 00@ Ƽ0`p z BM jJ?"6@ NNN?NpY@ DS2&0(2 { BP jJ?"6@ NNN?NY@ DS1&0(2 | BPU jJ?"6@ NNN?NPP7 DS3&0(2 } BY jJ?"6@ NNN?NY @ DS7&0(2B  HDjJ?"0@NNN?N0B  BDjJ?"0@NNN?N ` PB  BDjJ?"0@NNN?N```PB  BDjJ?"0@NNN?N`PB  BDjJ?"0@NNN?N`PB  BDjJ?"0@NNN?N ` PB  BDjJ?"0@NNN?N ` PB  BDjJ?"0@NNN?N ` P  B_ jJ?"6@ NNN?N P` 7 DS5&0(2  Bd jJ?"6@ NNN?N0 P 7 DS4&0(2  BXi jJ?"6@ NNN?N P@7 DS6&0(2B  Hm jJ?"6@ NNN?N0P  {I1,I2,I3}^ 0    Ǽ <$v jJ?"6@ NNN?N0w 9W0.l `P@ ռ P,$D 0  B+B#style.visibility<*ͼ%(D' =-g6B fade*<3<*ͼD' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*ּ%(D' =-g6B fade*<3<*ּD ' =%(D' =%(D[' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*ռ%(D' =-g6B fade*<3<*ռD' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*׼%(D' =-g6B fade*<3<*׼+p+0+ּ0 ++0+׼0 +K u4 0 p:h:@ep9(  r  S X̫ `@   W z 0p  p0,$@ 0  S Ϋ"`}p` LDEST,0GJ2  # "`?TB  c $DPP  S ѫ"`0 sI1cT0GOO   S  ث "`p ` NS100    S `ݫ "`e p C NS300    S x "`0p` KSRC,0G   S  "` P{I1}00 J2   # "`TB  c $DOE P  S h"`e   P{I1}00 J2  # "`P    S "` p C NS400 TB  c $D N P  S "`   9{ }0J2  # "`    S "` 0  sI1dT0GOOTB  c $D PP  S "`  9{ }0J2  # "`;  S "`e\ 9{ }0  S  "` W1 = [S1,S3,S4]r0    ,z PP  D @0 ,$D 0  S "`pPP LDEST,0G  S 8"`P@ NS700 TB  c $D/  S "` c sI3cT0GOO   S $ "`3  P{I3}00 J2 ! # "`S TB " c $DJ2 # # "`S  $ S $*$"`3 P{I3}00 J2 % # "`::  & S /&"`c8  9{ }0 ' S ,'"`  k W3 = [S7]F 0   ( S $9("` KSRC,0G l 0z0  0z,$@ 0 F S =F"` NS200  G S +B#style.visibility<*%(D' =-g6B fade*<3<*D[' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D[' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =-g6B fade*<3<*DD' =%(Dy' =%(D[' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D[' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D[' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*+HD u, 0 ..T]PK.(  r  S  `}   r  S Xp  2 Q BjJ?"6@`NNN?N@ ` ,$@ 08l P UP,$D 0 * C *"`P LPu is not a valid solution as it has configurations with storage violation.BM0JN n0  + " c , C ,"`0   NS200 D2 -  "`=   . C ."`nm N@  i{I1,I2}F0   / C T /"`0   NS300 D2 0  "`=  1 C p1"`@   y {I1,I2}P0  N @ I  2 sNB 3 S D  NB 4 S D  (2 5 h9  NB 6 S D   7 C (7"`0   NS100  8 C L8"`@0   KSRC,0G 9 C "9"`   P{I1}00 D2 :  "`=  D2 ;  "` - D2 <  "` - D2 =  "`{-  D2 >  "`y-  D2 ?  "`s-  NB @ S D  A C )A"`  NS400  B C .B"` ] /  P{I2}00  C C <4C"`  NS500  D C |9D"` p B  P{I2}00 NB E S D  F C >F"`   NS600  G C CG"`p q  :{ } 0NB H S D   I C GI"`   NS700  J C LJ"`p F  P{I3}00 NB K S D  NB L S D ~  M C $RM"`p u  P{I3}00  N C $WN"`i I  :DEST0 S C ZS"`@0 9{ }0  S ^"` p P ,$ 0 LdPu = Merge P1, P2 and P3 to get a valid solution.302l ;   Z;  ,$@ 062    + ` TB  c $Do    S k"`P;   NS100    S Dp "`; %  KSRC,0G   S t "` [ d  P{I1}00 J2   # "`+ p  # S 8z#"`@[ `K  9{ }0(l l;  ~  [; l ~ ,$D 0TB   c $Dl     S ~ "`0; `  NS200 J2  # "` h~   S 䃱"`@; ]   NS300 J2  # "` e ~ TB  c $Dh  TB  c $De    S H"` q   ` {I1}: 0  $ S $"`0[ P.  P{I2}00   S @"` `d  @0  l  ~  ]  ~ ,$D 0J2  # "`  b ~ J2  # "`  c { J2  # "` [~ J2 ! # "` X~ J2 % # "` T~   S ԙ"`P ; M   NS400   S <"` [ k .  P{I2}00   S "`0 ; @   NS500   S "`0 [ .  P{I2}00 TB  c $Db   S `"`@; dI  NS600   S "`@[ R^  9{ }0TB  c $D^     S  "` [ p2  P{I3}00 TB " c $D[  TB & c $DX   ' S '"`[ :  P{I3}00  ( S ("`   :DEST0 ) S ű)"`P; [  NS700 ` X Bʱ ?" @,$ 0 DNote that cost of Pu is a lower bound on cost of any valid solution.*E 11H  0޽h ? ff3LmNLm___PPT10.G(+mDU' = @B D' = @BA?%,( < +O%,( < +D ' =%(D' =%(D[' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*U%(D' =-g6B fade*<3<*UDq' =%(D' =%(D[' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*Q%(D' =-g6B fade*<3<*QD+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*Z%(D' =-g6B fade*<3<*ZD+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*]%(D' =-g6B fade*<3<*]D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*[%(D' =-g6B fade*<3<*[D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*X%(D' =-g6B fade*<3<*X+p+0+0 ++0+X0 + u 0 @8 0(  0x 0 c $ `   L 0 c $X99?0 0 TF,,t,t0fMMM ^ USequence, Constraints$0A/ 0 Tȷ,t,t0fMMM"`@& Candidate set of structuresf0 CCCC CRB 0 s *D  8   0 }n2 0 0fMMM"` c  0 N,t,t 0fMMM NRecommendation$0ARB  0 s *D0 f 0 0fMMM"`@<8 N 0`?  0 N,t,t 0fMMM"`N /Apply Split operator to get disjoint sequences `00GG#GCn 0 0fMMM"`98 ` 0  0@0   0 N,t,t 0fMMM"`P`   z2Solve each sequence independently using EXHAUSTIVE,302Cn 0 0fMMM"`` 0 f 0 0fMMM"`L0 f2 0 0fMMM"`LNRB 0 s *D> RB 0@ s *D 8 r 9  0 J 4 0 N,t,t0fMMM"`w u  ( Merge results of disjoint sequences \)0CGGCn 0 0fMMM"`r 9 RB 0 s *D ?' 0 <  jJ?"6@ NNN?N P ,$ 0 I or GREEDY-SEQ 0 2H 0 0޽h ? ff3LmNLmz___PPT10Z.}04+D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =-g6B fade*<3<*0+8+0+00 + u/ 0 00(  x  c $ `   x  c $( `&  H  0޽h ? ff3LmNLm___PPT10i.J|+D=' = @B +  u; 0 0r(  0x 0 c $ `    0 c $0# `<$D 0  "hu=H 0 0޽h ? ff3LmNLm  ___PPT10 .Uz+YD ' = @B DM ' = @BA?%,( < +O%,( < +D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*0:%(D' =-g6B fade*<3<*0:D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*0:%(D' =-g6B fade*<3<*0:D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =-g6B fade*<3<*0D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =-g6B fade*<3<*0+ u5 0 f(  r  S 2 `}     S ; `<$D 0  "hu=H  0޽h ? ff3LmNLm___PPT10.Uz+YDX' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*T%(D' =-g6B fade*<3<*TD' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*T%(D' =-g6B fade*<3<*TD' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*9%(D' =-g6B fade*<3<*9D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*9l%(D' =-g6B fade*<3<*9l+M u6 0 )F!F{@P aE(  ~  s *p]0p    8 p p  6( @ FS1(    6`  P  FS2(    6c  FSN(    6h    FSK(     6|V( ` FSL(    6to  \S0>    6t p ^SN+1>  j @ ` }t2   6"`!   BzB ^{I1}> t2   6"`t2  6"`   B  :{}   B< :{} t2  6"`, k   B @  D  t2  6"`  B L{}. `B  0D@`" ``B  0D`w``B  0D ` `  B`1 LI1.   B$0   ^{I1}> t2  6"` >   B  _  ^{I1}> `B  0D ` ``B  0D0``t2   6"`0 ! B袲 L{}. fB " 6D```8 T ` '# n2 ( 0"`! ) <p"` :{} n2 * 0"`n2 + 0"`  , < :{}  - <  :{} n2 . 0"`, k  / <p ,  D  n2 0 0"` 1 <x L{}. ZB 2 s *D@L" LZB 3 s *DLwLZB 4 s *D L L 5 <|`1 LI2.  6 <²0   n{I2}N n2 7 0"` >  8 <Ȳ _  n{I2}N ZB 9 s *D L LZB : s *D0LLn2 ; 0"`0 < <ϲo {I2}` `B = 0D`LLB  BD1?"0@NNN?NPpl  p   p ,$D 0`B j 0D ` T   x# 0  t2 l 6"` @  m 6ز  {I1,I2}         T   y#  t2 n 6"` P - o B"`  {I1,I2}        fB q 6D fB r 6D p `B p 0D ` fB s 6D C lB t <D ! l    ,$D 0tb  63"``=  U B| \ 1  D  T ` @\  # ` @\ t2 ? 6 "`` !\  @ B "`` @  ^{I1}> `B I 0D  T  :  ~#  : t2 Q 6 "` :  R 6    :{} T    #   t2 P 6 "`   S B     :{} T    #   t2 V 6 "`   W B$    L{}. `B Y 0Dp p t2 a 6"` 0  b B  ?  {I2}` `B c 0D0p |  [ B    qI1,I2P `B C 0D@ " fB D 6D T , ` \  # ` ` \ @ , ` k \  , ` k \ t2 A 6 "`, ` k \  B Bl   <  D   E B 0 l ,  ^{I1}> T  l _ h  #  l _ h t2 F 6 "` l > h  G B  l _ ,  ^{I1}> fB H 6DP  T l 0h  # l 0h t2 J 6 "`l 0h  K B,$ l ,  L{}. T  Q  #  @ t2 N 6 "` Q  O B) 4   :{} `B X 0D@p R } fB Z 6D | } T \   # \  t2 T 6 "`\   \ B. `   n{I2}N T 0    #   _  t2 ] 6 "`0  n   ^ Bx4 0   n{I2}N `B ` 0D0| } `B d 0D@ ` @ `B e 0D@, 0 @ fB f 6DP P @@ fB g 6D , p `B h 0D0, @ fB  6DP  H  0޽h ? ___ff3ff ___PPT10.:+9(D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*+D u8 0 +C#CyyB(  ~  s *B0p   fb  03"``=   <HE\ 1  D  L ` @\  # ` @\ n2  0"`` !\   <H"`` @  ^{I1}> XB  0D>  tL  :   #  : n2   0"` :    0'   :{} L     #   n2   0"`    <R   :{} L    #   n2  0"`    <V   L{}. B  T?D>?"0?@NNN?Np p f2  0"` 0   <X\ ?  {I2}` B  T?D>?"0?@NNN?Np 0| XB  0D> ` L   #  0  n2  0"` @    0d  {I1,I2}        L   #  n2  0"` P '  <l"`  {I1,I2}        XB  0D XB  0D p RB  s *D `    <v   qI1,I2P RB ! s *D @" XB " 0D L , ` \  ## ` ` \ N , ` k \  $ , ` k \ n2 % 0"`, ` k \  & <~  <  D   ' <ā0 l ,  ^{I1}> L  l _ h  (# l _ h n2 ) 0"` l > h  * <Ї l _ ,  ^{I1}> XB + 0D P  L l 0h  ,# l 0h n2 - 0"`l 0h  . <܍l ,  L{}. L  Q  /#  @ n2 0 0"` Q  1 <4   :{} RB 2 s *Dp @R } XB 3 0D| } L \   4#  \ n2 5 0"`\   6 <䘳`   n{I2}N L 0    7#  _  n2 8 0"`0  n   9 <d0   n{I2}N RB : s *D| 0} RB ; s *D @` @ RB < s *D, @0 @ XB = 0DP P @@ XB > 0D, p RB ? s *D, 0@ ^B @ 6D> C ^B A 6D ! d F p B p C 0@ FS1(   D 0X P  FS2(   E 0 FSN(   F 0    FSK(   G 0` FSL(   H 0`Z \S0>   I 0³p ^SN+1>   N ` J n2 K 0"`! L <0ȳB ^{I1}> n2 M 0"`n2 N 0"`  O <γ  :{}  P <ҳ :{} n2 Q 0"`, k  R <׳ @  D  n2 S 0"` T <,ڳ L{}. ZB U s *D@`" `ZB V s *D`w`ZB W s *D ` ` X <`1 LI1.  Y <0   ^{I1}> n2 Z 0"` >  [ <x _  ^{I1}> ZB \ s *D ` `ZB ] s *D0``n2 ^ 0"`0 _ < L{}. `B ` 0D```8 T ` a# n2 b 0"`! c <$"` :{} n2 d 0"`n2 e 0"`  f <H :{}  g <D :{} n2 h 0"`, k  i << ,  D  n2 j 0"` k <  L{}. ZB l s *D@L" LZB m s *DLwLZB n s *D L L o < `1 LI2.  p <0   n{I2}N n2 q 0"` >  r <  _  n{I2}N ZB s s *D L LZB t s *D0LLn2 u 0"`0 v <o {I2}` `B w 0D`LLB x BD1?"0@NNN?NPpB y Z?D>?"0?@NNN?N P  H  0޽h ? ___ff3ff___PPT10i.:+D=' = @B + u7 0 F(  x  c $* `}     c $/ `  "hu=H  0޽h ? ff3LmNLm___PPT10.Uz+D' = @B Dw' = @BA?%,( < +O%,( < +DS' =%(D' =%(D' =4@BBBB%(/%,( < +D' =1:B#ff0000*z3>!Bstyle.color= `B<*DS' =%(D' =%(D' =4@BBBB%(/%,( < +D' =1:B#ff0000*z3>!Bstyle.color= `B<*+^+k u 0 z d(  dr d S = `   `F p` d p`T d c $X99?` d TB,t,tdfMMMp . USequence, Constraints$0A7 d TlF,t,tdfMMM"`@& Candidate set of structuresf0 CCCC CZB d s *D  n2  d 0fMMM"` c  d N0%(,t,t dfMMM NRecommendation$0AZB  d s *D %  d N|P,t,t dfMMM"`N /Apply split operator to get disjoint sequences F00CC$CZB  d s *D  `  d NV,t,tdfMMM"`P`   @Solve each sequence independently using EXHAUSTIVE or GREEDY-SEQ(A0@Cn d 0fMMM"`@<n d 0fMMM"`9n d 0fMMM"`` 0 n d 0fMMM"`L n2 d 0fMMM"`pLZB d s *D  ZB d s *D   d N(,t,tdfMMM"`w u  ( Merge results of disjoint sequences D)0CCCn d 0fMMM"`r 9 n d 0fMMM"`9ZB d s *D  = d Nl`,t,tdfMMM"` )Apply cost-based pruning on each sequenced*0CCCC CH d 0޽h ? ff3LmNLm___PPT10i.}04+D=' = @B + u0 0 P0(  x  c $ `   x  c $xQ `&  H  0޽h ? ff3LmNLm___PPT10i.J|+D=' = @B + u< 0 "8c(  8x 8 c $ `   ~ 8 s *`@  %   "8 #""676]   8 <$ ? F>6___PPT9 C28%$(" d& 8 < ? VNF___PPT9(  T 25%4(" d#2 8 < ? VNF___PPT9(  `TPCH-22-I-10-END4(" d# 8 < ?m  F>6___PPT9 C16%$(" d&  8 < ? m  VNF___PPT9(  T 22%4(" d#2  8 <К ?m VNF___PPT9(  `TPCH-22-I-10-MID4(" d#  8 < ?6 m F>6___PPT9 B0%$(" d2&  8 << ? 6 m VNF___PPT9(  T 19%4(" d#)  8 <h ?6 m VNF___PPT9(  WTPCH-224(" d#* 8 < ? 6 VNF___PPT9(  XM = 3 GB4 " d#, 8 < ? 6 VNF___PPT9(  Z M = 1.2 GB4 " d #* 8 < ? 6 VNF___PPT9(  XWorkload4 " d#`B 8 01 ?  `B 8 01 ?`B 8 01 ? `B 8 01 ? `B 8 01 ?6 6 `B 8 01 ? `B 8 01 ? `B 8 01 ?m m `B 8 01 ?  H 8 0޽h ? ff3LmNLm___PPT10i.}@B&+D=' = @B +{ u 0 0 u"(  x  c $t `}   x  c $ 0@   }  u #""F}  *  <? = } F>6___PPT9 hNot available >(" d2(" d+  <?= } F>6___PPT9 i)Exhaustive was terminated after 24 hours $*(" d*'  <?= } VNF___PPT9(  UTPCH-222 " d#  <4? = F>6___PPT9 D2.3%$(" d  <h!? = F>6___PPT9 F98.4% $(" d*  <8%?= VNF___PPT9(  X TPCH-5-M-52 " d #  <'? F>6___PPT9 C<1%$(" d  <.? F>6___PPT9 D50% $(" d&  <0?VNF___PPT9(  TTPCH-32 " d#:  <5? VNF___PPT9(  h% reduction in quality6(" d#?  <d8? VNF___PPT9(  m% reduction in running time6(" d#*  <??VNF___PPT9(  XWorkload4 " d#ZB  s *1 ?ZB  s *1 ?} } ZB  s *1 ?} ZB   s *1 ?} ZB # s *1 ?ZB % s *1 ?} ZB ( s *1 ?  } ZB , s *1 ?ZB 9 s *1 ?= = H  0޽h ? ff3LmNLm___PPT10i.)} !G+D=' = @B + u1 0 p@(  ~  s *h+ `}     @0  @ #""YX[@    B\f jJ?"6@ NNN?N 0 4___PPT10 J___PPT9,$ R3.0%2(" d"   Bg jJ?"6@ NNN?Np z0___PPT10:___PPT9 G71.4%&(" d"   Blj jJ?"6@ NNN?N  p z0___PPT10:___PPT9 [ WKLD1-LOW6 " d #"   B`c jJ?"6@ NNN?N < 0 4___PPT10 J___PPT9,$ P0%2(" d"  Bq jJ?"6@ NNN?Np< z0___PPT10:___PPT9 G89.9%&(" d"  Bw jJ?"6@ NNN?N < p z0___PPT10:___PPT9 WWKLD16 " d#"H  Bp| jJ?"6@ NNN?N 0< F>6___PPT9 B0%$(" dK  Bm jJ?"6@ NNN?Np < F>6___PPT9 E<0.1%$(" d  BPz jJ?"6@ NNN?N p< z0___PPT10:___PPT9 YTPCH-226 " d#"  B܄ jJ?"6@ NNN?N @0z0___PPT10:___PPT9 1 % reduction in quality compared to WO-SPMR62 " d1#"  B jJ?"6@ NNN?Np@ z0___PPT10:___PPT9 5 % reduction in running time compared to WO-SPMR66 " d5#"  B` jJ?"6@ NNN?N @pz0___PPT10:___PPT9 ZWorkload6 " d#"B  61 ?"0@NNN?N @0@B  61 ?"0@NNN?N  0 B  61 ?"0@NNN?N @  B  61 ?"0@NNN?N0@0 B  61 ?"0@NNN?N 0B  61 ?"0@NNN?Np@p B  61 ?"0@NNN?N @ B   61 ?"0@NNN?N < 0< B ! 61 ?"0@NNN?N  0   # Bl ?"`P 0With split and merge (SPMR) VS without (WO-SPMR)@1H  0޽h ? ff3LmNLm___PPT10i.~w+D=' = @B +} u 0  l$(  lr l S  `}   r l S ,0 `V  H l 0޽h ? ff3LmNLm___PPT10i.}pڥS+D=' = @B +  0 `(  X  C      S  0    H  0޽h ? 3380___PPT10.P|06p   0 8(  8X 8 C     8 S  0    H 8 0޽h ? 3380___PPT10.p|p5  0  (  X  C      S @ 0    H  0޽h ? 3380___PPT10.7~;[}  0 0 (  X  C    ,  S |:, 0  ,  H  0޽h ? 3380___PPT10.~0zo" 0 @ 2(  X  C      S t 0   4 H  0޽h ? 3380___PPT10.~02  0  (  X  C      S @ 0    H  0޽h ? 3380___PPT10.~QV   0  (  X  C      S x 0    H  0޽h ? 3380___PPT10.0`F  0  (  X  C      S ڵ 0    H  0޽h ? 3380___PPT10.5  0  (  X  C      S  0    H  0޽h ? 3380___PPT10.|p  0  (  X  C      S   0    H  0޽h ? 3380___PPT10.}=b$ 0  4((  4^ 4 S     4 c $\ 0    H 4 0޽h ? 3380___PPT10.|p   0  @(  @X @ C     @ S  0    H @ 0޽h ? 3380___PPT10.P-I) 0  d((  d^ d S    G d c $,=, 0  G  H d 0޽h ? 3380___PPT10.~>  0 `(  X  C      S xӵ 0    H  0޽h ? 3380___PPT10.`3 / 0 (  X  C      S ~ 0    H  0޽h ? 3380___PPT10.6 0 0 (  X  C      S   0    H  0޽h ? 3380___PPT10.I.4 0 >(  ^  S      c $ 0   4 H  0޽h ? 3380___PPT10.~02.5 0  >(  ^  S      c $\ 0   4 H  0޽h ? 3380___PPT10.~02.6 0 @>(  ^  S      c $ 0   4 H  0޽h ? 3380___PPT10.~02.7 0 `>(  ^  S      c $t 0   4 H  0޽h ? 3380___PPT10.~028 0 ((  ^  S      c $ 0    H  0޽h ? 3380___PPT10.~`F 3 0 (  X  C    G  S aG 0  G  H  0޽h ? 3380___PPT10.Cw . 0 (  X  C      S @ 0    H  0޽h ? 3380___PPT10.H`~z - 0 (  X  C      S t 0    H  0޽h ? 3380___PPT10.IPbI\ 2 0 (  X  C      S Ȩ 0    H  0޽h ? 3380___PPT10.K ! 1 0  (   X   C       S \ 0    H   0޽h ? 3380___PPT10.KEa: 0  ((  ^  S      c $| 0    H  0޽h ? 3380___PPT10.K ! 9 0 0(  X  C      S d 0    H  0޽h ? 3380___PPT10.L.< 0 `$>(  $^ $ S     $ c $ 0   4 H $ 0޽h ? 3380___PPT10.|p= 0 4((  4^ 4 S     4 c $ 0    H 4 0޽h ? 3380___PPT10.K !> 0 <((  <^ < S     < c $ 0    H < 0޽h ? 3380___PPT10.E0Ԫrlg0Y]rIUU 0ZӋB w0V42t(!%SP.0[cj2 ~8: А=? J S N@UzjYTbto߸yl mqh8RdyIдe  ,G d@jv;:1Oh+'0D hp   Slide 1 Eric ChuEdge Eric Chu561Microsoft Office PowerPoint@l@`VF|@.G(g  <  y--$xx--'-- % % --'--%"EE--'@Garamond-. 392 -!Automatic Physical Design Tuning:."Systemx-@Garamond-. 3(2 7Workload as a Sequence.-@"Arial-. :2 Q"Sanjay Agrawal, Microsoft Research.-@"Arial-. 92 Z!Eric Chu, University of Wisconsinh.-@"Arial-.  2 Zk-.-@"Arial-. 2 ZmMadison.-@"Arial-. <2 b#Vivek Narasayya, Microsoft Research.-՜.+,0     On-screen Show N  )Arial GaramondTimes New Roman WingdingsTahomaSymbolVerdanaMiriamEdge:Automatic Physical Design Tuning: Workload as a Sequence!Automatic Physical Design Tuning)Microsoft Database Engine Tuning Advisor#Workload as a Sequence: MotivationSet VS SequenceModel Workload as a SequenceProblem SettingProblem Definition Search SpaceModel Workload as a Sequence(Optimal Algorithm for Single-Index Case General Case Multiple IndexesOptimal SolutionSearch-Space PruningModel Workload as a SequenceExploiting Disjoint Sequences(Efficiency Gain with Disjoint Sequences9Merge solutions of W1, W2, and W3: No storage violations+Merge in the presence of storage violationSolution with Split and MergeModel Workload as a SequenceGreedy Approach Greedy-SEQ%Combining Two Single-Index Solutions%Combining Two Single-Index SolutionsGreedy-SEQ: Greedy ApproachEnd-to-End SolutionModel Workload as a Sequence!Sequence VS Set-based approachesGreedy-SEQ VS Exhaustive!Effectiveness of Split and Merge Conclusion  Fonts UsedDesign Template Slide Titles !_* 0 Eric Chu Eric Chu  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)Current UserSummaryInformation(PowerPoint Document(NDocumentSummaryInformation8