并行查詢下查詢執(zhí)行計(jì)劃的選擇

裴澤鋒，牛保寧，張錦文，Amjad Muhammad

（太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院，太原030024）

0 引言

查詢是數(shù)據(jù)庫(kù)系統(tǒng)的主要工作負(fù)載，查詢效率的高低決定數(shù)據(jù)庫(kù)運(yùn)行性能的好壞。在數(shù)據(jù)庫(kù)系統(tǒng)中，一個(gè)查詢?cè)谡嬲龍?zhí)行前，查詢優(yōu)化器會(huì)生成多種查詢執(zhí)行計(jì)劃（即查詢?cè)跀?shù)據(jù)庫(kù)中的執(zhí)行方案）。盡管這些計(jì)劃最終生成完全相同的結(jié)果集，但它們的執(zhí)行效率卻存在很大差異［1］。尋找較優(yōu)的查詢執(zhí)行計(jì)劃可以以較小的代價(jià)、在很大程度上縮短查詢的響應(yīng)時(shí)間，提高查詢效率，進(jìn)而提高數(shù)據(jù)庫(kù)系統(tǒng)的性能。

目前，主流的數(shù)據(jù)庫(kù)管理系統(tǒng)大都是通過(guò)查詢優(yōu)化器為查詢選擇較優(yōu)執(zhí)行計(jì)劃，即查詢的多種執(zhí)行計(jì)劃中，使查詢響應(yīng)時(shí)間較少的執(zhí)行計(jì)劃［1-3］。雖然不同數(shù)據(jù)庫(kù)查詢優(yōu)化器實(shí)現(xiàn)有所差別，但它們都是依據(jù)執(zhí)行代價(jià)——成本預(yù)算［4］，為查詢選擇執(zhí)行代價(jià)較小的執(zhí)行計(jì)劃作為該查詢的較優(yōu)執(zhí)行計(jì)劃。PostgreSQL 作為目前成功的開源數(shù)據(jù)庫(kù)之一，它的優(yōu)化算法效率高于其他數(shù)據(jù)庫(kù)［1］，本文以PostgreSQL 為對(duì)象，研究并行查詢下查詢執(zhí)行計(jì)劃的選擇。查詢執(zhí)行前，客戶端發(fā)出查詢請(qǐng)求，解析器接收此請(qǐng)求并生成查詢樹，查詢優(yōu)化器中的規(guī)劃器接收查詢樹并生成可能的查詢執(zhí)行計(jì)劃，優(yōu)化器依據(jù)動(dòng)態(tài)規(guī)劃或基因算法等計(jì)算每個(gè)執(zhí)行計(jì)劃的執(zhí)行代價(jià)，從中選出執(zhí)行代價(jià)較小的一個(gè)執(zhí)行計(jì)劃作為較優(yōu)執(zhí)行計(jì)劃，并據(jù)此制定一個(gè)完整的規(guī)劃樹傳遞給執(zhí)行器去執(zhí)行［1，5］。

在數(shù)據(jù)庫(kù)管理系統(tǒng)中，查詢優(yōu)化器在為查詢生成不同的執(zhí)行路徑時(shí)，會(huì)綜合考慮數(shù)據(jù)表的掃描方式、表間連接方式及連接順序，在選擇較優(yōu)執(zhí)行路徑時(shí)，會(huì)依據(jù)查詢的復(fù)雜程度選用不同的算法。因此，當(dāng)數(shù)據(jù)庫(kù)中只有一個(gè)查詢運(yùn)行時(shí)，如果查詢不太復(fù)雜，查詢優(yōu)化器可以做到避免選擇最差執(zhí)行計(jì)劃，且在為此類查詢選擇較優(yōu)查詢計(jì)劃上可保持一定的準(zhǔn)確率。

隨著數(shù)據(jù)量的急劇增長(zhǎng)、用戶需求的不斷變化，查詢語(yǔ)句越發(fā)復(fù)雜。由于查詢優(yōu)化器優(yōu)化算法本身的局限性，它只能依據(jù)數(shù)據(jù)庫(kù)配置參數(shù)靜態(tài)地為查詢選擇一個(gè)較優(yōu)的執(zhí)行計(jì)劃，如果查詢語(yǔ)句過(guò)于復(fù)雜，在統(tǒng)計(jì)信息不準(zhǔn)確的情況下，成本估算的誤差會(huì)成倍放大［6］，因此會(huì)造成所選擇的較優(yōu)執(zhí)行計(jì)劃存在較大偏差。

