PowerPoint PresentationQuery ProcessingExampleSlide 4How do we execute query?Slide 6Relational Algebra - can be used to describe plans...Another idea:Slide 9Plan IIISlide 11Overview of Query OptimizationSlide 13Example: SQL querySlide 15Slide 16Slide 17Slide 18Example: Estimate Result SizesExample: One Physical PlanExample: Estimate costsSlide 22Slide 23Query OptimizationRelational algebra optimizationRules: Natural joins & cross products & unionNote:Rules: SelectsRules: s + combinedWhich are “good” transformations?Conventional wisdom: do projects earlyWhat if we have A, B indexes?Bottom line:In textbook: more transformationsOutline - Query ProcessingEstimating cost of query planEstimating result sizeSlide 38Size estimates for W = R1 x R2Selection cardinalityWhat about W = sz  val (R) ?Size estimate for W = R1 R2W = R1 R2 X  Y = ASlide 44In general W = R1 R2Using similar ideas, we can estimate sizes of:Example:Partial Result: U = R1 R2Z = U R3SummaryOutlineChapters 15-16a 1(Slides by Hector Garcia-Molina,http://www-db.stanford.edu/~hector/cs245/notes.htm)Chapters 15 and 16:Query ProcessingChapters 15-16a 2Query ProcessingQ  Query PlanFocus: Relational SystemChapters 15-16a 3ExampleSelect B,DFrom R,SWhere R.A = “c” AND S.E = 2 AND R.C=S.CChapters 15-16a 4 R: A B C S: C D Ea 1 10 10 x 2b 1 20 20 y 2c 2 10 30 z 2d 2 35 40 x 1e 3 45 50 y 3Answer B D2 xChapters 15-16a 5• How do we execute query?- Do Cartesian product- Select tuples- Do projectionOne ideaChapters 15-16a 6RXS R.A R.B R.C S.C S.D S.E a 1 10 10 x 2 a 1 10 20 y 2 . . C 2 10 10 x 2 . .Bingo!Got one...Chapters 15-16a 7Relational Algebra - can be used to describe plans...Ex: Plan IB,D R.A=“c” S.E=2  R.C=S.CXR SOR: B,D [ R.A=“c” S.E=2  R.C = S.C (RXS)]Chapters 15-16a 8Another idea:B,D R.A = “c” S.E = 2R SPlan II natural joinChapters 15-16a 9 R SA B C (R) (S) C D Ea 1 10 A B C C D E 10 x 2b 1 20 c 2 10 10 x 2 20 y 2c 2 10 20 y 2 30 z 2d 2 35 30 z 2 40 x 1e 3 45 50 y 3Chapters 15-16a 10Plan III Use R.A and S.C Indexes(1) Use R.A index to select R tuples with R.A = “c”(2) For each R.C value found, use S.C index to find matching tuples(3) Eliminate S tuples S.E  2(4) Join matching R,S tuples, project B,D attributes and place in resultChapters 15-16a 11 R SA B C C D Ea 1 10 10 x 2b 1 20 20 y 2c 2 10 30 z 2d 2 35 40 x 1e 3 45 50 y 3A CI1 I2=“c”<c,2,10><10,x,2>check=2?output: <2,x>next tuple:<c,7,15>Chapters 15-16a 12Overview of Query OptimizationChapters 15-16a 13parseconvertapply lawsestimate result sizesconsider physical plansestimate costspick bestexecute{P1,P2,…..}{(P1,C1),(P2,C2)...}Pi answerSQL queryparse treelogical query plan“improved” l.q.pl.q.p. +sizesstatisticsChapters 15-16a 14Example: SQL querySELECT titleFROM StarsInWHERE starName IN (SELECT nameFROM MovieStarWHERE birthdate LIKE ‘%1960’);(Find the movies with stars born in 1960)Chapters 15-16a 15Example: Parse Tree<Query><SFW>SELECT <SelList> FROM <FromList> WHERE <Condition><Attribute> <RelName> <Tuple> IN <Query>title StarsIn <Attribute> ( <Query> )starName <SFW>SELECT <SelList> FROM <FromList> WHERE <Condition><Attribute> <RelName> <Attribute> LIKE <Pattern>name MovieStar birthDate ‘%1960’Chapters 15-16a 16Example: Generating Relational AlgebratitleStarsIn <condition><tuple> IN name<attribute> birthdate LIKE ‘%1960’starName MovieStarAn expression using a two-argument , midway between a parse tree and relational algebraChapters 15-16a 17Example: Logical Query PlantitlestarName=nameStarsIn name birthdate LIKE ‘%1960’ MovieStarApplying the rule for IN conditionsChapters 15-16a 18Example: Improved Logical Query PlantitlestarName=nameStarsIn name birthdate LIKE ‘%1960’ MovieStarFig. 7.20: An improvement on fig. 7.18.Question:Push project toStarsIn?Chapters 15-16a 19Example: Estimate Result Sizes Need expected size StarsIn MovieStar Chapters 15-16a 20Example: One Physical Plan Parameters: join order, memory size, ...Hash joinSEQ scan index scanParameters:Select Condition,...StarsIn MovieStarChapters 15-16a 21Example: Estimate costsL.Q.PP1 P2 …. PnC1 C2 …. Cn Pick best!Chapters 15-16a 22Textbook outlineChapter 5: Algebra for queries[bags vs sets]- Select, project, join, ….[project lista,a+b->x,…]- Duplicate elimination, grouping, sortingChapter 15:- Physical operators- Scan,sort, …- Implementing operators and estimating their costChapters 15-16a 23Chapter 16:- Parsing- Algebraic laws- Parse tree -> logical query plan- Estimating result sizes- Cost based optimizationChapters 15-16a 24Query Optimization•Relational algebra level•Detailed query plan level–Estimate Costs•without indexes•with indexes–Generate and compare plansChapters 15-16a 25Relational algebra optimization•Transformation rules(preserve equivalence)•What are good transformations?Chapters 15-16a 26R x S = S x R(R x S) x T = R x (S x T)R U S = S U RR U (S U T) = (R U S) U TRules: Natural joins & cross products & unionR S = S R(R S) T = R (S T)Chapters 15-16a 27Note:•Can also write as trees, e.g.: T RR S S TChapters 15-16a 28Rules: Selectsp1p2(R) =p1vp2(R) = p1 [ p2 (R)][ p1 (R)] U [ p2 (R)]Chapters 15-16a 29Let p = predicate with only R attribs q = predicate with only S attribsp (R S) = q (R S) = Rules: combined [p (R)] S R [q (S)]Chapters 15-16a 30p1p2 (R)  p1 [p2 (R)] p (R S)  [p (R)] SR S  S RWhich are “good” transformations?Chapters 15-16a 31Conventional wisdom: do projects earlyExample: R(A,B,C,D,E) x={E} P: (A=3)  (B=“cat”)x {p (R)} vs. E {p{ABE(R)}}Chapters 15-16a 32What if we have A, B indexes?B = “cat” A=3Intersect pointers to getpointers to matching tuplesButChapters 15-16a 33Bottom line:•No transformation is always good•Usually good: