Outline ■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-7th Edition 16.2 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 16.2 ©Silberschatz, Korth and Sudarshan th Edition Outline ▪ 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 I name,title Odept name-Music Iname,title instructor Odept name-Music teaches Icourse id.tite instructor teaches Icourse id.tirle course course (a)Initial expression tree (b)Transformed expression tree Database System Concepts-7th Edition 16.3 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 16.3 ©Silberschatz, Korth and Sudarshan th Edition 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. (sort to remove duplicates) Π ame,title (merge join) sortD sorti ☒(hash join) dept name-Music course id,title (use index 1) instructor teaches course Find out how to view query execution plans on your favorite database Database System Concepts-7th Edition 16.4 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 16.4 ©Silberschatz, Korth and Sudarshan th Edition 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
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-7th Edition 16.5 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 16.5 ©Silberschatz, Korth and Sudarshan th Edition 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
Viewing Query Evaluation Plans Most database support explain Displays plan chosen by query optimizer,along with cost estimates Some syntax variations between databases Oracle:explain plan for followed by select*from table (dbms_xplan.display) SQL Server:set showplan_text on Some databases(e.g.PostgreSQL)support explain analyse Shows actual runtime statistics found by running the query,in addition to showing the plan Some databases(e.g.PostgreSQL)show cost as f./ f is the cost of delivering first tuple and is cost of delivering all results Database System Concepts-7th Edition 16.6 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 16.6 ©Silberschatz, Korth and Sudarshan th Edition Viewing Query Evaluation Plans ▪ Most database support explain • Displays plan chosen by query optimizer, along with cost estimates • Some syntax variations between databases ▪ Oracle: explain plan for followed by select * from table (dbms_xplan.display) ▪ SQL Server: set showplan_text on ▪ Some databases (e.g. PostgreSQL) support explain analyse • Shows actual runtime statistics found by running the query, in addition to showing the plan ▪ Some databases (e.g. PostgreSQL) show cost as f..l • f is the cost of delivering first tuple and l is cost of delivering all results
Generating Equivalent Expressions Database System Concepts-7th Edition 16.7 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 16.7 ©Silberschatz, Korth and Sudarshan th Edition Generating Equivalent Expressions
Transformation of Relational Expressions Two relational algebra expressions are said to be equivalent if the two expressions generate the same set of tuples on every lega/database instance Note:order of tuples is irrelevant we don't care if they generate different results on databases that violate integrity constraints 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 Database System Concepts-7th Edition 16.8 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 16.8 ©Silberschatz, Korth and Sudarshan th Edition Transformation 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 • we don’t care if they generate different results on databases that violate integrity constraints ▪ 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
Equivalence Rules 1.Conjunctive selection operations can be deconstructed into a sequence of individual selections. 01A2(E)三001(C2(E)》 2.Selection operations are commutative. 0,(C92(E)》三O2(C,(E) 3.Only the last in a sequence of projection operations is needed,the others can be omitted. Π(2(（ΠLn(E)…)》三ΠL,(E) here L1∈L2.∈Ln 4.Selections can be combined with Cartesian products and theta joins. a.09(E1XE2)≡E1☒9E2 b.091(E1凶02E2)三E1☒91A2E2 Database System Concepts-7th Edition 16.9 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 16.9 ©Silberschatz, Korth and Sudarshan th Edition Equivalence Rules 1. Conjunctive selection operations can be deconstructed into a sequence of individual selections. σ1 2 (E) ≡ σ1 (σ2 (E)) 2. Selection operations are commutative. σ1 (σ2 (E)) ≡ σ2 (σ1 (E)) 3. Only the last in a sequence of projection operations is needed, the others can be omitted. L1 ( L2 (…( Ln (E))…)) ≡ L1 (E) where L1 ⊆ L2 … ⊆ Ln 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
Equivalence Rules (Cont.) 5.Theta-join operations (and natural joins)are commutative. E1☆E2≡E2☒E1 6.(a)Natural join operations are associative: (E1☒E2)☒E3≡E1凶(E2☒E3) (b)Theta joins are associative in the following manner: (E1凶01E2)凶2A3E3三E1凶91A03(E2凶2E3) where 02 involves attributes from only E2 and E3. Database System Concepts-7th Edition 16.10 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 16.10 ©Silberschatz, Korth and Sudarshan th Edition Equivalence Rules (Cont.) 5. Theta-join operations (and natural joins) are commutative. E1 ⨝ E2 ≡ E2 ⨝ E1 6. (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
Pictorial Depiction of Equivalence Rules Rule 5 E1 E2 E2 Rule 6.a ◇外 Er E E2 E2 E3 60 Rule 7.a 凶 If 0 only has attributes from E 60 E2 Er E2 Database System Concepts-7th Edition 16.11 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 16.11 ©Silberschatz, Korth and Sudarshan th Edition Pictorial Depiction of Equivalence Rules