DOC PREVIEW
UMD CMSC 424 - Chapter 14: Query Optimization

This preview shows page 1-2-16-17-18-33-34 out of 34 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Chapter 14: Query OptimizationQuery Planning/OptimizationTransformation of Relational ExpressionsEquivalence RulesEquivalence Rules (Cont.)Pictorial Depiction of Equivalence RulesSlide 7Slide 8Slide 9Transformation ExampleExample with Multiple TransformationsMultiple Transformations (Cont.)Join Ordering ExampleCost 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 22Size Estimation for Other OperationsSize Estimation (Cont.)Estimation of Number of Distinct ValuesEstimation of Distinct Values (Cont.)Slide 27Searching for the best planSlide 29Left Deep Join TreesHeuristic OptimizationSteps in Typical Heuristic OptimizationStructure of Query OptimizersStructure of Query Optimizers (Cont.)Database System Concepts 5th Ed.©Silberschatz, Korth and SudarshanSee www.db-book.com for conditions on re-use Chapter 14: Query OptimizationChapter 14: Query OptimizationAmol DeshpandeAmol Deshpande(adapted from the slides at db-book.com(adapted from the slides at db-book.com))©Silberschatz, Korth and Sudarshan14.2Database System Concepts - 5th Edition, Aug 27, 2005.Query Planning/OptimizationQuery Planning/OptimizationGeneration of query-evaluation plans for an expression involves several steps:1. Generating logically equivalent expressions using equivalence rules.2. Annotating resultant expressions to get alternative query plans3. Choosing the cheapest plan based on estimated costThe overall process is called cost based optimization.©Silberschatz, Korth and Sudarshan14.3Database System Concepts - 5th Edition, Aug 27, 2005.Transformation of Relational ExpressionsTransformation of Relational ExpressionsTwo relational algebra expressions are said to be equivalent if on every legal database instance the two expressions generate the same set of tuplesNote: order of tuples is irrelevant©Silberschatz, Korth and Sudarshan14.4Database System Concepts - 5th Edition, Aug 27, 2005.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.5Database System Concepts - 5th Edition, Aug 27, 2005.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.6Database System Concepts - 5th Edition, Aug 27, 2005.Pictorial Depiction of Equivalence RulesPictorial Depiction of Equivalence Rules©Silberschatz, Korth and Sudarshan14.7Database System Concepts - 5th Edition, Aug 27, 2005.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 Sudarshan14.8Database System Concepts - 5th Edition, Aug 27, 2005.Equivalence Rules (Cont.)Equivalence Rules (Cont.)8. The projections operation distributes over the theta join operation as follows:(a) if  involves only attributes from L1  L2:(b) Consider a join E1  E2.  Let L1 and L2 be sets of attributes from E1 and E2, respectively. Let L3 be attributes of E1 that are involved in join condition , but are not in L1  L2, and let L4 be attributes of E2 that are involved in join condition , but are not in L1  L2.))(())(()(21212121EEEELLLL)))(())((()(212142312121EEEELLLLLLLL©Silberschatz, Korth and Sudarshan14.9Database System Concepts - 5th Edition, Aug 27, 2005.Equivalence Rules (Cont.)Equivalence Rules (Cont.)9. The set operations union and intersection are commutative E1  E2 = E2  E1 E1  E2 = E2  E1 (set difference is not commutative).10. Set union and intersection are associative. (E1  E2)  E3 = E1  (E2  E3) (E1  E2)  E3 = E1  (E2  E3)11. 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 projection operation distributes over union L(E1  E2) = (L(E1))  (L(E2))©Silberschatz, Korth and Sudarshan14.10Database System Concepts - 5th Edition, Aug 27, 2005.Transformation ExampleTransformation ExampleQuery: Find the names of all customers who have an account at some branch located in Brooklyn.customer_name(branch_city = “Brooklyn”(branch (account depositor)))Transformation using rule 7a. customer_name ((branch_city =“Brooklyn” (branch)) (account depositor))Performing the selection as early as possible reduces the size of the relation to be joined.©Silberschatz, Korth and Sudarshan14.11Database System Concepts - 5th Edition, Aug 27, 2005.Example with Multiple TransformationsExample with Multiple TransformationsQuery: Find the names of all customers with an account at a Brooklyn branch whose account balance is over $1000.customer_name((branch_city = “Brooklyn”  balance > 1000 (branch (account depositor)))Transformation using join associatively (Rule 6a):customer_name((branch_city = “Brooklyn”  balance > 1000 (branch account)) depositor) Second form


View Full Document

UMD CMSC 424 - Chapter 14: Query Optimization

Documents in this Course
Lecture 2

Lecture 2

36 pages

Databases

Databases

44 pages

Load more
Download Chapter 14: Query Optimization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Chapter 14: Query Optimization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Chapter 14: Query Optimization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?