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

1、2022-1-151數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)與原理數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)與原理2022-1-152第第9 9章查詢處理章查詢處理是指從數(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ò)程查詢處理的過(guò)程表達(dá)式的求值方法表達(dá)式的求值方法關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換查詢優(yōu)化的方法查詢優(yōu)化的方法查詢代價(jià)的度量查詢代價(jià)的度量查詢優(yōu)化器的構(gòu)造查詢優(yōu)化器的構(gòu)造實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)本章總結(jié)本章總結(jié)2022-1-153DBMSDBMS總體結(jié)

2、構(gòu)回顧：查詢處理器總體結(jié)構(gòu)回顧：查詢處理器應(yīng)用界面應(yīng)用界面索引索引統(tǒng)計(jì)數(shù)據(jù)統(tǒng)計(jì)數(shù)據(jù)數(shù)據(jù)文件數(shù)據(jù)文件數(shù)據(jù)字典數(shù)據(jù)字典應(yīng)用程序應(yīng)用程序交互查詢交互查詢數(shù)據(jù)庫(kù)模式數(shù)據(jù)庫(kù)模式嵌入式嵌入式DMLDML預(yù)編譯器預(yù)編譯器DMLDML編譯器編譯器DDLDDL解釋器解釋器查詢計(jì)算引擎查詢計(jì)算引擎事務(wù)管理器事務(wù)管理器緩沖區(qū)管理器緩沖區(qū)管理器文件管理器文件管理器日志日志2022-1-1549.19.1查詢處理的過(guò)程查詢處理的過(guò)程查詢處理 是指對(duì)最終用戶提交的查詢進(jìn)行： 解析 優(yōu)化 執(zhí)行 并最終給出查詢結(jié)果的處理過(guò)程。2022-1-1559.19.1查詢處理的過(guò)程查詢處理的過(guò)程查詢優(yōu)化器 問(wèn)題的提出： 一個(gè)查詢用SQ

3、L語(yǔ)言可以有多種表達(dá)方式； 而每個(gè)SQL語(yǔ)句又可以翻譯成多個(gè)等價(jià)的關(guān)系代數(shù)表達(dá)式。例如：select student_number from student where student_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ò)程。2022-1-1569.19.1查詢處理

