1、第七章: 關系系統及其查詢優化q關系系統的定義和分類q查詢處理q關系系統中的查詢優化關系系統的定義q關系系統: 支持關系數據模型的數據庫管理系統(粗略)q關系系統(確切定義): 一個系統可以定義為一個關系系統, 當且僅當它:支持關系數據庫支持選擇、投影和連接運算(自然連接), 對這些運算不要求定義任何物理存取路徑關系系統的分類:q許多關系系統的產品q按E.F.Codd的思想將關系系統分為:表式系統表式系統(a)最小關系系統最小關系系統(b)關系完備的系統關系完備的系統(c)全關系系統全關系系統(d)SMISMISMISMIabcdS: StructureI: IntegrityM: Manip

2、ulation關系數據模型關系數據模型集合操作集合操作關系系統的查詢處理:q查詢處理的步驟: queryParser &translatorRelational algebra expressionOptimizerExecution planEvaluationengineQuery outputdataStatisticsabout dataDBMS為什么需要查詢優化？q一個查詢實例: 求選修2號課程的學生姓名SQL表示:select Snamefrom Students, SCwhere Students.Sno=SC.Sno and Cno=2;關系代數表示:Q1= sname

3、(Students.Sno=SC.Sno and Cno=2(StudentsSC)Q2= sname(Cno=2(Students SC)Q3= sname( Students Cno=2(SC)q代價計算 Q1代價計算(僅考慮I/O代價)計算廣義笛卡爾積代價假定: 在內存中, 存放5塊Students元組和一塊SC元組, 一塊可以裝10個Students元組或100個SC元組. 假定: Students有1000個元組,SC有10000個元組, 其中選2號課程的有50個元組數據只有讀到內存才能進行連接Q1= sname( Students.Sno=SC.Sno and Cno=2(Stud

4、ents SC)10100SCStudents5塊塊通過讀取塊數計算I/O代價 讀取塊數計算方法: Students 1000個元組 SC 10000個元組讀取總塊數:若每秒讀寫20塊, 則花費:21001002010010010000510100010100010100SCStudents5塊塊s105202100Q1= sname( Students.Sno=SC.Sno and Cno=2(Students SC)Student塊數塊數Student讀入內存讀入內存的次數的次數SC塊數塊數條件條件:Students 1000個元組，個元組， SC 10000個元組個元組迪卡爾集后后的元組

5、個數為: 103 104=107連接后的中間結果內存放不下, 需暫時寫到外存若每塊可裝10個完成迪卡爾集后的元組, 則寫這些元組需: (107 /10)/20=5 104s選擇操作: 讀回需5 104s, 假設選擇后剩50個元組,均可放在內存投影操作: 查詢共花費: 105+2 5 104 105 s 28小時Q1= sname( Students.Sno=SC.Sno and Cno=2(Students SC)10100SCStudents5塊塊每秒讀每秒讀20塊塊Q2= sname( Cno=2(Students SC)Q2代價計算(僅考慮I/O代價)計算自然連接代價也要把數據讀到內存進

6、行連接, 但連接結果比笛卡爾積要小得多讀取塊數依然為:花費為2100/20 105s假設連接結果大小為104個元組, 寫到外存需: (104 /10)/20=50s210010020100100100005101000101000每秒讀每秒讀20塊塊 Q2= sname( Cno=2(Students SC) Q3= sname( Students Cno=2(SC)讀取自然連接結果, 執行選擇運算, 需50s, 選擇結果均可放在內存投影運算:總花費為: 105+50+50=205s 3.4分鐘分鐘Q3代價計算(僅考慮I/O代價)計算對SC做選擇運算的代價需讀SC到內存進行選擇運算讀SC塊數為

7、: 10000/100=100花費為: 100/20=5s選擇結果為50個SC元組, 均可放在內存Q3= sname( Students Cno=2(SC)計算和Students自然連接的 代價需讀Students到內存進行連 接運算讀Students塊數為: 1000/10=100花費為: 100/20=5s連接結果為50個元組, 均可放在內存投影運算:總花費: 5+5=10s1050SCStudents5塊塊關系系統的查詢優化:q關系系統的查詢優化由系統完成, 而不是由用戶完成優化器可以從數據字典獲取許多統計信息如果數據庫的物理統計信息改變了,優化器可以對查詢進行重新優化以選擇適應的執行計

8、劃優化器可以考慮數百種不同的執行計劃優化器包括了許多復雜的技術q優化目標: 尋求最優的執行計劃, 使查詢執行開銷盡量小關系系統的查詢優化:q查詢優化的一般步驟將查詢轉化成內部表示-語法樹根據等價變化規則, 將語法樹轉化成優化形式選擇低層操作算法生成查詢計劃q查詢執行開銷主要包括: 總代價=I/O代價+CPU代價q多用戶數據庫執行開銷: 總代價=I/O代價+CPU代價+內存代價關系系統的查詢優化:q查詢優化的一般準則: 下面的優化策略一般能提高查詢效率, 但不一定是最優的選擇運算盡可能先做, 降低中間結果大小在連接前,對關系適當的進行預處理: 對關系排序(排序合并連接方法)或在連接屬性上建索引(

9、索引連接方法)9500495002. 95003. 95001.Students95003 1 95003 2 95004 2 . 95004 3 . 95001 1 .SC循環嵌套連接循環嵌套連接(不不做任何預處理做任何預處理):.關系系統的查詢優化:9500195002. 95003. 95004.Students95001, 1 95003, 1 95003, 2 95004, 2 . 95004, 3 .SC排序合并連接排序合并連接(連連接的關系分別排接的關系分別排序序):.索引連接索引連接(在在SC的連接列的連接列Sno上上建立索引建立索引):Students95001 950039

10、5003 95004 95004.SC索引索引.9500495002. 95003. 95001.95003, 1 95003, 2 95004, 2 . 95004, 3 . 95001, 1 .SC關系系統的查詢優化:把投影運算和選擇運算同時進行 sno (cno=2(SC)把投影和其前或后的雙目運算結合起來 Cname(Course SC)把某些選擇同在它前面要執行的笛卡爾積結合起來成為一個連接運算 Students.Sno=SC.Sno and Cno=2(Students SC)找出公共子表達式sname( Students Cno=2(SC)關系系統的查詢優化:q關系代數等價變換規

11、則: 給定sname(Students.Sno=SC.Sno and Cno=2(StudentsSC)如何將上述提到的運算先做, 即得到:sname( Students Cno=2(SC)規則1: 連接、笛卡爾積的交換律 E1 E2 E2 E1 E1 E2= E2 E1 E1 E2= E2 E1 E: 關系代數表達式 F: 連接條件規則2: 連接、笛卡爾積的結合律 (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3)F1FFF2F1F2關系系統的查詢優化:規則3: 投影的串接定律 A1,A2,.,An( B1,

12、B2,.,Bn (E) A1,A2,.,An(E) 規則4: 選擇的串接定律 F1(F2(E) F1F2(E) 規則5: 選擇和投影的交換律 F(A1,A2,.,An(E) A1,A2,.,An(F(E) 特殊情況 A1,A2,.,An( F(E) A1,A2,.,An( F( A1,A2,.,An, B1,B2,.,Bm (E)規則6: 選擇與笛卡爾積的交換律 F(E1 E2) F(E1) E2 F僅和E1有關 F(E1 E2) F1(E1) F2( E2 ) F= F1F2 F(E1 E2) F2(F1(E1)E2 ) F1-E1 F2-E1E2關系系統的查詢優化:規則7: 選擇與并的交換

13、 F(E1 E2) F(E1) F(E2) 規則8: 選擇與差的交換 F(E1- E2) F(E1)- F(E2)規則9: 投影與笛卡爾積的交換 A1,A2,.,An, B1,B2,.,Bm(E1 E2) A1,A2,.,An(E1) B1,B2,.,Bm(E2) 規則10: 投影與并的交換 A1,A2,.,An (E1 E2) A1,A2,.,An(E1) A1,A2,.,An(E2) 關系系統的查詢優化:q關系代數表達式的優化算法: 應用關系代數等價變換規則來優化關系代數表達式, 使優化后的表達式能遵循查詢優化的一般準則, 在語法樹上進行優化關系代數表達式的優化算法輸入: 語法樹 1 利用

14、規則4把形如F1F2Fn(E) 變換成 F1(F2( (Fn(E).) 2 對每一個選擇, 利用規則48盡可能移到樹的葉端 3 對于每個投影, 利用規則3, 9, 10盡可能移到樹 的葉端 4 利用規則35把選擇和投影的串接合并成單個選擇, 單個投影, 或一個選擇后跟一個投影關系系統的查詢優化: 5 把處理后的語法樹內節點分組:每一雙目運算(, ,)和它的所有直接祖先(,)為一組,后代直到葉子全是單目運算也并入該組;若雙目運算為,且其后的選擇不能與它結合為等值連接時,這些單目運算單獨為一組. 6 生成一個程序, 每組節點的計算是程序中的一步輸出: 計算關系代數表達式的程序21頁頁 SSPP不能

15、結不能結合成等合成等值連接值連接 S.Sno=SC.SnoSCS能結合能結合成等值成等值連接連接關系系統的查詢優化:q優化的一般步驟: 因DBMS不同把查詢轉換成某種內部表示(例如關系代數語法樹)把語法樹轉化成標準(優化)形式選擇底層的存取路徑生成查詢計劃, 選擇代價最小的q例子: 設有供應商S, 零件P和供應關系SP三個關系, 其關系模式:S(Snum, Sname, City) P(Pnum, Pname, Weight, Size) SP(Snum, Pnum, Dept, Quan)關系系統的查詢優化:select Sname from S, SP, P where S.Snum=SP

16、.Snum and SP.Pnum=P.Pnum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000;原始語法樹: select-投影 from-笛卡爾積 where-選擇關系系統的查詢優化:Sname cSSPPC=S.Snum=SP.Snum and SP.Pnum=P.Pnum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000Sname cSSPPSname cSSPP s sp pSname cSSPP s sp pSnameSSPP s sp p s p sp c c優化優化:練

17、習練習1查詢要求查詢要求:l查詢信息系學生選修的所有的課程的課程名稱查詢信息系學生選修的所有的課程的課程名稱l寫出關系代數及其原始語法樹寫出關系代數及其原始語法樹,并進行優化處并進行優化處理理,畫出優化后的語法樹畫出優化后的語法樹.SELECT Cname FROM Students,Course,SCWHERE Students.sno=SC.sno and Co=SC.cno and Sdept=IS;練習練習1: Cname( Sdept=IS(Students SC Course) Cname c StudentsSCCourse 原始語法樹原始語法樹: Cname c1Student

18、sSCCourse C:Students.sno=Sc.sno SC.cno=Co Sdept=ISC: SC.cno=Co ,C1: Sdept=IS Cname c1 StudentsSCCourse c練習練習2查詢要求查詢要求:l一圖書管理數據庫，其關系如下：一圖書管理數據庫，其關系如下：BOOKS(Title,Author, Pname,LC_No)PUBLISHERS(Pname,Paddr,Pcity)BORROWERS(Name,Addr,City,Card_No)LOANS(Card_No,LC_No,Date)要求：要求：1.列出列出1999年年1月月1日前借出的所有書名和

19、借書人姓名日前借出的所有書名和借書人姓名2. 寫出關系代數及其原始語法樹寫出關系代數及其原始語法樹,并進行優化處理并進行優化處理,畫出優化畫出優化后的語法樹后的語法樹.SELECT Title,Name from BOOKS,BORROWERS,LOANSWHERE BOOKS. LC_No = LOANS. LC_No AND BORROWERS. Card_No= LOANS. Card_No ANDDate01/01/2003圖書編號圖書編號圖書證號圖書證號練習練習2: Title,Name( Date01/01/2003(BOOKS BORROWERS LOANS) Title,Nam

20、e Date01/01/2003 BOOKSBORROWERSLOANS 原始語法樹原始語法樹: BOOKS. LC_No = LOANS. LC_No AND BORROWERS. Card_No= LOANS. Card_No Title,Author,Pname,LC_No,Name,Addr,City,Card_No,Date練習練習2: Title,Name( Date01/01/2003(BOOKS BORROWERS LOANS)Date01/01/2003(BOOKS BORROWERS LOANS)= BOOKS Date01/01/2003(BORROWERS LOANS)=BOOKS BORROWERS Date01/01/2003(LOANS) Title,Name Date01/01/2003 BOOKSBORROWERSLOANS BOOKS. LC_No = LOANS. LC_No BORROWERS. Card_No= LOANS. Card_No 練習練習2: Title,Name( Date01/0