第5章查詢(xún)處理和優(yōu)化

第5系查詢(xún)處理和查詢(xún)優(yōu)查詢(xún)是數(shù)據(jù)庫(kù)管理系統(tǒng)中使用最頻繁、最基本的操，對(duì)系統(tǒng)性能有很大查詢(xún)優(yōu)化技術(shù)是關(guān)系數(shù)本章目的RDBMS的查詢(xún)處理步查詢(xún)優(yōu)化的概基本方法和技2013/12/22 第5第5章關(guān)系查詢(xún)處理和查詢(xún)優(yōu)5.15.3代數(shù)優(yōu)5.62013/12/22 詢(xún)處理過(guò)詢(xún)處理過(guò)把SQL查詢(xún)語(yǔ)句轉(zhuǎn)換成等價(jià)013/12/222 013/12/2224查詢(xún)處理DBMS不保留可執(zhí)行代碼，每一次都重新解釋行查詢(xún)語(yǔ)句，事務(wù)完成后返回查詢(xún)結(jié)果–編譯方當(dāng)數(shù)據(jù)庫(kù)中某些數(shù)據(jù)發(fā)生改變，再重新編譯編譯的方法主要優(yōu)點(diǎn)是2013/12/22 5.1.25.1.2 連接操作的實(shí) 投影操作的實(shí) 集合運(yùn)算的實(shí)2013/12/22 選擇操作的5-1】Select*fromstudentwhere條件表達(dá)式>，C1：無(wú)條C2：Sno=’200636’C3：Sage>C4：Sdept計(jì)算機(jī)andSno200636’C5：Sdept=‘計(jì)算機(jī)andSage>18C6：Sage18orSdept計(jì)算機(jī)2013/12/22 選擇操作的（1）順序掃描方實(shí)現(xiàn)選擇操作最簡(jiǎn)單的代價(jià)估算如下和內(nèi)存之間傳遞的），順序掃描方法的代價(jià)RB。R2013/12/22 選擇操作的（2）二分查找

查詢(xún)條C2：Sno二分查 順序掃描方法有效如果選擇是作用在非排序?qū)傩陨?代價(jià)也會(huì)相應(yīng)增代價(jià)估算如下二分查找法是針對(duì)文件的物理塊進(jìn)行的，平均搜代價(jià)log2BR如果選擇是作用在非排序?qū)傩陨?，那么將?huì)有塊包含所需的元組，代價(jià)也會(huì)相應(yīng)增加2013/12/22 選擇操作的（3）使用索引（或散列）的掃描方(h)2013/12/22 2檢索Sno>‘78’得到>18的所有元組指針得到>18的所有元組指針使用索引（或散列）的掃描方索引掃描算法的代價(jià)估1組可能會(huì)保存在不同塊上，情況下cost=L+S。2013/12/22 復(fù)合選擇－邏輯合取邏輯合取使用組合索以C4：Sdept計(jì)算機(jī)andSno200636’使用單獨(dú)索使用多個(gè)索2013/12/22 （4）復(fù)合選擇－邏輯合取邏輯合?。ˋND）（續(xù)使用單獨(dú)索以C5：Sdept計(jì)算機(jī)andSage18為例et對(duì)得到的元組檢查另一些選擇條件（如Sage>18）否滿(mǎn)足2013/12/22 （4）復(fù)合選擇－邏輯合取邏輯合?。ˋND）（續(xù)使用多個(gè)索分別檢索滿(mǎn)足單個(gè)條件以C5:Sdept計(jì)算andSage18為例，假設(shè)然后求這兩組指針的交集，再到student2013/12/22 （4）復(fù)合選擇－邏輯合取。））2013/12/22 （4）復(fù)合選擇－邏輯析取以C6為例，Sage18orSdept計(jì)算機(jī)2013/12/22 連接操作的（1）（2）（3）（4）（HashJoin）2013/12/22

A2013/12/22

例如，在關(guān)系S中的屬性B上存在索引則對(duì)于R中的每個(gè)元組，可以通過(guò)St[B]＝s[A]的所有元組而不必掃描S2013/12/22 等值連R

SABCABC568ACE5367882

BE3722在一般情況下，索引u2013/12/22 u適合連接的諸表已經(jīng)排好序的情如果連接的表沒(méi)有排好序先對(duì)Student表和SC連 Student表和SC表都只要掃描一 同如果兩個(gè)表原來(lái)無(wú)序，執(zhí)行時(shí)間加上對(duì)兩個(gè)表的排序時(shí) 對(duì)于兩個(gè)大表，先排序后使用排合并法執(zhí)行連接，總的時(shí)間一般仍會(huì)大的大減.

