清華大學(xué)數(shù)據(jù)庫(kù)access課件第09章：查詢處理

數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)與原理第Ⅲ部分DBMS的內(nèi)核(第９章－第11章)12/16/20221數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)與原理12/12/20221第9章查詢處理講課內(nèi)容：查詢處理是指從數(shù)據(jù)庫(kù)中提取數(shù)據(jù)的一系列活動(dòng)。這一系列活動(dòng)包括：將用高層數(shù)據(jù)庫(kù)語(yǔ)言表示的查詢語(yǔ)句，如SQL，翻譯成能在文件系統(tǒng)這一物理層上實(shí)現(xiàn)的表達(dá)式，如關(guān)系代數(shù)；為優(yōu)化查詢進(jìn)行的各種轉(zhuǎn)換；以及查詢的實(shí)際執(zhí)行。■查詢處理的過(guò)程■表達(dá)式的求值方法■關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換■查詢優(yōu)化的方法■查詢代價(jià)的度量■查詢優(yōu)化器的構(gòu)造■實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)■本章總結(jié)12/16/20222第9章查詢處理講課內(nèi)容：12/12/20222DBMS總體結(jié)構(gòu)回顧：查詢處理器用戶應(yīng)用界面索引統(tǒng)計(jì)數(shù)據(jù)數(shù)據(jù)文件數(shù)據(jù)字典應(yīng)用程序交互查詢數(shù)據(jù)庫(kù)模式應(yīng)用程序目標(biāo)碼嵌入式DML預(yù)編譯器DML編譯器DDL解釋器查詢計(jì)算引擎事務(wù)管理器緩沖區(qū)管理器文件管理器查詢處理器存儲(chǔ)管理器數(shù)據(jù)庫(kù)管理系統(tǒng)磁盤存儲(chǔ)器權(quán)限及完整性管理器日志12/16/20223DBMS總體結(jié)構(gòu)回顧：查詢處理器用戶應(yīng)用界面索引統(tǒng)計(jì)數(shù)據(jù)數(shù)據(jù)§9.1查詢處理的過(guò)程查詢處理是指對(duì)最終用戶提交的查詢進(jìn)行：解析優(yōu)化執(zhí)行并最終給出查詢結(jié)果的處理過(guò)程。12/16/20224§9.1查詢處理的過(guò)程查詢處理12/12/20224§9.1查詢處理的過(guò)程查詢優(yōu)化器問(wèn)題的提出：一個(gè)查詢用SQL語(yǔ)言可以有多種表達(dá)方式；而每個(gè)SQL語(yǔ)句又可以翻譯成多個(gè)等價(jià)的關(guān)系代數(shù)表達(dá)式。例如：selectstudent_numberfromstudentwherestudent_number<“s000003”可以翻譯成下面兩個(gè)關(guān)系代數(shù)表達(dá)式：①σstudent_number<”s000003”(Πstudent_number(student))②Πstudent_number(σstudent_number<”s000003”(student))表達(dá)式中的關(guān)系運(yùn)算又可以用不同的算法和索引去實(shí)現(xiàn)。因此，查詢優(yōu)化器的任務(wù)就是要找出代價(jià)最小的計(jì)算給定查詢的處理過(guò)程。12/16/20225§9.1查詢處理的過(guò)程查詢優(yōu)化器12/12/20225§9.1查詢處理的過(guò)程查詢優(yōu)化器輸入？輸出？查詢執(zhí)行計(jì)劃？帶注釋！注釋用于說(shuō)明：如何具體實(shí)施每個(gè)關(guān)系操作。例如：關(guān)系運(yùn)算所采用的算法將要使用的索引執(zhí)行原語(yǔ)：加上了有關(guān)“如何執(zhí)行”的注釋的關(guān)系代數(shù)運(yùn)算查詢執(zhí)行(計(jì)算)計(jì)劃：用于計(jì)算一個(gè)查詢的原語(yǔ)序列。12/16/20226§9.1查詢處理的過(guò)程查詢優(yōu)化器12/12/20226查詢優(yōu)化器查詢優(yōu)化為給定查詢選擇最有效的查詢執(zhí)行計(jì)劃的過(guò)程：在關(guān)系代數(shù)級(jí)進(jìn)行優(yōu)化，力圖找出與給定表達(dá)式等價(jià)、但執(zhí)行效率更高(?)的一個(gè)表達(dá)式；查詢語(yǔ)句處理的詳細(xì)策略的選擇。例如，確定算法與索引等。本章的主要內(nèi)容什么是查詢執(zhí)行計(jì)劃的代價(jià)？如何估計(jì)查詢執(zhí)行計(jì)劃的代價(jià)？如何進(jìn)行有效的查詢優(yōu)化？§9.1查詢處理的過(guò)程12/16/20227查詢優(yōu)化器§9.1查詢處理的過(guò)程12/12/20227§9.1查詢處理的過(guò)程執(zhí)行引擎輸入是查詢執(zhí)行計(jì)劃輸出則是具體的查詢結(jié)果還需要將實(shí)現(xiàn)關(guān)系運(yùn)算的算法與底層的文件操作指令結(jié)合起來(lái)！12/16/20228§9.1查詢處理的過(guò)程執(zhí)行引擎還需要將實(shí)現(xiàn)關(guān)系運(yùn)算的算法與底§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)的關(guān)系代數(shù)表達(dá)式它們的執(zhí)行結(jié)果相同，但代價(jià)不同。例如：“請(qǐng)給出計(jì)算機(jī)系的教師所講課程的課程名稱和教師姓名”，就可以用如下兩個(gè)等價(jià)的關(guān)系代數(shù)表達(dá)式來(lái)求值：Πcourse_name,teacher_name(σdepartment_name=“計(jì)算機(jī)系”(teacherteaching))Πcourse_name,teacher_name((σdepartment_name=“計(jì)算機(jī)系”(teacher))teaching)從感覺(jué)上講，哪個(gè)關(guān)系代數(shù)表達(dá)式的計(jì)算效率更高一些？為什么？12/16/20229§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)的關(guān)系代數(shù)表達(dá)式12/12/§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式樹為了更明顯地看出上述兩個(gè)表達(dá)式的差別，還可以用關(guān)系代數(shù)表達(dá)式樹來(lái)描述它們：12/16/202210§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式樹12/12/20§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式的轉(zhuǎn)換與等價(jià)通過(guò)等價(jià)規(guī)則進(jìn)行關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換；等價(jià)規(guī)則顧名思義就是指兩種不同形式的表達(dá)式可以相互轉(zhuǎn)換，而又保持等價(jià)；所謂保持等價(jià)是指兩個(gè)表達(dá)式產(chǎn)生的結(jié)果關(guān)系具有相同的屬性集和相同的元組集，但屬性出現(xiàn)的次序可以不同。等價(jià)規(guī)則在下面的等價(jià)規(guī)則中，用、1、2等表示謂詞；用L、L1、L2等表示屬性列表；用E、E1、E2等表示關(guān)系代數(shù)表達(dá)式。12/16/202211§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式的轉(zhuǎn)換與等價(jià)12/12/2§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則⑴合取選擇運(yùn)算可分解為單個(gè)選擇運(yùn)算的序列，該變換稱為的級(jí)聯(lián)：1∧2(E)=1(2(E))⑵選擇運(yùn)算滿足交換律：1(2(E))=2(1(E))⑶投影運(yùn)算序列中只有最后一個(gè)運(yùn)算是需要的，其余可省略。該轉(zhuǎn)換稱為的級(jí)聯(lián)：L1(L2(…(Ln(E))…))=L1(E)12/16/202212§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則12/12/202212§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則⑷選擇可與笛卡兒積以及theta連接相結(jié)合：①(E1E2)=E1E2②1(E12E2)=E11∧2E2