特別地，在實(shí)際的數(shù)據(jù)庫(kù)系統(tǒng)中，單一查詢運(yùn)行的情況比較罕見，大部分情況是不同查詢?cè)谝黄鸩⑿?，因此，一個(gè)查詢的運(yùn)行會(huì)受到其他查詢的影響，我們將其稱為查詢交互［7］。由于查詢交互現(xiàn)象的存在，相比其單獨(dú)運(yùn)行，查詢的響應(yīng)時(shí)間會(huì)有顯著變化，大部分查詢的響應(yīng)時(shí)間會(huì)變長(zhǎng)。而且，查詢并行數(shù)（MPL）越大，這種變化越發(fā)明顯。

但是，目前的查詢優(yōu)化器并沒有特別地考慮查詢交互這一關(guān)鍵因素的存在，僅通過(guò)數(shù)據(jù)庫(kù)參數(shù)配置很難準(zhǔn)確反映查詢交互。如果數(shù)據(jù)庫(kù)配置參數(shù)固定，查詢一旦確定，查詢的較優(yōu)執(zhí)行計(jì)劃隨之確定。我們認(rèn)為，在不同的查詢組合（兩個(gè)及兩個(gè)以上查詢并行運(yùn)行時(shí)的查詢集合）下，查詢的較優(yōu)執(zhí)行計(jì)劃可能也不同。假設(shè)當(dāng)查詢Q 單獨(dú)運(yùn)行時(shí)，查詢優(yōu)化器為該查詢選擇的較優(yōu)查詢計(jì)劃為A。測(cè)試實(shí)驗(yàn)證明，多數(shù)情況下，當(dāng)查詢Q 與其他查詢并行執(zhí)行時(shí)，較優(yōu)的執(zhí)行計(jì)劃不是A，如果按執(zhí)行計(jì)劃A 執(zhí)行查詢Q，會(huì)大幅度延長(zhǎng)其執(zhí)行時(shí)間，并嚴(yán)重影響其他查詢的執(zhí)行。因此，當(dāng)多個(gè)不同查詢并行時(shí)，目前的查詢優(yōu)化器并不能為查詢選擇當(dāng)前查詢組合下的較優(yōu)執(zhí)行計(jì)劃。

為此，本文提出一種度量查詢受查詢交互影響程度大小的標(biāo)準(zhǔn)QIs（Query Interactions），為選擇查詢執(zhí)行計(jì)劃時(shí)定量考慮查詢交互因素打下基礎(chǔ)。針對(duì)并行查詢下較優(yōu)執(zhí)行計(jì)劃的選擇，本文提出一種為查詢動(dòng)態(tài)選擇當(dāng)前查詢組合下較優(yōu)執(zhí)行計(jì)劃的方法TRating（Time Rating），該方法通過(guò)比較按照不同執(zhí)行計(jì)劃執(zhí)行的查詢?cè)诓樵兘M合中受查詢交互影響程度的大小，選擇受查詢交互影響較小的查詢所對(duì)應(yīng)的執(zhí)行計(jì)劃作為該查詢的較優(yōu)執(zhí)行計(jì)劃。

1 相關(guān)工作

目前，數(shù)據(jù)庫(kù)管理系統(tǒng)通過(guò)查詢優(yōu)化器為查詢選擇較優(yōu)執(zhí)行計(jì)劃。對(duì)于一個(gè)特定的查詢，在查詢執(zhí)行前，查詢優(yōu)化器中的規(guī)劃器負(fù)責(zé)為查詢生成所有可能的執(zhí)行計(jì)劃，優(yōu)化器依據(jù)成本預(yù)算從中選擇執(zhí)行代價(jià)最小的計(jì)劃。針對(duì)復(fù)雜度不同的查詢，查詢優(yōu)化器采用不同的算法進(jìn)行處理。對(duì)于比較簡(jiǎn)單的查詢，優(yōu)化器采用動(dòng)態(tài)規(guī)劃算法，該算法搜索范圍小且效率高；對(duì)于比較復(fù)雜的算法，則采用基因算法。基因算法是一種自適應(yīng)的算法，可以在較短的時(shí)間內(nèi)給出一個(gè)較優(yōu)的解［1］。因此，對(duì)于數(shù)據(jù)庫(kù)中單一運(yùn)行的查詢，查詢優(yōu)化器在為不太復(fù)雜的查詢選擇一個(gè)不壞的執(zhí)行計(jì)劃時(shí)可保持一定的準(zhǔn)確率。但是，如果查詢語(yǔ)句過(guò)于復(fù)雜，由于查詢優(yōu)化器成本估算算法的局限性，在統(tǒng)計(jì)信息估計(jì)不準(zhǔn)確時(shí)，成本估算的誤差會(huì)成倍放大，無(wú)法為查詢選擇較優(yōu)的執(zhí)行計(jì)劃［7］。

