一種交互感知的并行查詢調(diào)度策略

張青峰，許 靜，李珊珊

(南開大學(xué) 計算機與控制工程學(xué)院，天津300071)

0 引 言

在數(shù)據(jù)庫系統(tǒng)應(yīng)用中，查詢?nèi)蝿?wù)往往占絕大多數(shù)，因此查詢優(yōu)化是數(shù)據(jù)庫性能優(yōu)化的一項最為重要的技術(shù)手段。隨著數(shù)據(jù)庫變得越來越大，大量業(yè)務(wù)數(shù)據(jù)被收集和存儲起來，并基于海量數(shù)據(jù)進行更加智能的分析和決策。為了提高數(shù)據(jù)庫服務(wù)器的資源利用率和吞吐率，并行計算技術(shù)被引入到了數(shù)據(jù)庫系統(tǒng)中，通過并行查詢技術(shù)，可以使用更少的時間來完成相同數(shù)量的查詢?nèi)蝿?wù)，大大提升數(shù)據(jù)庫的性能。但同時當(dāng)大量查詢?nèi)蝿?wù)并行執(zhí)行共享計算資源和數(shù)據(jù)的時候會出現(xiàn)非常復(fù)雜的交互作用，這些復(fù)雜的交互作用將對系統(tǒng)性能產(chǎn)生巨大的影響［1］。這些影響可能是積極的，也可能是消極的，因此并行查詢?nèi)蝿?wù)的調(diào)度算法比傳統(tǒng)數(shù)據(jù)庫的查詢調(diào)度要復(fù)雜得多，選擇合適的調(diào)度算法將會顯著提升系統(tǒng)性能，從而使得查詢?nèi)蝿?wù)的執(zhí)行總時間最小。

針對以上問題，本文通過對并行查詢的交互作用進行實驗分析，構(gòu)建了一個基于查詢交互的性能模型，并提出了一種交互感知的并行查詢調(diào)度算法。交互感知的調(diào)度算法和傳統(tǒng)查詢調(diào)度方法的主要區(qū)別在于考慮了并行查詢之間的交互作用。通過基于MySQL/TPC－H 的實驗研究證明了ICMF 調(diào)度策略的有效性。通過利用ICMF 調(diào)度算法，相同數(shù)量查詢?nèi)蝿?wù)的整體執(zhí)行時間比SJF 算法和FCFS 算法大大減少。

1 相關(guān)研究工作

并行查詢的優(yōu)化和調(diào)度算法有很長的研究歷史，但大部分的研究工作都是依賴于查詢內(nèi)部的信息以及對系統(tǒng)底層資源信息的監(jiān)控，如國內(nèi)學(xué)者曹陽等人提出了使用遺傳算法來解決多連接表達式的并行查詢優(yōu)化問題［2］。國防科技大學(xué)的張麗等人提出在海量數(shù)據(jù)管理平臺中利用語義緩存技術(shù)對聚焦查詢進行優(yōu)化，提升查詢速度［3］。這些研究工作主要是基于查詢?nèi)蝿?wù)內(nèi)部的語法結(jié)構(gòu)信息和語義相關(guān)性來重用緩存數(shù)據(jù)，從而達到提高系統(tǒng)性能的目的。而本文的研究工作不需要提前知道查詢?nèi)蝿?wù)內(nèi)部的語義信息，通過實驗驅(qū)動的性能建模方法來捕獲并行查詢之間的交互作用來實現(xiàn)并行查詢的優(yōu)化。

一些傳統(tǒng)的查詢調(diào)度算法，如最短時間優(yōu)先(SJF)算法在實施訪問控制時，主要是基于查詢單獨執(zhí)行時的運行時間來進行調(diào)度，卻完全沒有考慮多查詢?nèi)蝿?wù)并行時的運行時間和單獨運行時可能會發(fā)生巨大的變化。當(dāng)前，對并行查詢調(diào)度算法的研究還有很多新的方法，如文獻［4］提出了一種基于分段線性的服務(wù)水平協(xié)議的調(diào)度策略，并通過預(yù)測查詢超時時間來進行動態(tài)的任務(wù)調(diào)度。文獻［5］通過動態(tài)調(diào)整數(shù)據(jù)庫的并行級別(MPL)來進行查詢調(diào)度，首先利用排隊論為系統(tǒng)設(shè)定一個初始的并行級別，并實時通過反饋監(jiān)控動態(tài)調(diào)整并行數(shù)，從而使得系統(tǒng)性能達到最優(yōu)，但對并行級別的調(diào)整策略也沒有考慮并行查詢之間的交互作用。在本文中，假定數(shù)據(jù)庫的并行級別是固定不變的，而基于并行查詢之間的交互作用動態(tài)調(diào)整數(shù)據(jù)庫的并行級別是未來的研究方向之一。本文認為并行查詢操作具有不同的處理特性，對資源的競爭使用模式也不同，并行查詢之間的交互作用會對系統(tǒng)性能產(chǎn)生巨大的影響，因此在進行查詢?nèi)蝿?wù)調(diào)度時，必須考慮并行查詢之間的交互作用才能實現(xiàn)更優(yōu)的系統(tǒng)性能。

