數(shù)據(jù)庫-第九章1ppt課件

1、信息工程教研室信息工程教研室數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論An Introduction to An Introduction to Database SystemDatabase System主講：趙云主講：趙云第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化代數(shù)優(yōu)化9.4 物理優(yōu)化物理優(yōu)化 9.5 小小 結(jié)結(jié) 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化n本章目的：本章目的： nRDBMS的查詢處理步驟的查詢處理步驟 n查詢優(yōu)化的

2、概念查詢優(yōu)化的概念 n基本方法和技術(shù)基本方法和技術(shù) n查詢優(yōu)化分類查詢優(yōu)化分類 ：n代數(shù)優(yōu)化：關(guān)系代數(shù)表達(dá)式的優(yōu)化代數(shù)優(yōu)化：關(guān)系代數(shù)表達(dá)式的優(yōu)化n物理優(yōu)化：存取路徑和低層操作算法的選物理優(yōu)化：存取路徑和低層操作算法的選擇擇第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化9.1.1 查詢處理步驟查詢處理步驟1.查詢分析：對查詢語句進(jìn)行掃描、詞法分析和語查詢分析：對查詢語句進(jìn)行掃描、詞法分析和語法分析，從查詢語句中識別語言符號，如法分析，從查詢語句中識別語言符號，如SQL關(guān)鍵關(guān)鍵字、屬性名和關(guān)系名等，字、屬性名和關(guān)系名等， 進(jìn)行詞法分析和語法分析，進(jìn)行詞法分析和語法分析，既判斷查詢語

3、句是否符合既判斷查詢語句是否符合SQL語法規(guī)則語法規(guī)則2.查詢檢查查詢檢查:根據(jù)數(shù)據(jù)字典對合法的查詢語句進(jìn)行語根據(jù)數(shù)據(jù)字典對合法的查詢語句進(jìn)行語義檢查。即檢查數(shù)據(jù)庫對象，屬性名和關(guān)系名等是義檢查。即檢查數(shù)據(jù)庫對象，屬性名和關(guān)系名等是否存在和是否有效，并根據(jù)數(shù)據(jù)字典中用戶權(quán)限和否存在和是否有效，并根據(jù)數(shù)據(jù)字典中用戶權(quán)限和完整性約束定義對用戶的存取權(quán)限進(jìn)行檢查。檢查完整性約束定義對用戶的存取權(quán)限進(jìn)行檢查。檢查通過后便把通過后便把SQL查詢語句轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表查詢語句轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式查詢樹）。把數(shù)據(jù)庫的外部名稱轉(zhuǎn)換為內(nèi)部達(dá)式查詢樹）。把數(shù)據(jù)庫的外部名稱轉(zhuǎn)換為內(nèi)部表示。表示。第九章第九

4、章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化3. 查詢優(yōu)化查詢優(yōu)化:選擇一種高效執(zhí)行的查詢處理策略選擇一種高效執(zhí)行的查詢處理策略查詢優(yōu)化分類查詢優(yōu)化分類 ：代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化物理優(yōu)化：指存取路徑和底層操作算法的選擇物理優(yōu)化：指存取路徑和底層操作算法的選擇查詢優(yōu)化方法選擇的依據(jù)：查詢優(yōu)化方法選擇的依據(jù)：基于規(guī)則基于規(guī)則(rule based)基于代價(jià)基于代價(jià)(cost based)基于語義基于語義(semantic based)4. 查詢執(zhí)行查詢執(zhí)行:依據(jù)優(yōu)化器的執(zhí)行策略生成查詢計(jì)劃，依據(jù)優(yōu)化器的執(zhí)行策略生成查詢計(jì)劃，由代碼生成器生成執(zhí)行這個(gè)

5、查詢計(jì)劃的代碼。由代碼生成器生成執(zhí)行這個(gè)查詢計(jì)劃的代碼。第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化查詢處理步驟查詢處理步驟第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化9.1.2 實(shí)現(xiàn)查詢操作的算法示例實(shí)現(xiàn)查詢操作的算法示例 v一、 選擇操作的實(shí)現(xiàn) v二、 連接操作的實(shí)現(xiàn)第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化v一、一、 選擇操作的實(shí)現(xiàn)選擇操作的實(shí)現(xiàn) 例1Select * from student where ；思索的幾種情況： C1：無條件； C2：Sno201915121； C3：Sage20； C4：SdeptCS AND Sag

6、e20； 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化n選擇操作典型實(shí)現(xiàn)方法：選擇操作典型實(shí)現(xiàn)方法：n1. 簡單的全表掃描方法簡單的全表掃描方法 n對查詢的基本表順序掃描，逐一檢查每個(gè)元對查詢的基本表順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組作組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出為結(jié)果輸出 n適合小表，不適合大表適合小表，不適合大表n2. 索引索引(或散列或散列)掃描方法掃描方法 n適合選擇條件中的屬性上有索引適合選擇條件中的屬性上有索引(例如例如B+樹樹索引或索引或Hash索引索引) n通過索引先找到滿足條件的元組主碼或元組通過索引先找到滿足條

