關系系統(tǒng)及查詢優(yōu)化

1、關系系統(tǒng)及查詢優(yōu)化 關系系統(tǒng)的定義、分類 全關系系統(tǒng)的十二條基本準則 查詢優(yōu)化的目標、步驟 查詢優(yōu)化的實例 查詢優(yōu)化的一般準則 關系代數(shù)表達式的優(yōu)化算法一、關系系統(tǒng)定義 關系系統(tǒng)：支持關系模型的數(shù)據(jù)庫管理系統(tǒng)稱為關系關系系統(tǒng)：支持關系模型的數(shù)據(jù)庫管理系統(tǒng)稱為關系系統(tǒng)。系統(tǒng)。（籠統(tǒng)） 關系模型中并非每一部分都同等重要，并不苛求一個實際的關系數(shù)據(jù)庫 管理系統(tǒng)必須完全支持關系模型，也不苛求完全支持關系模型的系統(tǒng)才能稱為關系系統(tǒng)。 一個系統(tǒng)可定義為關系系統(tǒng)，當且僅當它一個系統(tǒng)可定義為關系系統(tǒng)，當且僅當它至少至少： 1、支持關系數(shù)據(jù)結構（表） 2、支持選擇、投影和（自然）連接運算，對這些運算 不要求用戶

2、定義任何物理存取路徑。 對關系系統(tǒng)的最低要求關系系統(tǒng)的定義（續(xù)） 不支持關系數(shù)據(jù)結構的系統(tǒng)顯然不能稱為關系系統(tǒng) 僅支持關系數(shù)據(jù)結構，但沒有選擇、投影和連接運算功能的系統(tǒng)仍不能算作關系系統(tǒng)。 原因：不能提高用戶的生產(chǎn)率 支持選擇、投影和連接運算，但要求定義物理存取路徑，這種系統(tǒng)也不能算作真正的關系系統(tǒng) 原因：就降低或喪失了數(shù)據(jù)的物理獨立性 選擇、投影、連接運算是最有用的運算二、關系系統(tǒng)的分類前面定義的關系系統(tǒng)是關系系統(tǒng)的最小要求。按照E.F.Codd的思想，可以把關系系統(tǒng)分類：1、表式系統(tǒng) 僅支持表數(shù)據(jù)結構，不支持集合級的操作，不能算關系系統(tǒng)。2、最小關系系統(tǒng)支持關系數(shù)據(jù)結構和三種關系操作。（F

3、oxBase, FoxPro等）3、關系完備的系統(tǒng)支持關系數(shù)據(jù)結構和所有的關系代數(shù)操作（功能上等價）。4、全關系系統(tǒng)支持關系模型的所有特征。即不僅是關系上完備的，而且支持數(shù)據(jù)結構中域的概念，支持實體完整性和參照完整性。（目前大多數(shù)關系系統(tǒng)已接近或達到了這個目標）關系系統(tǒng)的分類 （續(xù)） 數(shù)據(jù)結構數(shù)據(jù)結構數(shù)據(jù)操作數(shù)據(jù)操作完整性完整性表式系統(tǒng)表式系統(tǒng)表表 (最小最小)關系系統(tǒng)關系系統(tǒng)表表選擇、投影、選擇、投影、連接連接 關系完備的系統(tǒng)關系完備的系統(tǒng)表表 全關系系統(tǒng)全關系系統(tǒng) 全關系系統(tǒng)的十二條基本準則 這是關系模型的奠基人E.F.Codd從理論和實際緊密結合的高度，對關系型DBMS的評述。從實際意義

4、上看，這十二條準則可以作為評價或購買關系型產(chǎn)品的標準。 詳細見書。三、關系系統(tǒng)的查詢優(yōu)化非關系系統(tǒng)中，用戶使用過程化的語言表達查詢要求、執(zhí)行的操作以及操作序列，用戶必須了解存取路徑，查詢效率由用戶的存取策略決定，需要用戶對 查詢程序進行“優(yōu)化”。而在關系系統(tǒng)中，用戶只需提出“干什么”，而不必指出“怎么干”，由系統(tǒng)來確定存取策略，提高查詢效率，即完成查詢優(yōu)化的工作。查詢優(yōu)化在關系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位，是影響RDBMS性能的關鍵因素。系統(tǒng)的“優(yōu)化器”功能與用戶“優(yōu)化工作”對比：1）可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息2）如果物理統(tǒng)計信息改變了，前者可重新優(yōu)化選擇相適應的執(zhí)行計劃，而后者必須重

