tailieunhanh - Lecture Database system concepts (6/e): Chapter 13 - Silberschatz, Korth, Sudarshan

Chapter 13 describes how queries are optimized. This chapter presents the following content: 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. | Chapter 13: Query Optimization Database System Concepts, 6th Ed. ©Silberschatz, Korth and Sudarshan See for conditions on re-use Chapter 13: 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 Database System Concepts - 6th Edition ©Silberschatz, Korth and Sudarshan Introduction Alternative ways of evaluating a given query Equivalent expressions Different algorithms for each operation Database System Concepts - 6th Edition ©Silberschatz, Korth and Sudarshan Introduction (Cont.) An evaluation plan defines exactly what algorithm is used for each operation, and how the execution of the operations is coordinated. Find out how to view query execution plans on your favorite database Database System Concepts - 6th Edition ©Silberschatz, Korth and Sudarshan Introduction (Cont.) Cost difference between evaluation plans for a query can be enormous . seconds vs. days in some cases Steps in cost-based query optimization 1. Generate logically equivalent expressions using equivalence rules 2. Annotate resultant expressions to get alternative query plans 3. 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 statistics Database System Concepts - 6th Edition ©Silberschatz, Korth and .