查詢交互作用指的是并行執(zhí)行的查詢?nèi)蝿?wù)之間的資源沖突，這些沖突會對系統(tǒng)性能產(chǎn)生巨大的影響［1］。目前，在數(shù)據(jù)庫研究領(lǐng)域?qū)Σ樵儍?yōu)化和查詢調(diào)度的研究非常多，但關(guān)于普通意義上的查詢交互的研究卻非常少。

國外的一些研究機構(gòu)中已經(jīng)有一些學(xué)者開始針對查詢交互進行探索，主要基于查詢交互進行延遲預(yù)測和性能評估。2008 年滑鐵盧大學(xué)的Mumtaz Ahmad 等人首次提出了并行查詢交互作用的概念，并在文獻［1，6，7］中詳細描述了查詢交互會對系統(tǒng)性能產(chǎn)生巨大的影響作用，并提出了基于查詢交互的性能優(yōu)化和調(diào)度算法，但與本文的調(diào)度算法不同的是對交互成本的計算方法，在文獻［6］中是基于并行查詢組合的不同類型查詢的數(shù)量來計算交互成本的，而本文中是基于不同查詢類單獨運行(MPL=1)和兩兩運行(MPL=2)的交互時間成本來進行建模的。Sean Tozer 等人在文獻［8］中通過對查詢交互作用進行分析和建模，針對多層架構(gòu)的網(wǎng)絡(luò)應(yīng)用提出了一種基于并行查詢交互的訪問控制策略，在文中提出當(dāng)一個網(wǎng)絡(luò)請求到達服務(wù)器時，通過預(yù)測請求的執(zhí)行時間來判斷是否允許訪問服務(wù)器，而此時需要考慮并行請求之間的交互作用。此外，布朗大學(xué)的Jennie Duggan 等人在文獻［9］中提出了基于查詢交互來預(yù)測查詢?nèi)蝿?wù)的響應(yīng)延遲，并提出了一個新的查詢延遲的度量指標(biāo)BAL(Buffer access Latency)。這些研究結(jié)果都證明了以下幾點問題:①查詢交互對性能有非常大的影響;②并行查詢之間的交互作用是非常復(fù)雜的，而且很難進行白盒分析;③通過實驗的方法可以有效地捕獲這些交互作用，并且能夠?qū)Σ樵兘换ソ⒄_的性能模型。這些研究成果都給了本文很大的啟示。

而在國內(nèi)，目前還沒有發(fā)現(xiàn)有學(xué)者明確提出基于查詢交互作用進行任務(wù)調(diào)度這方面的研究資料，本文的工作是在實驗的基礎(chǔ)上嘗試在并行查詢的優(yōu)化和調(diào)度策略研究中引入了查詢交互的分析。目前一些具體的研究工作，例如查詢優(yōu)化技術(shù)［10］、負載管理［11］等，都沒有考慮這些并行查詢執(zhí)行中所產(chǎn)生的交互作用影響。本文將通過實驗證明被這些研究工作忽略的交互作用會對性能產(chǎn)生非常巨大的影響，因此并行查詢的交互作用研究是一個非常值得深入研究的領(lǐng)域。

2 基于并行查詢交互的性能模型

2.1 并行查詢之間的交互作用分析

用Q1，Q2，…，Q22來表示TPC－H 的22 個查詢類型，在實驗中用QGEN 程序自動生成查詢語句中的參數(shù)，從而獲得具體的查詢實例［12］。數(shù)據(jù)庫系統(tǒng)的并行級別用MPL(multi programming level)來表示，MPL 是指在任何時候數(shù)據(jù)庫系統(tǒng)允許并行執(zhí)行查詢實例的最大數(shù)量。

接下來通過不同的實驗來分析不同的MPL并行情況下查詢交互對查詢組合中每個查詢?nèi)蝿?wù)完成時間的影響。在實驗過程中，測試數(shù)據(jù)都是均勻分布的，因此對同一查詢類型的不同查詢實例，在相同的環(huán)境下其執(zhí)行時間可以看做近似相等。

