《北邮课件数据库系统原理(英文)-14-14》由会员分享，可在线阅读，更多相关《北邮课件数据库系统原理(英文)-14-14（98页珍藏版）》请在金锄头文库上搜索。
1、PART 4,DATA STORAGE AND QUERY,Chapter 14 Query Optimization,14.1 Overviewwhy optimization needed 14.2 Transformation of relational expressionsequivalence rules14.4 Choice of evaluation plans Query optimization cost-based optimization,14.2heuristic optimization, 14.3,Main parts in Chapter 14,A SQL qu
2、ery statement may corresponds to several equivalent expressions ( or query evaluation plans ), each of which may have different costsQuery optimization is needed to choice an efficient query-evaluation plan with lower costsE.g.1. select * from r, s where r.A = s.A r.A=s.A (r s) is much slower than r
3、 s,14.1 Overview,E.g.2 Find the names of all customers who have an account at any branch located in Brooklyn select customer-name from branch, account, depositor where branch.name=account.name AND account.number =depositor.number AND branch-city = BrooklynFig.14.1,14.1 Overview,Fig. 14.1 Equivalent
4、Expression,说明：右图“连接”操作顺序仍然有问题，应当是：与“depositor”的连接操作安排在最后,The procedures of optimizationgenerating the equivalent expressions/query trees, by transforming of relational algebra expressions according to equivalence rules in14.2generating alternative evaluation plans, by annotating the resultant equiva
5、lent expressions with implementation algorithms for each operations in the expressionschoosing the optimal (that is, cheapest) or near-optimal plan based on the estimated cost, by cost-based optimizationheuristic optimization,14.1 Overview (cont.),The cost of operations is needed to estimate based o
6、n statistical information about relations, i.e. metadata e.g. number of tuples, number of distinct values for join attributes, etc.,14.1 Overview (cont.),14.2 Transformation of Relational Expressions,Definition. Two relational algebra expressions are equivalent, if on every legal database instances,
7、 the two expression generate the same set of tuples,Fig.14.0.1 Schema diagram for the banking enterprise,14.2.1 Equivalence Rules,Rule1.(选择串接律, 将1个选择操作分解为2个选择操作) Conjunctive selection operations can be deconstructed into a sequence of individual selections e.g. refer to Rule2. (选择交换律) Selection oper
8、ations are commutative :,14.2.1 Equivalence Rules (cont.),Rule3. (投影串接律) Only the final operation in a sequence of project operations is needednote: it is required that L1 L2 . Lne.g. loan-number loan-number, amount (loan) = loan-number (loan),14.2.1 Equivalence Rules (cont.),Rule4. (以连接操作代替选择和笛卡尔乘积
9、) Selections can be combined with Cartesian products and theta joinsa. (E1 E2) = E1 E2 note: definition of joinb. 1(E1 2 E2) = E1 1 2 E2 e.g. branch-name=“Perryridge”( borrower loan) = borrower (branch-name=“Perryridge) (borrower.loan-numbr=loan.loan-number) loan,14.2.1 Equivalence Rules (cont.),e.g
10、. branch-name=“Perryridge”( borrower loan) = borrower (branch-name=“Perryridge) (borrower.loan-numbr=loan.loan-number) loan the select statements correspond to the left and the rightBy Rule4, the number of operations can be reduced, and the costs of the right-hand expressions are less than that of t
11、he left-hand expressions often used in heuristic query optimizing,14.2.1 Equivalence Rules (cont.),! Rule5. (连接操作可交换) Theta join operations are commutative E1 E2 = E2 E1Fig. 14.2 ! the expression with smaller size should be arranged as the left one in the operation,14.2.1 Equivalence Rules (cont.),r
12、,s,原理： 针对r中元组t1，检查s中的元组t2.A，t1.A=t2.A ?方法： For r中每个元组t1， /*扫描 按照t1.A，查找s中满足t1.A=t2.A的元组t2， 合并元组t1和t2,连接属性A,t1,t2,|r|=m,|s|=n,假设 1. |r|=m，|s|=n 2. m1给定r中的元组t1，采用B/B+树索引、二分搜索机制，根据t1.A，查找s中满足t1.A=t2.A的元组t2，所需cost正比于树高，为： O(lgn) r s的cost为： O(mlgn) s r的cost为： O(nlgm),mlgn vs nlgm,m1, n=k*mnlgm - mlgn = k
13、*mlgm m(lgk*m ) = k*mlgm mlgk- mlgm = (k-1)mlgm mlgk一般情况下，(k-1)mlgm mlgk E.g. |r|=m=500，|s|=n=1000, k = n/m =2 (k-1)mlgm =500lg500 mlgk=500lg2,r: depositor, |r| = 7,s: account, |s| = 10,select *from depositor inner join account on depositor.accountnumber=account.accountnumber,select *from account in
14、ner join depositor on depositor.accountnumber=account.accountnumber,SQL Server查询优化器自动选择元组数少的depositor作为连接操作的outer关系，两条语句的查询执行计划、执行成本一样！,Innner Join in SQL Server,Rule6. (连接操作的结合率, associative) a. natural join operations are associative (E1 E2) E3 = E1 (E2 E3),b. Theta joins are associative in the fo
15、llowing manner: (E1 1 E2) 2 3 E3 = E1 1 3 (E2 2 E3) , where 2 involves attributes from only E2 and E3,14.2.1 Equivalence Rules (cont.),Fig.14.2 Pictorial Depiction of Equivalence Rules,Rule 5,Rule 6a,Rule 7a,Rule7. Selection operation distributes over theta-join(选择操作对于连接操作的分配率,选择条件下移)a. when all the attributes in 0 involve only the attributes of one of the expressions , e.g. E1, being joined 0E1 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) e.g. in Fig.14.0.2,
