北郵-數(shù)據(jù)庫(kù)系統(tǒng)原理(英文)-14-15

1、PART 4 DATA STORAGE AND QUERYChapter 14 Query Optimizationn14.1 Overviewnwhy optimization needed n14.2 Transformation of relational expressionsnequivalence rulesn14.4 Choice of evaluation plans Query optimization ncost-based optimization,14.2nheuristic optimization, 14.3Main parts in Chapter 14nA SQ

2、L query statement may corresponds to several equivalent expressions ( or query evaluation plans ), each of which may have different costsnQuery optimization is needed to choice an efficient query-evaluation plan with lower costsnE.g.1. select * from r, s where r.A = s.A r.A=s.A (r s) is much slower

3、than r s14.1 OverviewnE.g.2 Find the names of all customers who have an account at any branch located in Brooklynn select customer-name from branch, account, depositor where = AND account.number =depositor.number AND branch-city = BrooklynnFig.14.1 14.1 OverviewFig. 14.1 Equiv

4、alent Expression 說(shuō)明：右圖“連接”操作順序仍然有問(wèn)題，應(yīng)當(dāng)是：與“depositor”的連接操作安排在最后nThe procedures of optimizationngenerating the equivalent expressions/query trees, by transforming of relational algebra expressions according to equivalence rules in14.2ngenerating alternative evaluation plans, by annotating the resultan

5、t equivalent expressions with implementation algorithms for each operations in the expressionsnchoosing the optimal (that is, cheapest) or near-optimal plan based on the estimated cost, by ncost-based optimizationnheuristic optimization14.1 Overview (cont.)nThe cost of operations is needed to estima

6、te based on statistical information about relations, i.e. metadata ne.g. number of tuples, number of distinct values for join attributes, etc.14.1 Overview (cont.)14.2 Transformation of Relational ExpressionsnDefinition. Two relational algebra expressions are equivalent, if on every legal database i

7、nstances, the two expression generate the same set of tuplesFig.14.0.1 Schema diagram for the banking enterprise14.2.1 Equivalence RulesnRule1.(選擇串接律, 將1個(gè)選擇操作分解為2個(gè)選擇操作) Conjunctive selection operations can be deconstructed into a sequence of individual selections ne.g. refer to nRule2. (選擇交換律) Selec