特別地，在實(shí)際的數(shù)據(jù)庫(kù)系統(tǒng)中，單一查詢運(yùn)行的情況比較少見，多數(shù)情況下是不同查詢?cè)谝黄鸩⑿校⑿胁樵冮g存在查詢交互，這種交互會(huì)導(dǎo)致某一查詢的運(yùn)行受到其他查詢的影響［8］。由于查詢優(yōu)化器通過(guò)數(shù)據(jù)庫(kù)配置參數(shù)靜態(tài)地為查詢選擇查詢執(zhí)行計(jì)劃，這種選擇較優(yōu)執(zhí)行計(jì)劃的方式盡管一定程度上反映了查詢交互［9］，但是其并沒有特別地考慮查詢交互這一關(guān)鍵因素的存在，無(wú)法準(zhǔn)確地反映這種查詢交互現(xiàn)象。在并行查詢情景下，一個(gè)不壞的執(zhí)行計(jì)劃在另一查詢組合中可能會(huì)變得不好，甚至更差［9］。在這種情況下，如果仍用原有執(zhí)行計(jì)劃去執(zhí)行該查詢，會(huì)嚴(yán)重影響該查詢和其他查詢的性能。因此，通過(guò)查詢優(yōu)化器已無(wú)法為查詢準(zhǔn)確地選擇當(dāng)前查詢組合下較優(yōu)的執(zhí)行計(jì)劃［10-11］。

目前，有關(guān)考慮查詢交互的并行查詢下較優(yōu)執(zhí)行計(jì)劃的選擇還沒有專門的研究，大部分研究都是通過(guò)度量查詢交互進(jìn)而預(yù)測(cè)并行查詢下查詢的開銷及響應(yīng)時(shí)間［12-13］，進(jìn)而為查詢調(diào)度提供一定的依據(jù)。目前對(duì)響應(yīng)時(shí)間的預(yù)測(cè)方法主要集中于建立分析模型和統(tǒng)計(jì)模型。分析模型指把查詢計(jì)劃分段，估計(jì)每一段的工作量、系統(tǒng)的執(zhí)行速率，然后求得該段的執(zhí)行時(shí)間，最后把所有分段的執(zhí)行時(shí)間加起來(lái)即可。統(tǒng)計(jì)模型指事先選取并運(yùn)行一定量的樣本，依據(jù)樣本運(yùn)行結(jié)果，給定輸入和輸出，根據(jù)訓(xùn)練集利用統(tǒng)計(jì)的方法訓(xùn)練模型，然后通過(guò)測(cè)試集來(lái)評(píng)判模型的性能，最后依據(jù)模型給出預(yù)測(cè)結(jié)果。利用統(tǒng)計(jì)模型預(yù)測(cè)并行查詢的響應(yīng)時(shí)間性能要優(yōu)于分析模型。但是無(wú)論是分析模型還是統(tǒng)計(jì)模型，預(yù)測(cè)響應(yīng)時(shí)間只能用于合理地調(diào)度一批查詢的執(zhí)行順序。如果數(shù)據(jù)庫(kù)中到達(dá)一批查詢，按照先到先服務(wù)原則，先到查詢需要首先被處理。在這種情況下，如果可以為該查詢選擇當(dāng)前組合下較優(yōu)的執(zhí)行計(jì)劃，這對(duì)提高查詢效率，進(jìn)而提高數(shù)據(jù)庫(kù)運(yùn)行性能尤為重要。

在多查詢并行時(shí)，查詢交互這一關(guān)鍵因素會(huì)影響查詢的響應(yīng)時(shí)間，進(jìn)而影響查詢效率。Duggan 等［14］利用BAL（Buffer Access Latency）即查詢平均頁(yè)讀取時(shí)間來(lái)度量查詢交互。查詢Q單獨(dú)運(yùn)行時(shí)的BAL值等于該查詢讀取頁(yè)花費(fèi)的總時(shí)間除以此查詢讀取頁(yè)的總數(shù)。多查詢并行時(shí)，一個(gè)查詢的BAL 值越大，則表示其受其他查詢的影響程度越大，但這種度量只適用于中等大小查詢。之后，張錦文等［15-16］提出QueryRating 來(lái)度量?jī)蓚€(gè)查詢并行時(shí)查詢交互的大小，由于其直接采用查詢響應(yīng)時(shí)間的比值大小來(lái)衡量查詢交互的大小，宏觀直接且使用范圍廣；但QueryRating 只適用于度量?jī)蓚€(gè)查詢并行時(shí)，其中一個(gè)查詢受另一個(gè)查詢影響程度的大小。

