數(shù)據(jù)庫chpa原理及應用

1、數(shù)據(jù)庫原理及應用An Introduction to Database System第九章 關系查詢處理和查詢優(yōu)化關系系統(tǒng)及其查詢優(yōu)化（續(xù)）本章目的： RDBMS的查詢處理步驟 查詢優(yōu)化的概念 基本方法和技術 查詢優(yōu)化分類 ：代數(shù)優(yōu)化物理優(yōu)化查詢處理步驟（續(xù)）查詢處理步驟Select * form studenthaving sname=W字符串詞法分析語法分析符號轉換有沒有執(zhí)行該查詢的權限sname=Wstudent有沒有索引啦，記錄總數(shù)等 順序掃描的IO次數(shù)多少 使用索引為多少 調用使用索引的底層函數(shù)實現(xiàn)查詢操作的算法示例 一、 選擇操作的實現(xiàn) 二、 連接操作的實現(xiàn) 選擇操作的實現(xiàn) 例1S

2、elect * from student where ；考慮的幾種情況： C1：無條件； C2：Sno200215121； C3：SdeptCS AND Sage20； 選擇操作的實現(xiàn)（續(xù)）選擇操作典型實現(xiàn)方法：1. 簡單的全表掃描方法 對查詢的基本表順序掃描，逐一檢查每個元組是否滿足選擇條件，把滿足條件的元組作為結果輸出 適合小表，不適合大表2. 索引(或散列)掃描方法 適合選擇條件中的屬性上有索引(例如B+樹索引或Hash索引) 通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組 選擇操作的實現(xiàn)（續(xù)）例1-C2 以C2為例，Sno200215121，并且

3、Sno上有索引使用索引得到Sno為200215121 元組的指針通過元組指針在student表中檢索到該學生選擇操作的實現(xiàn)（續(xù)）例1-C3 以C3為例，SdeptCS AND Sage20，如果Sdept和Sage上都有索引：算法一：分別用上面兩種方法分別找到SdeptCS的一組元組指針和Sage20的另一組元組指針求這2組指針的交集到student表中檢索得到計算機系年齡大于20的學生算法二：找到SdeptCS的一組元組指針，通過這些元組指針到student表中檢索對得到的元組檢查另一些選擇條件(如Sage20)是否滿足把滿足條件的元組作為結果輸出。 連接操作的實現(xiàn) 連接操作是查詢處理中最耗

4、時的操作之一 本節(jié)只討論等值連接(或自然連接)最常用的實現(xiàn)算法 例2 SELECT * FROM Student，SC WHERE Student.Sno=SC.Sno； 連接操作的實現(xiàn)（續(xù)）1. 嵌套循環(huán)方法(nested loop) 2. 排序-合并方法(sort-merge join 或merge join)3. 索引連接(index join)方法 連接操作的實現(xiàn)（續(xù)）200215121200215122200215123200215124.200215121 1 92200215121 2 85200215121 3 88200215122 2 90200215122 3 80.排序

5、-合并連接方法示意圖連接操作的實現(xiàn)（續(xù)）-索引連接步驟： 在SC表上建立屬性Sno的索引，如果原來沒有該索引 對Student中每一個元組，由Sno值通過SC的索引查找相應的SC元組 把這些SC元組和Student元組連接起來 循環(huán)執(zhí)行，直到Student表中的元組處理完為止 An Introduction to Database System查詢優(yōu)化為什么要做優(yōu)化求選修了2號課程的學生姓名。用SQL表達： 假定學生-課程數(shù)據(jù)庫中有1000個學生記錄，10000個選課記錄其中選修2號課程的選課記錄為50個 SELECT Student.SnameFROM Student，SCWHERE Stu

6、dent.Sno=SC.Sno AND o=2；SSC1000條10000條50條方案1： Q1=Sname(Student.Sno=SC.Sno o=2 StudentSC)1.讀S表記錄：1000/10=100塊 100/20=5s2.讀SC表記錄: (100/5)*10000/100=2000塊 2000/20=100s3.連接: 忽略4.寫中間結果：1000*10000/10=106塊 106/ 20=50000s5.讀中間結果: 106塊 50000s6.過濾：忽略。 過濾結果 50/10=5塊 無需寫入硬盤 7. 投影：忽略 總共：(5+100 )/60=1668.4分鐘10010