(1)單獨運行(MPL=1)

首先，通過實驗獲得每個查詢類單獨運行(MPL=1)時的平均運行時間。

從TPC－H 查詢類型中選擇10 個中等量級的查詢類型，并用QGEN 程序為這個10 個查詢類分別生成10 個實例，然后在10 G 數(shù)據(jù)庫上單獨運行這100 個查詢語句，記錄每個查詢?nèi)蝿?wù)的執(zhí)行時間，從而可以計算獲得每個查詢類單獨運行時的平均運行時間。

在計算平均運行時間時，假定每個查詢?nèi)蝿?wù)都是預(yù)先加載好緩存的，因為每個查詢類第一個執(zhí)行的查詢實例都會有一些初始化緩存的開銷，因此對每個查詢類不計算第一個執(zhí)行的查詢實例的運行時間，從而可以獲得更準(zhǔn)確的平均時間開銷。

在表1 中可以看到這些查詢類在10 G 數(shù)據(jù)庫上運行時的平均花費時間。Tj代表了特定的查詢類型的10 個實例的平均運行時間。Tj將作為以后研究并行查詢交互作用的基準(zhǔn)時間。

表1 MPL=1 時的平均完成時間Table 1 Average completion time when MPL=1

(2)兩兩并行(MPL=2)

在研究了每個查詢類單獨運行時的平均運行時間之后，將對這10 個查詢類兩兩并行的交互作用進行實驗分析。所有10 個查詢類之間的唯一的兩兩組合，共有n*(n+1)/2 =55 個查詢組合，分別執(zhí)行這55 個查詢組合，并記錄相應(yīng)的運行時間的變化。

用Ti表示Qi單獨運行時的執(zhí)行時間，Ti/j表示Qi與Qj并行時的執(zhí)行時間，則可以ΔTi/j來表示Qi與Qj并行時的變化。

如果ΔTi/j是正的，說明速度變慢了，如果是負值，說明速度變快了。需要注意的是兩兩查詢之間的交互作用不是對稱的(ΔTi/j≠ΔTj/i)。

如表2 所示，表中分別記錄了55 組兩兩交互的運行時間。從表中可以看出，當(dāng)Q19和Q21一起運行時，它們分別獲得了大約4 s 和77 s 的加速;當(dāng)Q3和Q21一起并行時，Q21獲得了約38 s 的加速，而Q3的執(zhí)行時間卻增加了17 s;當(dāng)Q5和Q14并行運行時，它們的運行時間分別增加了大約52 s 和54 s。在此注意到Q19和Q21一起并行時，分別都獲得了性能加速，這個現(xiàn)象是因為兩個SQL在并行時，互相為對方加載了緩沖數(shù)據(jù)，因此同時出現(xiàn)了積極的交互影響，加快了查詢處理速度。

表2 MPL=2 時的交互作用分析Table 2 Interaction effect analysis when MPL=2

通過表2 中的數(shù)據(jù)可知，當(dāng)不同的查詢類兩兩并行時，其完成時間會出現(xiàn)不規(guī)則的變化，有減少也有增加。這也證明了并行查詢之間的交互作用會對查詢性能產(chǎn)生非常顯著的影響，這些影響有時會是積極的，但有時也會是消極的。

而交互作用的產(chǎn)生又是非常復(fù)雜的，其原因也是多種多樣的。例如，一個查詢Qi會把數(shù)據(jù)加載到緩沖池中，然后一個并行查詢Qj會用到這個數(shù)據(jù)，那就會產(chǎn)生積極的交互作用。而相對應(yīng)的，在硬件資源使用上的沖突會使Qi和Qj互相競爭，例如對CPU、內(nèi)存或者數(shù)據(jù)庫系統(tǒng)內(nèi)部資源存取鎖的使用上產(chǎn)生的沖突，就會產(chǎn)生消極的交互作用。

(3)高級別并行(MPL ＞2)

當(dāng)并行級別大于2 時，并行查詢之間的交互作用將變得更加復(fù)雜和難以捕獲。下面分別對不同并行級別情況下的交互作用進行實驗分析。

在表3 中，隨機抽取三個查詢類型進行組合，記錄并行運行時每個查詢的執(zhí)行時間。從表中數(shù)據(jù)可以看出，完成時間有減少的，也有延長的，不同組合中同一個類型查詢的完成時間變化是不規(guī)律的。

接下來，對M=5 的兩個查詢類型的不同組合的交互作用進行分析，如表4 所示。其中，Nij是查詢組合Mi中查詢類型Qj的實例數(shù)量，把組合Mi中的查詢類型Qj的平均運行時間表示為Aij。在表4 中依次減少Q(mào)19的實例數(shù)量，同時增加Q6的實例數(shù)量，觀察Q6和Q19的執(zhí)行時間的變化情況。

