2006年4月12日,1,第四章 關系系統及其查詢優化,2006年4月12日,2,第四章 關系系統及其查詢優化,4.1 關系系統 4.2 關系系統的查詢優化 4.3 小結,2006年4月12日,3,關系系統,能夠在一定程度上支持關系模型的數據庫管理系統是關系系統。 由于關系模型中并非每一部分都是同等重要的 并不苛求一個實際的關系系統必須完全支持關系模型。,4,關系系統與關系模型,關系數據結構 域及域上定義的關系 關系操作 并、交、差、廣義笛卡爾積、選擇、投影、連接、除等 關系完整性 實體完整性、參照完整性、用戶自己定義的完整性,2006年4月12日,5,關系系統的定義,一個數據庫管理系統可定義為關系系統，當且僅 當它至少支持： 1. 關系數據庫（即關系數據結構） 系統中只有表這種結構 2. 支持選擇、投影和（自然）連接運算 對這些運算不要求用戶定義任何物理存取路徑 對關系系統的最低要求,2006年4月12日,6,關系系統的定義,不支持關系數據結構的系統顯然不能稱為關系系統 僅支持關系數據結構，但沒有選擇、投影和連接運算功能的系統仍不能算作關系系統。 原因：不能提高用戶的生產率 支持選擇、投影和連接運算，但要求定義物理存取路徑，這種系統也不能算作真正的關系系統 原因：就降低或喪失了數據的物理獨立性 選擇、投影、連接運算是最有用的運算,2006年4月12日,7,4.1.2 關系系統的分類,分類依據：支持關系模型的程度 分類 表式系統：支持關系數據結構(即表) (最小)關系系統 支持：關系數據結構 選擇、投影、連接關系操作, 關系完備的系統 支持：關系數據結構 所有的關系代數操作 全關系系統 支持：關系模型的所有特征 特別是:數據結構中域的概念,（a）表式系統 (b) （最?。╆P系的 (c）關系完備的 (d)全關系的,2006年4月12日,8,關系系統的分類 （續）,2006年4月12日,9,第四章 關系系統及其查詢優化,4.1 關系系統 4.2 關系系統的查詢優化 4.3 小結,2006年4月12日,10,4.2 關系系統的查詢優化,4.2.1 查詢優化概述 4.2.2 查詢優化的必要性 4.2.3 查詢優化的一般準則 4.2.4 關系代數等價變換規則 4.2.5 關系代數表達式的優化算法 4.2.6 優化的一般步驟,2006年4月12日,11,4.2.1 查詢優化概述,查詢優化的必要性 查詢優化極大地影響RDBMS的性能。 查詢優化的可能性 關系數據語言的級別很高，使DBMS可以從關系表達式中分析查詢語義。,2006年4月12日,12,由DBMS進行查詢優化的好處,用戶不必考慮如何最好地表達查詢以獲得較好的效率 系統可以比用戶程序的優化做得更好 (1) 優化器可以從數據字典中獲取許多統計信息，而用戶程序則難以獲得這些信息,2006年4月12日,13,由DBMS進行查詢優化的好處,(2)如果數據庫的物理統計信息改變了，系統可以自動對查詢重新優化以選擇相適應的執行計劃。 在非關系系統中必須重寫程序，而重寫程序在實際應用中往往是不太可能的。 (3)優化器可以考慮數百種不同的執行計劃，而程序員一般只能考慮有限的幾種可能性。 (4)優化器中包括了很多復雜的優化技術,2006年4月12日,14,查詢優化目標,查詢優化的總目標 選擇有效策略，求得給定關系表達式的值 實際系統的查詢優化步驟 1. 將查詢轉換成某種內部表示，通常是語法樹 2. 根據一定的等價變換規則把語法樹轉換成標準 （優化）形式,2006年4月12日,15,實際系統的查詢優化步驟,3. 選擇低層的操作算法 對于語法樹中的每一個操作 計算各種執行算法的執行代價 選擇代價小的執行算法 4. 生成查詢計劃(查詢執行方案) 查詢計劃是由一系列內部操作組成的。,2006年4月12日,16,代價模型,集中式數據庫 單用戶系統 總代價 = I/O代價 + CPU代價 多用戶系統 總代價 = I/O代價 + CPU代價 + 內存代價 分布式數據庫 總代價 = I/O代價 + CPU代價+ 內存代價 + 通信代價,2006年4月12日,17,4.2.2 查詢優化的必要性,例：求選修了課程2的學生姓名 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2;,2006年4月12日,18,查詢優化的必要性（續）,假設1：外存： Student:1000條,SC:10000條, 選修2號課程:50條 假設2：一個內存塊裝元組:10個Student, 或100個SC, 內存中一次可以存放: 5塊Student元組, 1塊SC元組和若干塊連接結果元組 假設3：讀寫速度：20塊/秒 假設4：連接方法：基于數據塊的嵌套循環法,2006年4月12日,19,執行策略1,1 name(Student.Sno=SC.Sno SC.Cno=2 (StudentSC) StudentSC 讀取總塊數= 讀Student表塊數 + 讀SC表遍數 *每遍塊數 =1000/10+(1000/(105) (10000/100) =100+20100=2100 讀數據時間=2100/20=105秒,2006年4月12日,20,不同的執行策略,考慮I/O時間,中間結果大小 = 1000*10000 = 107 (1千萬條元組) 寫中間結果時間 = 10000000/10/20 = 50000秒 讀數據時間 = 50000秒 總時間 =1055000050000秒 = 100105秒 = 27.8小時,2006年4月12日,21,查詢優化的必要性（續）,2. 2 name(SC.Cno= 2 (Student SC) 讀取總塊數= 2100塊 讀數據時間=2100/20=105秒 中間結果大小=10000 （減少1000倍） 寫中間結果時間=10000/10/20=50秒 讀數據時間=50秒 總時間1055050秒205秒=3.4分,2006年4月12日,22,查詢優化的必要性（續）,3. 2 Sname(Student SC.Cno= 2 (SC) 讀SC表總塊數= 10000/100=100塊 讀數據時間=100/20=5秒 中間結果大小=50條 不必寫入外存 讀Student表總塊數= 1000/10=100塊 讀數據時間=100/20=5秒 總時間55秒10秒,2006年4月12日,23,查詢優化的必要性（續）,4. 2 name(Student SC.Cno=2 (SC) 假設SC表在Cno上有索引，Student表在Sno上有索引 讀SC表索引= 讀SC表總塊數= 50/1001塊 讀數據時間 中間結果大小=50條 不必寫入外存,2006年4月12日,24,查詢優化的必要性（續）, 讀Student表索引= 讀Student表總塊數= 50/10=5塊 讀數據時間 總時間10秒,2006年4月12日,25,4.2.3 查詢優化的一般準則,選擇運算應盡可能先做 目的：減小中間關系 在執行連接操作前對關系適當進行預處理 按連接屬性排序 在連接屬性上建立索引 投影運算和選擇運算同時做 目的：避免重復掃描關系 將投影運算與其前面或后面的雙目運算結合 目的：減少掃描關系的遍數,2006年4月12日,26,查詢優化的一般準則 （續）,某些選擇運算在其前面執行的笛卡爾積 = 連接運算 例：Student.Sno=SC.Sno (StudentSC) Student SC 提取公共子表達式,2006年4月12日,27,4.2.4 關系代數等價變換規則,關系代數表達式等價 指用相同的關系代替兩個表達式中相應的關系所得到的結果是相同的 上面的優化策略大部分都涉及到代數表達式的變換,2006年4月12日,28,常用的等價變換規則,設E1、E2等是關系代數表達式，F是條件表達式 l. 連接、笛卡爾積交換律 E1 E2 E2E1 E1 E2E2 E1 E1 F E2E2 F E1,2006年4月12日,29,關系代數等價變換規則（續）,2. 連接、笛卡爾積的結合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F F F F,2006年4月12日,30,關系代數等價變換規則（續）,3. 投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E) 假設： 1) E是關系代數表達式 2) Ai(i=1，2，n), Bj(j=l，2，m)是屬性名 3)A1, A2, , An構成Bl，B2，Bm的子集,2006年4月12日,31,關系代數等價變換規則（續）,4. 選擇的串接定律 F1 （ F2（E） F1 F2(E) 選擇的串接律說明 選擇條件可以合并 這樣一次就可檢查全部條件。,2006年4月12日,32,關系代數等價變換規則（續）,5. 選擇與投影的交換律 (1)假設: 選擇條件F只涉及屬性A1，An F (A1,A2, ,An(E) A1,A2, ,An(F(E) (2)假設: F中有不屬于A1, ,An的屬性B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An(F (A1,A2, ,An,B1,B2, ,Bm(E),2006年4月12日,33,關系代數等價變換規則（續）,6. 選擇與笛卡爾積的交換律 (1) 假設：F中涉及的屬性都是E1中的屬性 F (E1E2)F (E1)E2 (2) 假設：F=F1F2，并且F1只涉及E1中的屬性， F2只涉及E2中的屬性 則由上面的等價變換規則1，4，6可推出： F(E1E2) F1(E1)F2 (E2),2006年4月12日,34,關系代數等價變換規則（續）,(3) 假設： F=F1F2， F1只涉及E1中的屬性， F2涉及E1和E2兩者的屬性 F(E1E2) F2(F1(E1)E2) 它使部分選擇在笛卡爾積前先做,2006年4月12日,35,關系代數等價變換規則（續）,7. 選擇與并的交換 假設：E=E1E2，E1，E2有相同的屬性名 F(E1E2) F(E1) F(E2) 8. 選擇與差運算的交換 假設：E1與E2有相同的屬性名 F(E1-E2) F(E1) - F(E2),2006年4月12日,36,關系代數等價變換規則（續）,9. 投影與笛卡爾積的交換 假設：E1和E2是兩個關系表達式， A1，An是E1的屬性， B1，Bm是E2的屬性 A1,A2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,An（E1) B1,B2, ,Bm(E2),2006年4月12日,37,關系代數等價變換規則（續）,l0. 投影與并的交換 假設：E1和E2 有相同的屬性名 A1,A2, ,An(E1E2) A1,A2, ,An(E1) A1,A2, ,An(E2),2006年4月12日,38,小結,1-2: 連接、笛卡爾積的交換律、結合律 3： 合并或分解投影運算 4： 合并或分解選擇運算 5-8： 選擇運算與其他運算交換 5，9，10： 投影運算與其他運算交換,2006年4月12日,39,4.2 關系系統的查詢優化,4.2.1 查詢優化概述 4.2.2 查詢優化的必要性 4.2.3 查詢優化的一般準則 4.2.4 關系代數等價變換規則 4.2.5 關系代數表達式的優化算法 4.2.6 優化的一般步驟,2006年4月12日,40,4.2.5 關系代數表達式的優化算法,算法：關系表達式的優化 輸入：一個關系表達式的語法樹。 輸出：計算該表達式的程序。 方法： （1）分解選擇運算 利用規則4把形如F1 F2 Fn (E)變換為 F1 (F2( (Fn(E) ),2006年4月12日,41,關系代數表達式的優化算法 (續),（2）通過交換選擇運算，將其盡可能移到葉端 對每一個選擇，利用規則48盡可能把它移到樹的葉端。 （3）通過交換投影運算，將其盡可能移到葉端 對每一個投影利用規則3，9，l0，5中的一般形式盡可能把它移向樹的葉端。,2006年4月12日,42,關系代數表達式的優化算法 (續),（4）合并串接的選擇和投影，以便能同時執行或在一次掃描中完成 利用規則35把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。 使多個選擇或投影能同時執行，或在一次掃描中全部完成 盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。,2006年4月12日,43,關系代數表達式的優化算法 (續),（5）對內結點分組 把上述得到的語法樹的內節點分組。 每一雙目運算(， ，-)和它所有的直接祖先為一組(這些直接祖先是，運算)。 如果其后代直到葉子全是單目運算，則也將它們并入該組，但當雙目運算是笛卡爾積()，而且其后的選擇不能與它結合為等值連接時除外。把這些單目運算單獨分為一組。,2006年4月12日,44,關系代數表達式的優化算法 (續),（6）生成程序 生成一個程序，每組結點的計算是程序中的一步。 各步的順序是任意的，只要保證任何一組的計算不會在它的后代組之前計算。,2006年4月12日,45,4.2 關系系統的查詢優化,4.2.1 查詢優化概述 4.2.2 查詢優化的必要性 4.2.3 查詢優化的一般準則 4.2.4 關系代數等價變換規則 4.2.5 關系代數表達式的優化算法 4.2.6 優化的一般步驟,2006年4月12日,46,4.2.6 優化的一般步驟,1把查詢轉換成某種內部表示 2代數優化：把語法樹轉換成標準（優化） 形式 3物理優化：選擇低層的存取路徑 4生成查詢計劃，選擇代價最小的,2006年4月12日,47,優化的一般步驟 (續),（1）把查詢轉換成某種內部表示 例：求選修了課程2的學生姓名 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2;,2006年4月12日,48,（1）把查詢轉換成某種內部表示,語法樹,結果,project(Sname),select(SC.Cno=2),join(Student.Sno=SC.Sno),Student,SC,2006年4月12日,49,關系代數語法樹,2006年4月12日,50,（2）代數優化,利用優化算法把語法樹轉換成標準（優化）形式,2006年4月12日,51,（3）物理優化：選擇低層的存取路徑,- 優化器查找數據字典獲得當前數據庫狀態信息 選擇字段上是否有索引 連接的兩個表是否有序 連接字段上是否有索引 然后根據一定的優化規則選擇存取路徑 如本例中若SC表上建有Cno的索引，則應該利用這個索引，而不必順序掃描SC表。,2006年4月12日,52,（4）生成查詢計劃，選擇代價最小的,在作連接運算時，若兩個表(設為R1，R2)均無序，連接屬性上也沒有索引，則可以有下面幾種查詢計劃： 對兩個表作排序預處理 對R1在連接屬性上建索引 對R2在連接屬性上建索引 在R1，R2的連接屬性上均建索引 對不同的查詢計劃計算代價，選擇代價最小的一個。 在計算代價時主要考慮磁盤讀寫的I/O數，內存CPU處理時間在粗略計算時可不考慮。,2006年4月12日,53,第四章 關系系統及其查詢優化,4.1 關系系統 4.2 關系系統的查詢優化 4.3 小結,2006年4月12日,54,4.3 小結,關系系統 關系系統的定義 一個數據庫管理系統可定義為關系系統，當且僅當它至少支持： 1 關系數據庫（即關系數據結構） 2 支持選擇、投影和（自然）連接運算， 且不要求用戶定義任何物理存取路徑,2006年4月12日,55,小結 關系系統的定義： 一個系統可定義為關系系統，當且僅當它支持： 1關系數據庫。即從用戶觀點看，數據庫是由表構成的，并且 只有表這種結構。 2支持選擇、投影和（自然）連接運算。對這些運算不必要求 定義任何物理存取路徑。 關系系統分類 （a）表式系統 (b) （最小）關系的 (c）關系完備的 (d)全關系的,2006年4月12日,56,小結 （續）,關系系統的查詢優化 代數優化：關系代數表達式的優化 關系代數等價變換規則 關系代數表達式的優化算法 物理優化：存取路徑和低層操作算法的選擇,2006年4月12日,57,查詢優化的總目標是：選擇有效的策略。求得給定的關系表達式 的值 優化的一般策略： 1選擇運算應盡可能先做。 2在執行連接前對文件適當地預處理，預處理方法主要又兩種， 對文件排序和在連接屬性上建立索引。 3把投影運算和選擇運算同時進行。 4把投影同其前或后的雙目運算結合起來。 5 把某些選擇同在它前面要執行的笛卡兒積結合起來成為一個 連接字段。 6找出公共子表達式。,2006年4月12日,58,關系代數等價變換規則： 兩個關系表達式E1和E2是等價的，可記為E1 E2 1連接、笛卡兒積的交換律 設E1和 E2是關系代數表達式， F是連接運算的條件，則有： E1 E2 E2 E1 E1 E2 E2 E1 E1 E2 E2 E1 F F 2連接、笛卡兒積的結合律 設E1，E2，E3是關系表達式，F1和F2是連接運算的條件，則有： （E1E2）E3 E1（E2E3） （E1 E2） E3 （E1 E2） E3 (E1 E2) E3 E1 (E1 E2) 3投影的串接定律 A1,A2,An ( B1,B2,Bm(E) A1,A2,An (E) 這里，E是關系代數表達式，Ai（ i=1,2, , n ),Bj( j=1,2, , m )是,2006年4月12日,59,屬性名且A1,A2, , An構成B1,B2, , Bm 的子集. 4選擇的串接定律 F1（ F2（E） F1F2（E） 這里，E是關系代數表達式，F1，F2是選擇的條件。選擇的串接律 說明條件可以合并。這樣一次就可以檢查全部條件。 5選擇和投影的交換律 F(A1,A2,An (E) A1,A2,An(F(E) 這里,選擇條件F只涉及屬性A1,A2, , An。若F中有不屬于屬性 B1,B2, , Bm 則有更一般的規則 A1,A2,An(F(E) A1,A2,An(F(A1,A2,An , B1,B2, , Bm (E) 6選擇與笛卡兒積的交換律 如果F中涉及的屬性都是E1中的屬性，則 F（E1 E2） F （E1） E2 如果F=F1F2，并且F1只涉及E1中的屬性，F2只涉及E2中的屬性 ，則由上面的1,4,6 可推出： F（E1 E2） F 1（E1） F2 （E2）,2006年4月12日,60,若F1只涉及E1中的屬性， F2涉及E1和E2兩者的屬性，則仍有： F（E1 E2） F 2（F1 （E1） E2） 它使部分選擇在笛卡兒積前先做。