數(shù)據(jù)庫原理9-2

1、第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化授課教師：顧留碗復(fù)習(xí)上節(jié)課內(nèi)容復(fù)習(xí)上節(jié)課內(nèi)容v索引的創(chuàng)建及管理索引的創(chuàng)建及管理 建立索引的必要性 索引的類型 管理索引（創(chuàng)建、查看、修改、刪除）v關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 查詢分析 查詢檢查 查詢優(yōu)化 查詢執(zhí)行本次課學(xué)習(xí)內(nèi)容本次課學(xué)習(xí)內(nèi)容v關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 v代數(shù)優(yōu)化v物理優(yōu)化 一、關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化一、關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 v查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位 v關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素 v由于關(guān)系表達(dá)式的語義級別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語義，提供

2、了執(zhí)行查詢優(yōu)化的可能性 v查詢優(yōu)化的優(yōu)點不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好 ； （1）優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息許多統(tǒng)計信息，而用戶程序則難以獲得這些信息； （2）如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實際應(yīng)用中往往是不太可能的。 (3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃考慮數(shù)百種不同的執(zhí)行計劃，程序員一般只能考慮有限的幾種可能性。 (4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu)化相

3、當(dāng)于使得系統(tǒng)的自動優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)。所有人都擁有這些優(yōu)化技術(shù)。vRDBMS通過某種代價模型計算出各種查詢執(zhí)行策略的執(zhí)行代價，然后選取代價最小的執(zhí)行方案： 集中式數(shù)據(jù)庫集中式數(shù)據(jù)庫 執(zhí)行開銷主要包括： 磁盤存取塊數(shù)磁盤存取塊數(shù)(I/O代價代價) 處理機時間處理機時間(CPU代價代價) 查詢的內(nèi)存開銷查詢的內(nèi)存開銷 I/O代價是最主要的 分布式數(shù)據(jù)庫分布式數(shù)據(jù)庫 總代價總代價=I/O代價代價+CPU代價代價+內(nèi)存代價通信代價內(nèi)存代價通信代價v查詢優(yōu)化的總目標(biāo)： 選擇有效的策略； 求得給定關(guān)系表達(dá)式的值； 使得查詢代價最小(實際上是較小) ；實例演示（驗證為何需要查詢優(yōu)化？）實

