關(guān)系查詢處理和查詢優(yōu)化.ppt.Convertor

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

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

3、中要把數(shù)據(jù)庫對象的外部名稱轉(zhuǎn)換為內(nèi)部表示。查詢優(yōu)化每個查詢都會有許多可供選擇的執(zhí)行策略和操作算法，查詢優(yōu)化就是選擇一個高效執(zhí)行的查詢處理策略。查詢優(yōu)化有多種方法，按照優(yōu)化的層次一般可分為代數(shù)優(yōu)化和物理優(yōu)化。查詢優(yōu)化選擇的規(guī)則：基于規(guī)則的基于代價的基于語義的查詢執(zhí)行依據(jù)優(yōu)化器得到執(zhí)行策略生成查詢計劃，由代碼生成器(code gen erator)生成執(zhí)行這個查詢計劃的代碼。9.1.2 實現(xiàn)查詢操作的算法示例選擇操作連接操作選擇操作的實現(xiàn)例 1 Select * from student where 考慮 的幾種情況：C1 ：無條件C2：Sno=1C3: Sage20C4: Sdept= CS A

4、ND Sage201. 簡單的全表掃描方法2. 索引(或散列)掃描方法連接操作的實現(xiàn) 連接操作是查詢處理中最耗時的操作之一。例 2 Select * from Student ， SC where Student.Sno=SC.Sno;1. 嵌套循環(huán)方法2. 排序 -合并方法3. 索引連接方法4. Hash Join 方法9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2.1 查詢優(yōu)化概述9.2.2 一個實例9.2.1 查詢優(yōu)化概述查詢優(yōu)化的必要性查詢優(yōu)化極大地影響 RDBMS 的性能。查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語言的級別很高，使 DBMS 可以從關(guān)系表達式中分析查詢語義。由 DBMS 進行查詢優(yōu)化的好處

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

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

