并行查詢下查詢執行計劃的選擇

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

（太原理工大學信息與計算機學院，太原030024）

0 引言

查詢是數據庫系統的主要工作負載，查詢效率的高低決定數據庫運行性能的好壞。在數據庫系統中，一個查詢在真正執行前，查詢優化器會生成多種查詢執行計劃（即查詢在數據庫中的執行方案）。盡管這些計劃最終生成完全相同的結果集，但它們的執行效率卻存在很大差異［1］。尋找較優的查詢執行計劃可以以較小的代價、在很大程度上縮短查詢的響應時間，提高查詢效率，進而提高數據庫系統的性能。

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

在數據庫管理系統中，查詢優化器在為查詢生成不同的執行路徑時，會綜合考慮數據表的掃描方式、表間連接方式及連接順序，在選擇較優執行路徑時，會依據查詢的復雜程度選用不同的算法。因此，當數據庫中只有一個查詢運行時，如果查詢不太復雜，查詢優化器可以做到避免選擇最差執行計劃，且在為此類查詢選擇較優查詢計劃上可保持一定的準確率。

隨著數據量的急劇增長、用戶需求的不斷變化，查詢語句越發復雜。由于查詢優化器優化算法本身的局限性，它只能依據數據庫配置參數靜態地為查詢選擇一個較優的執行計劃，如果查詢語句過于復雜，在統計信息不準確的情況下，成本估算的誤差會成倍放大［6］，因此會造成所選擇的較優執行計劃存在較大偏差。

特別地，在實際的數據庫系統中，單一查詢運行的情況比較罕見，大部分情況是不同查詢在一起并行，因此，一個查詢的運行會受到其他查詢的影響，我們將其稱為查詢交互［7］。由于查詢交互現象的存在，相比其單獨運行，查詢的響應時間會有顯著變化，大部分查詢的響應時間會變長。而且，查詢并行數（MPL）越大，這種變化越發明顯。

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

為此，本文提出一種度量查詢受查詢交互影響程度大小的標準QIs（Query Interactions），為選擇查詢執行計劃時定量考慮查詢交互因素打下基礎。針對并行查詢下較優執行計劃的選擇，本文提出一種為查詢動態選擇當前查詢組合下較優執行計劃的方法TRating（Time Rating），該方法通過比較按照不同執行計劃執行的查詢在查詢組合中受查詢交互影響程度的大小，選擇受查詢交互影響較小的查詢所對應的執行計劃作為該查詢的較優執行計劃。

1 相關工作

目前，數據庫管理系統通過查詢優化器為查詢選擇較優執行計劃。對于一個特定的查詢，在查詢執行前，查詢優化器中的規劃器負責為查詢生成所有可能的執行計劃，優化器依據成本預算從中選擇執行代價最小的計劃。針對復雜度不同的查詢，查詢優化器采用不同的算法進行處理。對于比較簡單的查詢，優化器采用動態規劃算法，該算法搜索范圍小且效率高；對于比較復雜的算法，則采用基因算法。基因算法是一種自適應的算法，可以在較短的時間內給出一個較優的解［1］。因此，對于數據庫中單一運行的查詢，查詢優化器在為不太復雜的查詢選擇一個不壞的執行計劃時可保持一定的準確率。但是，如果查詢語句過于復雜，由于查詢優化器成本估算算法的局限性，在統計信息估計不準確時，成本估算的誤差會成倍放大，無法為查詢選擇較優的執行計劃［7］。

特別地，在實際的數據庫系統中，單一查詢運行的情況比較少見，多數情況下是不同查詢在一起并行，并行查詢間存在查詢交互，這種交互會導致某一查詢的運行受到其他查詢的影響［8］。由于查詢優化器通過數據庫配置參數靜態地為查詢選擇查詢執行計劃，這種選擇較優執行計劃的方式盡管一定程度上反映了查詢交互［9］，但是其并沒有特別地考慮查詢交互這一關鍵因素的存在，無法準確地反映這種查詢交互現象。在并行查詢情景下，一個不壞的執行計劃在另一查詢組合中可能會變得不好，甚至更差［9］。在這種情況下，如果仍用原有執行計劃去執行該查詢，會嚴重影響該查詢和其他查詢的性能。因此，通過查詢優化器已無法為查詢準確地選擇當前查詢組合下較優的執行計劃［10-11］。

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

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