7、101/20 s2/20 s3/20 s4/20 s5/20 sS-SC6/20 s7/20 s方案2： Q2=Sname( o=2 (Student SC)1.讀S表記錄：1000/10=100塊 100/20=5s2.讀SC表記錄: (100/5)*10000/100=2000塊 2000/20=100s3.自然連接: 忽略 1000條記錄4.寫中間結果：1000/10=100塊 100/ 20=5s5.讀中間結果: 100塊 5s6.過濾：忽略。 無需寫入硬盤 7. 投影：忽略 總共：(5+100+5+5)/60=1.91分鐘SELECT Student.SnameFROM Studen

8、t，SCWHERE Student.Sno=SC.Sno AND o=2；方案3： Q3=Sname(Student o=2(SC)1.讀SC表記錄: 10000/100=100塊 100/20=5s2.過濾:忽略。 50條/100=0.5塊 留內存3.讀S表記錄：1000/10=100塊 100/20=5s4.自然連接：忽略。 50/10=5塊 無需寫入硬盤5. 過濾：忽略。7. 投影：忽略。 總共：5+5=10秒SELECT Student.SnameFROM Student，SCWHERE Student.Sno=SC.Sno AND o=2；根據(jù)這個例子查詢優(yōu)化對于查詢效率至關重要為了

9、加快查詢，應該：盡量減少中間結果的IO操作盡量合并可以合并的操作那么怎樣才能達到上面的目的？選擇投影盡可能先做。選擇要和他前面的笛卡爾積盡可能合并成連接投影和選擇盡可能合并為一步查詢優(yōu)化概述RDBMS通過某種代價模型計算出各種查詢執(zhí)行策略的執(zhí)行代價，然后選取代價最小的執(zhí)行方案集中式數(shù)據(jù)庫執(zhí)行開銷主要包括：磁盤存取塊數(shù)(I/O代價)處理機時間(CPU代價)查詢的內存開銷 I/O代價是最主要的 分布式數(shù)據(jù)庫總代價=I/O代價+CPU代價+內存代價通信代價 An Introduction to Database System 代數(shù)優(yōu)化 關系代數(shù)表達式等價變換規(guī)則（續(xù)）常用的等價變換規(guī)則：1. 連接、

10、笛卡爾積交換律 設E1和E2是關系代數(shù)表達式，F(xiàn)是連接運算的條件，則有 E1 E2E2 E1 E1 E2E2 E1 E1 E2E2 E12. 連接、笛卡爾積的結合律 設E1，E2，E3是關系代數(shù)表達式，F(xiàn)1和F2是連接運算的條件，則有 (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) 關系代數(shù)表達式等價變換規(guī)則（續(xù)）3. 投影的串接定律 ( (E) (E)這里，E是關系代數(shù)表達式，Ai(i=1，2，n)，Bj(j=1，2，m)是屬性名且A1，A2，An構成B1，B2，Bm的子集。4. 選擇的串接定律 ( (E) (E)

11、這里，E是關系代數(shù)表達式，F(xiàn)1、F2是選擇條件。 選擇的串接律說明選擇條件可以合并。這樣一次就可檢查全部條件。關系代數(shù)表達式等價變換規(guī)則（續(xù)）5. 選擇與投影操作的交換律 F( (E) (F(E)選擇條件F只涉及屬性A1，An。若F中有不屬于A1，An的屬性B1，Bm則有更一般的規(guī)則： (F(E) (F( (E)關系代數(shù)表達式等價變換規(guī)則（續(xù)）6. 選擇與笛卡爾積的交換律如果F中涉及的屬性都是E1中的屬性，則 (E1E2) (E1)E2如果F=F1F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面的等價變換規(guī)則1，4，6可推出： (E1E2) (E1) (E2)若F1只涉及E1

12、中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則仍有 (E1E2) ( (E1)E2)它使部分選擇在笛卡爾積前先做。 關系代數(shù)表達式等價變換規(guī)則（續(xù)）7. 選擇與并的分配律設E=E1E2，E1，E2有相同的屬性名，則 F(E1E2)F(E1)F(E2)8. 選擇與差運算的分配律若E1與E2有相同的屬性名，則 F(E1-E2)F(E1)-F(E2)9. 選擇對自然連接的分配律 F(E1 E2)F(E1) F(E2) F只涉及E1與E2的公共屬性 關系代數(shù)表達式等價變換規(guī)則（續(xù)）10. 投影與笛卡爾積的分配律設E1和E2是兩個關系表達式，A1，An是E1的屬性，B1，Bm是E2的屬性，則 (E1E2)

13、(E1) (E2)11. 投影與并的分配律設E1和E2有相同的屬性名，則 (E1E2) (E1) (E2)查詢樹的啟發(fā)式優(yōu)化 典型的啟發(fā)式規(guī)則：1. 選擇運算應盡可能先做。在優(yōu)化策略中這是最重要、最基本的一條2. 把投影運算和選擇運算同時進行如有若干投影和選擇運算，并且它們都對同一個關系操作，則可以在掃描此關系的同時完成所有的這些運算以避免重復掃描關系查詢樹的啟發(fā)式優(yōu)化（續(xù)）3. 把投影同其前或其后的雙目運算結合起來4. 把某些選擇同在它前面要執(zhí)行的笛卡爾積結合起來成為一個連接運算5. 找出公共子表達式如果這種重復出現(xiàn)的子表達式的結果不是很大的關系并且從外存中讀入這個關系比計算該子表達式的時間

14、少得多，則先計算一次公共子表達式并把結果寫入中間文件是合算的當查詢的是視圖時，定義視圖的表達式就是公共子表達式的情況查詢樹的啟發(fā)式優(yōu)化（續(xù)）遵循這些啟發(fā)式規(guī)則，應用等價變換公式來優(yōu)化關系表達式的算法。算法：關系表達式的優(yōu)化輸入：一個關系表達式的查詢樹輸出：優(yōu)化的查詢樹方法：(1) 利用等價變換規(guī)則4把形如F1F2Fn(E)變換為F1(F2(Fn(E)。(2) 對每一個選擇，利用等價變換規(guī)則49盡可能把它移到樹的葉端。查詢樹的啟發(fā)式優(yōu)化（續(xù)）(3) 對每一個投影利用等價變換規(guī)則3，5，10，11中的一般形式盡可能把它移向樹的葉端。注意： 等價變換規(guī)則3使一些投影消失規(guī)則5把一個投影分裂為兩個，其

15、中一個有可能被移向樹的葉端 (4) 利用等價變換規(guī)則35把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成 查詢樹的啟發(fā)式優(yōu)化（續(xù)） (5) 把上述得到的語法樹的內節(jié)點分組。每一雙目運算(， ，-)和它所有的直接祖先為一組(這些直接祖先是(，運算)。如果其后代直到葉子全是單目運算，則也將它們并入該組但當雙目運算是笛卡爾積()，而且后面不是與它組成等值連接的選擇時，則不能把選擇與這個雙目運算組成同一組，把這些單目運算單獨分為一組 查詢樹的啟發(fā)式優(yōu)化（續(xù)）下面給出 SQL語句的代數(shù)優(yōu)化示例。 (1) 把SQL語句轉換成查詢樹，如下圖

16、所示查詢樹查詢樹的啟發(fā)式優(yōu)化（續(xù)）為了使用關系代數(shù)表達式的優(yōu)化法，假設內部表示是關系代數(shù)語法樹，則上面的查詢樹如下圖所示。 關系代數(shù)語法樹 查詢樹的啟發(fā)式優(yōu)化（續(xù)）(2) 對查詢樹進行優(yōu)化利用規(guī)則4、6把選擇 o=2移到葉端，查詢樹便轉換成下圖所示的優(yōu)化的查詢樹。這就是9.2.2節(jié)中Q3的查詢樹表示優(yōu)化后的查詢樹 可以合并為一步自然連接嗎？可以合并為一組？An Introduction to Database System物理優(yōu)化物理優(yōu)化代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑對于一個查詢語句有許多存取方案，它們的執(zhí)行效率不同， 僅僅進行代數(shù)優(yōu)化是不夠的 物理優(yōu)化就是要選擇

17、高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計劃 物理優(yōu)化（續(xù)）選擇的方法： 基于規(guī)則的啟發(fā)式優(yōu)化基于代價估算的優(yōu)化兩者結合的優(yōu)化方法選擇的啟發(fā)式規(guī)則:1. 對于小關系，使用全表順序掃描，即使選擇列上有索引 對于大關系，啟發(fā)式規(guī)則有：2. 對于選擇條件是主碼值的查詢查詢結果最多是一個元組，可以選擇主碼索引 3.對于選擇條件是非主屬性值的查詢，并且選擇列上有索引如果符合查詢的元組比例較小(10%)可以使用索引掃描方法否則還是使用全表順序掃描選擇的啟發(fā)式規(guī)則（續(xù)）:4. 對于選擇條件是屬性上的非等值查詢或者范圍查詢，且選擇列上有索引如果符合查詢的元組比例較小(10%)可以使用索引掃描否則還是使用全

18、表順序掃描 5. 對于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引，優(yōu)先采用組合索引掃描如果某些屬性上有一般的索引，用索引掃描否則還是使用全表順序掃描 6. 對于用OR連接的析取選擇條件，一般使用全表順序掃描連接操作的啟發(fā)式規(guī)則：1. 如果2個表都已經(jīng)按照連接屬性排序 選用排序-合并方法2. 如果一個表在連接屬性上有索引 選用索引連接方法3. 如果上面2個規(guī)則都不適用，其中一個表較小 選用Hash join方法4. 可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地講是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表)基于代價的優(yōu)化-可用的統(tǒng)計信息每個基本表該表的元組總數(shù)(N) 元組長度

19、(l)占用的塊數(shù)(B) 占用的溢出塊數(shù)(BO)基表的每個列該列不同值的個數(shù)(m)選擇率(f)如果不同值的分布是均勻的，f1/m如果不同值的分布不均勻，則每個值的選擇率具有該值的元組數(shù)/N該列最大值 最小值該列上是否已經(jīng)建立了索引及索引類型為什么這些信息是可用的？基于代價的優(yōu)化（續(xù)）索引(如B+樹索引)索引的層數(shù)(L)不同索引值的個數(shù)索引的選擇基數(shù)S(有S個元組具有某個索引值)索引的葉結點數(shù)(Y) 為什么這些信息是可用的？基于代價的優(yōu)化-示例 （續(xù)）1.全表掃描算法的代價估算公式如果基本表大小為B塊，全表掃描算法的代價 costB如果選擇條件是碼值，那么平均搜索代價 costB/22. 索引掃描算法的代價估算公式如果選擇條件是碼值則掃描主索引。若為B+樹，層數(shù)為L，需要存取B+樹