5、新寫程序，而實際應用中往往不太可能。3）前者可考慮數(shù)百種不同的執(zhí)行計劃，而程序員一般只能考慮有限的幾種可能性。4）前者包括了很多復雜的優(yōu)化技術，往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu)化使得所有人都擁有這些優(yōu)化技術。查詢優(yōu)化的一般步驟1）將查詢轉換成某種內(nèi)部表示，通常是語法樹（關系代數(shù)語法樹）。2）根據(jù)一定的等價變換規(guī)則把語法樹轉換成標準形式（優(yōu)化形式）?？刹捎藐P系代數(shù)表達式的優(yōu)化算法自動進行優(yōu)化。3）選擇低層的操作算法，即確定存取路徑。對于語法樹中的每一個操作需要根據(jù)存取路徑（有無索引）、數(shù)據(jù)的存儲分布、存儲數(shù)據(jù)的聚簇等信息來選擇具體的執(zhí)行算法。4）生成查詢計劃（執(zhí)行方案），選擇代價最小的

6、。對每個執(zhí)行計劃計算代價，從中選擇代價最小的一個。在集中式關系數(shù)據(jù)庫中，計算代價時主要考慮磁盤讀寫的I/O次數(shù)，也有一些系統(tǒng)換考慮了CPU的處理時間。目前的商品化RDBMS答對采用基于代價的優(yōu)化算法： 這種方法要求優(yōu)化器充分考慮系統(tǒng)中的各種參數(shù)（如緩沖區(qū)大小、表的大小、數(shù)據(jù)的分布、存取路徑等）。集中式數(shù)據(jù)庫：總代價=I/O代價+CPU代價 （時間）多用戶數(shù)據(jù)庫：總代價=I/O代價+CPU代價 +內(nèi)存代價 （時間）查詢優(yōu)化的一般準則1）選擇運算應盡可能先做。因為它可使計算的中間結果大大變小。2）在執(zhí)行連接（自然連接）前對關系適當?shù)仡A處理。主要有兩種方法，在連接屬性上建立索引和對關系排序，然后執(zhí)行

7、連接。（詳細見書 P.161）3）把投影運算和選擇運算同時進行。當他們對同一個關系操作，則可以在掃描關系的同時完成所有的這些運算來避免重復掃描關系。4）把投影和其前或其后的雙目運算結合起來，沒有必要為了去掉某些字段而掃描一遍關系。5）把某些選擇同在它前面要執(zhí)行的笛卡兒積結合起來成為一個連接運算，連接特別是等值連接運算要比同樣關系上的笛卡兒積省很多時間。6）找出公共子表達式，如果這種重復出現(xiàn)的子表達式結果不是很大，從外存讀入結果比計算該子表達式的時間少得多，可先計算一次該子表達式并把結果寫入中間文件是合算的。如查詢的是視圖，定義視圖的表達式就是公共子表達式的情況。關系代數(shù)等價變換規(guī)則 各種查詢語

8、言都可以轉換成關系代數(shù)表達式，因此查詢優(yōu)化可以轉換為對關系代數(shù)表達式的優(yōu)化。而其優(yōu)化的基礎是關系代數(shù)表達式的等價變換規(guī)則。 等價：等價：如果用相同的關系來代替兩個表達式中相應的關系所得到的結果是相同的，則說這兩個關系代數(shù)表達式E1、E2是等價的，記為E1E2。 常用的等價變換規(guī)則：常用的等價變換規(guī)則：10條（見書P.162-164）。 關系代數(shù)表達式的優(yōu)化原則：關系代數(shù)表達式的優(yōu)化原則：應用等價變換規(guī)則來優(yōu)化關系表達式，使得優(yōu)化后的表達式能遵循查詢優(yōu)化的一般準則，如把選擇和投影盡可能地早做（即把它們移到表達式語法樹的下部，葉端）。關系代數(shù)表達式的優(yōu)化算法算法：關系表達式的優(yōu)化。輸入：一個關系表

