1、數據庫原理咸陽師范學院信息工程學院第九章 關系查詢處理和查詢優化本章主要教學內容:9.1關系數據庫系統的查詢處理9.2關系數據庫系統的查詢優化9.3代數優化9.4物理優化重點及難點：了解查詢處理步驟；了解查詢處理的四個階段；掌握優化的方法；關系查詢處理和查詢優化查詢優化一般可分為代數優化和物理優化。代數優化是指關系代數表達式的優化。物理優化是指存取路徑和底層操作算法的選擇。9.1 關系數據庫系統的查詢處理9.1.1 查詢處理步驟9.1.2 實現查詢操作的算法示例9.1.1 查詢處理步驟查詢處理的任務是把用戶提交給RDBMS的查詢語句轉換為高效的執行計劃。RDBMS查詢處理可以分為4個階段：查詢

2、分析、查詢檢查、查詢優化和查詢執行。查詢分析對查詢語句進行掃描、詞法分析和語法分析。從查詢語句中識別出語言符號，如SQL關鍵字、屬性名和關系名等，進行語法檢查和語法分析，即判斷查詢語句是否符合SQL語法規則。查詢檢查根據數據字典對合法的查詢語句進行語義檢查，即檢查語句中的數據庫對象，如屬性名、關系名、是否存在和是否有效。根據數據字典中的用戶權限和完整性約束定義對用戶的存取權限進行檢查。檢查通過后便把SQL查詢語句轉換成等價的關系代數表達式。查詢檢查RDBMS一般都用查詢樹(query tree)，也稱為語法分析法(syntax tree)，來表示擴展的關系代數表達式。這個過程中要把數據庫對象的

3、外部名稱轉換為內部表示。查詢優化每個查詢都會有許多可供選擇的執行策略和操作算法，查詢優化就是選擇一個高效執行的查詢處理策略。查詢優化有多種方法，按照優化的層次一般可分為代數優化和物理優化。查詢優化選擇的規則：基于規則的基于代價的基于語義的查詢執行依據優化器得到執行策略生成查詢計劃，由代碼生成器(code generator)生成執行這個查詢計劃的代碼。9.1.2 實現查詢操作的算法示例選擇操作連接操作選擇操作的實現例1 Select * from student where <條件表達式>考慮<條件表達式>的幾種情況：C1：無條件C2：Sno=C3: Sage>2

4、0C4: Sdept=CS AND Sage>201.簡單的全表掃描方法2.索引（或散列）掃描方法連接操作的實現連接操作是查詢處理中最耗時的操作之一。例2 Select * from Student ，SC where Student.Sno=SC.Sno;1.嵌套循環方法2.排序-合并方法3.索引連接方法4.Hash Join方法9.2 關系數據庫系統的查詢優化9.2.1 查詢優化概述9.2.2 一個實例9.2.1 查詢優化概述查詢優化的必要性查詢優化極大地影響RDBMS的性能。 查詢優化的可能性關系數據語言的級別很高，使DBMS可以從關系表達式中分析查詢語義。 由DBMS進

5、行查詢優化的好處用戶不必考慮如何最好地表達查詢以獲得較好的效率系統可以比用戶程序的優化做得更好(1) 優化器可以從數據字典中獲取許多統計信息，而用戶程序則難以獲得這些信息 由DBMS進行查詢優化的好處(2)如果數據庫的物理統計信息改變了，系統可以自動對查詢重新優化以選擇相適應的執行計劃。 在非關系系統中必須重寫程序，而重寫程序在實際應用中往往是不太可能的。(3)優化器可以考慮數百種不同的執行計劃，而程序員一般只能考慮有限的幾種可能性。(4)優化器中包括了很多復雜的優化技術查詢優化目標查詢優化的總目標 選擇有效策略，求得給定關系表達式的值實際系統的查詢優化步驟1. 將查詢轉換成某種內部表示，通常