4、例演示（驗證為何需要查詢優(yōu)化？）例例1： 求選修了求選修了2號課程的學(xué)生姓名。號課程的學(xué)生姓名。假定學(xué)生-課程數(shù)據(jù)庫中有1000條學(xué)生記錄，10000條選課記錄；其中選修2號課程的選課記錄為50條； 用SQL表達(dá)： SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2 v系統(tǒng)可以用多種等價的關(guān)系代數(shù)表達(dá)式關(guān)系代數(shù)表達(dá)式來完成：Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 (StudentSC)Q2=Sname(Sc.Cno=2 (Student SC)Q3=Sname(St

5、udent Sc.Cno=2(SC)1、第一種情況、第一種情況v 分三個步驟： 計算StudentSC花費時間，即計算笛卡爾積操作時間； 計算Student.Sno=SC.SnoSc.Cno=2 花費時間，即計算選擇操作時間； 計算Sname花費時間，即計算投影操作時間；1）計算笛卡爾積時間）計算笛卡爾積時間v把Student和SC的每個元組連接起來的做法： 在內(nèi)存中盡可能多地裝入某個表(如Student表)的若干塊，留出一塊存放另一個表(如SC表)的元組； 把SC中的每個元組和Student中每個元組連接，連接后的元組裝滿一塊后就寫到中間文件上； 從SC中讀入一塊和內(nèi)存中的Student元組

6、連接，直到SC表處理完； 再讀入若干塊Student元組，讀入一塊SC元組； 重復(fù)上述處理過程，直到把Student表處理完；v 設(shè)一個塊能裝10個Student元組或100個SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為： =100 + 20100=2100塊v 若每秒讀寫20塊，則總計要花105s ；v 連接后的元組數(shù)為103104=107；v 設(shè)每塊能裝10個元組，則寫出這些塊要用106/20=5104s ；1010005101000100100002）計算選擇時間）計算選擇時間v 依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄； v 假定內(nèi)存處理時間忽

7、略；v 讀取中間文件花費的時間(同寫中間文件一樣)需5104s ；v 滿足條件的元組假設(shè)僅50個，均可放在內(nèi)存； 3）作投影操作）作投影操作v 把第2步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果 ；v 所有內(nèi)存處理時間均忽略不計；第一種情況下執(zhí)行查詢的總時間第一種情況下執(zhí)行查詢的總時間105 + 25104105s2、第二種情況、第二種情況v 分三個步驟： 計算Student SC花費時間，即計算自然連接操作時間； 計算Sc.Cno=2 花費時間，即計算選擇操作時間； 計算Sname花費時間，即計算投影操作時間；1）計算自然連接時間）計算自然連接時間v 讀取Student和SC表的策略不變，

8、總的讀取塊數(shù)仍為2100塊，花費105 s ；v 自然連接的結(jié)果比第一種情況大大減少，為104個 ；v 寫出這些元組時間為103/20=50s，為第一種情況的千分之一；2）計算選擇操作時間）計算選擇操作時間v 讀取中間文件塊，執(zhí)行選擇運算，花費時間也為50s；3）計算選擇操作時間：）計算選擇操作時間：把第2步結(jié)果投影輸出。 第二種情況下執(zhí)行查詢的總時間第二種情況下執(zhí)行查詢的總時間105+50+50205s 3、第三種情況、第三種情況v 分三個步驟： 先對SC表作選擇運算，只需讀一遍SC表，需存取100塊，花費時間為5s，因為滿足條件的元組僅50個，不必使用中間文件。 讀取Student表，把讀

9、入的Student元組和內(nèi)存中的SC元組作連接。也只需讀一遍Student表共100塊，花費時間為5s。 把連接結(jié)果投影輸出；第三種情況下執(zhí)行查詢的總時間第三種情況下執(zhí)行查詢的總時間5+5 10sv由Q1變換為Q2、 Q3得出結(jié)論： 即有選擇和連接操作時，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數(shù)優(yōu)化代數(shù)優(yōu)化；v在Q3中： SC表的選擇操作算法有全表掃描和索引掃描2種方法，經(jīng)過初步估算，索引掃描方法較優(yōu) ； 對于Student和SC表的連接，利用Student表上的索引，采用index join代價也較小，這就是物理優(yōu)化物理優(yōu)化； 二、代數(shù)優(yōu)化二、代數(shù)優(yōu)化v代數(shù)優(yōu)化策略代數(shù)優(yōu)化策

10、略： 通過對關(guān)系代數(shù)表達(dá)式的等價變換來提高查詢效率；v關(guān)系代數(shù)表達(dá)式的等價：指用相同的關(guān)系代替兩個表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的；v兩個關(guān)系表達(dá)式E1和E2是等價的，可記為E1E2 1）連接、笛卡爾積）連接、笛卡爾積交換律交換律 設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運算的條件，則有 E1 E2E2 E1 E1 E2E2 E1 E1 E2E2 E12）連接、笛卡爾積的）連接、笛卡爾積的結(jié)合律結(jié)合律 設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運算的條件，則有 (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E

11、3) 1、常用的等價變換規(guī)則（、常用的等價變換規(guī)則（P269）2、查詢樹的啟發(fā)式優(yōu)化、查詢樹的啟發(fā)式優(yōu)化v啟發(fā)式規(guī)則：啟發(fā)式規(guī)則： 選擇運算應(yīng)盡可能先做；選擇運算應(yīng)盡可能先做；在優(yōu)化策略中這是最重要、最基本的一條； 把投影運算和選擇運算同時進(jìn)行；把投影運算和選擇運算同時進(jìn)行； 如有若干投影和選擇運算，并且它們都對同一個關(guān)系操作，則可以在掃描此關(guān)系的同時完成所有的這些運算以避免重復(fù)掃描關(guān)系； 把投影同其前或其后的雙目運算結(jié)合起來； 把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個連接運算； 找出公共子表達(dá)式；優(yōu)化關(guān)系表達(dá)式的算法（優(yōu)化關(guān)系表達(dá)式的算法（P271） 算法：關(guān)系表達(dá)式的優(yōu)化；算法

12、：關(guān)系表達(dá)式的優(yōu)化；輸入：一個關(guān)系表達(dá)式的查詢樹；輸出：優(yōu)化的查詢樹；輸入：一個關(guān)系表達(dá)式的查詢樹；輸出：優(yōu)化的查詢樹；方法：方法：1）利用等價變換規(guī)則4把形如F1F2Fn(E)變換為F1(F2(Fn(E)；2）對每一個選擇，利用等價變換規(guī)則49盡可能把它移到樹的葉端；3）對每一個投影利用等價變換規(guī)則3，5，10，11中的一般形式盡可能把它移向樹的葉端；4）利用等價變換規(guī)則35把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影；5) 把上述得到的語法樹的內(nèi)節(jié)點分組。v例：將例例：將例1的的SQL語句的代數(shù)優(yōu)化；語句的代數(shù)優(yōu)化； 關(guān)系代數(shù)語法樹 三、物理優(yōu)化三、物理優(yōu)化v 代數(shù)優(yōu)化

13、改變查詢語句中操作的次序和組合，不涉及底層的存取路徑；對于一個查詢語句有許多存取方案，它們的執(zhí)行效率不同， 僅僅進(jìn)行代數(shù)優(yōu)化是不夠的 ；v 物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計劃 ；v 選擇的方法： 基于規(guī)則的啟發(fā)式優(yōu)化 基于代價估算的優(yōu)化 兩者結(jié)合的優(yōu)化方法1、基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化、基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化P2731） 選擇操作的啟發(fā)式規(guī)則: 對于小關(guān)系，使用全表順序掃描，即使選擇列上有索引 對于大關(guān)系，啟發(fā)式規(guī)則有： 對于選擇條件是主碼值的查詢； 查詢結(jié)果最多是一個元組，可以選擇主碼索引； 一般的RDBMS會自動建立主碼索引； 對于選擇條件是

14、非主屬性值的查詢，并且選擇列上有索引 要估算查詢結(jié)果的元組數(shù)目 如果比例較小(10%)可以使用索引掃描方法 否則還是使用全表順序掃描2） 連接操作的啟發(fā)式規(guī)則： 如果2個表都已經(jīng)按照連接屬性排序 選用排序-合并方法 如果一個表在連接屬性上有索引 選用索引連接方法 如果上面2個規(guī)則都不適用，其中一個表較小 選用Hash join方法 可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地講是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表) 。2、基于代價的優(yōu)化、基于代價的優(yōu)化P274v基于代價的優(yōu)化方法要計算各種操作算法的執(zhí)行代價，與數(shù)據(jù)庫的狀態(tài)密切相關(guān) ；v數(shù)據(jù)字典中存儲的優(yōu)化器需要的統(tǒng)計信息： 1）對每個基本表n該表的元組總數(shù)(N)n元組長度(l)n占用的塊數(shù)(B)n占用的溢出塊數(shù)(BO)2）對基表的每個列3）對索引(如B+樹索引)代價估算示例代價估算示例 1）全表掃描算法的代價估算公式 如果基本表大小為B塊，全表掃描算法的代價 costB 如果選擇