7、tudent, SCWHERE Student.Sno=SC.SnoAND SC.Cno=2;查詢優(yōu)化的必要性假設(shè) 1：外存：Student:1000 條 ,SC:10000 條, 選修 2 號課程 :50 條 假設(shè) 2：一個內(nèi)存塊裝元組 :10 個 Student, 或 100 個 SC, 內(nèi)存中一次可以存放 5 塊 Student 元組 ,1塊 SC 元組和若干塊連接結(jié)果元組假設(shè) 3：讀寫速度：20 塊 /秒假設(shè) 4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法 執(zhí)行策略 1Q1= ns name(6 Stude nt.S no=SC.S no A SC.C no=2 (Stude nt x SC)

8、Studentx SC讀取總塊數(shù) = 讀 Student 表塊數(shù) + 讀 SC 表遍數(shù)* 每遍塊數(shù)=1000/10+(1000/(10 5) x (x1 0000/1 00)= 1 00+20 x1 00= 2 1 00讀數(shù)據(jù)時間 =2100/20=105 秒不同的執(zhí)行策略 ,考慮 I/O 時間中間結(jié)果大小 = 1000*10000 = 107(1 千萬條元組 )寫中間結(jié)果時間 = /10/20 = 50000 秒6讀數(shù)據(jù)時間 = 50000 秒n總時間 =1055000050000 秒 = 100105 秒 = 27.8 小時查詢優(yōu)化的必要性2. Q 2= ns name(6 SC.C no

9、= 2 (Stude ntSC) 讀取總塊數(shù) = 2100 塊 讀數(shù)據(jù)時間 =2100/20=105 秒 中間結(jié)果大小 =10000 (減少 1000 倍) 寫中間結(jié)果時間 =10000/10/20=50 秒6讀數(shù)據(jù)時間 =50 秒n總時間= 1055050秒= 205秒=3.4 分 查詢優(yōu)化的必要性3. Q 2= n Sname(Student6 SC.Cno= 2 (SC)6讀 SC 表總塊數(shù) = 10000/100=100 塊 讀數(shù)據(jù)時間 =100/20=5 秒 中間結(jié)果大小 =50 條 不必寫入外存讀 Student 表總塊數(shù) = 1000/10=100 塊 讀數(shù)據(jù)時間 =100/20

10、=5 秒n總時間= 5 5 秒= 10 秒 查詢優(yōu)化的必要性4. Q 2= n S name(Student6 SC.Cno=2 (SC)假設(shè)SC表在Cno上有索引，Student表在Sno上有索引6讀 SC 表索引 = 讀 SC 表總塊數(shù) = 50/100 連接運算例：6 Student.Sno=SC.Sno （Studentx SC）Student SC提取公共子表達式 關(guān)系代數(shù)表達式的優(yōu)化算法 算法：關(guān)系表達式的優(yōu)化 輸入：一個關(guān)系表達式的語法樹。 輸出：計算該表達式的程序。方法：（1）分解選擇運算利用規(guī)則4把形如6 F1 A F2 AA Fn （E）變換為6 F1 （ 6 F2（ （

11、6 Fn（E） 關(guān)系代數(shù)表達式的優(yōu)化算法（2）通過交換選擇運算，將其盡可能移到葉端對每一個選擇，利用規(guī)則 48盡可能把它移到樹的葉端。（3）通過交換投影運算，將其盡可能移到葉端對每一個投影利用規(guī)則 3，9，l0，5 中的一般形式盡可能把它移向樹的葉端。 關(guān)系代數(shù)表達式的優(yōu)化算法（4）合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成利用規(guī)則 35 把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。 使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成 盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。 關(guān)系代數(shù)表達式的優(yōu)化算法（5）對內(nèi)結(jié)點分組 把上述得到的語法

12、樹的內(nèi)節(jié)點分組。每一雙目運算（X, , U,-）和它所有的直接祖先為一組 （這些直接祖先是6 , n運算）。 如果其后代直到葉子全是單目運算，則也將它們并入該組，但當雙目運算是笛卡爾積（X ）,而且其后的選擇不能與它結(jié)合為等值連接時除外。把這些單目運算單獨分為一組。 關(guān)系代數(shù)表達式的優(yōu)化算法（6）生成程序 生成一個程序,每組結(jié)點的計算是程序中的一步。 各步的順序是任意的,只要保證任何一組的計算不會在它的后代組之前計算。 優(yōu)化的一般步驟1把查詢轉(zhuǎn)換成某種內(nèi)部表示2 代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標準(優(yōu)化)形式3 物理優(yōu)化：選擇低層的存取路徑4 生成查詢計劃，選擇代價最小的優(yōu)化的一般步驟(1)把查詢轉(zhuǎn)

13、換成某種內(nèi)部表示例4:求選修了課程C 2的學(xué)生姓名SELECT Stude nt.S nameFROMStude nt, SCWHERE Stude nt.S no=SC.S noANDSC.C no=2;(1)把查詢轉(zhuǎn)換成某種內(nèi)部表示語法樹 結(jié)果project(S name)seleci(.SC.Cno- 2 )joi n(Stude nt.S no=SC.S no)Stude ntSC關(guān)系代數(shù)語法樹(2 )代數(shù)優(yōu)化利用優(yōu)化算法把語法樹轉(zhuǎn)換成標準(優(yōu)化)形式9.4物理優(yōu)化9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2基于代價的優(yōu)化9.4物理優(yōu)化-優(yōu)化器查找數(shù)據(jù)字典獲得當前數(shù)據(jù)庫狀態(tài)信息

14、選擇字段上是否有索引連接的兩個表是否有序連接字段上是否有索引然后根據(jù)一定的優(yōu)化規(guī)則選擇存取路徑如本例中若SC表上建有Cno的索引，則應(yīng)該利用這個索引，而不必順序掃描SC表。在作連接運算時，若兩個表 (設(shè)為R1, R2)均無序，連接屬性上也沒有索引，則可以有下面 幾種查詢計劃：對兩個表作排序預(yù)處理對R1在連接屬性上建索引對R2在連接屬性上建索引在R1 , R2的連接屬性上均建索引對不同的查詢計劃計算代價，選擇代價最小的一個。在計算代價時主要考慮磁盤讀寫的I/O數(shù)，內(nèi)存CPU處理時間在粗略計算時可不考慮。僅供個人用于學(xué)習、研究；不得用于商業(yè)用途For personal use only in study and research; not for commercial use.Nur f u r den pers?nlichen f u r Studien, Forschung, zu kommier