表3 MPL=3 時的交互作用分析Table 3 Interaction effect analysis when MPL=3

表4 兩個查詢類型的不同組合的交互作用分析Table 4 Interaction effect analysis for different query mixes

從表4 數(shù)據(jù)可以看出，即使只有兩個查詢類型時，僅僅用一個查詢類型的實例來替換另一個查詢類型的實例也會顯著地改變查詢執(zhí)行時間，這也進一步證明了查詢交互的重要性。

最后，將對多種查詢類型的組合進行試驗，如表5 中所示。選擇5 個查詢類型的實例進行組合變化，保持組合的實例數(shù)量M=5 不變，即保持并行級別MPL 不變。

從表5 中數(shù)據(jù)可以知道:當(dāng)查詢組合中有多個查詢類型時，其交互作用將更加復(fù)雜，在并行過程中變化某一個查詢類型的數(shù)量也可能會對其他并行的查詢?nèi)蝿?wù)產(chǎn)生非常大的影響。

從本節(jié)的大量實驗中可以得出以下結(jié)論:①一個包含了多種查詢類的組合并行運行時可能既包含積極的交互，也包含消極的交互。②對所有的查詢類來說，它的并行執(zhí)行時間與和它并行的查詢類關(guān)系非常密切，不同的并行查詢將產(chǎn)生截然不同的交互作用。③并行查詢的交互作用是相當(dāng)復(fù)雜的，在查詢組合中的一個小的改變有時會對其他查詢的性能產(chǎn)生巨大的影響，但這些影響又是非常難預(yù)測的。

表5 不同查詢組合的平均運行時間Table 5 Average completion time of different query mixes

基于以上的分析可知，并行查詢交互作用的產(chǎn)生因素是非常復(fù)雜的，要想對這些因素進行建模，就需要考慮硬件資源(CPU、內(nèi)存和磁盤I/O)，數(shù)據(jù)庫內(nèi)部構(gòu)件(查詢計劃、訪問方法、緩沖池、數(shù)據(jù)庫鎖)，操作系統(tǒng)內(nèi)部調(diào)度以及其他可能的因素。對所有這些因素進行建模，需要監(jiān)控并行過程中每一個指標(biāo)的變化情況，以便于在模型中反應(yīng)每一個產(chǎn)生因素，這是非常復(fù)雜和困難的，為了避免建立如此復(fù)雜的模型，本文主張采用實驗驅(qū)動的性能建模方法。

2.2 基于查詢交互成本的性能建模

以上這些實驗說明了除非能夠?qū)Σ樵兘M合中的并行交互作用進行建模，否則不可能得到最優(yōu)化的查詢性能，如果只關(guān)注單獨的查詢類型而忽略并行查詢之間的交互作用，不可能得出關(guān)于性能的準(zhǔn)確結(jié)論。因此，下一步的主要工作就是開發(fā)基于查詢交互作用的性能模型，準(zhǔn)確地建模對于進行性能優(yōu)化和任務(wù)調(diào)度都是非常重要的。

在上一節(jié)的分析中可知，為了對查詢交互作用進行建模，主張用實驗驅(qū)動的性能建模方法。目前，在查詢交互作用的相關(guān)研究工作中，基本上也都采用了實驗驅(qū)動的黑盒建模方法［6，7，9］。當(dāng)軟件系統(tǒng)變得越來越復(fù)雜時，實驗驅(qū)動的方法也越來越多地被用來建立健壯的軟件系統(tǒng)性能模型。關(guān)于實驗驅(qū)動的建模方法國內(nèi)外都有大量的嘗試，文獻［13］用實驗驅(qū)動的方法預(yù)測查詢的性能指標(biāo)，文獻［14］采用了實驗驅(qū)動技術(shù)來自動優(yōu)化數(shù)據(jù)庫的配置參數(shù)，這些工作證明對于數(shù)據(jù)庫性能建模來說，實驗驅(qū)動方法是可行和有效的。

本文中使用WEKA(Waikato environment for knowledge analysis toolkit，懷卡托智能分析環(huán)境)工具［15］來構(gòu)建并行查詢交互的性能模型。在WEKA 環(huán)境中，選擇線性回歸算法來建立模型和測試模型。在建模過程結(jié)束后，可以從樣本數(shù)據(jù)中得到一組回歸模型的系數(shù)。

