張青峰，許 靜，李珊珊

(南開(kāi)大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，天津300071)

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

(1)單獨(dú)運(yùn)行(MPL=1)

首先，通過(guò)實(shí)驗(yàn)獲得每個(gè)查詢類(lèi)單獨(dú)運(yùn)行(MPL=1)時(shí)的平均運(yùn)行時(shí)間。

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

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

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

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

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

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

用Ti表示Qi單獨(dú)運(yùn)行時(shí)的執(zhí)行時(shí)間，Ti/j表示Qi與Qj并行時(shí)的執(zhí)行時(shí)間，則可以ΔTi/j來(lái)表示Qi與Qj并行時(shí)的變化。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表5 不同查詢組合的平均運(yùn)行時(shí)間Table 5 Average completion time of different query mixes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入:并行負(fù)載W，由N 個(gè)查詢組成。

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

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

4 試驗(yàn)及分析

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

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

4.1 實(shí)驗(yàn)環(huán)境

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

4.2 實(shí)驗(yàn)數(shù)據(jù)和查詢負(fù)載

實(shí)驗(yàn)基于TPC－H 測(cè)試標(biāo)準(zhǔn)，生成了10 G 大小的TPC－H 測(cè)試數(shù)據(jù)庫(kù)。TPC－H 提供了DBGEN 工具來(lái)生成測(cè)試數(shù)據(jù)，并且保證生成的數(shù)據(jù)是均勻分布的。查詢負(fù)載是通過(guò)QGEN 工具來(lái)生成的，因?yàn)門(mén)PC－H 使用均勻分布的數(shù)據(jù)和查詢參數(shù)，因此對(duì)一個(gè)特定的查詢類(lèi)型來(lái)說(shuō)，不同參數(shù)的查詢實(shí)例的執(zhí)行時(shí)間的差異是可以忽略不計(jì)的。

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

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

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

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

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

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

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

M=2 時(shí)各算法并行執(zhí)行時(shí)序圖見(jiàn)圖1，圖1中，括號(hào)內(nèi)數(shù)字表示執(zhí)行時(shí)間?？梢钥闯觯贛=2 時(shí)，各種算法執(zhí)行過(guò)程中的調(diào)度順序差別非常大，而正是因?yàn)閳?zhí)行順序的不同，導(dǎo)致了查詢之間不同的交互作用，從而使整個(gè)負(fù)載的完成時(shí)間出現(xiàn)了較大的差異。

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

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

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

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

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

(2)高并行級(jí)別時(shí)(MPL ＞2)

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

首先回顧了查詢調(diào)度領(lǐng)域的相關(guān)研究工作，在此基礎(chǔ)上通過(guò)實(shí)驗(yàn)證明了并行查詢之間的交互作用會(huì)對(duì)系統(tǒng)性能產(chǎn)生非常巨大的影響。因此，在進(jìn)行并行查詢性能優(yōu)化時(shí)考慮這些交互作用是非常有必要的。引入了一個(gè)并行查詢負(fù)載的性能指標(biāo)(IC)來(lái)度量查詢之間的交互成本，并提出了一個(gè)交互成本最低優(yōu)先(ICMF)的調(diào)度算法，通過(guò)本算法可以對(duì)數(shù)據(jù)庫(kù)系統(tǒng)中的并行查詢實(shí)現(xiàn)較為理想的任務(wù)調(diào)度。實(shí)驗(yàn)結(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áng)，方強(qiáng)，王國(guó)仁，等.基于遺傳算法的多連接表達(dá)式并行查詢優(yōu)化［J］.軟件學(xué)報(bào)，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ù)強(qiáng)，李?lèi)?ài)平，等.海量數(shù)據(jù)管理平臺(tái)MDMP 中并行加載與查詢技術(shù)研究［J］.計(jì)算機(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é)報(bào)，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］.計(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.