Chapter 14: Query OptimizationChapter 14: Query OptimizationIntroductionIntroduction (Cont.)Slide 5Generating Equivalent ExpressionsTransformation of Relational ExpressionsEquivalence RulesEquivalence Rules (Cont.)Pictorial Depiction of Equivalence RulesSlide 11Slide 12Slide 13Transformation Example: Pushing SelectionsExample with Multiple TransformationsMultiple Transformations (Cont.)Transformation Example: Pushing ProjectionsJoin Ordering ExampleJoin Ordering Example (Cont.)Enumeration of Equivalent ExpressionsImplementing Transformation Based OptimizationCost EstimationChoice of Evaluation PlansCost-Based OptimizationDynamic Programming in OptimizationJoin Order Optimization AlgorithmLeft Deep Join TreesCost of OptimizationInteresting Sort OrdersHeuristic OptimizationStructure of Query OptimizersStructure of Query Optimizers (Cont.)Statistics for Cost EstimationStatistical Information for Cost EstimationHistogramsSelection Size EstimationSize Estimation of Complex SelectionsJoin Operation: Running ExampleEstimation of the Size of JoinsEstimation of the Size of Joins (Cont.)Slide 41Size Estimation for Other OperationsSize Estimation (Cont.)Estimation of Number of Distinct ValuesEstimation of Distinct Values (Cont.)Slide 46Additional Optimization TechniquesOptimizing Nested Subqueries**Optimizing Nested Subqueries (Cont.)Slide 50Slide 51Materialized Views**Materialized View MaintenanceIncremental View MaintenanceJoin OperationSelection and Projection OperationsAggregation OperationsAggregate Operations (Cont.)Other OperationsHandling ExpressionsQuery Optimization and Materialized ViewsMaterialized View SelectionExtra Slides: Additional Optimization TechniquesTop-K QueriesOptimization of UpdatesParametric Query OptimizationJoin MinimizationMultiquery OptimizationEnd of ChapterDatabase System Concepts 5th Ed.©Silberschatz, Korth and SudarshanSee www.db-book.com for conditions on re-use Chapter 14: Query OptimizationChapter 14: Query Optimization©Silberschatz, Korth and Sudarshan14.2Database System Concepts - 5th Edition, Oct 5, 2006.Chapter 14: Query OptimizationChapter 14: Query OptimizationIntroduction Transformation of Relational ExpressionsCatalog Information for Cost EstimationStatistical Information for Cost EstimationCost-based optimizationDynamic Programming for Choosing Evaluation PlansMaterialized views©Silberschatz, Korth and Sudarshan14.3Database System Concepts - 5th Edition, Oct 5, 2006.IntroductionIntroductionAlternative ways of evaluating a given queryEquivalent expressionsDifferent algorithms for each operation©Silberschatz, Korth and Sudarshan14.4Database System Concepts - 5th Edition, Oct 5, 2006.Introduction (Cont.)Introduction (Cont.)An evaluation plan defines exactly what algorithm is used for each operation, and how the execution of the operations is coordinated.©Silberschatz, Korth and Sudarshan14.5Database System Concepts - 5th Edition, Oct 5, 2006.Introduction (Cont.)Introduction (Cont.)Cost difference between evaluation plans for a query can be enormousE.g. seconds vs. days in some casesSteps 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 costEstimation of plan cost based on:Statistical information about relations. Examples:number of tuples, number of distinct values for an attributeStatistics estimation for intermediate resultsto compute cost of complex expressionsCost formulae for algorithms, computed using statisticsDatabase System Concepts 5th Ed.©Silberschatz, Korth and SudarshanSee www.db-book.com for conditions on re-use Generating Equivalent ExpressionsGenerating Equivalent Expressions©Silberschatz, Korth and Sudarshan14.7Database System Concepts - 5th Edition, Oct 5, 2006.Transformation of Relational ExpressionsTransformation of Relational ExpressionsTwo relational algebra expressions are said to be equivalent if the two expressions generate the same set of tuples on every legal database instanceNote: order of tuples is irrelevantIn SQL, inputs and outputs are multisets of tuplesTwo 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. An equivalence rule says that expressions of two forms are equivalentCan replace expression of first form by second, or vice versa©Silberschatz, Korth and Sudarshan14.8Database System Concepts - 5th Edition, Oct 5, 2006.Equivalence RulesEquivalence 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 ))(())((1221EE))(()(2121EE)())))((((121EELLnLL ©Silberschatz, Korth and Sudarshan14.9Database System Concepts - 5th Edition, Oct 5, 2006.Equivalence Rules (Cont.)Equivalence 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 Sudarshan14.10Database System Concepts - 5th Edition, Oct 5, 2006.Pictorial Depiction of Equivalence RulesPictorial Depiction of Equivalence Rules©Silberschatz, Korth and Sudarshan14.11Database System Concepts - 5th Edition, Oct 5, 2006.Equivalence Rules (Cont.)Equivalence 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. 0E1  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