當(dāng)一個新的查詢q 加入到一個查詢組合Mi中時，Mi中并行的其他查詢?yōu)?c1，c2，…，ct)，則q加入Mi后查詢組合的并行交互成本(Interaction cost，IC)可以構(gòu)造線性回歸方程計算如下:

以上回歸方程中，每一個查詢類在已經(jīng)初始化緩存情況下獨立運行時間平均值和兩兩查詢之間的交互作用為回歸方程求解提供了獨立變量的輸入值。

回歸方程可以用最小二乘法來求解導(dǎo)出相應(yīng)的系數(shù)α 和β，在每一個并行級別分別求一次。其中α 表示q 加入到M 中的時間偏移，而β 是指不同并行級別下兩兩并行交互成本對整體系統(tǒng)性能的影響。在此處，回歸模型沒有考慮加入q 后，cj對q產(chǎn)生的交互作用(即ΔTq/cj)的影響，因為對于整個組合的性能來說，加入q 后產(chǎn)生的交互成本主要是q 對cj的影響產(chǎn)生的。而在文獻［9］中建模是為了預(yù)測q 的執(zhí)行時間，因此需要考慮cj對q 產(chǎn)生的交互作用。

舉例:當(dāng)查詢a 加入到(b，c)的查詢組合后，計算因為a 的加入而產(chǎn)生的并行交互成本，則需要以下幾個輸入值:Ta，Tb，Tc為單獨運行時的平均時間;ΔTb/a，ΔTc/a為兩兩并行時的運行時間變化。

可以計算加入查詢a 后產(chǎn)生的并行交互成本為:

對不同的并行級別需要進行分別建模，當(dāng)并行級別為2，3，4，5 時，分別計算回歸方程的系數(shù)。當(dāng)MPL=2 時，10 個查詢類的并行交互需要執(zhí)行55 個組合;而當(dāng)MPL=3 時，則需要執(zhí)行110 個并行組合。因為MPL=2 和3 時，樣本空間數(shù)量相對比較小，因此可以直接對實驗數(shù)據(jù)進行建模分析。當(dāng)并行級別不斷增加時，回歸方程的樣本空間呈指數(shù)級增長，因此為了計算高級別并行查詢的交互成本，選擇合適的抽樣數(shù)量是非常必要的。而當(dāng)MPL 大于3 時，因為樣本空間相對比較大，因此對每一個查詢類型，在每個并行級別的樣本空間中均勻地隨機選取50 個觀測樣本，運行這些樣本可以計算獲得每一個并行級別的模型系數(shù)。

此外，WEKA 還支持很多其他高級的性能建模算法，如局部加權(quán)線性回歸模型、神經(jīng)網(wǎng)絡(luò)［13］、高斯處理模型［16］等。本文選擇線性回歸模型是因為對于并行查詢的交互作用來說，雖然其關(guān)系比較復(fù)雜，但利用線性回歸模型已經(jīng)能夠抓住查詢交互作用的主要性能特征，并且在實驗中也已經(jīng)得到了較好的分析結(jié)果。

3 交互感知的并行查詢調(diào)度算法

查詢?nèi)蝿?wù)完成總時間(Tsum)可以定義為從第一個查詢?nèi)蝿?wù)開始啟動到所有查詢?nèi)蝿?wù)都完成時總共消耗的時間。

已知并行負載W 由N 個查詢?nèi)蝿?wù)Q1，Q2，Q3，…，Qn構(gòu)成，每個查詢?nèi)蝿?wù)所屬的TPC－H 查詢類型是已知的，數(shù)據(jù)庫的并行級別為M，也就是說在并行過程中，同時最多只有M 個查詢在執(zhí)行，這M 個查詢就構(gòu)成了一個查詢組合mi，由所有的mi構(gòu)成了一個查詢組合集X={m1，m2，…，mi}，調(diào)度算法的目標(biāo)就是生成一個最優(yōu)順序的查詢組合集X。

首先做兩個假設(shè):

(1)所有特定某一類型的查詢都有著近似相同的性能。

(2)數(shù)據(jù)庫可以以任意的順序執(zhí)行隊列中的查詢?nèi)蝿?wù)。查詢之間的優(yōu)先級限制可以在系統(tǒng)外進行強行控制。

基于以上分析和假設(shè)，交互感知調(diào)度算法的實現(xiàn)方法就是優(yōu)先執(zhí)行交互成本低(積極交互)的查詢組合，避免執(zhí)行交互成本高(消極交互)的查詢組合，從而使整個并行任務(wù)的交互成本最低，也就是任務(wù)完成總時間Tsum最少。

交互感知的調(diào)度策略執(zhí)行步驟為:

