查詢優(yōu)化關(guān)鍵技術(shù)基礎(chǔ)概述目錄TOC\o"1-3"\h\u32328查詢優(yōu)化關(guān)鍵技術(shù)基礎(chǔ)概述 165041.1查詢優(yōu)化概述 1249571.2搜索空間 2146731.3基數(shù)估計(jì) 3277261.4代價(jià)模型 49931.5查詢優(yōu)化模型 51.1查詢優(yōu)化概述在查詢處理中，用戶首先向數(shù)據(jù)庫(kù)管理系統(tǒng)輸入查詢語(yǔ)句。同一個(gè)查詢意圖在查詢語(yǔ)句的表現(xiàn)上可能有所不同，這些不同的查詢語(yǔ)句復(fù)雜度也千差萬(wàn)別。即使是同一個(gè)查詢語(yǔ)句，也存在許多等價(jià)的查詢執(zhí)行計(jì)劃，這些查詢執(zhí)行計(jì)劃指定了了運(yùn)算符執(zhí)行順序、數(shù)據(jù)存取方式、是否使用索引等，這些因素都影響查詢執(zhí)行計(jì)劃的性能。另外，存儲(chǔ)在數(shù)據(jù)庫(kù)中的數(shù)據(jù)量不斷增長(zhǎng)也會(huì)導(dǎo)致有的查詢執(zhí)行計(jì)劃產(chǎn)生巨大的執(zhí)行代價(jià)，甚至無(wú)法執(zhí)行。查詢優(yōu)化是關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)和一些大數(shù)據(jù)處理引擎的核心。給定以聲明性語(yǔ)言（例如SQL）編寫的查詢，優(yōu)化器將找到最有效的查詢執(zhí)行計(jì)劃并將其提供給執(zhí)行器。盡管查詢優(yōu)化技術(shù)經(jīng)過(guò)了數(shù)十年的發(fā)展，面對(duì)復(fù)雜查詢時(shí)，由于搜索空間過(guò)大、基數(shù)估計(jì)誤差、代價(jià)模型不合理等因素，優(yōu)化器給出的結(jié)果有時(shí)還是不盡如人意。1.1.1查詢優(yōu)化的基本概念用戶輸入查詢高級(jí)語(yǔ)言（一般是SQL）后，查詢優(yōu)化器對(duì)查詢語(yǔ)句進(jìn)行語(yǔ)法分析、驗(yàn)證等階段后將高級(jí)查詢語(yǔ)言轉(zhuǎn)換成優(yōu)化器的內(nèi)部表示形式（一般是關(guān)系代數(shù)表達(dá)式）。接著，優(yōu)化器利用轉(zhuǎn)換規(guī)則對(duì)關(guān)系代數(shù)表達(dá)式進(jìn)行變換，最終輸出查詢執(zhí)行計(jì)劃。衡量?jī)?yōu)化器的兩個(gè)重要指標(biāo)是查詢計(jì)劃生成時(shí)間、查詢計(jì)劃執(zhí)行時(shí)間。1.1.2多連接查詢優(yōu)化技術(shù)多連接查詢指的是一些關(guān)系表R1Rn，滿足連接謂詞p1…pm時(shí)，將兩個(gè)關(guān)系表基于它們之間的連接謂詞組合起來(lái)，然后將得到的關(guān)系與其他關(guān)系合并，直到產(chǎn)生包含所有原始關(guān)系表的最終結(jié)果。在查詢處理中，連接操作是一個(gè)昂貴的操作，多連接查詢執(zhí)行計(jì)劃的代價(jià)很大程度上受連接順序的影響。多連接查詢優(yōu)化一個(gè)重要的優(yōu)化任務(wù)就是在很多等價(jià)的連接順序中確定一個(gè)最優(yōu)的，這個(gè)優(yōu)化任務(wù)通常被稱為joinordering問(wèn)題，屬于組合優(yōu)化問(wèn)題。連接順序問(wèn)題的時(shí)間復(fù)雜度是O(n!)，當(dāng)連接數(shù)量增加時(shí)，它將變得很難解決。找到一種快速、準(zhǔn)確地解決多連接查詢連接順序問(wèn)題的算法是非常必要的。1.2搜索空間根據(jù)Ioannidis的說(shuō)法，搜索空間可以被劃分為兩個(gè)部分：邏輯搜索空間和物理搜索空間[13]。邏輯搜索空間是本文考慮的重點(diǎn)。1.2.1邏輯搜索空間 邏輯搜索空間里的查詢計(jì)劃指定了運(yùn)算符的執(zhí)行順序，這些邏輯查詢計(jì)劃通常以樹的形式表示。例如，對(duì)于查詢：SELECT*FROMa,b,c,dWHEREa.ref1=b.ref2ANDb.ref3=c.ref4ANDc.ref5=d.ref6可以用圖2.1表示，這種形式的樹叫做左深樹。樹的葉子節(jié)點(diǎn)表示參與連接的關(guān)系表，中間節(jié)點(diǎn)表示連接運(yùn)算符。這個(gè)查詢同樣也可以被表示成圖2.2的樹，這種樹被稱為濃密樹。多連接查詢的邏輯搜索空間里包含了各種不同連接順序的查詢計(jì)劃。根據(jù)公式1.1，一個(gè)多連接查詢的邏輯搜索空間十分巨大，研究對(duì)應(yīng)的剪枝算法具有重要意義。圖2.1左深樹圖2.2濃密樹1.2.2物理搜索空間物理搜索空間里的查詢計(jì)劃指定了每個(gè)運(yùn)算符的物理執(zhí)行方式。對(duì)于連接運(yùn)算符，它的物理執(zhí)行方式有嵌套循環(huán)連接、歸并連接、哈希連接[14]等。選擇何種物理執(zhí)行方式和很多因素有關(guān)，例如關(guān)系表某一列是否有序、是否存在索引等。1.3基數(shù)估計(jì)基數(shù)估計(jì)用于估計(jì)每個(gè)運(yùn)算符輸出的元組數(shù)量。目前，主要的基數(shù)估計(jì)策略分為三類：基于概要的估計(jì)方法、基于采樣的估計(jì)方法、基于學(xué)習(xí)的估計(jì)方法。在這里僅介紹一些具有代表性的方法。1.3.1直方圖法直方圖有兩種類型：一維直方圖和d維直方圖（d>=2）。一維以上的直方圖可以捕獲不同屬性之間的相關(guān)性。一維直方圖通過(guò)將按照屬性a排序的元組劃分到B(>=1)個(gè)子集（稱為存儲(chǔ)桶）來(lái)構(gòu)造屬性a的一維直方圖，一般數(shù)據(jù)在所有存儲(chǔ)桶內(nèi)成均勻分布。d維直方圖先對(duì)對(duì)元組按照屬性組A排序，再將元組分到不同的存儲(chǔ)桶內(nèi)。1.3.2草圖法草圖法通過(guò)將屬性列建模為一個(gè)向量或矩陣來(lái)計(jì)算這個(gè)屬性的非重復(fù)值數(shù)量或某個(gè)值的頻率。也可以使用草圖法來(lái)估計(jì)連接操作產(chǎn)生的元組數(shù)量，思路是：分別在兩個(gè)關(guān)系表的連接屬性上構(gòu)建草圖（向量或矩陣），然后對(duì)兩個(gè)屬性的草圖做矩陣乘法來(lái)估計(jì)連接后的關(guān)系表大小。該方法僅支持等值連接和單屬性列連接。1.3.3采樣法采樣法進(jìn)行基數(shù)估計(jì)的思路是按照采樣比例收集關(guān)系表元組的樣本，用這些樣本進(jìn)行查詢，得到的元組數(shù)量再乘上采樣比例即可。采樣法的準(zhǔn)確度取決于樣本的數(shù)據(jù)分布和原始數(shù)據(jù)分布的相似度。1.4代價(jià)模型代價(jià)模型是查詢優(yōu)化中重要的部分，代價(jià)模型設(shè)計(jì)的準(zhǔn)確與否對(duì)生成的查詢計(jì)劃的優(yōu)劣有著很大影響。1.4.1查詢代價(jià)組成一個(gè)查詢有多個(gè)查詢執(zhí)行計(jì)劃，優(yōu)化器需要計(jì)算每個(gè)查詢執(zhí)行計(jì)劃的代價(jià)并選擇代價(jià)最小的查詢執(zhí)行計(jì)劃。為了得到查詢執(zhí)行計(jì)劃的代價(jià)，需要建立合理有效的代價(jià)估計(jì)模型。數(shù)據(jù)庫(kù)的查詢代價(jià)可以用許多不同的資源來(lái)衡量，主要包括以下幾種：I/O代價(jià)：I/O代價(jià)指的是訪問(wèn)磁盤的代價(jià)。對(duì)于駐留在磁盤上的大型數(shù)據(jù)庫(kù)，從中存取數(shù)據(jù)的代價(jià)通常高于其他代價(jià)。因此，早期的代價(jià)模型側(cè)重于I/O代價(jià)。但是隨著閃存技術(shù)發(fā)展，當(dāng)今大多數(shù)數(shù)據(jù)都可以經(jīng)濟(jì)高效地存儲(chǔ)在固態(tài)硬盤（SSD）上。此外，主存儲(chǔ)器的大小也顯著增長(zhǎng)，近些年有些數(shù)據(jù)已經(jīng)可以存儲(chǔ)在主存中進(jìn)行查詢。CPU代價(jià)：CPU代價(jià)指的是執(zhí)行查詢所需要的CPU時(shí)間。由于數(shù)據(jù)駐留在內(nèi)存或SSD上，I/O代價(jià)可以很小甚至忽略不計(jì)，但是每個(gè)查詢都需要CPU時(shí)間，不能忽略不計(jì)。CPU代價(jià)有些簡(jiǎn)單的估計(jì)方法，例如用每個(gè)元組的CPU代價(jià)乘以處理的元組數(shù)或者用每個(gè)運(yùn)算符的CPU代價(jià)乘以執(zhí)行的運(yùn)算符數(shù)量。數(shù)據(jù)庫(kù)存儲(chǔ)了每個(gè)元組、運(yùn)算符的CPU代價(jià)默認(rèn)值，這些值通常作為配置參數(shù)。通信代價(jià)：在并行數(shù)據(jù)庫(kù)系統(tǒng)和分布式數(shù)據(jù)庫(kù)系統(tǒng)中，不同節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)，會(huì)產(chǎn)生通信開銷。本文不涉及并行和分布式數(shù)據(jù)庫(kù)系統(tǒng)，因此不在此過(guò)多贅述。1.4.2選擇度估計(jì)選擇度指的是一個(gè)運(yùn)算符輸出的元組數(shù)量比上輸入的元組數(shù)量，選擇率在代價(jià)估計(jì)模型中占有重要地位，其精確程度直接影響最優(yōu)計(jì)劃的選取。選擇度常用計(jì)算方法如下：無(wú)參數(shù)法：使用Adhoc數(shù)據(jù)結(jié)構(gòu)或直方圖維護(hù)屬性值分布，無(wú)參數(shù)法中最典型的是直方圖法。參數(shù)法：使用一些預(yù)先估計(jì)出來(lái)的自由統(tǒng)計(jì)參數(shù)的數(shù)學(xué)分布函數(shù)來(lái)逼近真實(shí)分布。采樣法：對(duì)參與查詢的關(guān)系表進(jìn)行隨機(jī)采樣，將采樣得到這些元組作為子表進(jìn)行查詢，利用子表的查詢計(jì)劃計(jì)算選擇度。用采樣計(jì)算的選擇度來(lái)估計(jì)整體數(shù)據(jù)的選擇度。綜合法：將以上幾種方法結(jié)合起來(lái)。1.5查詢優(yōu)化模型當(dāng)前，查詢優(yōu)化模型主要分為兩種：基于代價(jià)的優(yōu)化（CBO）和基于規(guī)則的優(yōu)化。1.5.1基于代價(jià)的優(yōu)化基于代價(jià)的優(yōu)化器會(huì)根據(jù)優(yōu)化規(guī)則對(duì)關(guān)系代數(shù)表達(dá)式進(jìn)行轉(zhuǎn)換，原有的關(guān)系代數(shù)表達(dá)式也不會(huì)被替換掉，經(jīng)過(guò)一系列轉(zhuǎn)換后優(yōu)化器中會(huì)存在多個(gè)查詢執(zhí)行計(jì)劃，然后優(yōu)化器根據(jù)代價(jià)模型和統(tǒng)計(jì)信息計(jì)算每個(gè)查詢執(zhí)行計(jì)劃的代價(jià)，從中選擇代價(jià)最小的執(zhí)行計(jì)劃?；诖鷥r(jià)的優(yōu)化器枚舉所有等價(jià)的關(guān)系代數(shù)表達(dá)式的算法并不復(fù)雜。優(yōu)化器有一個(gè)等價(jià)查詢執(zhí)行計(jì)劃的集合EQ，初始里面只有一個(gè)查詢執(zhí)行計(jì)劃E。如果EQ中的某一個(gè)關(guān)系代數(shù)表達(dá)式匹配等價(jià)轉(zhuǎn)換規(guī)則的觸發(fā)結(jié)構(gòu)，優(yōu)化器根據(jù)轉(zhuǎn)換規(guī)則將該關(guān)系代數(shù)表達(dá)式變換，生成的新的查詢執(zhí)行計(jì)劃加入EQ中。此過(guò)程將一直執(zhí)行直到?jīng)]有新的查詢執(zhí)行計(jì)劃生成。這個(gè)過(guò)程具有高昂的時(shí)間復(fù)雜度和空間復(fù)雜度，但是在實(shí)際情況中有時(shí)并不需要枚舉所有的查詢計(jì)劃，例如對(duì)于查詢r(jià)1?r2?r3?r4?r5，表示r1，r2，r3先進(jìn)行連接，連接的結(jié)果再和r4，r5進(jìn)行連接。r1?r2?r3一共有實(shí)際過(guò)程更為復(fù)雜，目前所有的基于代價(jià)的優(yōu)化器都基于SystemR[15]和Volcano[16]。1.5.2基于規(guī)則的優(yōu)化基于規(guī)則的優(yōu)化器根據(jù)優(yōu)化規(guī)則對(duì)關(guān)系表達(dá)式進(jìn)行轉(zhuǎn)換，原有的表達(dá)式不會(huì)保留，經(jīng)過(guò)一系列轉(zhuǎn)換后生成最終的查詢執(zhí)行計(jì)劃?；谝?guī)則的優(yōu)化器使用一些啟發(fā)式規(guī)則，例如：優(yōu)先執(zhí)行投影操作。投影操作可以減少中間結(jié)果的列數(shù)，減少數(shù)據(jù)量從