基于以上查詢交互度量使用范圍的限制、查詢優化器為查詢選擇當前查詢組合下較優執行計劃存在較大偏差的問題，本文提出了一種度量查詢在多查詢(MPL ＞2)并行下受查詢交互影響程度大小的標準QIs，并基于查詢交互提出了一種動態地為查詢選擇當前查詢組合下較優執行計劃的方法TRating。當用戶提交的查詢到達時，依據先到先服務原則，為先到查詢選擇當前查詢組合下的較優執行計劃提供了依據，具有一定的實際意義。

2 并行查詢下較優執行計劃的選擇

2.1 QIs度量標準

Zhang 等［15］提出的QueryRating 的表達式如式（1），它直接計算響應時間的比值，建模復雜度低且準確率高。

QueryRating 可以度量兩兩查詢并行時由于查詢交互某一查詢受到另一查詢影響程度的大小。那么，如果多查詢并行(MPL ＞2)時，由于查詢交互，某一查詢會受到其余任何一個查詢的影響，如何度量多查詢并行時特定查詢所受查詢交互影響程度的大小是為該查詢選擇當前查詢組合下較優執行計劃的基礎。受Duggan 等［14］提出的B2L&BAL 模型預測查詢性能的啟發，本文通過考慮其他剩余每個查詢對要研究查詢的查詢交互大小，提出了一種度量多查詢并行時查詢所受查詢交互影響程度大小的標準QIs，表達式如下：

其中：

式（2）中：QIsqi表示多查詢并行時，查詢qi受其他剩余查詢查詢交互影響的大小；tqi表示查詢qi單獨運行時的響應時間；Durqi（Duration）可以看作查詢qi所受其他查詢查詢交互影響的持續時長。

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

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

2.2 TRating方法的具體實現

在實際的數據庫系統運行中，對于用戶提交的查詢，依據先到先服務原則，按照用戶提交查詢的先后順序執行查詢。那么，當某個查詢到來時，為查詢選擇當前查詢組合下較優的執行計劃對提高查詢效率十分必要。當按照特定執行計劃執行的某查詢在加入查詢組合時，相比其他執行計劃，按特定執行計劃執行的某查詢單獨運行時的響應時間較短，且它所受查詢交互影響程度越小，則其在查詢組合中的響應時間越短。也就是說，按特定執行計劃執行的某查詢單獨運行時的響應時間的長短和該查詢所受查詢交互影響程度的大小均會影響該查詢在查詢組合中最終的響應時間。響應時間越短的查詢對應的執行計劃即為該查詢在當前查詢組合中較優的執行計劃。

為能準確地描述該方法，本文定義該方法中用到的符號見表1。

表1 相關符號定義Tab.1 Definition of related symbols

相比其他執行計劃，如果按特定執行計劃執行的某查詢單獨運行時的響應時間較長，即使該查詢在查詢組合中受其余查詢的查詢交互影響較小，它最終的響應時間也可能較長；同樣地，如果按另一執行計劃執行的該查詢單獨運行時的響應時間較短，即使該查詢在查詢組合中受其余查詢的查詢交互影響較大，它最終的響應時間也可能較短。考慮到這種現象的存在，將Facqw_k值作為每個查詢計劃的基準值。建立的表達式如下：

其中，Facqw_k表示按qw_k執行計劃執行的查詢單獨運行時的響應時間所占該查詢所有執行計劃單獨運行時響應時間之和的比值，以此作為每個查詢執行計劃的基準值。

該方法具體流程如下：

1）構建兩張索引表IT1、IT2和兩張數據表T1、T2，并將索引表IT1和數據表T1關聯，索引表IT2和數據表T2關聯。

索引表IT1存儲A 中查詢的查詢編號i、每個查詢對應的所有執行計劃編號j，并將其分別設置為一級索引和二級索引。表結構見表2。