(1)從N 個查詢?nèi)蝿?wù)中選擇M 個查詢組成一個并行交互成本最小的查詢組合Mmin啟動并行任務(wù)。

(2)在任意一個查詢Qmin最先結(jié)束時，得到Mmin中的其他(M－1)個查詢?nèi)蝿?wù)。

(3)對每一個等待隊列中的查詢，計算其與正在執(zhí)行的(M－1)個查詢組成的查詢組合的并行交互成本。

(4)獲得新的并行交互成本最小的查詢Qnext。

(5)重新從(2)開始循環(huán)執(zhí)行，直到完成所有的查詢?nèi)蝿?wù)。

以上算法用形式化語言可以表示如下:

輸入:并行負載W，由N 個查詢組成。

輸出:并行交互成本最小優(yōu)先的查詢執(zhí)行順序。

在以上算法中，IC(i)指加入Qi后對查詢組合的交互成本，可以直接通過線性回歸方程得到交互成本的值。線性回歸方程的系數(shù)可以通過離線實驗獲得，因此不會對查詢?nèi)蝿?wù)的性能產(chǎn)生大的干擾。

4 試驗及分析

為了驗證本文提出的交互感知的并行查詢調(diào)度算法，本文用C++語言開發(fā)了一個并行查詢調(diào)度工具。調(diào)度工具作為一個獨立的組件來進行查詢?nèi)蝿?wù)的優(yōu)化調(diào)度，和數(shù)據(jù)庫服務(wù)器在邏輯上也是獨立的，從而保證不會對查詢?nèi)蝿?wù)本身產(chǎn)生過大的壓力。

通過實驗分別在不同的MPL 情況下，將交互感知的調(diào)度(Interaction cost minimum first，ICMF)算法與傳統(tǒng)數(shù)據(jù)庫的最短時間優(yōu)先(Shortest job first，SJF)算法和先到先服務(wù)(First come first served，F(xiàn)CFS)算法進行對比實驗，從而證明了ICMF 算法的有效性。

4.1 實驗環(huán)境

實驗使用的硬件配置是:Intel Core 2 Pentium 4 Duo CPU 2.83 GHz，12 GB 內(nèi)存。操作系統(tǒng)為Windows 2008，數(shù)據(jù)庫采用的是開源的MySQL5.0，使用的存儲引擎是MyISAM，數(shù)據(jù)庫的緩沖池大小設(shè)置為2.4 G，并假設(shè)相關(guān)的數(shù)據(jù)庫配置參數(shù)都已經(jīng)進行了較好的優(yōu)化。

4.2 實驗數(shù)據(jù)和查詢負載

實驗基于TPC－H 測試標(biāo)準(zhǔn)，生成了10 G 大小的TPC－H 測試數(shù)據(jù)庫。TPC－H 提供了DBGEN 工具來生成測試數(shù)據(jù)，并且保證生成的數(shù)據(jù)是均勻分布的。查詢負載是通過QGEN 工具來生成的，因為TPC－H 使用均勻分布的數(shù)據(jù)和查詢參數(shù)，因此對一個特定的查詢類型來說，不同參數(shù)的查詢實例的執(zhí)行時間的差異是可以忽略不計的。

首先從TPC－H 查詢類型中選擇10 個中等量級的查詢類型，這10 個查詢類的執(zhí)行時間在所有22 個查詢類中也都是中等長度的。

選擇這10 個查詢類型的依據(jù)是:如果某一個查詢?nèi)蝿?wù)的運行時間過長，那么就只能觀察到該任務(wù)與其他大部分查詢?nèi)蝿?wù)的交互作用，而無法更多地捕獲其他查詢之間的交互作用;而相反，如果查詢?nèi)蝿?wù)的執(zhí)行時間過短，就不能反映出它對其他查詢?nèi)蝿?wù)的影響。

此外，本文選擇10 個相同級別的查詢類型的另外一個原因是為了避免對不同量級的查詢進行建模。文獻［11］對這個問題進行了更詳盡的研究，在他們的研究工作中，將查詢類型根據(jù)不同的量級進行了分組，并對每一組查詢進行建模分析。另外長事務(wù)在并行時可能會產(chǎn)生更加復(fù)雜的交互作用，其調(diào)度算法也會完全不同。關(guān)于以上這些方面的工作都將作為以后重點關(guān)注的研究方向。

基于以上原因，本文選擇了這10 個運行時間中等的查詢類型作為本論文的研究對象，每個查詢類型可以根據(jù)需要生成不同的查詢?nèi)蝿?wù)實例。

4.3 實驗結(jié)果與分析

(1)兩兩并行時(MPL=2)