基于以上查詢交互度量使用范圍的限制、查詢優(yōu)化器為查詢選擇當(dāng)前查詢組合下較優(yōu)執(zhí)行計(jì)劃存在較大偏差的問(wèn)題，本文提出了一種度量查詢?cè)诙嗖樵?MPL ＞2)并行下受查詢交互影響程度大小的標(biāo)準(zhǔn)QIs，并基于查詢交互提出了一種動(dòng)態(tài)地為查詢選擇當(dāng)前查詢組合下較優(yōu)執(zhí)行計(jì)劃的方法TRating。當(dāng)用戶提交的查詢到達(dá)時(shí)，依據(jù)先到先服務(wù)原則，為先到查詢選擇當(dāng)前查詢組合下的較優(yōu)執(zhí)行計(jì)劃提供了依據(jù)，具有一定的實(shí)際意義。

2 并行查詢下較優(yōu)執(zhí)行計(jì)劃的選擇

2.1 QIs度量標(biāo)準(zhǔn)

Zhang 等［15］提出的QueryRating 的表達(dá)式如式（1），它直接計(jì)算響應(yīng)時(shí)間的比值，建模復(fù)雜度低且準(zhǔn)確率高。

QueryRating 可以度量?jī)蓛刹樵儾⑿袝r(shí)由于查詢交互某一查詢受到另一查詢影響程度的大小。那么，如果多查詢并行(MPL ＞2)時(shí)，由于查詢交互，某一查詢會(huì)受到其余任何一個(gè)查詢的影響，如何度量多查詢并行時(shí)特定查詢所受查詢交互影響程度的大小是為該查詢選擇當(dāng)前查詢組合下較優(yōu)執(zhí)行計(jì)劃的基礎(chǔ)。受Duggan 等［14］提出的B2L&BAL 模型預(yù)測(cè)查詢性能的啟發(fā)，本文通過(guò)考慮其他剩余每個(gè)查詢對(duì)要研究查詢的查詢交互大小，提出了一種度量多查詢并行時(shí)查詢所受查詢交互影響程度大小的標(biāo)準(zhǔn)QIs，表達(dá)式如下：

其中：

式（2）中：QIsqi表示多查詢并行時(shí)，查詢qi受其他剩余查詢查詢交互影響的大?。籺qi表示查詢qi單獨(dú)運(yùn)行時(shí)的響應(yīng)時(shí)間；Durqi（Duration）可以看作查詢qi所受其他查詢查詢交互影響的持續(xù)時(shí)長(zhǎng)。

本文對(duì)式（2）、（3）作如下解釋：多查詢并行時(shí)，由于查詢交互，對(duì)于某個(gè)查詢，其余查詢都會(huì)阻礙或促進(jìn)該查詢的執(zhí)行。在考慮該查詢受查詢交互影響大小時(shí)，要分別考慮其余每個(gè)查詢對(duì)該查詢的影響即，因此，本文將不同的進(jìn)行求和表示其余查詢對(duì)該查詢的影響大小。特別地，本文認(rèn)為，該查詢單獨(dú)運(yùn)行時(shí)間的長(zhǎng)短會(huì)影響其受查詢交互影響程度的持續(xù)時(shí)長(zhǎng)，該查詢單獨(dú)運(yùn)行時(shí)響應(yīng)時(shí)間越長(zhǎng)，則當(dāng)其加入查詢組合后，它受查詢交互影響的持續(xù)時(shí)長(zhǎng)也越長(zhǎng)。因此，本文通過(guò)Durqi表示查詢qi所受其他查詢查詢交互影響的持續(xù)時(shí)長(zhǎng)。Durqi越大，表示其響應(yīng)時(shí)間所占比例越大，則當(dāng)該查詢加入查詢組合時(shí)，它所受其他查詢查詢交互影響的持續(xù)時(shí)長(zhǎng)也越大。

由式（2）、（3）可以看出，QIsqi值越大，表示多查詢并行時(shí)，由于查詢交互，查詢qi受其他查詢的影響程度越大。

2.2 TRating方法的具體實(shí)現(xiàn)