3

2013/12/22 散列連接（HashJoin）中劃分階段(partitioning對(duì)包含較少元組的表(比如R)進(jìn)行一遍處..........把它的元組按hash函..........1/22

關(guān)系 對(duì)另一個(gè)表(S)把S的元組散列到適當(dāng)?shù)膆ash把元組與桶中所有來(lái)自R并與之相匹配的元組連接起12/22

.....yy

.....

散列連接法前提以完全放入內(nèi)存的hash投影操作的否則通常的做法是先對(duì)操作結(jié)果進(jìn)行排序，去掉多余即把投影結(jié)果中的每條2013/12/22Sunda否則把該元組插入桶 集合運(yùn)算的并、差、交運(yùn)算實(shí)現(xiàn)的常用方法類(lèi)似排序合并法由于積的操作結(jié)果中包含了R和S中每個(gè)元組的組合，其結(jié)果比參與運(yùn)算的關(guān)系大得多,2013/12/22 第5第5章關(guān)系查詢(xún)處理和查詢(xún)優(yōu)5.15.3代數(shù)優(yōu)5.62013/12/22 5.25.2查詢(xún)優(yōu)化極大地影響RDBMS的性查詢(xún)優(yōu)化的可能關(guān)系系統(tǒng)的查詢(xún)優(yōu)化的用戶(hù)不必考慮如何最好地表達(dá)查系統(tǒng)可以比用戶(hù)程序2013/12/22 5.25.2–(1化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶(hù)程序則難以獲得這些(2)在非關(guān)系系統(tǒng)中必須重寫(xiě)程序，而重寫(xiě)程序在(3)。(4)2013/12/22 查詢(xún)優(yōu)化查詢(xún)優(yōu)化的總目標(biāo)：選擇有效策略，求得給定關(guān)系表)（1）代數(shù)優(yōu)是關(guān)系代數(shù)表達(dá)式的按照一定的規(guī)則，改變代數(shù)表達(dá)式中操作的次序組合，使查詢(xún)執(zhí)行更高效2013/12/22 查詢(xún)優(yōu)化（2）基于存取路徑的合理選擇的存取路徑以獲得需要考慮數(shù)據(jù)的物理組織和路徑，以及底層操（3）基于代價(jià)估算的對(duì)于多個(gè)可選的查詢(xún)策略通過(guò)估算執(zhí)行策略的代價(jià),從中選擇代價(jià)最小的作為執(zhí)行策略2013/12/22 查詢(xún)優(yōu)化【例5-2】查詢(xún)選修“DataBase”課程的學(xué)生成績(jī)。用SELECTFROMCourse，SC 等價(jià)關(guān)系代數(shù)表達(dá)2013/12/22 首先在內(nèi)存中盡可能多地裝入Course表，留出一塊存SC的元然后，把SC中的每個(gè)元組和C中的每個(gè)元組連接,完成之后，繼續(xù)讀入下一塊SC的元組，同樣和內(nèi)存中Cours的每個(gè)元組連接，依此類(lèi)推，直到SC表的元組接下來(lái)，再把表中沒(méi)有裝入的元組盡可能多地裝入內(nèi)存，同樣逐塊裝入SC表的元組去作元組的連接，2013/12/22 查詢(xún)優(yōu)化個(gè)SC元組。每次在內(nèi)存中放5塊Course元組和1塊SC元總塊數(shù)=讀Course表的塊數(shù)＋讀SC表的塊數(shù)＝讀Course表的塊數(shù)+讀SC表遍數(shù)*每遍塊 10＝10＋2×100＝210讀數(shù)據(jù)時(shí)間=210/20=10.5