6、是語法樹2. 根據一定的等價變換規則把語法樹轉換成標準 （優化）形式實際系統的查詢優化步驟3. 選擇低層的操作算法對于語法樹中的每一個操作計算各種執行算法的執行代價選擇代價小的執行算法4. 生成查詢計劃(查詢執行方案)查詢計劃是由一系列內部操作組成的。代價模型集中式數據庫單用戶系統總代價 = I/O代價 + CPU代價多用戶系統總代價 = I/O代價 + CPU代價 + 內存代價分布式數據庫 總代價 = I/O代價 + CPU代價+ 內存代價 + 通信代價 4.2.2 查詢優化的必要性 例：求選修了課程2的學生姓名 SELECT Student.SnameFROM Student,

7、SCWHERE Student.Sno=SC.SnoAND SC.Cno='2' 查詢優化的必要性假設1：外存：Student:1000條,SC:10000條, 選修2號課程:50條假設2：一個內存塊裝元組:10個Student, 或100個SC, 內存中一次可以存放: 5塊Student元組, 1塊SC元組和若干塊連接結果元組假設3：讀寫速度：20塊/秒假設4：連接方法：基于數據塊的嵌套循環法執行策略11=name(Student.Sno=SC.Sno SC.Cno='2' (Student×SC)  Student×SC 讀取總

8、塊數= 讀Student表塊數 + 讀SC表遍數 *每遍塊數 =1000/10+(1000/(10×5) ×(10000/100) =100+20×100=2100 讀數據時間=2100/20=105秒不同的執行策略,考慮I/O時間中間結果大小 = 1000*10000 = 107 (1千萬條元組)寫中間結果時間 = 10000000/10/20 = 50000秒 讀數據時間 = 50000秒 總時間 =1055000050000秒 = 100105秒 = 27.8小時查詢優化的必要性2. 2 name(SC.Cno=' 2&

9、#39; (Student SC) 讀取總塊數= 2100塊讀數據時間=2100/20=105秒中間結果大小=10000 （減少1000倍）寫中間結果時間=10000/10/20=50秒 讀數據時間=50秒  總時間1055050秒205秒=3.4分查詢優化的必要性3. 2 Sname(Student SC.Cno=' 2' (SC) 讀SC表總塊數= 10000/100=100塊讀數據時間=100/20=5秒 中間結果大小=50條 不必寫入外存 讀 Student表總塊數= 1000/10=100塊讀數據時

10、間=100/20=5秒   總時間55秒10秒 查詢優化的必要性4. 2 name(Student SC.Cno='2' (SC)假設SC表在Cno上有索引，Student表在Sno上有索引  讀SC表索引=讀SC表總塊數= 50/100<1塊讀數據時間 中間結果大小=50條 不必寫入外存查詢優化的必要性 讀Student表索引=讀Student表總塊數= 50/10=5塊讀數據時間 總時間<10秒9.3代數優化9.3.1 關系代數表達式等價變換規則9.3.2 查詢樹的啟發式優化9.3.1 關系代數表達式等價變換規則關系代數表

11、達式等價指用相同的關系代替兩個表達式中相應的關系所得到的結果是相同的上面的優化策略大部分都涉及到代數表達式的變換常用的等價變換規則設E1、E2等是關系代數表達式，F是條件表達式 l. 連接、笛卡爾積交換律E1× E2 E2×E1E1 E2E2 E1 E1 F E2E2 F E1關系代數等價變換規則2. 連接、笛卡爾積的結合律 (E1×E2) × E3 E1 × (E2×E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F F F F關系代數等價變換規則3. 投影的串接定律 A1,A2, L

12、,An( B1,B2, L,Bm(E) A1,A2, L,An (E)假設：1)E是關系代數表達式2)Ai(i=1，2，n), Bj(j=l，2，m)是屬性名3)A1, A2, , An構成Bl，B2，Bm的子集 關系代數等價變換規則4. 選擇的串接定律 F1 （ F2（E） F1 F2(E)選擇的串接律說明 選擇條件可以合并這樣一次就可檢查全部條件。 關系代數等價變換規則5. 選擇與投影的交換律(1)假設: 選擇條件F只涉及屬性A1，An F (A1,A2, L,An(E) A1,A2, L,An(F(E) (2)假設: F中有不屬于A1, ,An的屬性B1,Bm A1,A2, L

13、,An ( F (E) A1,A2, L,An(F (A1,A2, L,An,B1,B2, L,Bm(E)關系代數等價變換規則6. 選擇與笛卡爾積的交換律(1) 假設：F中涉及的屬性都是E1中的屬性 F (E1×E2)F (E1)×E2 (2) 假設：F=F1F2，并且F1只涉及E1中的屬性， F2只涉及E2中的屬性 則由上面的等價變換規則1，4，6可推出： F(E1×E2) F1(E1)×F2 (E2)關系代數等價變換規則(3) 假設： F=F1F2， F1只涉及E1中的屬性， F2涉及E1和E2兩者的屬性 F(E1×E2) F2(

14、F1(E1)×E2) 它使部分選擇在笛卡爾積前先做 關系代數等價變換規則7. 選擇與并的交換假設：E=E1E2，E1，E2有相同的屬性名F(E1E2) F(E1) F(E2) 8. 選擇與差運算的交換假設：E1與E2有相同的屬性名F(E1-E2) F(E1) - F(E2) 關系代數等價變換規則9. 投影與笛卡爾積的交換假設：E1和E2是兩個關系表達式， A1，An是E1的屬性， B1，Bm是E2的屬性 A1,A2, ,An,B1,B2, ,Bm （E1×E2) A1,A2, ,An（E1)× B1,B2, ,Bm(E2)關系代數等價變換規則l0. 投影

15、與并的交換假設：E1和E2 有相同的屬性名 A1,A2, ,An(E1E2) A1,A2, ,An(E1) A1,A2, ,An(E2) 9.3.2 查詢樹的啟發式優化選擇運算應盡可能先做  目的：減小中間關系在執行連接操作前對關系適當進行預處理按連接屬性排序在連接屬性上建立索引 投影運算和選擇運算同時做目的：避免重復掃描關系將投影運算與其前面或后面的雙目運算結合目的：減少掃描關系的遍數9.3.2 查詢樹的啟發式優化某些選擇運算在其前面執行的笛卡爾積 => 連接運算 例：Student.Sno=SC.Sno (Student×SC)  

16、Student SC提取公共子表達式關系代數表達式的優化算法 算法：關系表達式的優化輸入：一個關系表達式的語法樹。輸出：計算該表達式的程序。方法：（1）分解選擇運算 利用規則4把形如F1 F2 Fn (E)變換為 F1 (F2( (Fn(E) ) 關系代數表達式的優化算法（2）通過交換選擇運算，將其盡可能移到葉端 對每一個選擇，利用規則48盡可能把它移到樹的葉端。 （3）通過交換投影運算，將其盡可能移到葉端對每一個投影利用規則3，9，l0，5中的一般形式盡可能把它移向樹的葉端。 關系代數表達式的優化算法（4）合并串接的選擇和投影，以便能同時執行或在一次掃描中完成利用規則35把選擇和投

17、影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執行，或在一次掃描中全部完成盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。 關系代數表達式的優化算法（5）對內結點分組把上述得到的語法樹的內節點分組。每一雙目運算(×， ，-)和它所有的直接祖先為一組(這些直接祖先是，運算)。如果其后代直到葉子全是單目運算，則也將它們并入該組，但當雙目運算是笛卡爾積(×)，而且其后的選擇不能與它結合為等值連接時除外。把這些單目運算單獨分為一組。 關系代數表達式的優化算法（6）生成程序生成一個程序，每組結點的計算是程序中的一步。各步的順序是任意的，

18、只要保證任何一組的計算不會在它的后代組之前計算。 優化的一般步驟 1把查詢轉換成某種內部表示2代數優化：把語法樹轉換成標準（優化） 形式3物理優化：選擇低層的存取路徑4生成查詢計劃，選擇代價最小的 優化的一般步驟（1）把查詢轉換成某種內部表示例4：求選修了課程2的學生姓名SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno='2' （1）把查詢轉換成某種內部表示語法樹 結果project(Sname) select(SC.Cno=¢2¢) join(Student.Sno=SC.Sno) StudentSC關系代數語法樹（2）代數優化利用優化算法把語法樹轉換成標準（優化）形式9.4 物理優化9.4.1 基于啟發式規則的存取路徑選擇優化9.4.2 基于代價的優化9