在實(shí)際的數(shù)據(jù)庫(kù)系統(tǒng)運(yùn)行中，對(duì)于用戶提交的查詢，依據(jù)先到先服務(wù)原則，按照用戶提交查詢的先后順序執(zhí)行查詢。那么，當(dāng)某個(gè)查詢到來(lái)時(shí)，為查詢選擇當(dāng)前查詢組合下較優(yōu)的執(zhí)行計(jì)劃對(duì)提高查詢效率十分必要。當(dāng)按照特定執(zhí)行計(jì)劃執(zhí)行的某查詢?cè)诩尤氩樵兘M合時(shí)，相比其他執(zhí)行計(jì)劃，按特定執(zhí)行計(jì)劃執(zhí)行的某查詢單獨(dú)運(yùn)行時(shí)的響應(yīng)時(shí)間較短，且它所受查詢交互影響程度越小，則其在查詢組合中的響應(yīng)時(shí)間越短。也就是說(shuō)，按特定執(zhí)行計(jì)劃執(zhí)行的某查詢單獨(dú)運(yùn)行時(shí)的響應(yīng)時(shí)間的長(zhǎng)短和該查詢所受查詢交互影響程度的大小均會(huì)影響該查詢?cè)诓樵兘M合中最終的響應(yīng)時(shí)間。響應(yīng)時(shí)間越短的查詢對(duì)應(yīng)的執(zhí)行計(jì)劃即為該查詢?cè)诋?dāng)前查詢組合中較優(yōu)的執(zhí)行計(jì)劃。

為能準(zhǔn)確地描述該方法，本文定義該方法中用到的符號(hào)見表1。

表1 相關(guān)符號(hào)定義Tab.1 Definition of related symbols

相比其他執(zhí)行計(jì)劃，如果按特定執(zhí)行計(jì)劃執(zhí)行的某查詢單獨(dú)運(yùn)行時(shí)的響應(yīng)時(shí)間較長(zhǎng)，即使該查詢?cè)诓樵兘M合中受其余查詢的查詢交互影響較小，它最終的響應(yīng)時(shí)間也可能較長(zhǎng)；同樣地，如果按另一執(zhí)行計(jì)劃執(zhí)行的該查詢單獨(dú)運(yùn)行時(shí)的響應(yīng)時(shí)間較短，即使該查詢?cè)诓樵兘M合中受其余查詢的查詢交互影響較大，它最終的響應(yīng)時(shí)間也可能較短。考慮到這種現(xiàn)象的存在，將Facqw_k值作為每個(gè)查詢計(jì)劃的基準(zhǔn)值。建立的表達(dá)式如下：

其中，F(xiàn)acqw_k表示按qw_k執(zhí)行計(jì)劃執(zhí)行的查詢單獨(dú)運(yùn)行時(shí)的響應(yīng)時(shí)間所占該查詢所有執(zhí)行計(jì)劃單獨(dú)運(yùn)行時(shí)響應(yīng)時(shí)間之和的比值，以此作為每個(gè)查詢執(zhí)行計(jì)劃的基準(zhǔn)值。

該方法具體流程如下：

1）構(gòu)建兩張索引表IT1、IT2和兩張數(shù)據(jù)表T1、T2，并將索引表IT1和數(shù)據(jù)表T1關(guān)聯(lián)，索引表IT2和數(shù)據(jù)表T2關(guān)聯(lián)。

索引表IT1存儲(chǔ)A 中查詢的查詢編號(hào)i、每個(gè)查詢對(duì)應(yīng)的所有執(zhí)行計(jì)劃編號(hào)j，并將其分別設(shè)置為一級(jí)索引和二級(jí)索引。表結(jié)構(gòu)見表2。

表2 索引表IT1Tab.2 Index table IT1

索引表IT2存儲(chǔ)C 中查詢組合編號(hào)f、每個(gè)查詢組合中查詢qi和查詢qn所對(duì)應(yīng)的QueryRating 值和的編號(hào)和，并將查詢組合編號(hào)設(shè)置為一級(jí)索引。表結(jié)構(gòu)見表3。

表3 索引表IT2Tab.3 Index table IT2

數(shù)據(jù)表T1、T2分別對(duì)應(yīng)索引表IT1、IT2中數(shù)據(jù)實(shí)際值，另數(shù)據(jù)表T1需要存儲(chǔ)每個(gè)qi_j單獨(dú)運(yùn)行時(shí)的響應(yīng)時(shí)間。

由索引表IT1、數(shù)據(jù)表T1獲取按特定執(zhí)行計(jì)劃執(zhí)行的查詢單獨(dú)運(yùn)行時(shí)的響應(yīng)時(shí)間，由索引表IT2、數(shù)據(jù)表T2獲取該查詢所受其他查詢的QueryRating。

