Chapter 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 Database System Concepts-5th Edition,Oct 5,2006. 14.2 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 14.2 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006. Chapter 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
Introduction Alternative ways of evaluating a given query Equivalent expressions Different algorithms for each operation Π customer_nane Π customer._行afie branch_city=Brooklyn branch branch_city=Brooklyn account depositor branch account depositor Database System Concepts-5th Edition,Oct 5,2006. 14.3 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 14.3 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006. Introduction Alternative ways of evaluating a given query Equivalent expressions Different algorithms for each operation
Introduction (Cont.) An evaluation plan defines exactly what algorithm is used for each operation,and how the execution of the operations is coordinated. Π customer_name(sort to remove duplicates) ☆(hash join) ☒(merge join) depositor pipeline pipeline branch_city Brooklyn balance<1000 (use index 1) (use linear scan) branch account Database System Concepts-5th Edition,Oct 5,2006. 14.4 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 14.4 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006. Introduction (Cont.) An evaluation plan defines exactly what algorithm is used for each operation, and how the execution of the operations is coordinated
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 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-5th Edition,Oct 5,2006. 14.5 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 14.5 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006. 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 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
☒ 无法显示该图片。 Generating Equivalent Expressions Database System Concepts 5th Ed. @Silberschatz,Korth and Sudarshan See www.db-book.com for conditions on re-use
Database System Concepts 5th Ed. ©Silberschatz, Korth and Sudarshan See www.db-book.com for conditions on re-use Generating Equivalent Expressions