CMSC424 Database Design Instructor Amol Deshpande amol cs umd edu Query Optimization Introduction Example of a Simple Type of Query Transformation of Relational Expressions Statistics Estimation Optimization Algorithms Query Optimization Why Many different ways of executing a given query Huge differences in cost Example select from person where ssn 123 Size of person 1GB Sequential Scan Takes 1GB 20MB s 50s Use an index on SSN assuming one exists Approx 4 Random I Os 40ms Query Optimization Equivalent relational expressions Drawn as a tree List the operations and the order Query Optimization Execution plans Evaluation expressions annotated with the methods used Query Optimization Steps Generate all possible execution plans for the query Figure out the cost for each of them Choose the best Not done exactly as listed above Too many different execution plans for that Typically interleave all of these into a single efficient search algorithm Query Optimization Steps Generate all possible execution plans for the query First generate all equivalent expressions Then consider all annotations for the operations Figure out the cost for each of them Compute cost for each operation Using the formulas discussed before One problem How do we know the number of result tuples for say balance Add them 2500 account Choose the best Query Optimization Introduction Example of a Simple Type of Query Transformation of Relational Expressions Statistics Estimation Optimization Algorithms A Simple Case Queries with only selections on a single relation with no indexes select from person where substr name 1 1 in A B C and zipcode 94720 and date of birth to date 1978 05 31 yyyy mm dd Relation contains 1 000 000 tuples CPU Costs 100ns 1ns 1000ns A Simple Case Possible execution plan For each tuple Evaluate substr predicate If true Evaluate zipcode predicate If true evaluate date of birth predicate If true output the tuple 6 different possibilities How to choose one A Simple Case Compute cost of each possibility Say substr zipcode date of birth Need some more information selectivity fraction of tuples expected to pass the predicates Let selectivity substr predicate 3 26 Let selectivity zipcode predicate 1 100 And selectivity date of birth predicate 1 3 How are selectivities computed Must keep track of some additional information about the relations A Simple Case Compute cost of each possibility Say substr zipcode date of birth Given that Cost of the above plan 1 000 000 100ns 1 000 000 3 26 1ns 1 000 000 1 26 1 100 1000ns approx 100 5 ms Cost of the plan zipcode substr date of birth Approx 12 92 ms About a factor of 10 better A Simple Case Compute cost of each possibility Say substr zipcode date of birth Cost of the plan zipcode substr date of birth Approx 12 92 ms About a factor of 10 better General algorithm Don t need to check all n Possibilities Sort the predicates in the increasing order by 1 selectivity predicate cost of the predicate Query Optimization General case Need A way to enumerate all plans A way to find the cost of each plan Sub problem Estimating the selectivities of various operations A way to search through the plans efficiently Query Optimization Introduction Example of a Simple Type of Query Transformation of Relational Expressions Statistics Estimation Optimization Algorithms Equivalence of Expressions Two relational expressions equivalent iff Equivalence rules Their result is identical on all legal databases Allow replacing one expression with another Examples 1 E E 1 2 1 2 2 Selections are commutative 1 2 E 2 1 E Equivalence Rules Examples 3 L1 L2 Ln E L1 E 5 E1 E2 E2 E1 7 a If 0 only involves attributes from E 1 0 E1 And E2 0 E1 so on Many rules of this type E2 Pictorial Depiction Example Find the names of all customers with an account at a Brooklyn branch whose account balance is over 1000 customer name branch city Brooklyn branch account balance 1000 depositor Apply the rules one by one customer name branch city Brooklyn branch account balance 1000 depositor customer name branch city Brooklyn branch account depositor balance 1000 Example Equivalence of Expressions The rules give us a way to enumerate all equivalent expressions Note that the expressions don t contain physical access methods join methods etc Simple Algorithm Start with the original expression Apply all possible applicable rules to get a new set of expressions Repeat with this new set of expressions Till no new expressions are generated Equivalence of Expressions Works but is not feasible Consider a simple case R1 R3 Rn Just join commutativity and associativity will give us At least n 2 2 n At worst R2 n 2 n Typically the process of enumeration is combined with the search process Evaluation Plans We still need to choose the join methods etc Option 1 Choose for each operation separately Usually okay but sometimes the operators interact Consider joining three relations on the same attribute R1 a R2 a R3 Best option for R2 join R3 might be hash join But if R1 is sorted on a then sort merge join is preferable Because it produces the result in sorted order by a Also we need to decide whether to use pipelining or materialization Such issues are typically taken into account when doing the optimization Query Optimization Introduction Example of a Simple Type of Query Transformation of Relational Expressions Optimization Algorithms Statistics Estimation Optimization Algorithms Two types Exhaustive That attempt to find the best plan Heuristical That are simpler but are not guaranteed to find the optimal plan Consider a simple case Join of the relations R1 Rn No selections no projections Still very large plan space Searching for the best plan Option 1 Enumerate all equivalent expressions for the original query expression Using the rules outlined earlier Estimate cost for each and choose the lowest Too expensive Consider finding the best join order for r1 r2 rn There are 2 n 1 n 1 different join orders for above expression With n 7 the number is 665280 with n 10 the number is greater than 176 billion Searching for the best plan Option 2 Dynamic programming There is too much commonality between the plans Also costs are additive Reduces the cost down to O n3 n or O n2 n in most cases Interesting orders increase this a little bit Considered acceptable Caveat Sort orders also called interesting orders Typically n 10 Switch to heuristic if not acceptable Left Deep Join Trees In left deep join trees the right hand side input for each
View Full Document
Unlocking...