7、件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表指針，再通過元組指針直接在查詢的基本表中找到元組中找到元組 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化v二、二、 連接操作的實(shí)現(xiàn)連接操作的實(shí)現(xiàn) n連接操作是查詢處理中最耗時(shí)的操作之一 n本節(jié)只討論等值連接(或自然連接)最常用的實(shí)現(xiàn)算法 n例2 SELECT * FROM Student，SC n WHERE Student.Sno=SC.Sno； 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化銜接銜接(或自然連接或自然連接)最常用的實(shí)現(xiàn)算法最常用的實(shí)現(xiàn)算法 1. 嵌套循環(huán)方法嵌套循環(huán)方法(nested

8、loop) 2. 排序排序-合并方法合并方法(sort-merge join 或或merge join)3. 索引連接索引連接(index join)方法方法 4. Hash Join方法方法 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化1.嵌套循環(huán)方法嵌套循環(huán)方法(nested loop)對外層循環(huán)對外層循環(huán)(Student)的每一個(gè)元組的每一個(gè)元組(s)，檢索內(nèi)層，檢索內(nèi)層循環(huán)循環(huán)(SC)中的每一個(gè)元組中的每一個(gè)元組(sc)檢查這兩個(gè)元組在連接屬性檢查這兩個(gè)元組在連接屬性(sno)上是否相等上是否相等如果滿足連接條件，則串接后作為結(jié)果輸出，直到如果滿足連接條件，則串接后作

9、為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止外層循環(huán)表中的元組處理完為止 201915121201915122201915123201915124.201915121 1 92201915121 2 85201915121 3 88201915122 2 90201915122 3 80.排序-合并連接方法示意圖第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化2.排序排序-合并方法合并方法(sort-merge join 或或merge join) 適合連接的諸表已經(jīng)排好序的情況適合連接的諸表已經(jīng)排好序的情況 排序合并連接方法的步驟：排序合并連接方法的步驟：如果連接的表沒有排好序

10、，先對如果連接的表沒有排好序，先對Student表和表和SC表按連接屬表按連接屬性性Sno排序排序 取取Student表中第一個(gè)表中第一個(gè)Sno，依次掃描，依次掃描SC表中具有相同表中具有相同Sno的元組的元組當(dāng)掃描到當(dāng)掃描到Sno不相同的第一個(gè)不相同的第一個(gè)SC元組時(shí)，返回元組時(shí)，返回Student表掃表掃描它的下一個(gè)元組，再掃描描它的下一個(gè)元組，再掃描SC表中具有相同表中具有相同Sno的元組，的元組，把它們連接起來把它們連接起來 重復(fù)上述步驟直到重復(fù)上述步驟直到Student 表掃描完表掃描完 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化3. 索引連接索引連接(index

11、 join)方法方法步驟：步驟： 在在SC表上建立屬性表上建立屬性Sno的索引，如果原來沒有該的索引，如果原來沒有該索引索引 對對Student中每一個(gè)元組，由中每一個(gè)元組，由Sno值通過值通過SC的索的索引查找相應(yīng)的引查找相應(yīng)的SC元組元組 把這些把這些SC元組和元組和Student元組連接起來元組連接起來 循環(huán)執(zhí)行循環(huán)執(zhí)行，直到，直到Student表中的元組處理完為表中的元組處理完為止止 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化4. Hash Join方法方法 把連接屬性作為把連接屬性作為hash碼，用同一個(gè)碼，用同一個(gè)hash函數(shù)把函數(shù)把R和和S中的元組散列到同一個(gè)

12、中的元組散列到同一個(gè)hash文件中文件中步驟：步驟：劃分階段劃分階段(partitioning phase)：對包含較少元組的表對包含較少元組的表(比如比如R)進(jìn)行一遍處理進(jìn)行一遍處理把它的元組按把它的元組按hash函數(shù)分散到函數(shù)分散到hash表的桶中表的桶中試探階段試探階段(probing phase)：也稱為連接階段：也稱為連接階段(join phase) 對另一個(gè)表對另一個(gè)表(S)進(jìn)行一遍處理進(jìn)行一遍處理把把S的元組散列到適當(dāng)?shù)牡脑M散列到適當(dāng)?shù)膆ash桶中桶中把元組與桶中所有來自把元組與桶中所有來自R并與之相匹配的元組連接并與之相匹配的元組連接起來起來 第九章第九章 關(guān)系查詢處理及其查