⑸theta連接(包括自然連接)運(yùn)算滿足交換律：E1E2=E2E1

⑹自然連接運(yùn)算滿足結(jié)合律：①(E1E2)E3=E1(E2E3)

theta連接具有以下方式的結(jié)合律：②(E11E2)2∧3E3=E11∧3(E22E3)2只涉及E2與E3的屬性；由于任意一個(gè)條件都可為空，因此笛卡兒積運(yùn)算也滿足結(jié)合率！12/16/202213§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則2只涉及E2與E3的屬§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則⑺選擇運(yùn)算在下面兩個(gè)條件下對(duì)theta連接運(yùn)算具有分配律：①當(dāng)選擇條件0的所有屬性只涉及E1時(shí)：0(E1E2)=(0(E1))E2②當(dāng)選擇條件1只涉及E1的屬性，2只涉及E2時(shí)：1∧2(E1E2)=(1(E1))(2(E2))⑻投影運(yùn)算對(duì)theta連接運(yùn)算具有分配律：①令L1、L2分別是E1、E2的屬性，而連接條件只涉及L1∪L2中的屬性，則：L1∪L2(E1E2)=(L1(E1))(L2(E2))12/16/202214§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則12/12/202214§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則⑻投影運(yùn)算對(duì)theta連接運(yùn)算具有分配律：②令L1、L2分別是E1、E2的屬性，L3是E1里出現(xiàn)在連接條件中但不在L1∪L2中的屬性，而L4是E2里出現(xiàn)在連接條件中但不在L1∪L2中的屬性，那么：L1∪L2(E1E2)=L1∪L2((L1∪L3(E1))(L2∪L4(E2)))⑼集合運(yùn)算并與交滿足交換律：①E1∪E2=E2∪E1；②E1∩E2=E2∩E1但是集合差運(yùn)算不滿足交換律！12/16/202215§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則12/12/202215§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則⑽集合運(yùn)算并與交滿足結(jié)合律：(E1∪E2)∪E3=E1∪(E2∪E3)(E1∩E2)∩E3=E1∩(E2∩E3)⑾選擇運(yùn)算對(duì)并、交、差運(yùn)算具有分配律：(E1∪E2)=(E1)∪(E2)(E1∩E2)=(E1)∩(E2)(E1-E2)=(E1)-(E2)⑿投影運(yùn)算對(duì)并運(yùn)算具有分配率：L(E1∪E2)=(L(E1))∪(L(E2))12/16/202216§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則12/12/202216§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例假設(shè)student和selecting是以下關(guān)系模式上的關(guān)系：Student_schema=(student_number,student_name,department_name)Selecting_schema=(student_number,course_name)對(duì)于關(guān)系代數(shù)表達(dá)式：Πstudent_name(σdepartment_name=“計(jì)算機(jī)系”(studentselecting))12/16/202217§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例12/12/202§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例利用前面介紹的規(guī)則⑺①，可以得到如下的等價(jià)表達(dá)式：Πstudent_name((σdepartment_name=“計(jì)算機(jī)系”(student))selecting)如果將上述查詢修改為：Πstudent_name(σdepartment_name=“計(jì)算機(jī)系”∧course_namelike”數(shù)據(jù)庫(kù)%”(studentselecting))那么，如何對(duì)上述表達(dá)式進(jìn)行等價(jià)變換呢？12/16/202218§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例12/12/202§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例由于選擇條件中屬性department_name只涉及到關(guān)系student，而屬性course_name只涉及到關(guān)系selecting，因此利用規(guī)則⑺②將表達(dá)式變換為：Πstudent_name((σdepartment_name=“計(jì)算機(jī)系”(student))(σcourse_namelike”數(shù)據(jù)庫(kù)%”(selecting)))12/16/202219§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例12/12/202表達(dá)式轉(zhuǎn)換舉例用關(guān)系代數(shù)表達(dá)式樹可以更明顯地看出上述兩個(gè)表達(dá)式的差別：§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換12/16/202220表達(dá)式轉(zhuǎn)換舉例§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換12/12/202§9.3查詢代價(jià)的度量查詢處理的代價(jià)查詢處理的代價(jià)可以通過(guò)該查詢對(duì)各種資源的使用情況進(jìn)行衡量。資源包括：磁盤存取(磁盤I/O)執(zhí)行查詢所用的CPU時(shí)間并行/分布式數(shù)據(jù)庫(kù)系統(tǒng)中的通信開(kāi)銷磁盤訪問(wèn)通常是最主要的代價(jià)，這是因?yàn)椋捍疟P存取比內(nèi)存操作(CPU)要慢得多；CPU速度的提升要比磁盤速度的提升快的多。結(jié)論：磁盤存取代價(jià)是查詢執(zhí)行計(jì)劃代價(jià)的合理度量。12/16/202221§9.3查詢代價(jià)的度量查詢處理的代價(jià)12/12/202221§9.3查詢代價(jià)的度量代價(jià)模型為了簡(jiǎn)化磁盤存取代價(jià)的計(jì)算，需要構(gòu)造一個(gè)簡(jiǎn)單的代價(jià)模型：存取代價(jià)用從磁盤向主存?zhèn)魉偷奈锢韷K數(shù)來(lái)度量假定所有塊傳送的代價(jià)相同。該假定忽略了：尋道時(shí)間(搜索時(shí)間)：將磁頭移動(dòng)到所期望的磁道或柱面的時(shí)間；旋轉(zhuǎn)等待時(shí)間：等待所需要的數(shù)據(jù)(扇區(qū))旋轉(zhuǎn)到讀寫頭下的時(shí)間延遲。忽略了將查詢的最終結(jié)果寫回磁盤的代價(jià)；實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)是最壞情形下的代價(jià)：即主存中緩沖區(qū)只能容納數(shù)目不多的數(shù)據(jù)塊，需要不斷地訪問(wèn)外存。12/16/202222§9.3查詢代價(jià)的度量代價(jià)模型12/12/202222§9.3查詢代價(jià)的度量用于估計(jì)代價(jià)的統(tǒng)計(jì)信息查詢優(yōu)化器利用存儲(chǔ)在DBMS的系統(tǒng)目錄中的統(tǒng)計(jì)信息來(lái)估計(jì)查詢執(zhí)行計(jì)劃的代價(jià)，相關(guān)的統(tǒng)計(jì)信息包括：nr：關(guān)系r中元組的數(shù)目；br：關(guān)系r的元組所占用的塊數(shù)目；sr：關(guān)系r中一個(gè)元組的大?。籪r：關(guān)系r的塊因子，即一個(gè)物理塊中能存放的關(guān)系r的元組數(shù)目；V(A,r)：關(guān)系r中屬性A所具有的不同值的數(shù)目：該數(shù)目與A(r)的大小相同。若A為關(guān)系r的碼，則V(A,r)=nr。12/16/202223§9.3查詢代價(jià)的度量用于估計(jì)代價(jià)的統(tǒng)計(jì)信息12/12/20§9.3查詢代價(jià)的度量用于估計(jì)代價(jià)的統(tǒng)計(jì)信息查詢優(yōu)化器利用存儲(chǔ)在DBMS的系統(tǒng)目錄中的統(tǒng)計(jì)信息來(lái)估計(jì)查詢執(zhí)行計(jì)劃的代價(jià)，相關(guān)的統(tǒng)計(jì)信息包括：SC(A,r)：關(guān)系r的屬性A的選擇基數(shù)。給定關(guān)系r及其屬性A，假定至少有一條記錄滿足等值條件，那么SC(A,r)表示在屬性A上滿足某個(gè)等值條件的平均記錄數(shù)：若A為r的碼，則SC(A,r)=1；若A為非碼屬性，并假定V(A,r)個(gè)不同的值在多個(gè)元組中平均分配，則SC(A,r)=(nr/V(A,r))。HTi：索引i的層數(shù)，即索引i的高度；對(duì)于散列索引，HTi=1。12/16/202224§9.3查詢代價(jià)的度量用于估計(jì)代價(jià)的統(tǒng)計(jì)信息12/12/20§9.3查詢代價(jià)的度量統(tǒng)計(jì)信息的維護(hù)與使用這里提到的統(tǒng)計(jì)信息是經(jīng)過(guò)簡(jiǎn)化的，實(shí)際系統(tǒng)的查詢優(yōu)化器通常包含更多的統(tǒng)計(jì)信息。這些統(tǒng)計(jì)信息：在適當(dāng)?shù)臅r(shí)候，比如系統(tǒng)負(fù)載比較輕的時(shí)候，進(jìn)行更新，而不是實(shí)時(shí)更新。利用這些統(tǒng)計(jì)信息來(lái)估計(jì)實(shí)現(xiàn)各種關(guān)系代數(shù)運(yùn)算的算法代價(jià)，并把算法A的代價(jià)估計(jì)記為EA。12/16/202225§9.3查詢代價(jià)的度量統(tǒng)計(jì)信息的維護(hù)與使用12/12/202§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)概述在關(guān)系代數(shù)中，不同的關(guān)系運(yùn)算有：、、、∪、∩、和運(yùn)算等等；這些運(yùn)算的實(shí)現(xiàn)都離不開(kāi)對(duì)文件的掃描！實(shí)現(xiàn)這些運(yùn)算的不同算法是《數(shù)據(jù)結(jié)構(gòu)》這門課要講的內(nèi)容，包括算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析；本節(jié)的主要內(nèi)容是以前面介紹的代價(jià)模型為基礎(chǔ)，根據(jù)系統(tǒng)目錄中的統(tǒng)計(jì)信息來(lái)分析實(shí)現(xiàn)關(guān)系運(yùn)算的具體算法的磁盤存取代價(jià)，即在磁盤和主存儲(chǔ)器之間傳送的數(shù)據(jù)塊數(shù)！12/16/202226§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)概述12/12/202226§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)選擇運(yùn)算在查詢處理中，實(shí)現(xiàn)選擇運(yùn)算的算法通常是文件掃描。文件掃描是用于定位、檢索滿足選擇條件的記錄的搜索算法：不用索引的搜索算法：文件掃描線性搜索算法A1二分法搜索算法A2使用索引的搜索算法：索引文件掃描有主索引的碼屬性上的等值比較算法A3有主索引的非碼屬性上的等值比較算法A4其他搜索算法……12/16/202227§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)選擇運(yùn)算12/12/20222§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)文件掃描線性搜索算法A1：每個(gè)數(shù)據(jù)塊均被掃描算法代價(jià)：EA1=br效率低但可用于任何文件，且不管是否有索引。二分法搜索算法A2：文件按照某一屬性A排序選擇條件是屬性A上的等值比較二分法搜索針對(duì)文件的數(shù)據(jù)塊進(jìn)行EA2=log2(br)+SC(A,r)/fr-1找到符合條件的第一個(gè)數(shù)據(jù)塊的代價(jià)滿足選擇條件的記錄數(shù)因?yàn)橛幸粔K已被檢索到12/16/202228§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)文件掃描找到符合條件的第一個(gè)數(shù)§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)索引文件掃描有主索引的碼屬性上的等值比較算法A3：選擇條件是碼屬性上的等值比較利用在碼屬性上建立的主索引找到一條記錄算法代價(jià)為：EA3=HTi+1有主索引的非碼屬性上的等值比較算法A4：選擇條件是非碼屬性A上的等值比較利用在非碼屬性A上建立的主索引找到多條記錄算法代價(jià)為：EA4=HTi+SC(A,r)/fr索引文件掃描算法增加了訪問(wèn)索引的代價(jià)。12/16/202229§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)索引文件掃描12/12/202§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)連接運(yùn)算連接運(yùn)算是RDBMS要著重解決的關(guān)系代數(shù)運(yùn)算之一；數(shù)據(jù)庫(kù)的很多查詢都涉及到連接運(yùn)算，因此連接運(yùn)算的效率就成為衡量DBMS性能的一個(gè)主要指標(biāo)。實(shí)現(xiàn)連接運(yùn)算的各種算法有：嵌套循環(huán)連接算法索引嵌套循環(huán)連接算法歸并連接算法散列連接算法其他連接算法……12/16/202230§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)連接運(yùn)算12/12/20223§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)嵌套循環(huán)連接以theta連接rs為例：12/16/202231§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)嵌套循環(huán)連接12/12/202§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)嵌套循環(huán)連接算法分析：與文件的線性掃描算法類似，關(guān)系文件的每個(gè)數(shù)據(jù)塊都必須被訪問(wèn)；不要求有任何索引，任何連接條件都能適應(yīng)；對(duì)關(guān)系r的每一條記錄都必須對(duì)關(guān)系s做一次完整的掃描，因此算法代價(jià)為：最壞情況下：緩沖區(qū)只能容納每個(gè)關(guān)系的一個(gè)數(shù)據(jù)塊，因而EJ=nr*bs+br最好情況下：兩個(gè)關(guān)系都能放到內(nèi)存里，因而算法代價(jià)為EJ=bs+br第一節(jié)課的問(wèn)題：誰(shuí)將作為連接的內(nèi)關(guān)系？12/16/202232§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)嵌套循環(huán)連接12/12/202§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)索引嵌套循環(huán)連接將嵌套循環(huán)連接算法中的文件掃描用索引掃描來(lái)代替：算法分析：在給定元組tr的情況下，在關(guān)系s中查找滿足連接條件的元組本質(zhì)上是在s上做選擇運(yùn)算。因此該算法的代價(jià)為：EJ=br+nr*c其中c是使用連接條件并利用索引對(duì)關(guān)系s進(jìn)行單個(gè)選擇運(yùn)算的代價(jià)。索引該建在什么地方？12/16/202233§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)索引嵌套循環(huán)連接算法分析：12§9.5表達(dá)式的求值方法概述：關(guān)系代數(shù)表達(dá)式的代價(jià)估計(jì)前面討論的都是實(shí)現(xiàn)單個(gè)關(guān)系運(yùn)算的算法與算法分析；實(shí)際上在一個(gè)關(guān)系代數(shù)表達(dá)式里常常含有多個(gè)不同或相同的關(guān)系運(yùn)算，那么如何估計(jì)整個(gè)表達(dá)式的計(jì)算代價(jià)呢？這主要與整個(gè)表達(dá)式的計(jì)算方法有關(guān)：實(shí)體化計(jì)算方法流水線計(jì)算方法上述兩種方法的相互結(jié)合(參見(jiàn)§9.6)12/16/202234§9.5表達(dá)式的求值方法概述：關(guān)系代數(shù)表達(dá)式的代價(jià)估計(jì)12/§9.5表達(dá)式的求值方法實(shí)體化計(jì)算方法以適當(dāng)?shù)捻樞蛎看螆?zhí)行表達(dá)式里的一個(gè)關(guān)系運(yùn)算，每次計(jì)算的結(jié)果都被保存(實(shí)體化)到一個(gè)臨時(shí)關(guān)系中以備后面的運(yùn)算使用。如：Πcourse_name((σstudent_number<”s000003”(student))selecting)12/16/202235§9.5表達(dá)式的求值方法實(shí)體化計(jì)算方法12/12/20223§9.5表達(dá)式的求值方法實(shí)體化計(jì)算方法實(shí)體化計(jì)算方法的缺點(diǎn)是需要構(gòu)造臨時(shí)關(guān)系，這些臨時(shí)關(guān)系除非很小(可以放在內(nèi)存里)，否則就必須寫到磁盤上(tempdb)；實(shí)體化計(jì)算方法的代價(jià)不僅僅是表達(dá)式中所涉及的關(guān)系運(yùn)算的代價(jià)總和，還應(yīng)該加上把中間結(jié)果寫回磁盤的代價(jià)；在估計(jì)單個(gè)關(guān)系運(yùn)算的代價(jià)時(shí)，忽略了將運(yùn)算結(jié)果回寫到磁盤的代價(jià)。但對(duì)由多個(gè)關(guān)系運(yùn)算構(gòu)成的表達(dá)式，就不能簡(jiǎn)單地忽略掉回寫磁盤的代價(jià)！12/16/202236§9.5表達(dá)式的求值方法實(shí)體化計(jì)算方法12/12/20223§9.5表達(dá)式的求值方法流水線計(jì)算方法將表達(dá)式中的多個(gè)關(guān)系運(yùn)算組合成一個(gè)操作流水線來(lái)實(shí)現(xiàn)，即將一個(gè)運(yùn)算的結(jié)果作為輸入直接傳送到下一個(gè)運(yùn)算。例如：Πcourse_name((σstudent_number<”s000003”(student))selecting)12/16/202237§9.5表達(dá)式的求值方法流水線計(jì)算方法12/12/20223§9.5表達(dá)式的求值方法兩種計(jì)算方法的比較實(shí)體化計(jì)算方法需要產(chǎn)生臨時(shí)關(guān)系、回寫中間結(jié)果，這可能會(huì)影響查詢的執(zhí)行效率。但該方法可以直接利用各個(gè)關(guān)系運(yùn)算的算法實(shí)現(xiàn)(即操作代碼)；而流水線計(jì)算方法雖然具有減少產(chǎn)生臨時(shí)關(guān)系、提高查詢執(zhí)行效率的優(yōu)點(diǎn)，但它需要對(duì)流水線中的每一關(guān)系運(yùn)算建模，以便能夠重用各個(gè)關(guān)系運(yùn)算的操作代碼。12/16/202238§9.5表達(dá)式的求值方法兩種計(jì)算方法的比較12/12/202§9.5表達(dá)式的求值方法流水線計(jì)算方法模型最簡(jiǎn)單的模型就是：每一關(guān)系運(yùn)算都作為系統(tǒng)內(nèi)獨(dú)立的進(jìn)程或線程；獨(dú)立的線程從流水化的輸入中接受元組流，并產(chǎn)生一個(gè)元組流作為其輸出；對(duì)于流水線中的每對(duì)相鄰運(yùn)算，都創(chuàng)建一個(gè)緩沖區(qū)來(lái)保存從一個(gè)運(yùn)算傳送到另一個(gè)運(yùn)算的元組。12/16/202239§9.5表達(dá)式的求值方法流水線計(jì)算方法模型12/12/202§9.5表達(dá)式的求值方法流水線計(jì)算方法的執(zhí)行需求者驅(qū)動(dòng)：“拉”的過(guò)程系統(tǒng)不停地向位于流水線頂端的操作發(fā)出需要元組的請(qǐng)求；每當(dāng)一個(gè)運(yùn)算收到需要元組的請(qǐng)求時(shí)，它就計(jì)算下一個(gè)或多個(gè)元組并返回它們。生產(chǎn)者驅(qū)動(dòng)：“推”的過(guò)程流水線上的各個(gè)關(guān)系運(yùn)算并不等待元組請(qǐng)求，而是不停地產(chǎn)生元組；流水線底端的每個(gè)操作不斷地產(chǎn)生元組并將它們放在輸出緩沖區(qū)中，直到緩沖區(qū)滿為止。12/16/202240§9.5表達(dá)式的求值方法流水線計(jì)算方法的執(zhí)行12/12/20§9.6查詢優(yōu)化的方法為什么查詢優(yōu)化器是必須的？查詢優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，根據(jù)這些信息選擇有效的執(zhí)行計(jì)劃，而用戶和應(yīng)用程序則難以獲得這些信息；如果數(shù)據(jù)庫(kù)的統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)地對(duì)查詢重新進(jìn)行優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。如果讓用戶或應(yīng)用程序去跟蹤數(shù)據(jù)庫(kù)統(tǒng)計(jì)信息的變化往往是不太可能的；查詢優(yōu)化器可以同時(shí)考慮數(shù)百種不同的查詢執(zhí)行計(jì)劃，而數(shù)據(jù)庫(kù)程序員一般只能考慮有限的幾種可能性。12/16/202241§9.6查詢優(yōu)化的方法為什么查詢優(yōu)化器是必須的？12/12/§9.6查詢優(yōu)化的方法查詢優(yōu)化的步驟與方式查詢優(yōu)化器的任務(wù)就是要產(chǎn)生一個(gè)代價(jià)最小的查詢執(zhí)行計(jì)劃。這要分兩步走：產(chǎn)生邏輯上與給定表達(dá)式等價(jià)的表達(dá)式；對(duì)表達(dá)式做不同方式的注釋，產(chǎn)生后選計(jì)劃：實(shí)現(xiàn)算法的選擇索引的選擇執(zhí)行方法的選擇在查詢優(yōu)化器中，這兩步是交叉進(jìn)行的，產(chǎn)生一部分表達(dá)式并注釋，然后又產(chǎn)生一部分表達(dá)式并注釋……12/16/202242§9.6查詢優(yōu)化的方法查詢優(yōu)化的步驟與方式12/12/202§9.6查詢優(yōu)化的方法查詢執(zhí)行計(jì)劃舉例12/16/202243§9.6查詢優(yōu)化的方法查詢執(zhí)行計(jì)劃舉例12/12/20224查詢優(yōu)化的方法由于產(chǎn)生了很多后選的查詢執(zhí)行計(jì)劃，并且這些計(jì)劃是表達(dá)式與注釋交叉產(chǎn)生的，因此如何對(duì)整個(gè)表達(dá)式進(jìn)行優(yōu)化，產(chǎn)生代價(jià)最小的執(zhí)行計(jì)劃是一個(gè)問(wèn)題；一般來(lái)說(shuō)，簡(jiǎn)單地為每個(gè)關(guān)系運(yùn)算選擇一個(gè)代價(jià)最小的算法，整個(gè)表達(dá)式的代價(jià)可能最小。但這樣做往往是事與愿違！因此，必須采用一定的查詢優(yōu)化策略才能滿足需要：基于代價(jià)的優(yōu)化啟發(fā)式優(yōu)化§9.6查詢優(yōu)化的方法12/16/202244查詢優(yōu)化的方法§9.6查詢優(yōu)化的方法12/12/202244§9.6查詢優(yōu)化的方法基于代價(jià)的優(yōu)化方法將各種可能的查詢執(zhí)行計(jì)劃全部產(chǎn)生出來(lái)，然后從中估計(jì)出代價(jià)最小的一個(gè)；這件事情說(shuō)起來(lái)容易做起來(lái)很難，幾乎是不可能的！例如：考慮r1r2r3的連接順序的組合：12種！12/16/202245§9.6查詢優(yōu)化的方法基于代價(jià)的優(yōu)化方法12/12/2022§9.6查詢優(yōu)化的方法啟發(fā)式優(yōu)化方法利用啟發(fā)式規(guī)則來(lái)減少基于代價(jià)優(yōu)化的可選方案數(shù)；這種摸著石頭過(guò)河的優(yōu)化方法就叫啟發(fā)式優(yōu)化方法。啟發(fā)式優(yōu)化的規(guī)則如下：將合取(∧)選擇運(yùn)算分解為單個(gè)選擇運(yùn)算序列；盡可能早地執(zhí)行選擇運(yùn)算；確定哪些選擇運(yùn)算和連接運(yùn)算將產(chǎn)生比較小的關(guān)系，重新組織表達(dá)式中多個(gè)連接的順序；將有關(guān)選擇運(yùn)算和笛卡兒積運(yùn)算組成連接運(yùn)算；將投影屬性分解，并盡可能早地執(zhí)行投影運(yùn)算；識(shí)別哪些運(yùn)算可用流水線方法執(zhí)行就采用它。12/16/202246§9.6查詢優(yōu)化的方法啟發(fā)式優(yōu)化方法12/12/202246§9.7查詢優(yōu)化器的構(gòu)造實(shí)際DBMS中，大多數(shù)優(yōu)化器都是將基于代價(jià)的優(yōu)化和啟發(fā)式優(yōu)化規(guī)則結(jié)合起來(lái)。IBM的SystemR：并不考慮所有的連接順序，僅考慮右操作數(shù)是原始關(guān)系r1,r2,…,rn的連接順序。這種連接順序稱為左深連接順序。Sybase的優(yōu)化器：對(duì)索引掃描采用了較好的代價(jià)估計(jì)技術(shù)，它充分考慮了包含所要元組的頁(yè)在緩沖區(qū)中的概率。Oracle的優(yōu)化器：分為兩個(gè)部件：一個(gè)基于啟發(fā)式規(guī)則，一個(gè)基于代價(jià)。它們交叉協(xié)同工作。12/16/202247§9.7查詢優(yōu)化器的構(gòu)造實(shí)際DBMS中，大多數(shù)優(yōu)化器都是將基§9.7查詢優(yōu)化器的構(gòu)造左深連接順序左深連接與非左深連接的區(qū)別r1r2r3r4r5r5r1r2r3r412/16/202248§9.7查詢優(yōu)化器的構(gòu)造左深連接順序左深連接與非左深連接的區(qū)§9.7查詢優(yōu)化器的構(gòu)造SQLServer2000SQLServer采用基于代價(jià)的優(yōu)化方法；但由于基于代價(jià)的優(yōu)化的后選方案數(shù)可能太多，因此SQLServer2000采用啟發(fā)式規(guī)則來(lái)減少基于代價(jià)優(yōu)化的可選方案數(shù)；這種啟發(fā)式規(guī)則大約有300到400條，遺憾的是三校訪問(wèn)小組沒(méi)能從微軟獲得一條有意義的啟發(fā)式規(guī)則。12/16/202249§9.7查詢優(yōu)化器的構(gòu)造SQLServer200012/小結(jié):查詢優(yōu)化是永恒的主題查詢處理的代價(jià)是什么？代價(jià)模型假定了什么？忽略了什么？如何估計(jì)查詢執(zhí)行計(jì)劃的代價(jià)？利用統(tǒng)計(jì)信息查詢優(yōu)化的方法基于代價(jià)的優(yōu)化啟發(fā)式優(yōu)化規(guī)則實(shí)際DBMS是二者的結(jié)合12/16/202250小結(jié):查詢優(yōu)化是永恒的主題查詢處理的代價(jià)是什么？12/12/小結(jié):查詢優(yōu)化是永恒的主題新的查詢優(yōu)化技術(shù)Ioannidis等人在1992年提出了參數(shù)化的查詢優(yōu)化技術(shù)，解決關(guān)系大小頻繁變化時(shí)的查詢處理問(wèn)題；值的非均勻分布為查詢結(jié)果大小及代價(jià)估計(jì)帶來(lái)了問(wèn)題。為解決此問(wèn)題，提出了使用值分布直方圖的代價(jià)估計(jì)技術(shù)；多查詢的優(yōu)化技術(shù)：尋找只需計(jì)算一次的公共子表達(dá)式。12/16/202251小結(jié):查詢優(yōu)化是永恒的主題新的查詢優(yōu)化技術(shù)12/12/202數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)與原理第Ⅲ部分DBMS的內(nèi)核(第９章－第11章)12/16/202252數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)與原理12/12/20221第9章查詢處理講課內(nèi)容：查詢處理是指從數(shù)據(jù)庫(kù)中提取數(shù)據(jù)的一系列活動(dòng)。這一系列活動(dòng)包括：將用高層數(shù)據(jù)庫(kù)語(yǔ)言表示的查詢語(yǔ)句，如SQL，翻譯成能在文件系統(tǒng)這一物理層上實(shí)現(xiàn)的表達(dá)式，如關(guān)系代數(shù)；為優(yōu)化查詢進(jìn)行的各種轉(zhuǎn)換；以及查詢的實(shí)際執(zhí)行?！霾樵兲幚淼倪^(guò)程■表達(dá)式的求值方法■關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換■查詢優(yōu)化的方法■查詢代價(jià)的度量■查詢優(yōu)化器的構(gòu)造■實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)■本章總結(jié)12/16/202253第9章查詢處理講課內(nèi)容：12/12/20222DBMS總體結(jié)構(gòu)回顧：查詢處理器用戶應(yīng)用界面索引統(tǒng)計(jì)數(shù)據(jù)數(shù)據(jù)文件數(shù)據(jù)字典應(yīng)用程序交互查詢數(shù)據(jù)庫(kù)模式應(yīng)用程序目標(biāo)碼嵌入式DML預(yù)編譯器DML編譯器DDL解釋器查詢計(jì)算引擎事務(wù)管理器緩沖區(qū)管理器文件管理器查詢處理器存儲(chǔ)管理器數(shù)據(jù)庫(kù)管理系統(tǒng)磁盤存儲(chǔ)器權(quán)限及完整性管理器日志12/16/202254DBMS總體結(jié)構(gòu)回顧：查詢處理器用戶應(yīng)用界面索引統(tǒng)計(jì)數(shù)據(jù)數(shù)據(jù)§9.1查詢處理的過(guò)程查詢處理是指對(duì)最終用戶提交的查詢進(jìn)行：解析優(yōu)化執(zhí)行并最終給出查詢結(jié)果的處理過(guò)程。12/16/202255§9.1查詢處理的過(guò)程查詢處理12/12/20224§9.1查詢處理的過(guò)程查詢優(yōu)化器問(wèn)題的提出：一個(gè)查詢用SQL語(yǔ)言可以有多種表達(dá)方式；而每個(gè)SQL語(yǔ)句又可以翻譯成多個(gè)等價(jià)的關(guān)系代數(shù)表達(dá)式。例如：selectstudent_numberfromstudentwherestudent_number<“s000003”可以翻譯成下面兩個(gè)關(guān)系代數(shù)表達(dá)式：①σstudent_number<”s000003”(Πstudent_number(student))②Πstudent_number(σstudent_number<”s000003”(student))表達(dá)式中的關(guān)系運(yùn)算又可以用不同的算法和索引去實(shí)現(xiàn)。因此，查詢優(yōu)化器的任務(wù)就是要找出代價(jià)最小的計(jì)算給定查詢的處理過(guò)程。12/16/202256§9.1查詢處理的過(guò)程查詢優(yōu)化器12/12/20225§9.1查詢處理的過(guò)程查詢優(yōu)化器輸入？輸出？查詢執(zhí)行計(jì)劃？帶注釋！注釋用于說(shuō)明：如何具體實(shí)施每個(gè)關(guān)系操作。例如：關(guān)系運(yùn)算所采用的算法將要使用的索引執(zhí)行原語(yǔ)：加上了有關(guān)“如何執(zhí)行”的注釋的關(guān)系代數(shù)運(yùn)算查詢執(zhí)行(計(jì)算)計(jì)劃：用于計(jì)算一個(gè)查詢的原語(yǔ)序列。12/16/202257§9.1查詢處理的過(guò)程查詢優(yōu)化器12/12/20226查詢優(yōu)化器查詢優(yōu)化為給定查詢選擇最有效的查詢執(zhí)行計(jì)劃的過(guò)程：在關(guān)系代數(shù)級(jí)進(jìn)行優(yōu)化，力圖找出與給定表達(dá)式等價(jià)、但執(zhí)行效率更高(?)的一個(gè)表達(dá)式；查詢語(yǔ)句處理的詳細(xì)策略的選擇。例如，確定算法與索引等。本章的主要內(nèi)容什么是查詢執(zhí)行計(jì)劃的代價(jià)？如何估計(jì)查詢執(zhí)行計(jì)劃的代價(jià)？如何進(jìn)行有效的查詢優(yōu)化？§9.1查詢處理的過(guò)程12/16/202258查詢優(yōu)化器§9.1查詢處理的過(guò)程12/12/20227§9.1查詢處理的過(guò)程執(zhí)行引擎輸入是查詢執(zhí)行計(jì)劃輸出則是具體的查詢結(jié)果還需要將實(shí)現(xiàn)關(guān)系運(yùn)算的算法與底層的文件操作指令結(jié)合起來(lái)！12/16/202259§9.1查詢處理的過(guò)程執(zhí)行引擎還需要將實(shí)現(xiàn)關(guān)系運(yùn)算的算法與底§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)的關(guān)系代數(shù)表達(dá)式它們的執(zhí)行結(jié)果相同，但代價(jià)不同。例如：“請(qǐng)給出計(jì)算機(jī)系的教師所講課程的課程名稱和教師姓名”，就可以用如下兩個(gè)等價(jià)的關(guān)系代數(shù)表達(dá)式來(lái)求值：Πcourse_name,teacher_name(σdepartment_name=“計(jì)算機(jī)系”(teacherteaching))Πcourse_name,teacher_name((σdepartment_name=“計(jì)算機(jī)系”(teacher))teaching)從感覺(jué)上講，哪個(gè)關(guān)系代數(shù)表達(dá)式的計(jì)算效率更高一些？為什么？12/16/202260§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)的關(guān)系代數(shù)表達(dá)式12/12/§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式樹為了更明顯地看出上述兩個(gè)表達(dá)式的差別，還可以用關(guān)系代數(shù)表達(dá)式樹來(lái)描述它們：12/16/202261§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式樹12/12/20§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式的轉(zhuǎn)換與等價(jià)通過(guò)等價(jià)規(guī)則進(jìn)行關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換；等價(jià)規(guī)則顧名思義就是指兩種不同形式的表達(dá)式可以相互轉(zhuǎn)換，而又保持等價(jià)；所謂保持等價(jià)是指兩個(gè)表達(dá)式產(chǎn)生的結(jié)果關(guān)系具有相同的屬性集和相同的元組集，但屬性出現(xiàn)的次序可以不同。等價(jià)規(guī)則在下面的等價(jià)規(guī)則中，用、1、2等表示謂詞；用L、L1、L2等表示屬性列表；用E、E1、E2等表示關(guān)系代數(shù)表達(dá)式。12/16/202262§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式的轉(zhuǎn)換與等價(jià)12/12/2§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則⑴合取選擇運(yùn)算可分解為單個(gè)選擇運(yùn)算的序列，該變換稱為的級(jí)聯(lián)：1∧2(E)=1(2(E))⑵選擇運(yùn)算滿足交換律：1(2(E))=2(1(E))⑶投影運(yùn)算序列中只有最后一個(gè)運(yùn)算是需要的，其余可省略。該轉(zhuǎn)換稱為的級(jí)聯(lián)：L1(L2(…(Ln(E))…))=L1(E)12/16/202263§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則12/12/202212§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則⑷選擇可與笛卡兒積以及theta連接相結(jié)合：①(E1E2)=E1E2②1(E12E2)=E11∧2E2

