關(guān)系查詢處理和查詢優(yōu)化小結(jié)

1、關(guān)系查詢處理和查詢優(yōu)化小結(jié)一關(guān)系查詢優(yōu)化的概述查詢優(yōu)化在關(guān)系數(shù)據(jù)庫(kù)中的重要性及必要性關(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)化夕做得更好。查詢優(yōu)化的可能性和優(yōu)點(diǎn)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得 這些信息如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以 選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重

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

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

4、：避免重復(fù)掃描關(guān)系 將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合 目的：減少掃描關(guān)系的遍數(shù) 在執(zhí)行連接操作前對(duì)關(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）合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成5）對(duì)內(nèi)結(jié)點(diǎn)分組6）生成程序例：6 Student.Sno=SC.Sno (Student x SC)Student SC -提取公共子表達(dá)式；例如：查詢小王選修的所有課程?？梢杂藐P(guān)系代數(shù)來(lái)表達(dá)多種不同的查詢 方法

5、。S1=n cno(T S.sno=SC.sno A S.sname= “小王” (S x SC)S2=n cno ( c S.sname= “小王”(s OSC)S3=n cno ( c S.sname= “小王” (S:) SC)三種查詢的結(jié)果是完全相同的，但三種查詢的具體操作、所占用的內(nèi)存、 所消耗的時(shí)間是不相同的。顯然：S3 優(yōu)于S2 優(yōu)于S1查詢優(yōu)化對(duì)減少系統(tǒng)開銷、提高運(yùn)行速度是很重要的。物理優(yōu)化物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，球的優(yōu)化的查詢 計(jì)劃，達(dá)到查詢優(yōu)化的目標(biāo)。物理優(yōu)化可以選擇的方法基于規(guī)則的啟發(fā)式優(yōu)化；大多數(shù)情況下都適用?；诖鷥r(jià)估算的優(yōu)化；優(yōu)化器估算不同執(zhí)

6、行策略的代價(jià)，并選出具有最 小代價(jià)的執(zhí)行計(jì)劃。兩者結(jié)合的優(yōu)化方法。選擇操作的啟發(fā)式規(guī)則對(duì)于小關(guān)系，使用全表順序掃描，即使選擇列上有索引； 對(duì)于大關(guān)系，啟發(fā)式規(guī)則有：對(duì)于選擇條件是主碼二值的查詢； 查詢結(jié)果最多是一個(gè)元組，可以選擇主碼索引； 一般的RDBMSs自動(dòng)建立主碼索引；對(duì)于選擇條件是非主屬性二值的查詢，并且選擇列上有索引 要估算查詢結(jié)果的元組數(shù)目如果比例較小(10%)可以使用索引掃描方法 否則還是使用全表順序掃描全表掃描算法的代價(jià)估算公式如果基本表大小為B塊，全表掃描算法的代價(jià)cost = B 如果選擇條件是碼二值，則平均代價(jià) cost = B/2排序 -合并連接算法的代價(jià)估算公式如果連接表已經(jīng)按照連接屬性排好序，則cost二Br+Bs+(Frs*Nr*Ns)/Mrs 。 如果必須對(duì)文件排序 需要在代價(jià)函數(shù)中加上排序的代價(jià) 對(duì) 于 包 含 B 個(gè) 塊 的 文 件 排 序 的 代 價(jià) 大 約 是 (2*B)+(2*B*log2B)三.總結(jié)對(duì)于數(shù)據(jù)庫(kù)的設(shè)計(jì)，數(shù)據(jù)庫(kù)的查詢優(yōu)化是必不可少的；查詢處理時(shí)RDBM的核心, 而查詢優(yōu)化技術(shù)是查詢處理的關(guān)鍵。一個(gè)好的查詢優(yōu)化處理能使的執(zhí)行效率更 高，