讀寫(xiě)速度：20塊/中間結(jié)果大小=10000*100= (條元組Sua組讀數(shù)據(jù)時(shí)間=10.5 讀寫(xiě)速度：20塊/需要將上一步已經(jīng)連接好的106個(gè)元組重新讀入內(nèi)存，按假定內(nèi)存處理時(shí)間忽略，讀數(shù)據(jù)時(shí)間=5000秒與寫(xiě)文一樣,忽略?xún)?nèi)存處理時(shí)間滿(mǎn)足條件的元組為100個(gè)，可以 仍為100個(gè)元組，可以放在內(nèi)存中，不需要作I/O，同樣忽略?xún)?nèi)存處理2013/12/22 5.2.2查詢(xún)優(yōu)化 ame=‘DataBase’(Course?①總塊數(shù)210讀數(shù)據(jù)時(shí)間=210/20=10.5寫(xiě)中間結(jié)果時(shí)間=10000/10/20=50②這一步需要將上一步已經(jīng)連接好的10個(gè)元組重新讀入內(nèi)存，檢查是否滿(mǎn)足選擇條件，產(chǎn)生一個(gè)個(gè)元組讀數(shù)據(jù)時(shí)間=50 在屬性Grade上作投影操作，不需要作I/O＝＋5＋ 5.2.2查詢(xún)優(yōu)化Sname(SC? ①對(duì)Course表進(jìn)行選擇運(yùn)算，需要先裝入Course表元組=塊讀數(shù)據(jù)時(shí)間=10/20=0.5選擇滿(mǎn)足條件的元組，產(chǎn)生滿(mǎn)足條件的結(jié)果集為1②這一步包括將1000個(gè)SC的元組依次讀入內(nèi)存，和內(nèi)存中的1個(gè)Cour元組作自然連接。只需讀一遍SC=塊讀數(shù)據(jù)時(shí)間=100/20=5П，不需要作I/O總時(shí)間＝0.5＋5＝5.52013/12/22 條ame移到連條ame移到連接操作中的關(guān)系Course在第一個(gè)表達(dá)式中， 積實(shí)現(xiàn)兩個(gè)關(guān)系的查 ame=‘DataBase’(Course?選擇條 o 與積選擇條 o 與積組合成連接5.2.2查詢(xún)優(yōu)化Sname(SC? 假設(shè)表在o上有索①讀數(shù)據(jù)時(shí)間=10/20=0.5秒②不用 全部的SC元組， “DataBase”相對(duì)應(yīng)的課程代碼Cno相同的那些元組， 總塊數(shù)=100/100＝1塊③基于索引掃描的方法能進(jìn)一步提高查詢(xún)的性能，這就a 第5第5章關(guān)系查詢(xún)處理和查詢(xún)優(yōu)5.15.3代數(shù)優(yōu)5.62013/12/22 代數(shù)優(yōu)化策略：通過(guò)對(duì)關(guān)系代數(shù)表達(dá)式的等價(jià)變換提關(guān)系代數(shù)表達(dá)式等價(jià)是指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的，兩個(gè)關(guān)系表25.3.1關(guān)系代數(shù)表達(dá)式的等價(jià)設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)l.連接、積交E1×E2≡E2×

系統(tǒng)可以選擇小關(guān)系作

2013/12/22

2.連接 積的結(jié)合(E1×E2)× ≡E1× E3≡E1 ≡

對(duì)同一關(guān)系代數(shù)表達(dá)式的多個(gè)以轉(zhuǎn)換成

B1,B2,…,Bm A1,A2,…,AnE是關(guān)系代數(shù)表2013/12/22 F(F(E))≡F 選擇的串接定律說(shuō)明選這樣一次就可檢查全部5.選擇與投影的交換

假設(shè):選擇條件F只涉及屬性

A,A

(E))≡

A,A

(E)) A,A,A

F(E))≡

A,A,,A,B,B,,B 2013/12/22

6.選擇 積的交換假設(shè)：F中涉及的屬性都是E1F(E1×E2)≡F涉及E2中的屬性，則由上面的等價(jià)變換規(guī)則1，4，6可F(E1×E2)≡F1(E1)×F2假設(shè)：F=F1∧F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2涉及和E2兩者的屬F(E1×E2)≡F2(它使部分選擇 積前先2013/12/22

擇在積之前先7.選擇與并的分配假設(shè)：E=E1∪E2，E1，E2有相同的屬性F(E1∪E2)≡F(E1)∪8.選擇與差運(yùn)算的分假設(shè)：E1與E2有相同的屬F(E1-E2)≡F(E1)-9.選擇對(duì)自然連接的分 E2)≡ F只涉及E1與E2的公共屬2013/12/22 10.投影 積的分配假設(shè)：E1和E2是兩個(gè)關(guān)系表達(dá)式，A1，…，An是E1的屬性B1，…，Bm是E2的屬性 A,A,,A,B

A,A

