Database System Concepts, 6th Ed.Silberschatz, Korth and SudarshanSee www.db- for conditions on re-use Chapter 13: Query OptimizationSilberschatz, Korth and Sudarshan1.2Database System Concepts - 6th EditionChapter 13: Query OptimizationnIntroduction nTransformation of Relational ExpressionsnCatalog Information for Cost EstimationnStatistical Information for Cost EstimationnCost-based optimizationnDynamic Programming for Choosing Evaluation PlansnMaterialized views Silberschatz, Korth and Sudarshan1.3Database System Concepts - 6th EditionIntroductionnAlternative ways of evaluating a given querylEquivalent expressionslDifferent algorithms for each operationSilberschatz, Korth and Sudarshan1.4Database System Concepts - 6th EditionIntroduction (Cont.)nAn evaluation plan defines exactly what algorithm is used for each operation, and how the execution of the operations is coordinated.nFind out how to view query execution plans on your favorite databaseSilberschatz, Korth and Sudarshan1.5Database System Concepts - 6th EditionIntroduction (Cont.)nCost difference between evaluation plans for a query can be enormouslE.g. seconds vs. days in some casesnSteps in cost-based query optimization1.Generate logically equivalent expressions using equivalence rules2.Annotate resultant expressions to get alternative query plans3.Choose the cheapest plan based on estimated costnEstimation of plan cost based on:lStatistical information about relations. Examples:4number of tuples, number of distinct values for an attributelStatistics estimation for intermediate results4to compute cost of complex expressionslCost formulae for algorithms, computed using statisticsDatabase System Concepts, 6th Ed.Silberschatz, Korth and SudarshanSee www.db- for conditions on re-use Generating Equivalent ExpressionsSilberschatz, Korth and Sudarshan1.7Database System Concepts - 6th EditionTransformation of Relational ExpressionsnTwo relational algebra expressions are said to be equivalent if the two expressions generate the same set of tuples on every legal database instancelNote: order of tuples is irrelevantlwe dont care if they generate different results on databases that violate integrity constraintsnIn SQL, inputs and outputs are multisets of tupleslTwo expressions in the multiset version of the relational algebra are said to be equivalent if the two expressions generate the same multiset of tuples on every legal database instance. nAn equivalence rule says that expressions of two forms are equivalentlCan replace expression of first form by second, or vice versaSilberschatz, Korth and Sudarshan1.8Database System Concepts - 6th EditionEquivalence Rules1. Conjunctive selection operations can be deconstructed into a sequence of individual selections.2. Selection operations are commutative.3. Only the last in a sequence of projection operations is needed, the others can be omitted.4.Selections can be combined with Cartesian products and theta joins.a.(E1 X E2) = E1 E2 b.1(E1 2 E2) = E1 1 2 E2 Silberschatz, Korth and Sudarshan1.9Database System Concepts - 6th EditionEquivalence Rules (Cont.)5. Theta-join operations (and natural joins) are commutative.E1 E2 = E2 E16. (a) Natural join operations are associative: (E1 E2) E3 = E1 (E2 E3)(b) Theta joins are associative in the following manner: (E1 1 E2) 2 3 E3 = E1 1 3 (E2 2 E3) where 2 involves attributes from only E2 and E3.Silberschatz, Korth and Sudarshan1.10Database System Concepts - 6th EditionPictorial Depiction of Equivalence RulesSilberschatz, Korth and Sudarshan1.11Database System Concepts - 6th EditionEquivalence Rules (Cont.)7.The selection operation distributes over the theta join operation under the following two conditions:(a) When all the attributes in 0 involve only the attributes of one of the expressions (E1) being joined. 0E1 E2) = (0(E1) E2 (b) When 1 involves only the attributes of E1 and 2 involves only the attributes of E2. 1 E1 E2) = (1(E1) ( (E2)Silberschatz, Korth and Sudarshan1.12Database System Concepts - 6th EditionEquivalence Rules (Cont.)8.The projection operation distributes over the theta join operation as follows:(a) if involves only attributes from L1 L2:(b) Consider a join E1 E2. l Let L1 and L2 be sets of attributes from E1 and E2, respectively. lLet L3 be attributes of E1 that are involved in join condition , but are not in L1 L2, andl let L4 be attributes of E2 that are involved in join condition , but are not in L1 L2.)()()(21212121EEEELLLL=)()()(212142312121EEEELLLLLLLL=Silberschatz, Korth and Sudarshan1.13Database System Concepts - 6th EditionEquivalence Rules (Cont.)9.The set operations union and intersection are commutative E1 E2 = E2 E1 E1 E2 = E2 E1 9.(set difference is not commutative).10.Set union and intersection are associative. (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 = E1 (E2 E3)9.The selection operation distributes over , and . (E1 E2) = (E1) (E2) and similarly for and in place of Also: (E1 E2) = (E1) E2 and similarly for in place of , but not for 12. The pro