2）給定MPL=w，當(dāng)某查詢qw到達(dá)數(shù)據(jù)庫(kù)時(shí)，該查詢與目前正在執(zhí)行的(w-1)個(gè)查詢構(gòu)成一個(gè)查詢組合。

由索引IT1表、數(shù)據(jù)表T1得到該查詢的所有執(zhí)行計(jì)劃qw_k及其對(duì)應(yīng)單獨(dú)運(yùn)行時(shí)的響應(yīng)時(shí)間tqw_j，計(jì)算出Facqw_k值。

3）比較所有執(zhí)行計(jì)劃對(duì)應(yīng)的TRatingqw_k，較小的TRatingqw_k值所對(duì)應(yīng)的執(zhí)行計(jì)劃即為該查詢?cè)诋?dāng)前查詢組合下較優(yōu)的查詢執(zhí)行計(jì)劃。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境與設(shè)計(jì)

本實(shí)驗(yàn)選用的測(cè)試基準(zhǔn)為TPC-H［17］，查詢模板為2，3，4，8，10，12，14，22。這些模板涵蓋了分組、排序、聚集、連接、子查詢等多表查詢操作，其默認(rèn)執(zhí)行計(jì)劃包含了各種基本表的掃描方式、表間連接方式及連接順序。本實(shí)驗(yàn)分別給每個(gè)查詢指定三個(gè)不同的執(zhí)行計(jì)劃，把按不同執(zhí)行計(jì)劃執(zhí)行的同一查詢看作不同查詢。實(shí)驗(yàn)環(huán)境配置如表4。

表4 實(shí)驗(yàn)環(huán)境配置Tab.4 Experimental environment configuration

為查詢選擇當(dāng)前查詢組合下較優(yōu)的執(zhí)行計(jì)劃，必須首先獲取查詢的多個(gè)執(zhí)行計(jì)劃。本文首先獲取查詢的多個(gè)執(zhí)行計(jì)劃，緊接著通過(guò)實(shí)驗(yàn)驗(yàn)證同一查詢?cè)诓煌樵兘M合下所選擇的較優(yōu)執(zhí)行計(jì)劃不同這一現(xiàn)象的大量存在。最后，給定MPL，依據(jù)先到先服務(wù)原則，根據(jù)實(shí)際用戶提交查詢的先后，對(duì)比當(dāng)前查詢優(yōu)化器，通過(guò)實(shí)驗(yàn)驗(yàn)證本文所提出的為查詢選擇當(dāng)前查詢組合下較優(yōu)執(zhí)行計(jì)劃方法的準(zhǔn)確性。

3.2 執(zhí)行計(jì)劃生成及其響應(yīng)時(shí)間

由于執(zhí)行計(jì)劃的生成會(huì)綜合考慮基本表的訪問(wèn)順序、表間的連接方式和連接順序，因此本文在生成查詢執(zhí)行計(jì)劃時(shí)，對(duì)于單表查詢著重考慮基本表的訪問(wèn)順序，對(duì)于多表查詢，著重考慮表間連接方式和連接順序，以此生成代表性執(zhí)行計(jì)劃。

使用explain 命令，PostgreSQL 查詢優(yōu)化器直接生成查詢默認(rèn)的執(zhí)行計(jì)劃。依據(jù)上述原則，通過(guò)關(guān)閉或打開執(zhí)行計(jì)劃開關(guān)，使得優(yōu)化器允許或禁止使用一些掃描或連接方法，進(jìn)而生成一定數(shù)量的執(zhí)行計(jì)劃，且其執(zhí)行的查詢響應(yīng)時(shí)間少于或多于默認(rèn)執(zhí)行計(jì)劃響應(yīng)時(shí)間，且相差不宜過(guò)大。最后通過(guò)pg_hint_plan 插件綁定查詢計(jì)劃，使查詢按指定的執(zhí)行計(jì)劃去執(zhí)行。下面通過(guò)圖1、圖2說(shuō)明。

圖1 默認(rèn)執(zhí)行計(jì)劃Fig.1 Default execution plan

圖2 關(guān)閉MergeJoin后的執(zhí)行計(jì)劃Fig.2 Excution plan after closing MergeJoin

實(shí)驗(yàn)中，服務(wù)器只開啟PostgreSQL 數(shù)據(jù)庫(kù)進(jìn)程，分別單獨(dú)運(yùn)行每個(gè)查詢、并行執(zhí)行每?jī)蓚€(gè)查詢組成的查詢組合，利用PostgreSQL 的pg_stat_statement 模塊獲取查詢的響應(yīng)時(shí)間，通過(guò)多次運(yùn)行求平均值的方法減少其他因素干擾，準(zhǔn)確獲取響應(yīng)時(shí)間，從而求得響應(yīng)時(shí)間的比值。