8、tion operations are commutative :)()(2121EE)()(1221EE14.2.1 Equivalence Rules (cont.)nRule3. (投影串接律) Only the final operation in a sequence of project operations is needednnote: it is required that L1 L2 . Lnne.g. loan-number loan-number, amount (loan) = loan-number (loan) )()(121EELLnLL14.2.1 Equiv

9、alence Rules (cont.)nRule4. (以連接連接操作代替選擇選擇和笛卡爾乘積笛卡爾乘積) 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 ne.g. branch-name=“Perryridge”( borrower loan) = borrower (branch-name=“Perryridge) (borrower.loan-numbr=loan.

10、loan-number) loan 14.2.1 Equivalence Rules (cont.)ne.g. 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 rightnBy Rule4, the number of operations can be reduced, and the cost

11、s of the right-hand expressions are less than that of the left-hand expressions noften used in heuristic query optimizing14.2.1 Equivalence Rules (cont.)n! Rule5. (連接操作可交換) Theta join operations are commutative E1 E2 = E2 E1nFig. 14.2 n! the expression with smaller size should be arranged as the lef

12、t one in the operation14.2.1 Equivalence Rules (cont.)rst1.At2.A原理： 針對(duì)r中元組t1，檢查s中的元組t2.A，t1.A=t2.A ?方法： For r中每個(gè)元組t1， /*掃描 按照t1.A，查找s中滿足t1.A=t2.A的元組t2， 合并元組t1和t2連接屬性At1t2|r|=m|s|=nn假設(shè) 1. |r|=m，|s|=n 2. m1n給定r中的元組t1，采用B/B+樹(shù)索引、二分搜索機(jī)制，根據(jù)t1.A，查找s中滿足t1.A=t2.A的元組t2，所需cost正比于樹(shù)高，為： O(lgn)n r s的cost為： O(mlgn

13、) s r的cost為： O(nlgm) mlgn vs nlgmn m1, n=k*mnnlgm - mlgn = k*mlgm m(lgk*m ) = k*mlgm mlgk- mlgm = (k-1)mlgm mlgkn一般情況下，(k-1)mlgm mlgkn E.g. |r|=m=500，|s|=n=1000, k = n/m =2 (k-1)mlgm =500lg500 mlgk=500lg2r: depositor, |r| = 7s: account, |s| = 10select *from depositor inner join account on depositor.

14、accountnumber=account.accountnumberselect *from account inner join depositor on account.accountnumber=depositor.accountnumberSQL Server查詢優(yōu)化器自動(dòng)選擇元組數(shù)少的depositor作為連接操作的outer關(guān)系，兩條語(yǔ)句的查詢執(zhí)行計(jì)劃、執(zhí)行成本一樣！Innner Join in SQL ServernRule6. (連接操作的結(jié)合率, associative) a. natural join operations are associative (E1 E2)

15、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 E314.2.1 Equivalence Rules (cont.)Fig.14.2 Pictorial Depiction of Equivalence RulesRule 5Rule 6aRule 7anRule7. Selection operation distributes ov

16、er theta-join(選擇操作對(duì)于連接操作的分配率,選擇條件下移)na. 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 nb. when 1 involves only the attributes of E1, and 2 involves only the attributes of E2 1 E1 E2) = (1(E1) ( (E2)n e.g. in Fig.14.0.21

17、4.2.1 Equivalence Rules (cont.)n When Rule7 is applied, the size of relations participating in theta-join operation is reduced, thus evaluation costs are reduced account branchFig.14.0.2 An example of Rule7nRule8. Projection operation distributes over theta-join(投影操作對(duì)于連接操作的分配率,投影下移)na. L1 and L2 are

18、 the attributes of E1 and E2 respectively. if join condition involves only attributes in L1 L2, then )()()(2.12.12121EEEELLLL14.2.1 Equivalence Rules (cont.) branch-name, branch-city branch-name, amount branch loanbranch-name, branch-city branch-name, amount branch loanFig.14.0.3 An example of Rule

19、8aL1L2E1: branch (branch-name, branch-city, assets) E2:loan(loan-number, branch-name, amount) b. consider a join E1 E2nlet L1 and L2 be sets of attributes from E1 and E2, respectivelynlet L3 be attributes of E1 that are involved in join condition , but are not in L1 L2, andnlet L4 be attributes of E

20、2 that are involved in join condition , but are not in L1 L2.)()().(2.12142312121EEEELLLLLLLL14.2.1 Equivalence Rules (cont.) branch-city loan-number branch loan branch-city, assets loan-number, amount branch loanFig.14.0.4 An example of Rule 8bB. assets L. amountL1L2L4L3B. assets L. amountE1: branc

21、h (branch-name, branch-city, assets) E2:loan(loan-number, branch-name, amount) branch-city loan-number nRule9. The set operations union and intersection are commutative E1 E2 = E2 E1 E1 E2 = E2 E1 set difference is not commutativenRule10. Set union and intersection are associative (E1 E2) E3 = E1 (E

22、2 E3) (E1 E2) E3 = E1 (E2 E3)14.2.1 Equivalence Rules (cont.)nRule11. (選擇操作對(duì)于集合并、交、差的分配率) The selection operation distributes over , and . n (E1 E2) = (E1) (E2)n similarly for and in place of n (E1 E2) = (E1) E2n similarly for in place of , but not for nRule12. (投影操作對(duì)于集合并的分配率) The projection operati

23、on distributes over union L(E1 E2) = (L(E1) (L(E2) 14.2.1 Equivalence Rules (cont.)nFind the names of all customers who have an account at some branch located in Brooklyncustomer-name(branch-city = “Brooklyn”(branch (account depositor)nTransformation using rule 7a. customer-name (branch-city =“Brook

24、lyn” (branch) (account depositor)nPerforming the selection as early as possible reduces the size of the relation to be joined. 14.2.2 Example OnenFor nWhen we compute t (branch-city = “Brooklyn” (branch) account ) we obtain a temporal relation t whose schema is:T(branch-name, branch-city, assets, ac

25、count-number, balance)nPush projections using equivalence rules 8a and 8b; eliminate unneeded attributes from intermediate results to get: customer-name ( account-number t(branch-name, branch-city, assets, account- number, balance) depositor(customer-name, account-number)customer-name(branch-city =

26、“Brooklyn” (branch) account) depositor) 14.2.2 Example TwonFind 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) nTransformation using join associatively (Rule 6a), ref

27、er to Fig.14.314.2.2 Example ThreeFig. 14.3 Multiple transformations14.2.2 Example Three (cont.)注意連接操作執(zhí)行順序的變化!14.2.3 Join OrderingnFor all relations r1, r2, and r3,(r1 r2) r3 = r1 (r2 r3 )nIf r2 r3 is quite large and r1 r2 is small, we choose (r1 r2) r3 so that we compute and store a smaller tempora

28、ry relation.nConsider the expressioncustomer-name (branch-city = “Brooklyn” (branch) account depositor)nCould compute account depositor first, and join result with branch-city = “Brooklyn” (branch), but account depositor is likely to be a large relation.nSince it is more likely that only a small fra

29、ction of the banks customers have accounts in branches located in Brooklyn, it is better to compute branch-city = “Brooklyn” (branch) accountfirst. 14.2.3 An Example nHow to estimate the cost of an operationnestimating the size of the resultant relations produced by the operation p, according to sta

30、tistics in the catalog about the relations on which the operation is conductedn e.g. customer-name(balance2500(account) customer)ncomputing the cost of the operation in terms of disk access, by means of the cost formulae shown in chapter13ndisk access is the predominant cost, and the number of block

31、 transfers from disk is used as a measure of the actual cost of evaluation.14.3 Estimating Statistics of Expression Resultsnnr: number of tuples in a relation rnbr: number of blocks containing tuples of rnlr: size of a tuple of r in bytesnfr: blocking factor of rnthe number of tuples of r that fit i

32、nto one blocknIf tuples of r are stored together physically in a file, then: 14.3.1 Statistics in Catalog for OptimizationrfrnrbnV(A, r): number of distinct values that appear in r for attribute Ansame as the size of A(r), | A(r)|nStatistics about indices, such as heights of B+-trees, that is HTi, a

33、nd the number of leaf pages in the indices, are also in catalogStatistics in Catalog for Optimization (cont.)nAn example for statistical informationnnaccount = 10000 (account has 10,000 tuples)nfaccount= 20 (20 tuples of account fit in one block)nV(branch-name, account) = 50 (50 branches)nV(balance,

34、 account) = 500 (500 different balance values)nassume the following indices exist on accountna primary, B+-tree index for the attribute branch-namena secondary, B+-tree index for the attribute balanceStatistics in Catalog for Optimization (cont.)nThe size estimation of the result of a selection oper

35、ation depends on the selection predicates, that is single equality predicate, single comparison predicate, and combination of predicatesnEquality selection A=a (r)nassuming uniform distribution of values in relations, and the value a appears in attribute A of some record in rn the selection is estim

36、ated to have nnr / V(A, r) tuples satisfying A=a nnr /V(A, r) /fr blocks that these tuples occupy14.3.2 Selection Size EstimationnComparison selections AV(r) nthe lowest and highest values of attributes, that is min(A, r) and max(A, r), are available in catalognthe estimated number of records/tuples

37、 satisfying comparison condition A Vn0, if v 90join conditionselection conditionsExample OnenPrinciples select A1, A2, , An from r1, r2, , rn where P corresponds to A1, A2, , An (P ( r1 r2 rn ) )Example One (cont.)nStep2. Initial Relational algebra expression nE1 = sname( s.s#=sc.s# sex=M grade90 (S

38、 SC ) ) 或：sname(sex=M grade90 (S SC ) )nStep3. Initial query treen Fig. 14.0.5 (a), E1nStep4. By means of Rule1, Rule7b, distribute operations over relation S and SCn Fig. 14.0.5 (b), E2Example One (cont.)sname grade90 sex=MSSC（b）E2sname S (S#, sname, age, sex)SC (S#, C#, grade) (a) Initial query tr

39、ee E1 s.s#=sc.s# sex=M grade90s.s#=sc.s#nStep5. By means of Rule4.a, replace selection and Cartesian product with natural join nFig. 14.0.5 (c), E3nStep6. ! By means of Rule8b, distribute operations over relation S and SCnFig. 14.0.5 (d),nThe final optimized expression E4 that is equivalent to initi

40、al expression E1 is n sname sname, S# (sex=M (S) grade90 (grade, S# (SC) Example One (cont.)（c）E3s.s#=sc.s# sname, S# SC(S#, C#, grade) （d）E4sname grade90 sex=M S(S#, sname, age, sex)SC (S#, C#, grade) s.s#=sc.s# sname sex=Mgrade90 S# S(S#, sname, age, sex)nConsider the following insurance database,

41、 where the primary keys are underlined, nPerson(driver-id, name, address) nCar(license, model, year)nAccident(report-number, date, location)nParticipated(driver-id , license, report-number, damage-amount)Example Two nProblemsnGive a SQL statement to find out the driver name, license, report-number o

42、f the accidents which happened in Beijing and before May 3, 2008nGive the initial query tree for this query, and construct an optimized and equivalent relational algebra expression for it by means of heuristic optimizationExample Two (cont.)nStep1. SQL statementn Select name, license, Accident.repor

43、t-number From Person, Participate, Accident Where Person.driver_id = Participate.driver_id AND Accident.report_number = Participate.report_number AND Location=Beijing AND date 5/3/2008nStep2. Initial expression name, license, Accident.report-number ( Person.driver_id = Participate.driver_id AND Acci

44、dent.report_number = Participate.report_number AND Location=Beijing AND date 5/3/2003 (Person Participate Accident )Example Two (cont.) name, license, Accident.report-number Person.driver_id = Participate.driver_id AND Accident.report_number = Participate.report_number AND Location=Beijing AND date

45、5/3/2003Person ParticipateAccident(a) initial query tree name, license, Accident.report-number Accident.report_numberPerson(driver-id, name, address) Participate(driver-id, license, report-number, damage-amount) Accident(report-number, date ,location)(b) optimal query treeAccident.report.number = Pa

46、rticipate.report_numberPerson.driver_id = Participate.driver_id driver_id, name driver_id, license, report-numberLocation=Beijing AND date 100000 and amount1000Example Three (cont.) customer-name loan.loan-number customer- name, loan-number borrower ( customer-name, loan-number, borrow-date)loan.loa

47、n-number ,branch-name amount100000 Branch (branch-name, branch-city, assets)實(shí)際DBS中的查詢優(yōu)化n教科書(shū)上的選擇、投影操作下移的實(shí)現(xiàn)方式 實(shí)際平臺(tái)下（如SQL Server）與后面的連接操作結(jié)合在一起做，避免多次關(guān)系代數(shù)操作： 1. 采用pipeline，在對(duì)參與連接運(yùn)算的關(guān)系掃描過(guò)程中完成符合條件的元組選擇 2. 再選出后續(xù)步驟需要的屬性投影 customer-name account.accountnumber customername, accountnumber depositor ( customernam

48、e, accountnumber, accessdate)account.accountnumber ,branchname balance100000 branch (branchname, branchcity, assets)基于索引選擇下移投影下移選擇下移投影下移？投影下移連接實(shí)現(xiàn)方式投影下移？連接+投影n給定如下關(guān)系數(shù)據(jù)庫(kù) Employee(Employee#, Name, Address, Super-E#, E-D#) Department(D#, Dname, manager#, depart-location) Project(P#, Pname, Plocation, P-

49、D#)n查詢：對(duì)于每個(gè)在“哈爾濱”進(jìn)行的工程項(xiàng)目，列出其工程項(xiàng)目號(hào)P# ，工程所屬部門(mén)號(hào)P-D#, 該部門(mén)領(lǐng)導(dǎo)的名字Name和地址Addressn要求：寫(xiě)出該查詢的SQL語(yǔ)句；轉(zhuǎn)換為關(guān)系代數(shù)表達(dá)式并利用啟發(fā)式方法進(jìn)行查詢優(yōu)化；給出優(yōu)化后的關(guān)系代數(shù)表達(dá)式。n Select P#, P-D#, Name, Address) From Project, Department, Employee Where Plocation =哈爾濱 AND P-D#= D# AND manager# = Employee#Example Four (cont.) P#, P-D#, Name, Address P

50、#, P-D#, manager# employee#, name, address Employee P#, P-D# P-location=“哈爾濱”P(pán)rojectD#, manager#Department作業(yè)nConsider the following schema, where the primary keys are underlined , nSuppliers (supplier-id, supplier-name, city, telephone, address) nParts ( parts-id, parts-name, parts-color) nCatalog (

51、supplier-id, parts-id, price ) n. n(1) Give an SQL statement to find out the name and telephone of the suppliers who supply a red part whose price is below $2000. n(2) Translate this SQL statement into an initial query tree, and give an optimized query tree for it, by means of heuristic query optimi

52、zation. Database System Concepts - Chapter 14 Query Optimization -80Appendix A SQL Server平臺(tái)下觀察比較SQL語(yǔ)句查詢執(zhí)行計(jì)劃顯示估計(jì)的查詢執(zhí)行計(jì)劃13.5.2 indexed nested loop join， 在內(nèi)關(guān)系branch的連接屬性branchname上建有索引13.3.2 A3算法;inner relation, holded in main memoryA1算法；outer relation13.5.5 hash join， Fig. 13.813.4A1算法；outer relationD

53、atabase System Concepts - Chapter 14 Query Optimization -82Database System Concepts - Chapter 14 Query Optimization -83May 2014Database System Concepts - Chapter 14 Query Optimization -84May 2014Database System Concepts - Chapter 14 Query Optimization -85May 2014Database System Concepts - Chapter 14

54、 Query Optimization -8613.5.5 hash join， Fig. 13.8May 2014Database System Concepts - Chapter 14 Query Optimization -8713.4Database System Concepts - Chapter 14 Query Optimization -88比較2條SQL語(yǔ)句查詢成本同時(shí)提交1批（2條）查詢語(yǔ)句：該批次中2條查詢語(yǔ)句的成本之比： 42% vs. 58%Database System Concepts - Chapter 14 Query Optimization -90Ap

55、pendix A Sybase 平臺(tái)下的查詢執(zhí)行計(jì)劃優(yōu)化n Select max(BscpID) From BSCAppendix A Sybase 平臺(tái)下的查詢執(zhí)行計(jì)劃優(yōu)化（續(xù)）n查詢實(shí)驗(yàn)內(nèi)容n 單表、多表（如3張表）的查詢、插入、刪除、修改所對(duì)應(yīng)的查詢執(zhí)行計(jì)劃比較n有無(wú)索引、索引類(lèi)型對(duì)查詢、插入、刪除、修改等操作的代價(jià)的影響n查詢結(jié)果相同、但表達(dá)形式不一樣的多個(gè)等價(jià)的查詢、刪除、插入、修改語(yǔ)句的查詢執(zhí)行計(jì)劃的比較例如。 delete from loan where amount between 0 and 50Appendix A Sybase 平臺(tái)下的查詢執(zhí)行計(jì)劃優(yōu)化（續(xù)）Appendi

56、x A Sybase 平臺(tái)下的查詢執(zhí)行計(jì)劃優(yōu)化（續(xù)）delete from loanwhere amount in ( select amount from loan where amount = 0 and amount = 50) Appendix B DDBS查詢代價(jià)與數(shù)據(jù)分布的關(guān)系n 分布式數(shù)據(jù)庫(kù)系統(tǒng)DDBS中, 數(shù)據(jù)在各站點(diǎn)的分布和站點(diǎn)間通訊代價(jià)/傳輸時(shí)間將影響到整個(gè)查詢代價(jià)n例. n S(S#，SNAME，AGE，SEX) , 104個(gè)元組，站點(diǎn)An C(C#，CNAME，TEACHER), 105個(gè)元組，站點(diǎn)Bn SC(S#，C#，GRADE), 106個(gè)元組，站點(diǎn)An 元組平均長(zhǎng)度100bit，站點(diǎn)間傳輸速率v = 104 bit/s ，通 信延遲d=1s。假設(shè)無(wú)副本n查詢要求n 在支持分片透明性的DDBS（分布在A和B 2個(gè)站點(diǎn)）中， 查詢“所有選修所有選修