在MPL=2 時，為10 個查詢類型分別生成一個查詢語句，分別用ICMF 算法、SJF 算法和FCFS算法執(zhí)行10 個查詢?nèi)蝿?wù)，比較三種算法的性能。

M=2 時各算法并行執(zhí)行時序圖見圖1，圖1中，括號內(nèi)數(shù)字表示執(zhí)行時間。可以看出，在M=2 時，各種算法執(zhí)行過程中的調(diào)度順序差別非常大，而正是因為執(zhí)行順序的不同，導(dǎo)致了查詢之間不同的交互作用，從而使整個負載的完成時間出現(xiàn)了較大的差異。

在圖2 中，對各個查詢類型實例在三種算法中的執(zhí)行時間分別進行了比較，可以看出在不同的算法中，各個查詢類型的執(zhí)行時間變化也不盡相同，Q3、Q6、Q8、Q10、Q19相對來說變化差異比較小，也就是說這些查詢類型在并行時表現(xiàn)的更加平穩(wěn)，而Q2、Q7、Q9、Q14、Q21相對來說變化差異比較大，這些查詢類型對并行時產(chǎn)生的交互作用更加敏感。

通過以上比較也可以發(fā)現(xiàn)，在ICMF 算法中正是因為多數(shù)的查詢實例完成時間發(fā)生了較為積極的變化，而使得整個任務(wù)的總完成時間最小。在實驗中，相同負載在三種算法中的總完成時間比較如圖3 所示。通過圖3 可以看出，對于10 個相同的查詢?nèi)蝿?wù)，MPL=2 情況下，ICMF 算法比FCFS 算法的運行時間提高了大約26 min，比SJF算法的運行時間提高了約9 min。因此可以證明在并行級別為2 的情況下，考慮了并行任務(wù)之間交互作用的ICMF 調(diào)度算法查詢性能更好。

圖1 M=2 時各算法并行執(zhí)行時序圖Fig.1 Sequence diagram of each algorithm when M=2

圖2 各個查詢類型在不同算法中的執(zhí)行時間比較Fig.2 Completion time of each query template in different algorithms

圖3 相同負載用三種算法調(diào)度的總完成時間比較Fig.3 Total time of same work with different algorithms

(2)高并行級別時(MPL ＞2)

首先對10 個查詢?nèi)蝿?wù)的負載進行實驗，分別設(shè)置數(shù)據(jù)庫的并行級別為3，4，5，并在不同的并行級別分別使用ICMF 算法、SJF 算法和FCFS 算法進行調(diào)度，記錄執(zhí)行整個任務(wù)所花費的總時間。

在圖4 中可以看出，在只有10 個查詢?nèi)蝿?wù)組成的負載情況下，當(dāng)MPL=3，4，5 時，各個算法執(zhí)行情況下負載完成總時間差異不是很大，這是因為負載數(shù)量較少，不能很好地體現(xiàn)各個算法之間的優(yōu)劣。

圖4 10 個查詢?nèi)蝿?wù)在不同MPL 情況下的總完成時間Fig.4 Total time of 10 queries with different MPL

為了更好地分析高并行級別時的交互作用，需要首先增加負載的數(shù)量，為每個查詢類型分別生成了6 個查詢語句實例，總共60 個查詢?nèi)蝿?wù)實例。假設(shè)60 個查詢語句按照輪流加載1 個查詢類型實例的順序到達，調(diào)度工具可以預(yù)先知道即將到來的10 個查詢?nèi)蝿?wù)的類型。

分別在不同的并行級別用三種算法進行調(diào)度，每次調(diào)度時對即將到來的10 個查詢實例分別計算加入到正在運行的任務(wù)中所產(chǎn)生的交互成本IC，選擇交互成本最小的查詢?nèi)蝿?wù)加入執(zhí)行隊列，記錄執(zhí)行所有負載所花費的總時間。實驗結(jié)果如圖5 所示。

圖5 60 個查詢?nèi)蝿?wù)在不同MPL 情況下的總完成時間Fig.5 Total time of 60 queries with different MPL

通過以上實驗數(shù)據(jù)可以知道，ICMF 算法與最短時間優(yōu)先算法和先到先執(zhí)行算法比較，ICMF 算法能夠較大幅度地提升系統(tǒng)性能，通過消除并行查詢之間的消極影響，能夠顯著提高系統(tǒng)的吞吐率，并且隨著并行級別的提升，其優(yōu)勢也更加明顯。但同時伴隨著并行級別的提升，查詢之間的交互作用也更加復(fù)雜，因此下一步工作將對更高級別的并行查詢交互進行實驗和探索。

5 結(jié)束語