13、詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化n查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位 n關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素 n由于關(guān)系表達(dá)式的語義級別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語義，提供了執(zhí)行查詢優(yōu)化的可能性 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述n關(guān)系系統(tǒng)的查詢優(yōu)化n非關(guān)系系統(tǒng)第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化n查詢優(yōu)化的優(yōu)點(diǎn)查詢優(yōu)化的優(yōu)點(diǎn)n(1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶

14、程序則難以獲得這些信息而用戶程序則難以獲得這些信息n(2)如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。用中往往是不太可能的。n (3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，程序優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，程序員一般只能考慮有限的幾種可能性。員一般只能考慮有限的幾種可能性。n(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)

15、化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)動優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化nRDBMS通過某種代價(jià)模型計(jì)算出各種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案n集中式數(shù)據(jù)庫n執(zhí)行開銷主要包括：n磁盤存取塊數(shù)(I/O代價(jià))n處理機(jī)時(shí)間(CPU代價(jià))n查詢的內(nèi)存開銷 nI/O代價(jià)是最主要的 n分布式數(shù)據(jù)庫n總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)通信代價(jià) 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化n查詢優(yōu)化的總目標(biāo)：n選

16、擇有效的策略n求得給定關(guān)系表達(dá)式的值n使得查詢代價(jià)最小(實(shí)際上是較小) 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化9.2.2 一個(gè)實(shí)例一個(gè)實(shí)例例3 求選修了2號課程的學(xué)生姓名。用SQL表達(dá)： SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2； 假定學(xué)生-課程數(shù)據(jù)庫中有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄其中選修2號課程的選課記錄為50個(gè) 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化n系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來完成這一查詢nQ1=Sname(St

17、udent.Sno=SC.SnoSc.Cno=2 (StudentSC)nQ2=Sname(Sc.Cno=2 (Student SC)nQ3=Sname(Student Sc.Cno=2(SC)n第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化n一、第一種情況一、第一種情況n Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 StudentSC)n1. 計(jì)算廣義笛卡爾積計(jì)算廣義笛卡爾積 n把把Student和和SC的每個(gè)元組連接起來的做法：的每個(gè)元組連接起來的做法：n在內(nèi)存中盡可能多地裝入某個(gè)表在內(nèi)存中盡可能多地裝入某個(gè)表(如如Student表表)的若干塊，

18、的若干塊，留出一塊存放另一個(gè)表留出一塊存放另一個(gè)表(如如SC表表)的元組。的元組。n把把SC中的每個(gè)元組和中的每個(gè)元組和Student中每個(gè)元組連接，連接后的中每個(gè)元組連接，連接后的元組裝滿一塊后就寫到中間文件上元組裝滿一塊后就寫到中間文件上n從從SC中讀入一塊和內(nèi)存中的中讀入一塊和內(nèi)存中的Student元組連接，直到元組連接，直到SC表表處理完。處理完。n再讀入若干塊再讀入若干塊Student元組，讀入一塊元組，讀入一塊SC元組元組n重復(fù)上述處理過程，直到把重復(fù)上述處理過程，直到把Student表處理完表處理完n設(shè)一個(gè)塊能裝10個(gè)Student元組或100個(gè)SC元組，在內(nèi)存中存放5塊Stud

19、ent元組和1塊SC元組，則讀取總塊數(shù)為 n n n =100+20100=2100塊n其中，讀Student表100塊。讀SC表20遍，每遍100塊。若每秒讀寫20塊，則總計(jì)要花105s n連接后的元組數(shù)為103104=107。設(shè)每塊能裝10個(gè)元組，則寫出這些塊要用106/20=5104s 101000510100010010000第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化2. 作選擇操作 依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄 假定內(nèi)存處理時(shí)間忽略。讀取中間文件花費(fèi)的時(shí)間(同寫中間文件一樣)需5

20、104s 滿足條件的元組假設(shè)僅50個(gè)，均可放在內(nèi)存 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化3. 作投影操作 把第2步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果 第一種情況下執(zhí)行查詢的總時(shí)間105+25104105s所有內(nèi)存處理時(shí)間均忽略不計(jì) 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化n二、二、 第二種情況第二種情況 n Q2=Sname(Sc.Cno=2 (Student SC)n1. 計(jì)算自然連接計(jì)算自然連接 n執(zhí)行自然連接，讀取執(zhí)行自然連接，讀取Student和和SC表的策略表的策略不變，總的讀取塊數(shù)仍為不變，總的讀取塊數(shù)仍為2100塊花費(fèi)塊花

21、費(fèi)105 s n自然連接的結(jié)果比第一種情況大大減少，為自然連接的結(jié)果比第一種情況大大減少，為104個(gè)個(gè) n寫出這些元組時(shí)間為寫出這些元組時(shí)間為104/10/20=50s，為，為第一種情況的千分之一第一種情況的千分之一 n2. 讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時(shí)讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時(shí)間也為間也為50s。n3. 把第把第2步結(jié)果投影輸出。步結(jié)果投影輸出。n 第二種情況總的執(zhí)行時(shí)間第二種情況總的執(zhí)行時(shí)間105+50+50205s 第九章第九章 關(guān)系查詢處理及其查詢優(yōu)化關(guān)系查詢處理及其查詢優(yōu)化n三、三、 第三種情況第三種情況n Q3=Sname(Student Sc.Cno=2(SC)n1. 先對先對SC表作選擇