9、達式的語法樹。輸出：計算該表達式的程序。1）利用規(guī)則4把形如F1F2 Fn(E)變換為 F1( F2( Fn(E)。2）對每個選擇，利用規(guī)則4-8盡可能把它移到樹的葉端。3）對每個投影，利用規(guī)則3，9，10，5中的一般形式盡可能把它移向樹的葉端。4）利用規(guī)則3-5把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使得多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成。5）將得到的語法樹的內(nèi)結點進行分組。每一雙目運算和它所有的直接祖先（ ， ）為一組；如果其后代直到葉子全是單目運算，則也將它們并入該組；但當雙目運算是笛卡兒積，而且其后的選擇不能與它結合為等值連接時,則一直到葉子的一

10、目運算結點須單獨立一組。6）自動生成一個程序。每組結點的計算是程序中的一步。各步的順序是任意的，只要保證任何一組的計算不會在它的后代組之前計算。7）執(zhí)行時從葉端依次向上進行，每組運算只對關系進行一次掃描。優(yōu)化的一般步驟（1）把查詢轉換成某種內(nèi)部表示 通常是（關系代數(shù)）語法樹，以4.2.2節(jié)中的實例為例。（2）把語法樹轉換成標準（優(yōu)化）形式。 語法樹最終的優(yōu)化形式語法樹最終的優(yōu)化形式（運用了哪些變換規(guī)則？） Sname Student.Sno=SC.Sno Sname,Sno Sno Student Cno=2 SC StudentCno=2SCSnameStudent.Sno=SC.SnoSn

11、ame, Student.Sno, SC.Sno（3）選擇低層的存取路徑 根據(jù)第（2）步得到的優(yōu)化了的語法樹計算關系表達式值的時候要充分考慮索引、數(shù)據(jù)的存儲分布等存取路徑，利用它們進一步改善查詢效率。 優(yōu)化器查找數(shù)據(jù)字典獲得當前數(shù)據(jù)庫狀態(tài)信息選擇字段上是否有索引連接的兩個表是否有序連接字段上是否有索引 然后根據(jù)一定的優(yōu)化規(guī)則選擇存取路徑（4）生成查詢計劃，選擇代價最小的）生成查詢計劃，選擇代價最小的 查詢計劃是由一組內(nèi)部過程組成的，這組內(nèi)部過程實現(xiàn)按某條存取路徑計算關系表達式的值。 在作連接運算時，若兩個表(設為R1，R2)均無序，連接屬性上也沒有索引，則可以有下面幾種查詢計劃： 對兩個表作排

12、序預處理 對R1在連接屬性上建索引 對R2在連接屬性上建索引 在R1，R2的連接屬性上均建索引 對不同的查詢計劃計算代價，選擇代價最小的一個。 在計算代價時主要考慮磁盤讀寫的I/O數(shù)，內(nèi)存CPU處理時間在粗略計算時可不考慮。實例_查詢優(yōu)化的實例 SELECT Student.Sname FROM Student,SC WHER Student.Sno=SC.Sno AND SC.Cno=2;系統(tǒng)可以用多種等價的關系代數(shù)表達式來完成這一查詢： 如 q1= sname( student.sno=o=2(studentsc) q2= sname( o=2(student sc) q3= sname(

13、student o=2(sc)這三種不同的查詢執(zhí)行策略，其查詢時間相差很大?？赏ㄟ^某種代價模型(如只計算I/O時間代價)，粗略計算出各種查詢執(zhí)行方案的代價，選擇代價最小的來實現(xiàn)查詢。實例_查詢優(yōu)化的實例 讀取Student和SC表的策略Student表SC表100個SC元組內(nèi)存緩沖區(qū)中間文件10個Student元組10個連接后的元組第一個五塊第二個五塊 共一千個學生記錄 共一萬個選課記錄 第1100個元組第101200個元組 第110個元組第1120個元組第一塊第二塊第 n 塊 Student表第1個五塊的元組 SC表第1塊的元組 SC表第2塊的元組 SC表第n塊的元組 Student表第2個五塊的元組 SC表第1塊的元組 SC表第2塊的元組 SC表第n塊的元組 Student表最后五塊的元組 SC表第1塊的元組 SC表第2塊的元組 SC表第n塊的元組 假設1：1000個學生記錄，10000個選課記錄，在內(nèi)存中存放5塊Student元組和一塊SC元組，一塊能裝10個學生記錄或100個選課記錄。 則讀取總塊數(shù)為： 1000 1000 10000 10 105 10