⑸theta連接(包括自然連接)運(yùn)算滿足交換律：E1E2=E2E1

⑹自然連接運(yùn)算滿足結(jié)合律：①(E1E2)E3=E1(E2E3)

theta連接具有以下方式的結(jié)合律：②(E11E2)2∧3E3=E11∧3(E22E3)2只涉及E2與E3的屬性；由于任意一個(gè)條件都可為空，因此笛卡兒積運(yùn)算也滿足結(jié)合率！12/16/202264§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則2只涉及E2與E3的屬§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則⑺選擇運(yùn)算在下面兩個(gè)條件下對(duì)theta連接運(yùn)算具有分配律：①當(dāng)選擇條件0的所有屬性只涉及E1時(shí)：0(E1E2)=(0(E1))E2②當(dāng)選擇條件1只涉及E1的屬性，2只涉及E2時(shí)：1∧2(E1E2)=(1(E1))(2(E2))⑻投影運(yùn)算對(duì)theta連接運(yùn)算具有分配律：①令L1、L2分別是E1、E2的屬性，而連接條件只涉及L1∪L2中的屬性，則：L1∪L2(E1E2)=(L1(E1))(L2(E2))12/16/202265§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則12/12/202214§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則⑻投影運(yùn)算對(duì)theta連接運(yùn)算具有分配律：②令L1、L2分別是E1、E2的屬性，L3是E1里出現(xiàn)在連接條件中但不在L1∪L2中的屬性，而L4是E2里出現(xiàn)在連接條件中但不在L1∪L2中的屬性，那么：L1∪L2(E1E2)=L1∪L2((L1∪L3(E1))(L2∪L4(E2)))⑼集合運(yùn)算并與交滿足交換律：①E1∪E2=E2∪E1；②E1∩E2=E2∩E1但是集合差運(yùn)算不滿足交換律！12/16/202266§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則12/12/202215§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則⑽集合運(yùn)算并與交滿足結(jié)合律：(E1∪E2)∪E3=E1∪(E2∪E3)(E1∩E2)∩E3=E1∩(E2∩E3)⑾選擇運(yùn)算對(duì)并、交、差運(yùn)算具有分配律：(E1∪E2)=(E1)∪(E2)(E1∩E2)=(E1)∩(E2)(E1-E2)=(E1)-(E2)⑿投影運(yùn)算對(duì)并運(yùn)算具有分配率：L(E1∪E2)=(L(E1))∪(L(E2))12/16/202267§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則12/12/202216§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例假設(shè)student和selecting是以下關(guān)系模式上的關(guān)系：Student_schema=(student_number,student_name,department_name)Selecting_schema=(student_number,course_name)對(duì)于關(guān)系代數(shù)表達(dá)式：Πstudent_name(σdepartment_name=“計(jì)算機(jī)系”(studentselecting))12/16/202268§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例12/12/202§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例利用前面介紹的規(guī)則⑺①，可以得到如下的等價(jià)表達(dá)式：Πstudent_name((σdepartment_name=“計(jì)算機(jī)系”(student))selecting)如果將上述查詢修改為：Πstudent_name(σdepartment_name=“計(jì)算機(jī)系”∧course_namelike”數(shù)據(jù)庫(kù)%”(studentselecting))那么，如何對(duì)上述表達(dá)式進(jìn)行等價(jià)變換呢？12/16/202269§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例12/12/202§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例由于選擇條件中屬性department_name只涉及到關(guān)系student，而屬性course_name只涉及到關(guān)系selecting，因此利用規(guī)則⑺②將表達(dá)式變換為：Πstudent_name((σdepartment_name=“計(jì)算機(jī)系”(student))(σcourse_namelike”數(shù)據(jù)庫(kù)%”(selecting)))12/16/202270§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例12/12/202表達(dá)式轉(zhuǎn)換舉例用關(guān)系代數(shù)表達(dá)式樹可以更明顯地看出上述兩個(gè)表達(dá)式的差別：§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換12/16/202271表達(dá)式轉(zhuǎn)換舉例§9.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換12/12/202§9.3查詢代價(jià)的度量查詢處理的代價(jià)查詢處理的代價(jià)可以通過(guò)該查詢對(duì)各種資源的使用情況進(jìn)行衡量。資源包括：磁盤存取(磁盤I/O)執(zhí)行查詢所用的CPU時(shí)間并行/分布式數(shù)據(jù)庫(kù)系統(tǒng)中的通信開(kāi)銷磁盤訪問(wèn)通常是最主要的代價(jià)，這是因?yàn)椋捍疟P存取比內(nèi)存操作(CPU)要慢得多；CPU速度的提升要比磁盤速度的提升快的多。結(jié)論：磁盤存取代價(jià)是查詢執(zhí)行計(jì)劃代價(jià)的合理度量。12/16/202272§9.3查詢代價(jià)的度量查詢處理的代價(jià)12/12/202221§9.3查詢代價(jià)的度量代價(jià)模型為了簡(jiǎn)化磁盤存取代價(jià)的計(jì)算，需要構(gòu)造一個(gè)簡(jiǎn)單的代價(jià)模型：存取代價(jià)用從磁盤向主存?zhèn)魉偷奈锢韷K數(shù)來(lái)度量假定所有塊傳送的代價(jià)相同。該假定忽略了：尋道時(shí)間(搜索時(shí)間)：將磁頭移動(dòng)到所期望的磁道或柱面的時(shí)間；旋轉(zhuǎn)等待時(shí)間：等待所需要的數(shù)據(jù)(扇區(qū))旋轉(zhuǎn)到讀寫頭下的時(shí)間延遲。忽略了將查詢的最終結(jié)果寫回磁盤的代價(jià)；實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)是最壞情形下的代價(jià)：即主存中緩沖區(qū)只能容納數(shù)目不多的數(shù)據(jù)塊，需要不斷地訪問(wèn)外存。12/16/202273§9.3查詢代價(jià)的度量代價(jià)模型12/12/202222§9.3查詢代價(jià)的度量用于估計(jì)代價(jià)的統(tǒng)計(jì)信息查詢優(yōu)化器利用存儲(chǔ)在DBMS的系統(tǒng)目錄中的統(tǒng)計(jì)信息來(lái)估計(jì)查詢執(zhí)行計(jì)劃的代價(jià)，相關(guān)的統(tǒng)計(jì)信息包括：nr：關(guān)系r中元組的數(shù)目；br：關(guān)系r的元組所占用的塊數(shù)目；sr：關(guān)系r中一個(gè)元組的大??；fr：關(guān)系r的塊因子，即一個(gè)物理塊中能存放的關(guān)系r的元組數(shù)目；V(A,r)：關(guān)系r中屬性A所具有的不同值的數(shù)目：該數(shù)目與A(r)的大小相同。若A為關(guān)系r的碼，則V(A,r)=nr。12/16/202274§9.3查詢代價(jià)的度量用于估計(jì)代價(jià)的統(tǒng)計(jì)信息12/12/20§9.3查詢代價(jià)的度量用于估計(jì)代價(jià)的統(tǒng)計(jì)信息查詢優(yōu)化器利用存儲(chǔ)在DBMS的系統(tǒng)目錄中的統(tǒng)計(jì)信息來(lái)估計(jì)查詢執(zhí)行計(jì)劃的代價(jià)，相關(guān)的統(tǒng)計(jì)信息包括：SC(A,r)：關(guān)系r的屬性A的選擇基數(shù)。給定關(guān)系r及其屬性A，假定至少有一條記錄滿足等值條件，那么SC(A,r)表示在屬性A上滿足某個(gè)等值條件的平均記錄數(shù)：若A為r的碼，則SC(A,r)=1；若A為非碼屬性，并假定V(A,r)個(gè)不同的值在多個(gè)元組中平均分配，則SC(A,r)=(nr/V(A,r))。HTi：索引i的層數(shù)，即索引i的高度；對(duì)于散列索引，HTi=1。12/16/202275§9.3查詢代價(jià)的度量用于估計(jì)代價(jià)的統(tǒng)計(jì)信息12/12/20§9.3查詢代價(jià)的度量統(tǒng)計(jì)信息的維護(hù)與使用這里提到的統(tǒng)計(jì)信息是經(jīng)過(guò)簡(jiǎn)化的，實(shí)際系統(tǒng)的查詢優(yōu)化器通常包含更多的統(tǒng)計(jì)信息。這些統(tǒng)計(jì)信息：在適當(dāng)?shù)臅r(shí)候，比如系統(tǒng)負(fù)載比較輕的時(shí)候，進(jìn)行更新，而不是實(shí)時(shí)更新。利用這些統(tǒng)計(jì)信息來(lái)估計(jì)實(shí)現(xiàn)各種關(guān)系代數(shù)運(yùn)算的算法代價(jià)，并把算法A的代價(jià)估計(jì)記為EA。12/16/202276§9.3查詢代價(jià)的度量統(tǒng)計(jì)信息的維護(hù)與使用12/12/202§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)概述在關(guān)系代數(shù)中，不同的關(guān)系運(yùn)算有：、、、∪、∩、和運(yùn)算等等；這些運(yùn)算的實(shí)現(xiàn)都離不開(kāi)對(duì)文件的掃描！實(shí)現(xiàn)這些運(yùn)算的不同算法是《數(shù)據(jù)結(jié)構(gòu)》這門課要講的內(nèi)容，包括算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析；本節(jié)的主要內(nèi)容是以前面介紹的代價(jià)模型為基礎(chǔ)，根據(jù)系統(tǒng)目錄中的統(tǒng)計(jì)信息來(lái)分析實(shí)現(xiàn)關(guān)系運(yùn)算的具體算法的磁盤存取代價(jià)，即在磁盤和主存儲(chǔ)器之間傳送的數(shù)據(jù)塊數(shù)！12/16/202277§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)概述12/12/202226§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)選擇運(yùn)算在查詢處理中，實(shí)現(xiàn)選擇運(yùn)算的算法通常是文件掃描。文件掃描是用于定位、檢索滿足選擇條件的記錄的搜索算法：不用索引的搜索算法：文件掃描線性搜索算法A1二分法搜索算法A2使用索引的搜索算法：索引文件掃描有主索引的碼屬性上的等值比較算法A3有主索引的非碼屬性上的等值比較算法A4其他搜索算法……12/16/202278§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)選擇運(yùn)算12/12/20222§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)文件掃描線性搜索算法A1：每個(gè)數(shù)據(jù)塊均被掃描算法代價(jià)：EA1=br效率低但可用于任何文件，且不管是否有索引。二分法搜索算法A2：文件按照某一屬性A排序選擇條件是屬性A上的等值比較二分法搜索針對(duì)文件的數(shù)據(jù)塊進(jìn)行EA2=log2(br)+SC(A,r)/fr-1找到符合條件的第一個(gè)數(shù)據(jù)塊的代價(jià)滿足選擇條件的記錄數(shù)因?yàn)橛幸粔K已被檢索到12/16/202279§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)文件掃描找到符合條件的第一個(gè)數(shù)§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)索引文件掃描有主索引的碼屬性上的等值比較算法A3：選擇條件是碼屬性上的等值比較利用在碼屬性上建立的主索引找到一條記錄算法代價(jià)為：EA3=HTi+1有主索引的非碼屬性上的等值比較算法A4：選擇條件是非碼屬性A上的等值比較利用在非碼屬性A上建立的主索引找到多條記錄算法代價(jià)為：EA4=HTi+SC(A,r)/fr索引文件掃描算法增加了訪問(wèn)索引的代價(jià)。12/16/202280§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)索引文件掃描12/12/202§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)連接運(yùn)算連接運(yùn)算是RDBMS要著重解決的關(guān)系代數(shù)運(yùn)算之一；數(shù)據(jù)庫(kù)的很多查詢都涉及到連接運(yùn)算，因此連接運(yùn)算的效率就成為衡量DBMS性能的一個(gè)主要指標(biāo)。實(shí)現(xiàn)連接運(yùn)算的各種算法有：嵌套循環(huán)連接算法索引嵌套循環(huán)連接算法歸并連接算法散列連接算法其他連接算法……12/16/202281§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)連接運(yùn)算12/12/20223§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)嵌套循環(huán)連接以theta連接rs為例：12/16/202282§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)嵌套循環(huán)連接12/12/202§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)嵌套循環(huán)連接算法分析：與文件的線性掃描算法類似，關(guān)系文件的每個(gè)數(shù)據(jù)塊都必須被訪問(wèn)；不要求有任何索引，任何連接條件都能適應(yīng)；對(duì)關(guān)系r的每一條記錄都必須對(duì)關(guān)系s做一次完整的掃描，因此算法代價(jià)為：最壞情況下：緩沖區(qū)只能容納每個(gè)關(guān)系的一個(gè)數(shù)據(jù)塊，因而EJ=nr*bs+br最好情況下：兩個(gè)關(guān)系都能放到內(nèi)存里，因而算法代價(jià)為EJ=bs+br第一節(jié)課的問(wèn)題：誰(shuí)將作為連接的內(nèi)關(guān)系？12/16/202283§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)嵌套循環(huán)連接12/12/202§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)索引嵌套循環(huán)連接將嵌套循環(huán)連接算法中的文件掃描用索引掃描來(lái)代替：算法分析：在給定元組tr的情況下，在關(guān)系s中查找滿足連接條件的元組本質(zhì)上是在s上做選擇運(yùn)算。因此該算法的代價(jià)為：EJ=br+nr*c其中c是使用連接條件并利用索引對(duì)關(guān)系s進(jìn)行單個(gè)選擇運(yùn)算的代價(jià)。索引該建在什么地方？12/16/202284§9.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)索引嵌套循環(huán)連接算法分析：12§9.5表達(dá)式的求值方法概述：關(guān)系代數(shù)表達(dá)式的代價(jià)估計(jì)前面討論的都是實(shí)現(xiàn)單個(gè)關(guān)系運(yùn)算的算法與算法分析；實(shí)際上在一個(gè)關(guān)系代數(shù)表達(dá)式里常常含有多個(gè)不同或相同的關(guān)系運(yùn)算，那么如何估計(jì)整個(gè)表達(dá)式的計(jì)算代價(jià)呢？這主要與整個(gè)表達(dá)式的計(jì)算方法有關(guān)：實(shí)體化計(jì)算方法流水線計(jì)算方法上述兩種方法的相互結(jié)合(參見(jiàn)§9.6)12/16/202285§9.5表達(dá)式的求值方法概述：關(guān)系代數(shù)表達(dá)式的代價(jià)估計(jì)12/§9.5表達(dá)式的求值方法實(shí)體化計(jì)算方法以適當(dāng)?shù)捻樞蛎看螆?zhí)行表達(dá)式里的一個(gè)關(guān)系運(yùn)算，每次計(jì)算的結(jié)果都被保存(實(shí)體化)到一個(gè)臨時(shí)關(guān)系中以備后面的運(yùn)算使用。如：Πcourse_name((σstudent_number<”s000003”(student))selecting)12/16/202286§9.5表達(dá)式的求值方法實(shí)體化計(jì)算方法12/12/20223§9.5表達(dá)式的求值方法實(shí)體化計(jì)算方法實(shí)體化計(jì)算方法的缺點(diǎn)是需要構(gòu)造臨時(shí)關(guān)系，這些臨時(shí)關(guān)系除非很小(可以放在內(nèi)存里)，否則就必須寫到磁盤上(tempdb)；實(shí)體化計(jì)算方法的代價(jià)不僅僅是表達(dá)式中所涉及的關(guān)系運(yùn)算的代價(jià)總和，還應(yīng)該加上把中間結(jié)果寫回磁盤的代價(jià)；在估計(jì)單個(gè)關(guān)系運(yùn)算的代價(jià)時(shí)，忽略了將運(yùn)算結(jié)果回寫到磁盤的代價(jià)。但對(duì)由多個(gè)關(guān)系運(yùn)算構(gòu)成的表達(dá)式，就不能簡(jiǎn)單地忽略掉回寫磁盤的代價(jià)！12/16/202287§9.5表達(dá)式的求值方法實(shí)體化計(jì)算方法12/12/20223§9.5表達(dá)式的求值方法流水線計(jì)算方法將表達(dá)式中的多個(gè)關(guān)系運(yùn)算組合成一個(gè)操作流水線來(lái)實(shí)現(xiàn)，即將一個(gè)運(yùn)算的結(jié)果作為輸入直接傳送到下一個(gè)運(yùn)算。例如：Πcourse_name((σstudent_number<”s000003”(student))selecting)12/16/202288§9.5表達(dá)式的求值方法流水線計(jì)算方法12/12/20223§9.5表達(dá)式的求值方法兩種計(jì)算方法的比較實(shí)體化計(jì)算方法需要產(chǎn)生臨時(shí)關(guān)系、回寫中間結(jié)果，這可能會(huì)影響查詢的執(zhí)行效率。但該方法可以直接利用各個(gè)關(guān)系運(yùn)算的算法實(shí)現(xiàn)(即操作代碼)；而流水線計(jì)算方法雖然具有減少產(chǎn)生臨時(shí)關(guān)系、提高查詢執(zhí)行效率的優(yōu)點(diǎn)，但它需要對(duì)流水線中的每一關(guān)系運(yùn)算建模，以便能夠重用各個(gè)關(guān)系運(yùn)算的操作代碼。12/16/202289§9.5表達(dá)式的求值方法兩種計(jì)算方法的比較12/12/202§9.5表達(dá)式的求值方法流水線計(jì)算方法模型最簡(jiǎn)單的模型就是：每一關(guān)系運(yùn)算都作為系統(tǒng)內(nèi)獨(dú)立的進(jìn)程或線程；獨(dú)立的線程從流水化的輸入中接受元組流，并產(chǎn)生一個(gè)元組流作為其輸出；對(duì)于流水線中的每對(duì)相鄰運(yùn)算，都創(chuàng)建一個(gè)緩沖區(qū)來(lái)保存從一個(gè)運(yùn)算傳送到另一個(gè)運(yùn)算的元組。12/16/202290§9.5表達(dá)式的求值方法流水線計(jì)算方法模型12/12/202§9.5表達(dá)式的求值方法流水線計(jì)算方法的執(zhí)行需求者驅(qū)動(dòng)：“拉”的過(guò)程系統(tǒng)不停