3.3 查詢組合不同時(shí)的較優(yōu)執(zhí)行計(jì)劃驗(yàn)證

本文分別對(duì)并行度MPL=2，4，6，8 時(shí)的同一查詢加入不同查詢組合所選擇的較優(yōu)執(zhí)行計(jì)劃進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，同一查詢?cè)诓煌樵兘M合下所選擇的較優(yōu)查詢計(jì)劃不同，而且這種現(xiàn)象普遍存在，平均約占71%。由于篇幅受限，圖3僅對(duì)部分樣例實(shí)驗(yàn)結(jié)果進(jìn)行展示，并加以說(shuō)明。

圖3 關(guān)閉nestloop后MPL=4時(shí)，同一查詢加入不同的查詢組合時(shí)的較優(yōu)執(zhí)行計(jì)劃抽樣Fig.3 Sampling of better execution plan of one query adding to different query combinations with nestloop closed and MPL=4

圖3 中：每組由兩個(gè)柱狀圖構(gòu)成，它們分別表示同一查詢加入不同的查詢組合中構(gòu)成新的查詢組合，每個(gè)柱狀圖分成三段，每一段表示按不同的執(zhí)行計(jì)劃執(zhí)行的此查詢加入查詢組合，自底向上分別表示執(zhí)行計(jì)劃1、2、3，執(zhí)行計(jì)劃1 為PostgreSQL 查詢優(yōu)化器給出的執(zhí)行計(jì)劃，每段長(zhǎng)度分別對(duì)應(yīng)按特定執(zhí)行計(jì)劃執(zhí)行的此查詢加入查詢組合后的響應(yīng)時(shí)間的長(zhǎng)短。

由圖3 可知，多數(shù)情況下，每組的兩個(gè)柱狀圖的三段長(zhǎng)度均不相同，這說(shuō)明當(dāng)同一查詢加入不同的查詢組合時(shí)，所選擇的較優(yōu)執(zhí)行計(jì)劃并不相同。比如，當(dāng)查詢加入a1、a2 查詢組合時(shí)，對(duì)應(yīng)與a1 構(gòu)成新的查詢組合，該查詢的較優(yōu)執(zhí)行計(jì)劃為PostgreSQL 查詢優(yōu)化器給出的執(zhí)行計(jì)劃即執(zhí)行計(jì)劃1；但對(duì)應(yīng)與a2 構(gòu)成的新的查詢組合，該查詢的較優(yōu)執(zhí)行計(jì)劃為執(zhí)行計(jì)劃2，不同于執(zhí)行計(jì)劃1。

本文對(duì)此種現(xiàn)象作如下解釋：對(duì)于單一運(yùn)行的查詢，由于查詢優(yōu)化器搜索算法的限制，目前其僅能做到避免選擇最差執(zhí)行計(jì)劃，當(dāng)查詢比較復(fù)雜時(shí)，為查詢選擇較優(yōu)執(zhí)行計(jì)劃會(huì)存在較大偏差；對(duì)于并行運(yùn)行的查詢，優(yōu)化器并沒有特別地考慮查詢交互這一主要因素，因?yàn)椴樵冊(cè)诓煌樵兘M合下選擇較優(yōu)執(zhí)行計(jì)劃的偏差更大，因此，此種現(xiàn)象的大量存在十分正常。

3.4 TRating和查詢優(yōu)化器對(duì)比

模擬用戶提交查詢的實(shí)際場(chǎng)景，依據(jù)先到先服務(wù)原則，分別在MPL=2，4，6，8 時(shí)計(jì)算TRating 方法和查詢優(yōu)化器為查詢選擇較優(yōu)執(zhí)行計(jì)劃的準(zhǔn)確率，結(jié)果如表5所示。

由表5 可知，在不同并行度下，與目前查詢優(yōu)化器相比，本文所提方法選擇較優(yōu)執(zhí)行計(jì)劃準(zhǔn)確率平均提高了25 個(gè)百分點(diǎn)。本文方法之所以準(zhǔn)確率提高，是因?yàn)樗跒椴樵冞x擇當(dāng)前查詢組合下的較優(yōu)執(zhí)行計(jì)劃時(shí)，特別地考慮了多查詢并行時(shí)查詢交互這一關(guān)鍵因素，并合理地度量了特定查詢?cè)诓樵兘M合中所受的查詢交互影響的大小。盡管這樣，隨著并行度的增加、查詢間交互的復(fù)雜化，預(yù)測(cè)準(zhǔn)確率會(huì)稍有下降，屬正?，F(xiàn)象。

