1、關(guān)系查詢處理和查詢優(yōu)化小結(jié)一關(guān)系查詢優(yōu)化的概述1 . 查詢優(yōu)化在關(guān)系數(shù)據(jù)庫中的重要性及必要性關(guān)系系統(tǒng)的查詢優(yōu)化既是rdbms 實(shí)現(xiàn)的關(guān)鍵技術(shù)又是關(guān)系系統(tǒng)的優(yōu)點(diǎn)所在。 它減輕了用戶選擇存取路徑的負(fù)擔(dān)。 查詢優(yōu)化極大地影響 rdbms 的性能。用戶只要提出“干什么”，不必指出“怎么干”。查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的“優(yōu)化夕做得更好。2 .查詢優(yōu)化的可能性和優(yōu)點(diǎn)1） 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程序則難以獲得這些信息2）如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。在非關(guān)系系統(tǒng)

2、中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。3）優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，程序員一般只能考慮有限的幾種可能性。4）優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)；3 .查詢優(yōu)化的一般準(zhǔn)則( l )選擇運(yùn)算應(yīng)盡可能先做；( 2 )把投影運(yùn)算和選擇運(yùn)算同時進(jìn)行；( 3 )把投影同其前或其后的雙目運(yùn)算結(jié)合起來執(zhí)行；( 4 )把某些選擇同在它前面要執(zhí)行的笛卡兒積結(jié)合起來成為一個連接運(yùn)算；( 5 )找出公共子表達(dá)式；( 6 )選取合適的連接算法。4 . 查詢優(yōu)化的一般步驟(l)把查詢轉(zhuǎn)換成某種內(nèi)部表示，通

3、常用的內(nèi)部表示是語法樹。( 2 )把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)(優(yōu)化)形式。即利用優(yōu)化算法，把原始的語法樹轉(zhuǎn)換成優(yōu)化的形式。( 3 )選擇低層的存取路徑。( 4 )生成查詢計劃，選擇代價最小的。5 .代價模型一般 dbms 采用基于代價的優(yōu)化算法：集中式數(shù)據(jù)庫單用戶系統(tǒng)總代價=i/o代價+ cpu代價多用戶系統(tǒng)總代價=i/o代價+ cpu代價+內(nèi)存代價分布式數(shù)據(jù)庫總代價=i/o代價+ cpu代價+內(nèi)存代價+通信代價.關(guān)系數(shù)據(jù)庫查詢優(yōu)化方法1. 代數(shù)優(yōu)化關(guān)系代數(shù)表達(dá)式等價指用相同的關(guān)系代替兩個表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的1 ）查詢樹啟發(fā)式優(yōu)化，一般規(guī)則有選擇運(yùn)算應(yīng)盡可能先做（最重要，最根本）目的

4、：減小中間關(guān)系投影運(yùn)算和選擇運(yùn)算同時做目的：避免重復(fù)掃描關(guān)系將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合目的：減少掃描關(guān)系的遍數(shù)在執(zhí)行連接操作前對關(guān)系適當(dāng)進(jìn)行預(yù)處理按連接屬性排序在連接屬性上建立索引某些選擇運(yùn)算在其前面執(zhí)行的笛卡爾積= 連接運(yùn)算2 ）查詢樹的啟發(fā)式優(yōu)化 算法（ 1 ）分解選擇運(yùn)算（ 2 ）通過交換選擇運(yùn)算，將其盡可能移到葉端(3)通過交換投影運(yùn)算，將其盡可能移到葉端(4)合并申接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成(5)對內(nèi)結(jié)點(diǎn)分組(6)生成程序例：6student.sno=sc.sno(student xsc)xstudent sc提取公共子表達(dá)式；例如：查詢小王選修的所

5、有課程。可以用關(guān)系代數(shù)來表達(dá)多種不同的查詢方法。s1= ttcno ( os.sno=sc.sno a s.sname= “小王”(s sc)s2= ttcno ( o- s.sname= “小王”x(s sc)s3= ttcno ( os.sname= “小王”(ssc)三種查詢的結(jié)果是完全相同的，但三種查詢的具體操作、所占用的內(nèi)存、 所消耗的時間是不相同的。顯然：s3 優(yōu)于 s2 優(yōu)于s1查詢優(yōu)化對減少系統(tǒng)開銷、提高運(yùn)行速度是很重要的。2.物理優(yōu)化物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，球的優(yōu)化的查詢計劃，達(dá)到查詢優(yōu)化的目標(biāo)。1 )物理優(yōu)化可以選擇的方法1 ) 基于規(guī)則的啟發(fā)式優(yōu)化

6、；大多數(shù)情況下都適用。2 ) 基于代價估算的優(yōu)化； 優(yōu)化器估算不同執(zhí)行策略的代價， 并選出具有最小代價的執(zhí)行計劃。3 ) 兩者結(jié)合的優(yōu)化方法。2)選擇操作的啟發(fā)式規(guī)則對于小關(guān)系，使用全表順序掃描，即使選擇列上有索引；對于大關(guān)系，啟發(fā)式規(guī)則有：對于選擇條件是主碼=值的查詢；查詢結(jié)果最多是一個元組，可以選擇主碼索引；一般的 rdbms 會自動建立主碼索引；對于選擇條件是非主屬性=值的查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小 (10%)可以使用索引掃描方法否則還是使用全表順序掃描3)全表掃描算法的代價估算公式如果基本表大小為b塊，全表掃描算法的代價cost=b如果選擇條件是碼=值，則平均代價cost = b/24 )排序-合并連接算法的代價估算公式如果連接表已經(jīng)按照連接屬性排好序則 costbr+bs+(frs*nr*ns)/mrs 。如果必須對文件排序需要在代價函數(shù)中加上排序的代價對于包含b個塊的文件排序的代價大約是(2*b)+(2*b*log2b)三.總結(jié)對于數(shù)據(jù)庫的設(shè)計，數(shù)據(jù)庫的查詢優(yōu)化是必不可少的；查詢處理時rdbms 的核心， 而查詢優(yōu)化技術(shù)是查詢處理的關(guān)鍵。 一個好的查詢優(yōu)化處理能使的執(zhí)行效率更高，減小程序的設(shè)計代價。查詢優(yōu)化能避免不必要的復(fù)雜性， 對于有些查詢構(gòu)建