表2 索引表IT1Tab.2 Index table IT1

索引表IT2存儲C 中查詢組合編號f、每個查詢組合中查詢qi和查詢qn所對應的QueryRating 值和的編號和，并將查詢組合編號設置為一級索引。表結構見表3。

表3 索引表IT2Tab.3 Index table IT2

數據表T1、T2分別對應索引表IT1、IT2中數據實際值，另數據表T1需要存儲每個qi_j單獨運行時的響應時間。

由索引表IT1、數據表T1獲取按特定執行計劃執行的查詢單獨運行時的響應時間，由索引表IT2、數據表T2獲取該查詢所受其他查詢的QueryRating。

2）給定MPL=w，當某查詢qw到達數據庫時，該查詢與目前正在執行的(w-1)個查詢構成一個查詢組合。

由索引IT1表、數據表T1得到該查詢的所有執行計劃qw_k及其對應單獨運行時的響應時間tqw_j，計算出Facqw_k值。

3）比較所有執行計劃對應的TRatingqw_k，較小的TRatingqw_k值所對應的執行計劃即為該查詢在當前查詢組合下較優的查詢執行計劃。

3 實驗結果與分析

3.1 實驗環境與設計

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

表4 實驗環境配置Tab.4 Experimental environment configuration

為查詢選擇當前查詢組合下較優的執行計劃，必須首先獲取查詢的多個執行計劃。本文首先獲取查詢的多個執行計劃，緊接著通過實驗驗證同一查詢在不同查詢組合下所選擇的較優執行計劃不同這一現象的大量存在。最后，給定MPL，依據先到先服務原則，根據實際用戶提交查詢的先后，對比當前查詢優化器，通過實驗驗證本文所提出的為查詢選擇當前查詢組合下較優執行計劃方法的準確性。

3.2 執行計劃生成及其響應時間

由于執行計劃的生成會綜合考慮基本表的訪問順序、表間的連接方式和連接順序，因此本文在生成查詢執行計劃時，對于單表查詢著重考慮基本表的訪問順序，對于多表查詢，著重考慮表間連接方式和連接順序，以此生成代表性執行計劃。

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

圖1 默認執行計劃Fig.1 Default execution plan

圖2 關閉MergeJoin后的執行計劃Fig.2 Excution plan after closing MergeJoin

實驗中，服務器只開啟PostgreSQL 數據庫進程，分別單獨運行每個查詢、并行執行每兩個查詢組成的查詢組合，利用PostgreSQL 的pg_stat_statement 模塊獲取查詢的響應時間，通過多次運行求平均值的方法減少其他因素干擾，準確獲取響應時間，從而求得響應時間的比值。

3.3 查詢組合不同時的較優執行計劃驗證

本文分別對并行度MPL=2，4，6，8 時的同一查詢加入不同查詢組合所選擇的較優執行計劃進行實驗。實驗結果表明，同一查詢在不同查詢組合下所選擇的較優查詢計劃不同，而且這種現象普遍存在，平均約占71%。由于篇幅受限，圖3僅對部分樣例實驗結果進行展示，并加以說明。

圖3 關閉nestloop后MPL=4時，同一查詢加入不同的查詢組合時的較優執行計劃抽樣Fig.3 Sampling of better execution plan of one query adding to different query combinations with nestloop closed and MPL=4

圖3 中：每組由兩個柱狀圖構成，它們分別表示同一查詢加入不同的查詢組合中構成新的查詢組合，每個柱狀圖分成三段，每一段表示按不同的執行計劃執行的此查詢加入查詢組合，自底向上分別表示執行計劃1、2、3，執行計劃1 為PostgreSQL 查詢優化器給出的執行計劃，每段長度分別對應按特定執行計劃執行的此查詢加入查詢組合后的響應時間的長短。

由圖3 可知，多數情況下，每組的兩個柱狀圖的三段長度均不相同，這說明當同一查詢加入不同的查詢組合時，所選擇的較優執行計劃并不相同。比如，當查詢加入a1、a2 查詢組合時，對應與a1 構成新的查詢組合，該查詢的較優執行計劃為PostgreSQL 查詢優化器給出的執行計劃即執行計劃1；但對應與a2 構成的新的查詢組合，該查詢的較優執行計劃為執行計劃2，不同于執行計劃1。