表5 TRating和查詢優(yōu)化器準(zhǔn)確率對(duì)比Tab.5 Accuracy comparison between TRating and query optimizer

更可觀的是，當(dāng)前查詢優(yōu)化器是基于成本估算為查詢選擇較優(yōu)執(zhí)行計(jì)劃，它需要計(jì)算每個(gè)執(zhí)行計(jì)劃所涉及各種操作的成本，計(jì)算量大。相對(duì)于查詢優(yōu)化器，本文TRating 方法在為查詢選擇較優(yōu)執(zhí)行計(jì)劃時(shí)，由于模型選擇的合理性，所涉及的計(jì)算量較小。因此，實(shí)驗(yàn)發(fā)現(xiàn)，在相同的計(jì)算環(huán)境下，本文方法TRating耗時(shí)遠(yuǎn)小于當(dāng)前查詢優(yōu)化器。除此之外，不難發(fā)現(xiàn)，在不同MPL 值下，通過(guò)本文方法TRating 選擇較優(yōu)執(zhí)行計(jì)劃的準(zhǔn)確率均高于當(dāng)前查詢優(yōu)化器，這是因?yàn)楸疚姆椒ㄌ貏e地考慮了并行查詢下查詢交互這一關(guān)鍵因素。因此，隨著MPL 即查詢并行數(shù)的增加和查詢交互的復(fù)雜化，雖然本文方法TRating準(zhǔn)確率會(huì)有所下降，但仍優(yōu)于當(dāng)前查詢優(yōu)化器。

實(shí)驗(yàn)發(fā)現(xiàn)，在少數(shù)情況下，當(dāng)本文方法不能為查詢選擇較優(yōu)執(zhí)行計(jì)劃時(shí)，其所選擇執(zhí)行計(jì)劃仍然為次優(yōu)執(zhí)行計(jì)劃（即除去較優(yōu)執(zhí)行計(jì)劃，使查詢響應(yīng)時(shí)間較少的執(zhí)行計(jì)劃），同樣避免了最壞執(zhí)行計(jì)劃，也具有相當(dāng)?shù)膶?shí)際意義。表6 是MPL=2，4，6，8 時(shí)，本文TRating 方法為查詢選擇次優(yōu)執(zhí)行計(jì)劃的準(zhǔn)確率。由表6 可知，在不同并行度下，本文TRating 方法為查詢選擇次優(yōu)執(zhí)行計(jì)劃（包括較優(yōu)執(zhí)行計(jì)劃）平均預(yù)測(cè)準(zhǔn)確率高達(dá)69%，由此可知本文所提方法具有相當(dāng)高的可靠性。

表6 TRating選擇次優(yōu)執(zhí)行計(jì)劃準(zhǔn)確率Tab.6 TRating accuracy for suboptimal execution plan selection

4 結(jié)語(yǔ)

查詢是數(shù)據(jù)庫(kù)的主要負(fù)載，查詢效率直接決定數(shù)據(jù)庫(kù)系統(tǒng)的性能。多查詢并行時(shí)，由于現(xiàn)有查詢優(yōu)化器只能依據(jù)參數(shù)配置靜態(tài)地為查詢選擇一個(gè)不壞的執(zhí)行計(jì)劃，并沒有特別地考慮查詢交互這一關(guān)鍵因素，導(dǎo)致其在為查詢選擇當(dāng)前查詢組合下的較優(yōu)執(zhí)行計(jì)劃時(shí)存在較大偏差?；诖耍疚暮侠淼囟攘苛颂囟ú樵?cè)诙嗖樵儾⑿袝r(shí)受查詢交互影響程度的大小，在此基礎(chǔ)上，創(chuàng)新性地提出了動(dòng)態(tài)地為查詢選擇當(dāng)前查詢組合下較優(yōu)執(zhí)行計(jì)劃的方法TRating，并通過(guò)實(shí)驗(yàn)驗(yàn)證了其合理性。當(dāng)用戶提交的查詢到達(dá)時(shí)，依據(jù)先到先服務(wù)原則，為先到查詢選擇當(dāng)前查詢組合下的較優(yōu)執(zhí)行計(jì)劃提供了依據(jù)，具有一定的實(shí)際意義。隨著查詢并行度的增加、查詢交互的復(fù)雜化，如何更準(zhǔn)確地建立方法，或通過(guò)訓(xùn)練深度學(xué)習(xí)模型，保持其預(yù)測(cè)準(zhǔn)確率不變是后續(xù)研究的重點(diǎn)。