首先回顧了查詢調(diào)度領(lǐng)域的相關(guān)研究工作，在此基礎(chǔ)上通過實驗證明了并行查詢之間的交互作用會對系統(tǒng)性能產(chǎn)生非常巨大的影響。因此，在進行并行查詢性能優(yōu)化時考慮這些交互作用是非常有必要的。引入了一個并行查詢負載的性能指標(biāo)(IC)來度量查詢之間的交互成本，并提出了一個交互成本最低優(yōu)先(ICMF)的調(diào)度算法，通過本算法可以對數(shù)據(jù)庫系統(tǒng)中的并行查詢實現(xiàn)較為理想的任務(wù)調(diào)度。實驗結(jié)果表明，交互成本最小優(yōu)先的調(diào)度算法是一種有效的任務(wù)調(diào)度算法，比傳統(tǒng)的查詢調(diào)度方法在整體性能上有較為顯著的提升。

［1］Ahmad M，Aboulnaga A，Babu S.Query interactions in database workloads［C］∥Processings of the Workshop on Testing Database Systems，Providence，Rhode Island，USA，2009.

［2］曹陽，方強，王國仁，等.基于遺傳算法的多連接表達式并行查詢優(yōu)化［J］.軟件學(xué)報，2002，13(2):250－257.Cao Yang，F(xiàn)ang Qiang，Wang Guo－ren，et al.Parallel query optimization techniques for multi－join expressions based on genetic algorithm［J］.Journal of Software，2002，13(2):250－257.

［3］張麗，楊樹強，李愛平，等.海量數(shù)據(jù)管理平臺MDMP 中并行加載與查詢技術(shù)研究［J］.計算機研究與發(fā)展，2007，44(Suppl.):475－480.Zhang Li，Yang Shu－qiang，Li Ai－ping，et al.Parallel data loading and query techniques in massive data management platform［J］.Journal of Computer Research and Development，2007，44(Suppl.):475－480.

［4］Chi Y，Moon H J，Hacigumus H.iCBS:incremental cost based scheduling under piecewise linear slas［J］.Proceedings of the VLDB Endowment，2011，4(9):563－574.

［5］Bianca Schroeder，Mor Harchol－Balter，Arun Iyengar，et al.How to determine a good multi－programming level for external scheduling［C］∥Proceedings of ICDE，2006.

［6］Ahmad M，Aboulnaga A，Babu S，et al.Modeling and exploiting query interactions in database systems［C］∥Proceedings of CIKM，2008:183－192.

［7］Ahmad M，Duan S，Aboulnaga A，et al.Interactionaware prediction of business intelligence workload completion times［C］∥Proceedings of ICDE，2010:413－416.

［8］Tozer S，Brecht T，Aboulnaga A.Q－cop:avoiding bad query mixes to minimize client timeouts under heavy loads［C］∥Proceedings of ICDE，2010:397－408.

［9］Duggan J，Cetintemel U，Papaemmanouil O，et al.Performance prediction for concurrent database workloads［C］∥In SIGMOD Conference，2011:337－348.

［10］張延松，張宇，黃偉，等.分布式聚集函數(shù)支持的內(nèi)存OLAP 并行查詢處理技術(shù)［J］.軟件學(xué)報，2009，20(Suppl.):165－175.Zhang Yan－song，Zhang Yu，Huang Wei，et al.Distributed aggregate functions enabled parallel mainmemory OLAP query processing technique［J］.Journal of Software，2009，20(Suppl.):165－175.

［11］閆鶯，金澈清，曹鋒，等.多數(shù)據(jù)流上共享窗口連接查詢的降載策略［J］.計算機研究與發(fā)展，2004，41(10):1836－1841.Yan Ying，Jin Che－qing，Cao Feng，et al.Load shedding for shared window joins over data streams［J］.Journal of Computer Research and Development，2004，41(10):1836－1841.

［12］TPC－H benchmark specification［DB/OL］.http://www.tpc.org/tpch

［13］Ganapathi A，Kuno H，Dayal U，et al.Predicting multiple metrics for queries:Better decisions enabled by machine learning［C］∥In Proceedings of ICDE，2009:592－603.

［14］Babu S，Borisov N，Duan S，et al.Automated experiment－driven management of(database)systems［C］∥Proceedings of the Workshop on Hot Topics in Operating Systems，2009.

［15］WEKA workbench［DB/OL］.http://www.cs.waikato.ac.nz/ml/weka/.

［16］Sheikh M B，Minhas U F，Khan O Z，et al.A bayesian approach to online performance modeling for database appliances using gaussian models［C］∥International Conference on Autonomic Computing，2011:121－130.