本文對此種現象作如下解釋：對于單一運行的查詢，由于查詢優化器搜索算法的限制，目前其僅能做到避免選擇最差執行計劃，當查詢比較復雜時，為查詢選擇較優執行計劃會存在較大偏差；對于并行運行的查詢，優化器并沒有特別地考慮查詢交互這一主要因素，因為查詢在不同查詢組合下選擇較優執行計劃的偏差更大，因此，此種現象的大量存在十分正常。

3.4 TRating和查詢優化器對比

模擬用戶提交查詢的實際場景，依據先到先服務原則，分別在MPL=2，4，6，8 時計算TRating 方法和查詢優化器為查詢選擇較優執行計劃的準確率，結果如表5所示。

由表5 可知，在不同并行度下，與目前查詢優化器相比，本文所提方法選擇較優執行計劃準確率平均提高了25 個百分點。本文方法之所以準確率提高，是因為它在為查詢選擇當前查詢組合下的較優執行計劃時，特別地考慮了多查詢并行時查詢交互這一關鍵因素，并合理地度量了特定查詢在查詢組合中所受的查詢交互影響的大小。盡管這樣，隨著并行度的增加、查詢間交互的復雜化，預測準確率會稍有下降，屬正常現象。

表5 TRating和查詢優化器準確率對比Tab.5 Accuracy comparison between TRating and query optimizer

更可觀的是，當前查詢優化器是基于成本估算為查詢選擇較優執行計劃，它需要計算每個執行計劃所涉及各種操作的成本，計算量大。相對于查詢優化器，本文TRating 方法在為查詢選擇較優執行計劃時，由于模型選擇的合理性，所涉及的計算量較小。因此，實驗發現，在相同的計算環境下，本文方法TRating耗時遠小于當前查詢優化器。除此之外，不難發現，在不同MPL 值下，通過本文方法TRating 選擇較優執行計劃的準確率均高于當前查詢優化器，這是因為本文方法特別地考慮了并行查詢下查詢交互這一關鍵因素。因此，隨著MPL 即查詢并行數的增加和查詢交互的復雜化，雖然本文方法TRating準確率會有所下降，但仍優于當前查詢優化器。

實驗發現，在少數情況下，當本文方法不能為查詢選擇較優執行計劃時，其所選擇執行計劃仍然為次優執行計劃（即除去較優執行計劃，使查詢響應時間較少的執行計劃），同樣避免了最壞執行計劃，也具有相當的實際意義。表6 是MPL=2，4，6，8 時，本文TRating 方法為查詢選擇次優執行計劃的準確率。由表6 可知，在不同并行度下，本文TRating 方法為查詢選擇次優執行計劃（包括較優執行計劃）平均預測準確率高達69%，由此可知本文所提方法具有相當高的可靠性。

表6 TRating選擇次優執行計劃準確率Tab.6 TRating accuracy for suboptimal execution plan selection

4 結語

查詢是數據庫的主要負載，查詢效率直接決定數據庫系統的性能。多查詢并行時，由于現有查詢優化器只能依據參數配置靜態地為查詢選擇一個不壞的執行計劃，并沒有特別地考慮查詢交互這一關鍵因素，導致其在為查詢選擇當前查詢組合下的較優執行計劃時存在較大偏差。基于此，本文合理地度量了特定查詢在多查詢并行時受查詢交互影響程度的大小，在此基礎上，創新性地提出了動態地為查詢選擇當前查詢組合下較優執行計劃的方法TRating，并通過實驗驗證了其合理性。當用戶提交的查詢到達時，依據先到先服務原則，為先到查詢選擇當前查詢組合下的較優執行計劃提供了依據，具有一定的實際意義。隨著查詢并行度的增加、查詢交互的復雜化，如何更準確地建立方法，或通過訓練深度學習模型，保持其預測準確率不變是后續研究的重點。