B

l1.投影與并的分配A,A

(E1∪E2)≡

A,A

2013/12/22 代數(shù)優(yōu)化典型的啟發(fā)式規(guī)目的：減小中間關(guān)在優(yōu)化策略中這是最重要、目的：避免重復(fù)掃將投影運(yùn)算與其前面或合目的：減少掃描關(guān)2013/12/22 代數(shù)優(yōu)化典型的啟發(fā)式規(guī)則（續(xù)(4)把某些選擇同在它前面要執(zhí)行的 ： 在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處2013/12/22 5.3.25.3.2典型的啟發(fā)式規(guī)則（續(xù)(5)找出公共子表2013/12/22 代數(shù)優(yōu)化遵循這些啟發(fā)式規(guī)則，應(yīng)用關(guān)系代數(shù)等價(jià)變換公式來(lái)算法輸入輸出方法(1)利用等價(jià)變換規(guī)則4把形如F1∧F2∧…∧Fn(E)變換為F1(F2(…(Fn(E))…))。2013/12/22 代數(shù)優(yōu)化 注意等價(jià)變換規(guī)則3 2013/12/22 代數(shù)優(yōu)化(5)把上述得到的語(yǔ)法樹(shù)的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算()和它所有的直接祖先為一組(這些直接祖先是,運(yùn)算)。 2013/12/22 5.3.3代數(shù)優(yōu)化【例5-3】查詢(xún)選修了“DataBase”這門(mén)課程的計(jì)算機(jī)學(xué)院 SELECTFROMStudent，SC，WHEREStudent.Sno=SC.Snoo2013/12/22 SELECTSELECTFROMStudent，SC，CourseWHEREStudent.Sno=SC.Snoand 2013/12/22 ySELECTySELECTWHEREStudent.Sno=SC.SnoandandStudent.Dept='計(jì)算機(jī)學(xué)院andFROMStudent，SC， 5.3.3代數(shù)優(yōu)化算（3）對(duì)查詢(xún)樹(shù)進(jìn)行變換選擇運(yùn)算,得到單獨(dú)的4

選擇操作.盡可能將選擇操 移到樹(shù)的葉××

0205.3.3代數(shù)優(yōu)化算（3）對(duì)查詢(xún)樹(shù)進(jìn)行優(yōu)化(續(xù)根據(jù)算法5.1中的每一雙目運(yùn)算(,∪,－)和些直接祖先是,運(yùn)算)

×

×

2013/12/22

第5第5章關(guān)系查詢(xún)處理和查詢(xún)優(yōu)5.15.3代數(shù)優(yōu)5.62013/12/22 ,2013/12/22 選擇操作的啟發(fā)式對(duì)于大關(guān)系，啟發(fā)要估算查詢(xún)結(jié)果的元組如果比例較小(<10%)否則還是使用全表順序(4)對(duì)于選擇條件是屬性上的非等值查詢(xún)或者范圍查詢(xún)并且選擇列上有索引，與(3)2013/12/22 (5)(5)對(duì)于用AND優(yōu)先采用組合索引掃描如果某些屬性上有一般則可以用索引掃描否則使用全表順序掃2013/12/22 (1)選用排序-(2)如果一個(gè)表在連接屬性上有索選用索引連接方(3)如果上面兩個(gè)規(guī)則都不適用，其中一個(gè)表較2013/12/22 連接操作的啟發(fā)式 理由設(shè)連接表R與S分別占用的塊數(shù)為Br與連接操作使用的內(nèi)存緩沖區(qū)塊數(shù)為分配K-1塊給外如果R為外表BR

K1 –顯然應(yīng)該選塊數(shù)小的表–2013/12/22啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行的系–解釋執(zhí)行的系統(tǒng)，優(yōu)化開(kāi)銷(xiāo)包含在查詢(xún)總開(kāi)銷(xiāo)之編譯執(zhí)行的系統(tǒng)中查詢(xún)可以采用精細(xì)復(fù)雜一些 代價(jià) 在查詢(xún)執(zhí)行時(shí)生成的中間文件的代內(nèi)存使用代價(jià)：查詢(xún)執(zhí)行需要的內(nèi)存緩沖區(qū)數(shù)通信代價(jià)：查詢(xún)過(guò)程中數(shù)據(jù)在不同數(shù)據(jù)庫(kù)節(jié)點(diǎn)傳送2013/12/22 統(tǒng)計(jì)