4、的過(guò)程查詢處理的過(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ǔ)序列。2022-1-157查詢優(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.19.1查詢處理

5、的過(guò)程查詢處理的過(guò)程2022-1-1589.19.1查詢處理的過(guò)程查詢處理的過(guò)程執(zhí)行引擎 輸入是查詢執(zhí)行計(jì)劃 輸出則是具體的查詢結(jié)果還需要將實(shí)現(xiàn)關(guān)系運(yùn)算的算法與底層的文件操作指令結(jié)合起來(lái)！2022-1-1599.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(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_na

6、me(department_name = “計(jì)算機(jī)系”(teacher)teaching) 從感覺(jué)上講，哪個(gè)關(guān)系代數(shù)表達(dá)式的計(jì)算效率更高一些？為什么？2022-1-15109.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式樹(shù) 為了更明顯地看出上述兩個(gè)表達(dá)式的差別，還可以用關(guān)系代數(shù)表達(dá)式樹(shù)來(lái)描述它們：2022-1-15119.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(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)系具有相同的屬性集和相同的元組集，但屬性

7、出現(xiàn)的次序可以不同。等價(jià)規(guī)則 在下面的等價(jià)規(guī)則中，用、1、2等表示謂詞；用L、L1、L2等表示屬性列表；用E、E1、E2等表示關(guān)系代數(shù)表達(dá)式。2022-1-15129.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則合取選擇運(yùn)算可分解為單個(gè)選擇運(yùn)算的序列，該變換稱為的級(jí)聯(lián)：12(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)2022-1-15139.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則選擇可與笛卡兒積以及theta連接相結(jié)合：(E1E

8、2) = E1E21(E12E2) = E112E2 theta連接(包括自然連接)運(yùn)算滿足交換律：E1E2 = E2E1 自然連接運(yùn)算滿足結(jié)合律：(E1E2)E3 = E1(E2E3)theta連接具有以下方式的結(jié)合律：(E11E2)23E3 = E113(E22E3)2只涉及E2與E3的屬性；由于任意一個(gè)條件都可為空，因此笛卡兒積運(yùn)算也滿足結(jié)合率！2022-1-15149.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(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只涉

9、及E2時(shí)：12(E1E2) = (1(E1)(2(E2)投影運(yùn)算對(duì)theta連接運(yùn)算具有分配律：令L1、L2分別是E1、E2的屬性，而連接條件只涉及L1L2中的屬性，則：L1L2(E1E2) = (L1(E1)(L2(E2)2022-1-15159.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則投影運(yùn)算對(duì)theta連接運(yùn)算具有分配律：令L1、L2分別是E1、E2的屬性，L3是E1里出現(xiàn) 在連接條件中但不在L1L2中的屬性，而L4 是E2里出現(xiàn)在連接條件中但不在L1L2中的 屬性，那么：L1L2(E1E2) = L1L2(L1L3(E1)(L2L4(E2)集合運(yùn)算并與交滿足交換律：E1

10、E2 = E2E1；E1E2 = E2E1 但是集合差運(yùn)算不滿足交換律！2022-1-15169.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換等價(jià)規(guī)則集合運(yùn)算并與交滿足結(jié)合律： (E1E2)E3 = E1(E2E3) (E1E2)E3 = E1(E2E3)選擇運(yùn)算對(duì)并、交、差運(yùn)算具有分配律： (E1E2) = (E1)(E2) (E1E2) = (E1)(E2) (E1-E2) = (E1)-(E2)投影運(yùn)算對(duì)并運(yùn)算具有分配率：L(E1E2) = (L(E1)(L(E2)2022-1-15179.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例 假設(shè)student和selec

11、ting是以下關(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) )2022-1-15189.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換表達(dá)式轉(zhuǎn)換舉例 利用前面介紹的規(guī)則，可以得到如下的等價(jià)表達(dá)式： student_name(department_name=“計(jì)算機(jī)系

12、”(student)selecting) 如果將上述查詢修改為： student_name(department_name=“計(jì)算機(jī)系”course_name like ”數(shù)據(jù)庫(kù)%”(studentselecting) ) 那么，如何對(duì)上述表達(dá)式進(jìn)行等價(jià)變換呢？2022-1-15199.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(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ī)系”(stude

13、nt)(course_name like ”數(shù)據(jù)庫(kù)%”(selecting) )2022-1-1520表達(dá)式轉(zhuǎn)換舉例 用關(guān)系代數(shù)表達(dá)式樹(shù)可以更明顯地看出上述兩個(gè)表達(dá)式的差別：9.29.2關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換關(guān)系代數(shù)表達(dá)式的轉(zhuǎn)換2022-1-15219.39.3查詢代價(jià)的度量查詢代價(jià)的度量查詢處理的代價(jià) 查詢處理的代價(jià)可以通過(guò)該查詢對(duì)各種資源的使用情況進(jìn)行衡量。資源包括： 磁盤(pán)存取(磁盤(pán)I/O) 執(zhí)行查詢所用的CPU時(shí)間 并行/分布式數(shù)據(jù)庫(kù)系統(tǒng)中的通信開(kāi)銷 磁盤(pán)訪問(wèn)通常是最主要的代價(jià)，這是因?yàn)椋?磁盤(pán)存取比內(nèi)存操作(CPU)要慢得多； CPU速度的提升要比磁盤(pán)速度的提升快的多。 結(jié)論：磁盤(pán)存取代

14、價(jià)是查詢執(zhí)行計(jì)劃代價(jià)的合理度量。2022-1-15229.39.3查詢代價(jià)的度量查詢代價(jià)的度量代價(jià)模型 為了簡(jiǎn)化磁盤(pán)存取代價(jià)的計(jì)算，需要構(gòu)造一個(gè)簡(jiǎn)單的代價(jià)模型： 存取代價(jià)用從磁盤(pán)向主存?zhèn)魉偷奈锢韷K數(shù)來(lái)度量 假定所有塊傳送的代價(jià)相同。該假定忽略了：尋道時(shí)間(搜索時(shí)間)：將磁頭移動(dòng)到所期望的磁道或柱面的時(shí)間；旋轉(zhuǎn)等待時(shí)間：等待所需要的數(shù)據(jù)(扇區(qū))旋轉(zhuǎn)到讀寫(xiě)頭下的時(shí)間延遲。 忽略了將查詢的最終結(jié)果寫(xiě)回磁盤(pán)的代價(jià)； 實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)是最壞情形下的代價(jià)：即主存中緩沖區(qū)只能容納數(shù)目不多的數(shù)據(jù)塊，需要不斷地訪問(wèn)外存。2022-1-15239.39.3查詢代價(jià)的度量查詢代價(jià)的度量用于估計(jì)代價(jià)的統(tǒng)計(jì)信息

15、查詢優(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。2022-1-15249.39.3查詢代價(jià)的度量查詢代價(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ù)

16、。給定關(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。2022-1-15259.39.3查詢代價(jià)的度量查詢代價(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)系

17、代數(shù)運(yùn)算的算法代價(jià)，并把算法A的代價(jià)估計(jì)記為EA。2022-1-15269.49.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)實(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)這門(mén)課要講的內(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)算的具體算法的磁盤(pán)存取代價(jià)，即在磁盤(pán)和主存儲(chǔ)器之間傳送的數(shù)據(jù)塊數(shù)！2022-1-15279.49.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)選擇運(yùn)算在查詢處理中，實(shí)現(xiàn)選擇運(yùn)算的算法通常是文件掃描。文件

18、掃描是用于定位、檢索滿足選擇條件的記錄的搜索算法： 不用索引的搜索算法：文件掃描線性搜索算法A1二分法搜索算法A2 使用索引的搜索算法：索引文件掃描有主索引的碼屬性上的等值比較算法A3有主索引的非碼屬性上的等值比較算法A4 其他搜索算法2022-1-15289.49.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)實(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找

19、到符合條件的第一個(gè)數(shù)據(jù)塊的代價(jià)滿足選擇條件的記錄數(shù)因?yàn)橛幸粔K已被檢索到2022-1-15299.49.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)實(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à)。2022-1-15309.49.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)實(shí)現(xiàn)關(guān)系運(yùn)算的算

20、法代價(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)連接算法 歸并連接算法 散列連接算法 其他連接算法2022-1-15319.49.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)嵌套循環(huán)連接 以theta連接rs為例：2022-1-15329.49.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)嵌套循環(huán)連接 算法分析： 與文件的線性掃描算法類似，關(guān)系文件的每個(gè)數(shù)據(jù)塊都必須被訪問(wèn)； 不要求有任何索引，任何連接條件都能適應(yīng)； 對(duì)關(guān)系r

21、的每一條記錄都必須對(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)系？2022-1-15339.49.4實(shí)現(xiàn)關(guān)系運(yùn)算的算法代價(jià)實(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à)。索引該建

22、在什么地方？2022-1-15349.59.5表達(dá)式的求值方法表達(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)2022-1-15359.59.5表達(dá)式的求值方法表達(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_n

23、umber”s000003”(student)selecting)2022-1-15369.59.5表達(dá)式的求值方法表達(dá)式的求值方法實(shí)體化計(jì)算方法 實(shí)體化計(jì)算方法的缺點(diǎn)是需要構(gòu)造臨時(shí)關(guān)系，這些臨時(shí)關(guān)系除非很小(可以放在內(nèi)存里)，否則就必須寫(xiě)到磁盤(pán)上(tempdb)； 實(shí)體化計(jì)算方法的代價(jià)不僅僅是表達(dá)式中所涉及的關(guān)系運(yùn)算的代價(jià)總和，還應(yīng)該加上把中間結(jié)果寫(xiě)回磁盤(pán)的代價(jià)； 在估計(jì)單個(gè)關(guān)系運(yùn)算的代價(jià)時(shí)，忽略了將運(yùn)算結(jié)果回寫(xiě)到磁盤(pán)的代價(jià)。但對(duì)由多個(gè)關(guān)系運(yùn)算構(gòu)成的表達(dá)式，就不能簡(jiǎn)單地忽略掉回寫(xiě)磁盤(pán)的代價(jià)！2022-1-15379.59.5表達(dá)式的求值方法表達(dá)式的求值方法流水線計(jì)算方法 將表達(dá)式中的多個(gè)關(guān)系

24、運(yùn)算組合成一個(gè)操作流水線來(lái)實(shí)現(xiàn)，即將一個(gè)運(yùn)算的結(jié)果作為輸入直接傳送到下一個(gè)運(yùn)算。例如：course_name(student_number”s000003”(student)selecting)2022-1-15389.59.5表達(dá)式的求值方法表達(dá)式的求值方法兩種計(jì)算方法的比較 實(shí)體化計(jì)算方法需要產(chǎn)生臨時(shí)關(guān)系、回寫(xiě)中間結(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)算的操作代碼。2022-1-15399.59.5表達(dá)式的求值

25、方法表達(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)算的元組。2022-1-15409.59.5表達(dá)式的求值方法表達(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è)

26、操作不斷地產(chǎn)生元組并將它們放在輸出緩沖區(qū)中，直到緩沖區(qū)滿為止。2022-1-15419.69.6查詢優(yōu)化的方法查詢優(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ù)程序員一般只能考慮有限的幾種可能性。2022-1-15429.69.6查詢優(yōu)化的方法查詢優(yōu)化的方法查詢優(yōu)化的步驟與方式 查詢優(yōu)化

27、器的任務(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á)式并注釋2022-1-15439.69.6查詢優(yōu)化的方法查詢優(yōu)化的方法查詢執(zhí)行計(jì)劃舉例2022-1-1544查詢優(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.69.6查詢優(yōu)化的方法查詢優(yōu)化的方法2022-1-15459.69.6查詢優(yōu)化的方法查詢優(yōu)化的方法基于代價(jià)的優(yōu)化方法 將各種可能的查詢執(zhí)行計(jì)劃全部產(chǎn)生出來(lái)，然后從中估計(jì)出代價(jià)最小的一個(gè)； 這件事情說(shuō)起來(lái)容易做起來(lái)很難，幾乎是不可能的！例如： 考慮r1r2r3的連接順序的組合：12種！2022-1-15469.69.6查詢優(yōu)化的方法查詢優(yōu)化的方法啟發(fā)式優(yōu)化方法 利用啟發(fā)式規(guī)則來(lái)減少基于代價(jià)優(yōu)化的可選方案數(shù)； 這種摸著石