劉冬燕，牛保寧+，張錦文

(1.太原理工大學(xué) 信息與計(jì)算機(jī)學(xué)院，山西 晉中 030600；2.北方自動(dòng)控制技術(shù)研究所 軟件研發(fā)部，山西 太原 030006)

0 引 言

數(shù)據(jù)庫(kù)管理任務(wù)依據(jù)查詢響應(yīng)時(shí)間，結(jié)合系統(tǒng)優(yōu)化配置的目標(biāo)，選擇下一步要執(zhí)行的任務(wù)，為數(shù)據(jù)庫(kù)的性能管理提供決策支持[1]。查詢響應(yīng)時(shí)間由使用資源時(shí)間和等待資源時(shí)間[2]組成，詳述查詢執(zhí)行過(guò)程的查詢計(jì)劃決定了查詢使用資源的時(shí)間，并行運(yùn)行查詢會(huì)產(chǎn)生查詢交互[3-5]，直接影響查詢等待資源的時(shí)間。因此，對(duì)查詢響應(yīng)時(shí)間建模應(yīng)將查詢計(jì)劃、查詢交互納入考慮。

經(jīng)過(guò)數(shù)十年的研究，查詢響應(yīng)時(shí)間預(yù)測(cè)模型按建模理論可分為：分析模型和統(tǒng)計(jì)模型[6]。分析模型簡(jiǎn)化資源爭(zhēng)用降低復(fù)雜度，使得模型預(yù)測(cè)準(zhǔn)確率較統(tǒng)計(jì)模型低[7]?，F(xiàn)有統(tǒng)計(jì)模型將查詢交互信息映射成查詢響應(yīng)時(shí)間，采集樣本訓(xùn)練預(yù)先確定好的模型函數(shù)，其預(yù)先確定的模型函數(shù)限制了對(duì)樣本的擬合精度，該模型僅對(duì)查詢交互進(jìn)行擬合忽略了查詢本身所具有的信息，多數(shù)統(tǒng)計(jì)模型無(wú)法應(yīng)對(duì)訓(xùn)練集中未出現(xiàn)過(guò)的查詢。人工神經(jīng)網(wǎng)絡(luò)無(wú)需預(yù)先確定模型函數(shù)，通過(guò)對(duì)樣本集自學(xué)習(xí)來(lái)擬合模型函數(shù)[8,9]?，F(xiàn)有人工神經(jīng)網(wǎng)絡(luò)僅能預(yù)測(cè)單個(gè)查詢的響應(yīng)時(shí)間，而典型的工作負(fù)載包含多個(gè)查詢并行運(yùn)行。根據(jù)對(duì)數(shù)十年查詢響應(yīng)時(shí)間相關(guān)文獻(xiàn)的研究可知，當(dāng)前數(shù)據(jù)庫(kù)領(lǐng)域還沒(méi)有研究者提出使用人工神經(jīng)網(wǎng)絡(luò)模型預(yù)測(cè)并行查詢響應(yīng)時(shí)間。

聯(lián)機(jī)分析處理(online analytical processing，OLAP)系統(tǒng)通過(guò)對(duì)數(shù)據(jù)的多維分析為決策提供依據(jù)，需周期性地批量運(yùn)行固定查詢。本文以O(shè)LAP系統(tǒng)這一特定場(chǎng)景為對(duì)象，針對(duì)統(tǒng)計(jì)模型存在的問(wèn)題，結(jié)合查詢計(jì)劃、查詢交互兩大要素，研究用全連接神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)并行查詢響應(yīng)時(shí)間。

本文的主要貢獻(xiàn)如下：

(1)提出用全連接神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)并行查詢的響應(yīng)時(shí)間。采用全連接神經(jīng)網(wǎng)絡(luò)，訓(xùn)練網(wǎng)絡(luò)建立模型，進(jìn)行預(yù)測(cè)；

(2)采用查詢計(jì)劃特征分量描述查詢的資源需求、查詢交互特征分量描述查詢之間的資源爭(zhēng)用，共同構(gòu)成神經(jīng)網(wǎng)絡(luò)的輸入特征向量；

(3)本文所提全連接神經(jīng)網(wǎng)絡(luò)模型可實(shí)現(xiàn)對(duì)并行查詢響應(yīng)時(shí)間的動(dòng)態(tài)預(yù)測(cè)，直接抽取包含新查詢查詢組合的查詢計(jì)劃特征、查詢交互特征，輸入到模型中實(shí)現(xiàn)動(dòng)態(tài)預(yù)測(cè)。

訓(xùn)練好全連接神經(jīng)網(wǎng)絡(luò)后，進(jìn)行了多組模型預(yù)測(cè)的實(shí)驗(yàn)，結(jié)果表明全連接神經(jīng)網(wǎng)絡(luò)模型預(yù)測(cè)準(zhǔn)確率優(yōu)于代表性統(tǒng)計(jì)模型，一定程度上說(shuō)明了全連接神經(jīng)網(wǎng)絡(luò)模型的可行性。

1 相關(guān)研究

1.1 查詢響應(yīng)時(shí)間預(yù)測(cè)模型

現(xiàn)有查詢響應(yīng)時(shí)間預(yù)測(cè)模型分為：分析模型與統(tǒng)計(jì)模型。

分析模型建立在數(shù)據(jù)庫(kù)成本模型之上，結(jié)合查詢計(jì)劃所涉及到操作工作量轉(zhuǎn)化為查詢的響應(yīng)時(shí)間。并行分析模型中，并行運(yùn)行的查詢存在查詢交互導(dǎo)致建模過(guò)程復(fù)雜，而現(xiàn)有的研究丟棄了查詢的部分特征，使得模型預(yù)測(cè)準(zhǔn)確率較統(tǒng)計(jì)模型低[2]。

統(tǒng)計(jì)模型預(yù)先確定數(shù)學(xué)模型函數(shù)，通過(guò)采集樣本對(duì)模型函數(shù)進(jìn)行訓(xùn)練。并行查詢響應(yīng)時(shí)間預(yù)測(cè)中，最為代表性的統(tǒng)計(jì)模型是張錦文等提出的相似性模型[2]，對(duì)查詢交互進(jìn)行量化分析并在此基礎(chǔ)上建立相似性模型。該模型從查詢響應(yīng)時(shí)間的樣本庫(kù)中選取包含該查詢的K個(gè)組合的響應(yīng)時(shí)間，取均值作為目標(biāo)查詢的響應(yīng)時(shí)間。與分析模型相比，統(tǒng)計(jì)模型建模不需要分析查詢計(jì)劃及其涉及到的操作，通過(guò)采集樣本對(duì)統(tǒng)計(jì)模型函數(shù)進(jìn)行訓(xùn)練得到模型、進(jìn)行預(yù)測(cè)。模型預(yù)測(cè)準(zhǔn)確率較高，但是統(tǒng)計(jì)模型缺點(diǎn)在于，不知道預(yù)先確定的模型函數(shù)是否適合樣本，使得模型準(zhǔn)確率無(wú)法提高。

循環(huán)神經(jīng)網(wǎng)絡(luò)模型[10]按建模理論來(lái)講屬于統(tǒng)計(jì)模型的一種，但不同于一般的統(tǒng)計(jì)模型，不需要提前設(shè)定模型函數(shù)，僅對(duì)樣本集學(xué)習(xí)就能建立模型,但該模型僅對(duì)單個(gè)查詢響應(yīng)時(shí)間進(jìn)行預(yù)測(cè)，實(shí)用性低。

1.2 模型特征的提取

不同的模型需要選取不同的特征與之匹配。分析模型、循環(huán)神經(jīng)網(wǎng)絡(luò)模型均對(duì)查詢計(jì)劃進(jìn)行分析，模型特征細(xì)化到查詢操作符。

統(tǒng)計(jì)模型僅擬合查詢交互，選取查詢交互信息作為特征。相似性模型用QueryRating[2,11]來(lái)度量查詢交互。并行程度大于2時(shí)，根據(jù)查詢受到的直接影響、間接影響將所涉及到的QueryRating特征壓縮成二維特征。

分析模型提供了一個(gè)白盒視角，顯示地表達(dá)數(shù)據(jù)庫(kù)系統(tǒng)的工作機(jī)制；統(tǒng)計(jì)模型提供了一個(gè)黑盒的視角，隱式地表達(dá)了查詢交互的影響。

1.3 模型動(dòng)態(tài)性

在分析模型中，如果出現(xiàn)新查詢，為適應(yīng)該查詢，則所有對(duì)查詢的估計(jì)值都將頻繁發(fā)生變化[9]，導(dǎo)致估計(jì)不準(zhǔn)確。并行分析模型隨著并行程度的增加，管道數(shù)量劇增，由于查詢交互每個(gè)管道的成本須做相應(yīng)調(diào)整，建模復(fù)雜度高，使得模型可用性降低，甚至變得不可用。

目前，實(shí)現(xiàn)并行查詢響應(yīng)時(shí)間預(yù)測(cè)的統(tǒng)計(jì)模型主要有線性模型、高斯交互模型、適應(yīng)性交互模型、B2L模型、相似性模型。除相似性模型之外，其余模型僅能實(shí)現(xiàn)對(duì)已有查詢的預(yù)測(cè)，無(wú)法應(yīng)對(duì)訓(xùn)練集中未出現(xiàn)過(guò)的查詢，動(dòng)態(tài)性差。

2 問(wèn)題與方法

數(shù)據(jù)庫(kù)系統(tǒng)中，查詢不斷地進(jìn)出，一個(gè)查詢可能會(huì)包含在多個(gè)查詢組合中運(yùn)行完成，對(duì)查詢響應(yīng)時(shí)間的預(yù)測(cè)只能是對(duì)查詢?cè)诋?dāng)前所處的查詢組合中持續(xù)運(yùn)行到結(jié)束的時(shí)間。當(dāng)查詢組合發(fā)生變化，查詢響應(yīng)時(shí)間需要做出更新。本節(jié)針對(duì)上述問(wèn)題分兩步完成：對(duì)固定查詢組合中每個(gè)查詢響應(yīng)時(shí)間進(jìn)行預(yù)測(cè)；基于固定查詢組合動(dòng)態(tài)實(shí)現(xiàn)可變查詢組合中查詢響應(yīng)時(shí)間預(yù)測(cè)。第2.1節(jié)詳細(xì)介紹上述問(wèn)題并提出解決思路，第2.2節(jié)介紹全連接神經(jīng)網(wǎng)絡(luò)模型的相關(guān)知識(shí)，第2.3節(jié)、2.4節(jié)分別對(duì)固定查詢組合、可變查詢組合下查詢響應(yīng)時(shí)間的問(wèn)題進(jìn)行定義并提出解決方案。表1是對(duì)本文所涉及到主要概念的說(shuō)明。

表1 相關(guān)術(shù)語(yǔ)描述

2.1 問(wèn)題與解決思路

數(shù)據(jù)庫(kù)系統(tǒng)中，并行運(yùn)行的查詢?cè)趫?zhí)行過(guò)程中，一些查詢結(jié)束執(zhí)行，新的查詢進(jìn)入，查詢組合不斷改變，同一查詢的運(yùn)行過(guò)程可能會(huì)經(jīng)歷多個(gè)不同查詢組合。由于查詢的進(jìn)出是未知的，因此，這里對(duì)查詢響應(yīng)時(shí)間的預(yù)測(cè)是指：某一時(shí)刻，查詢?cè)诋?dāng)前組合中運(yùn)行到結(jié)束的時(shí)間，再加上查詢已經(jīng)運(yùn)行的時(shí)間。如圖1所示，T1時(shí)刻，查詢1結(jié)束，查詢2進(jìn)入，與查詢5、查詢3組成新查詢組合(5，2，3)。查詢5經(jīng)歷(5，1，3)與(5，2，3)兩個(gè)查詢組合，其響應(yīng)時(shí)間等于這兩個(gè)組合中查詢5的運(yùn)行時(shí)間和。

圖1 3個(gè)查詢并行運(yùn)行示例

查詢?cè)诋?dāng)前組合中從開(kāi)始一直運(yùn)行到結(jié)束的時(shí)間，本文稱之為查詢?cè)诠潭ú樵兘M合中的響應(yīng)時(shí)間。T1時(shí)刻，對(duì)查詢5的響應(yīng)時(shí)間預(yù)測(cè)由兩部分組成：查詢5在組合(5，2，3) 中運(yùn)行到結(jié)束的時(shí)間T2-T1，查詢5在組合 (5，1，3) 中已經(jīng)運(yùn)行的時(shí)間T1-T0。查詢5實(shí)際在組合(5，2，3)中的運(yùn)行時(shí)間T2-T1是它在固定查詢組合 (5，2，3) 中的響應(yīng)時(shí)間，減去它在組合(5，1，3)中已完成工作的時(shí)間。這要求計(jì)算查詢?cè)谇懊娼M合中所完成工作占整個(gè)工作的比例。

數(shù)據(jù)庫(kù)系統(tǒng)中，查詢的執(zhí)行速度是復(fù)雜多變的，精確計(jì)算查詢?cè)谝呀?jīng)歷的組合中所完成工作占整個(gè)工作的比例需要為查詢執(zhí)行速度建模，并非易事，不在本文的討論范圍。為了實(shí)現(xiàn)對(duì)并行查詢響應(yīng)時(shí)間的預(yù)測(cè)，本文假設(shè)查詢的執(zhí)行速度是勻速的。假設(shè)查詢5在固定查詢組合(5，1，3)、(5，2，3)的響應(yīng)時(shí)間已知分別為t、t1， (T1-T0)/t得出查詢5在固定查詢組合(5，1，3)完成的工作量， 1-(T1-T0)/t 計(jì)算出查詢5未完成的工作量即，查詢5在查詢組合(5，2，3)需要執(zhí)行的工作量， (1-(T1-T0)/t)*t1得出T1時(shí)刻查詢5的剩余運(yùn)行時(shí)間。通過(guò)對(duì)查詢5響應(yīng)時(shí)間的分析，可知查詢響應(yīng)時(shí)間的預(yù)測(cè)需分兩步實(shí)現(xiàn)：第一，完成固定查詢組合下查詢響應(yīng)時(shí)間的預(yù)測(cè)；第二，在實(shí)現(xiàn)固定查詢組合預(yù)測(cè)的基礎(chǔ)上，估計(jì)查詢的剩余工作量，實(shí)現(xiàn)對(duì)可變查詢組合預(yù)測(cè)。

進(jìn)行預(yù)測(cè)之前，我們需要對(duì)全連接神經(jīng)網(wǎng)絡(luò)進(jìn)行設(shè)計(jì)。

2.2 全連接神經(jīng)網(wǎng)絡(luò)

2.2.1 網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)

建立全連接神經(jīng)網(wǎng)絡(luò)需要確定網(wǎng)絡(luò)層結(jié)構(gòu)、輸入特征、預(yù)測(cè)標(biāo)簽、超參數(shù)。層結(jié)構(gòu)的關(guān)鍵在于隱藏層的層數(shù)，增加隱藏層會(huì)使得訓(xùn)練時(shí)間延長(zhǎng)且容易出現(xiàn)過(guò)擬合，一般情況下，優(yōu)先選用只有一個(gè)隱藏層的網(wǎng)絡(luò)，通過(guò)增加節(jié)點(diǎn)數(shù)來(lái)降低誤差；George Cybenko證明僅有一個(gè)隱藏層的人工神經(jīng)網(wǎng)絡(luò)，通過(guò)增加節(jié)點(diǎn)數(shù)能夠逼近任意函數(shù)。因此，本文采用只有一個(gè)隱藏層的網(wǎng)絡(luò)，如圖2所示。輸入層由QPF、QIF共同組成，其輸入節(jié)點(diǎn)數(shù)為10 425(詳見(jiàn)2.2.2節(jié))。

圖2 網(wǎng)絡(luò)結(jié)構(gòu)

2.2.2 輸入特征、預(yù)測(cè)標(biāo)簽設(shè)計(jì)

本文采集查詢計(jì)劃相關(guān)操作與查詢交互數(shù)據(jù)共同作為全連接神經(jīng)網(wǎng)絡(luò)模型的輸入特征。查詢組合的輸入特征設(shè)計(jì)為QPF、QIF。

QPF是一個(gè)查詢的查詢計(jì)劃構(gòu)成的特征。查詢中的每個(gè)操作由以下4部分組成：操作的類型、操作涉及到的表、列以及結(jié)果行的平均寬度[11]。其中，操作的類型，例如Seq Scan、Hash Join等，本文所用的PostgreSQL數(shù)據(jù)庫(kù)共有34種操作類型，將操作對(duì)應(yīng)類型的位置置1，其余為0；操作涉及到的表，TPC-H[12]中共有8張表，涉及到的表對(duì)應(yīng)位置置1，其余為0；操作涉及到的列共有61個(gè)，對(duì)應(yīng)位置置1，其余置為0；操作涉及到的結(jié)果行的平均寬度劃分20個(gè)區(qū)域，區(qū)域間隔10，操作涉及到的寬度對(duì)應(yīng)位置置為1，其余為0。本文選取的查詢模板最多含有25種操作，每個(gè)操作信息包含123位分別是34個(gè)操作類型、8張表、61個(gè)列、20個(gè)結(jié)果行平均寬度之和。經(jīng)計(jì)算，一個(gè)含有25種操作類型的查詢共有3075位。

QueryRating是查詢兩兩并行運(yùn)行時(shí)的響應(yīng)時(shí)間與單獨(dú)運(yùn)行響應(yīng)時(shí)間的比值，可用如式(1)所示

ri/j=ti/j/ti

(1)

式中：ti/j表示查詢i與j并行時(shí)，i的響應(yīng)時(shí)間；ti表示查詢i單獨(dú)運(yùn)行時(shí)的響應(yīng)時(shí)間；ri/j則是對(duì)查詢i的量化值，反映查詢之間資源爭(zhēng)用的強(qiáng)弱程度，當(dāng)ri/j>1 說(shuō)明查詢i與查詢j存在資源競(jìng)爭(zhēng)關(guān)系，反之說(shuō)明查詢i與查詢j存在資源合作關(guān)系。

QIF是一個(gè)查詢受其它查詢影響的QueryRating值所形成的組合。實(shí)驗(yàn)統(tǒng)計(jì)QueryRating值最大不超過(guò)200，因此，計(jì)算查詢QueryRating值將其對(duì)應(yīng)1到200個(gè)位置中相應(yīng)的位置置1，其余置0。例如，查詢組合 (Q1，Q2，Q3)， 則其輸入特征為 (QPF1,QIF1,QPF2,QIF2,QPF3,QIF3)。 為了便于計(jì)算，本文對(duì)少于25個(gè)操作類型的查詢采取補(bǔ)零方法補(bǔ)成3075位。每一個(gè)QIF含有兩個(gè)QueryRating值共400位，如Q1的QIF包含(QueryRatingQ1,Q2,Query-RatingQ1,Q3)。所以3個(gè)查詢并行運(yùn)行，其輸入神經(jīng)元的個(gè)數(shù)為3*(3075+400) 等于10 425。

訓(xùn)練神經(jīng)網(wǎng)絡(luò)模型時(shí)，除了需要特征向量，還需要預(yù)測(cè)標(biāo)簽也就是模型的輸出，本文采用直接預(yù)測(cè)時(shí)間的方法。一個(gè)查詢組合有m個(gè)查詢，那么預(yù)測(cè)標(biāo)簽則為與之對(duì)應(yīng)的m個(gè)響應(yīng)時(shí)間。

2.3 固定查詢組合預(yù)測(cè)

2.3.1 問(wèn)題定義

我們通過(guò)例子來(lái)說(shuō)明本節(jié)要解決的問(wèn)題，如圖3所示，假設(shè)有3個(gè)查詢1、2、3同時(shí)運(yùn)行，每有查詢結(jié)束則繼續(xù)向系統(tǒng)提交該查詢，保持查詢組合不變。預(yù)測(cè)固定查詢組合(1，2，3)中查詢1、2、3各自的響應(yīng)時(shí)間。

圖3 固定查詢組合運(yùn)行示例

根據(jù)上述問(wèn)題，將預(yù)測(cè)問(wèn)題定義為：

定義1 問(wèn)題定義：查詢集合S={Qi|i=1,2,…,M}， 并行程度為M，則將查詢集合S中的M個(gè)查詢提交到數(shù)據(jù)庫(kù)運(yùn)行，運(yùn)行過(guò)程中查詢組合保持不變，分別預(yù)測(cè)M個(gè)查詢的響應(yīng)時(shí)間。

2.3.2 解決方案

本節(jié)通過(guò)全連接神經(jīng)網(wǎng)絡(luò)模型來(lái)預(yù)測(cè)固定查詢組合下查詢的響應(yīng)時(shí)間，如圖4所示。獲取查詢計(jì)劃、查詢交互結(jié)果數(shù)據(jù)(OLAP系統(tǒng)中抽取)，將這兩部分?jǐn)?shù)據(jù)按照2.2.2節(jié)編碼成模型的輸入特征，輸入到全連接神經(jīng)網(wǎng)絡(luò)模型中進(jìn)行訓(xùn)練，得出模型。對(duì)于待測(cè)試的查詢組合，組合查詢的查詢計(jì)劃特征、查詢交互特征輸入到模型，預(yù)測(cè)出查詢組合中各查詢的響應(yīng)時(shí)間。

圖4 模型框架

2.4 可變查詢組合預(yù)測(cè)

2.4.1 問(wèn)題定義

由第2.1節(jié)圖1可知，查詢5經(jīng)歷了(5,1,3)與(5,2,3)兩個(gè)查詢組合，在不同組合中資源的爭(zhēng)用情況不同，顯然在查詢組合(5,1,3)時(shí)采用全連接神經(jīng)網(wǎng)絡(luò)模型給出查詢5響應(yīng)時(shí)間不能準(zhǔn)確反映其真實(shí)的響應(yīng)時(shí)間。對(duì)可變查詢組合的預(yù)測(cè)問(wèn)題就演變查詢1結(jié)束時(shí)，對(duì)查詢5的剩余時(shí)間估計(jì)。

根據(jù)以上描述，將預(yù)測(cè)問(wèn)題定義為：

定義2 問(wèn)題定義：查詢集合S={Qi|i=1,2,…,N}， 并行程度為M，則從查詢集合S中隨機(jī)選M個(gè)查詢提交到數(shù)據(jù)庫(kù)運(yùn)行；當(dāng)某一個(gè)查詢運(yùn)行完成，數(shù)據(jù)庫(kù)系統(tǒng)從剩余N-M個(gè)查詢中隨機(jī)選取一個(gè)與正在運(yùn)行的查詢組成新的查詢組合并估計(jì)不包含新查詢的其它查詢的剩余時(shí)間。

2.4.2 解決方案

針對(duì)可變查詢組合響應(yīng)時(shí)間預(yù)測(cè)問(wèn)題，使用全連接神經(jīng)網(wǎng)絡(luò)模型與剩余時(shí)間估計(jì)方法(式(2))共同實(shí)現(xiàn)對(duì)查詢剩余時(shí)間的估計(jì)[11]。同時(shí)記錄初始時(shí)刻、每個(gè)查詢的結(jié)束時(shí)間、查詢?cè)诿總€(gè)線程中的執(zhí)行順序與所經(jīng)歷的組合數(shù)，結(jié)合算法1給出查詢隊(duì)列中所有查詢的響應(yīng)時(shí)間

(2)

式中：查詢Qi包含于Com1與Com2兩個(gè)組合，當(dāng)查詢Com1組合中有一個(gè)查詢結(jié)束時(shí)，對(duì)查詢Qi的剩余時(shí)間進(jìn)行估計(jì)；其中，T右上標(biāo)的f、i分別代表查詢Qi在查詢組合ComX(X=1、2) 中已運(yùn)行的時(shí)間、固定查詢組合中的響應(yīng)時(shí)間；前兩部分時(shí)間的比值代表查詢Qi完成的任務(wù)量；1減去比值那部分代表查詢Qi剩余的任務(wù)量；由于Qi的完成時(shí)間包含在兩個(gè)查詢組合中，不同組合中受到的查詢交互不同，存在總?cè)蝿?wù)量大于1的情況，采用tanh()函數(shù)確保剩余的任務(wù)量范圍在(0，1)之間。

具體實(shí)現(xiàn)如下：

(1)某一查詢結(jié)束，新查詢到來(lái)時(shí)判斷新查詢組合是否在固定查詢組合響應(yīng)時(shí)間樣本庫(kù)中：如果在，取出樣本庫(kù)中的查詢的響應(yīng)時(shí)間；如果不存在，調(diào)用全連接神經(jīng)網(wǎng)絡(luò)模型給出預(yù)測(cè)；

(2)依據(jù)式(2)剩余時(shí)間估計(jì)方法，給出查詢組合中未運(yùn)行完成查詢的剩余時(shí)間，加上查詢已運(yùn)行的時(shí)間預(yù)測(cè)出查詢的剩余時(shí)間；

(3)判斷查詢隊(duì)列是否結(jié)束，若沒(méi)結(jié)束，循環(huán)上述兩步估計(jì)查詢的剩余時(shí)間，直到查詢結(jié)束。

完成查詢隊(duì)列中查詢剩余時(shí)間的估計(jì)后，結(jié)合算法1給出查詢隊(duì)列中每個(gè)查詢的響應(yīng)時(shí)間。其中，第(1)行變量初始化；第(2)行～第(10)行依次計(jì)算Nc-1個(gè)查詢的響應(yīng)時(shí)間；其中第(3)行～第(9)行計(jì)算m+1線程中所有查詢的響應(yīng)時(shí)間；第(4)行～第(6)行，獲取查詢所涉及到的組合數(shù)并賦值給cur，arr[cur]取出第cur個(gè)時(shí)間，arr[per] 取出開(kāi)始時(shí)間，兩部分差值得到查詢的響應(yīng)時(shí)間，同時(shí)將cur賦值給per，下一個(gè)的cur等于賦值后的per加上查詢涉及到的組合數(shù)；第(7)行記錄查詢的響應(yīng)時(shí)間；第(8)行，記錄查詢的個(gè)數(shù)。第(11)行返回所有查詢的響應(yīng)時(shí)間。

算法1： 計(jì)算查詢響應(yīng)時(shí)間的算法

輸入：

arr[1,…,nt,…,p] //初始時(shí)刻與每個(gè)查詢依次完成時(shí)刻的組合

i[1,…,nt,…,Nc][1,…,n1c,…,N1c][1,…,n2c,…,N2c]

//線程， 查詢ID， 查詢經(jīng)歷的組合數(shù)

輸出：

{time}1i//time是i個(gè)查詢的響應(yīng)時(shí)間

Begin

(1) per←0,i←1

(2)form=0 to Nc-1do

(3)forn=0 to N1c-1do

(4) cur←per + i[m][n][1]

(5) t←arr[cur]-arr[per]

(6) per←cur

(7) time←t

(8) i++

(9)endfor

(10)endfor

(11) return {time}1i

End

3 實(shí)驗(yàn)分析與驗(yàn)證

本章3.1節(jié)介紹實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集，3.2節(jié)介紹對(duì)模型的評(píng)估，3.3節(jié)介紹相關(guān)實(shí)驗(yàn)設(shè)計(jì)與實(shí)現(xiàn)。

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

實(shí)驗(yàn)采用Java與Python語(yǔ)言共同開(kāi)發(fā)，系統(tǒng)環(huán)境為Windows10，處理器為Inter(R) pentium(R) CPU G4400@3.30 GHz 3.31 GHz實(shí)驗(yàn)數(shù)據(jù)來(lái)源于TPC-H，選用PostgreSQL數(shù)據(jù)庫(kù)、大小10 GB。

人工神經(jīng)網(wǎng)絡(luò)通常需要采集大量的數(shù)據(jù)進(jìn)行訓(xùn)練，因此本文在22個(gè)查詢模板的基礎(chǔ)上增加了單表查詢、多表連接、表的聚合操作查詢，有助于統(tǒng)計(jì)更多的查詢組合數(shù)據(jù)，提高模型的擬合能力。實(shí)驗(yàn)從25個(gè)查詢模板選取并行程度為3的查詢組成2300個(gè)查詢組合，針對(duì)不同的實(shí)驗(yàn)選取不同覆蓋率的訓(xùn)練樣本進(jìn)行實(shí)驗(yàn)。

3.2 模型評(píng)價(jià)

實(shí)驗(yàn)通過(guò)兩方面來(lái)實(shí)現(xiàn)對(duì)模型的評(píng)估：均方誤差(mean square error，MSE)、Acc。MSE用來(lái)對(duì)數(shù)據(jù)的變化情況進(jìn)行評(píng)估，Acc用來(lái)對(duì)模型預(yù)測(cè)的準(zhǔn)確率進(jìn)行評(píng)估(并行度為3時(shí)準(zhǔn)確率的計(jì)算公式)。具體實(shí)現(xiàn)如式(3)、式(4)所示

(3)

(4)

式(3)中，MSE是預(yù)測(cè)值與真實(shí)值差值平方的期望；式(4)中，Acc是對(duì)待預(yù)測(cè)查詢組合中所有查詢響應(yīng)時(shí)間預(yù)測(cè)準(zhǔn)確率的均值。n表示有n個(gè)查詢組合，3n表示n個(gè)查詢組合共有3n個(gè)查詢，pi表示模型預(yù)測(cè)出的查詢i的響應(yīng)時(shí)間，yi為查詢i在查詢組合中真實(shí)運(yùn)行的時(shí)間。MSE值越接近于0，預(yù)測(cè)值越逼近真實(shí)值。Acc越大說(shuō)明模型預(yù)測(cè)越準(zhǔn)確。

3.3 實(shí)驗(yàn)設(shè)計(jì)與分析

3.3.1 全連接神經(jīng)網(wǎng)絡(luò)模型收斂性

采用2300個(gè)查詢組合數(shù)據(jù)的80%作為訓(xùn)練集(訓(xùn)練集的20%作為驗(yàn)證集)，訓(xùn)練模型，得到訓(xùn)練集與驗(yàn)證集的損失變化如圖5所示。

圖5 訓(xùn)練集與有效集的損失

圖5中，橫坐標(biāo)表示查詢組合迭代的次數(shù)，縱坐標(biāo)表示損失，虛線表示訓(xùn)練集損失變化曲線，實(shí)線表示驗(yàn)證集損失變化曲線；隨著迭代次數(shù)增加，模型收斂，訓(xùn)練集和驗(yàn)證集的損失變化趨勢(shì)迅速減小并趨于穩(wěn)定，說(shuō)明預(yù)測(cè)值趨近于真實(shí)值，模型穩(wěn)定。在模型趨于穩(wěn)定的情況下，計(jì)算測(cè)試集的查詢組合的MSE值為0.0043說(shuō)明預(yù)測(cè)值接近于真實(shí)值。

3.3.2 樣本覆蓋率60%情況下3種模型比較

實(shí)驗(yàn)從2300個(gè)查詢組合中選取60%的數(shù)據(jù)作訓(xùn)練集，模擬真實(shí)復(fù)雜數(shù)據(jù)庫(kù)訓(xùn)練集樣本覆蓋率較低的情況。待預(yù)測(cè)查詢組合由復(fù)雜度不同的9個(gè)查詢并行程度為3組成。并行程度為3的查詢組合(Qi，Qj，Qk)，采用相似性模型、僅由查詢計(jì)劃建立的全連接神經(jīng)網(wǎng)絡(luò)模型、本文設(shè)計(jì)的全連接神經(jīng)網(wǎng)絡(luò)模型分別對(duì)待預(yù)測(cè)查詢組合中位于第一、二、三個(gè)位置的Qi、Qj、Qk進(jìn)行預(yù)測(cè)，并計(jì)算這些位置的預(yù)測(cè)準(zhǔn)確率，結(jié)果如圖6所示。

圖6 3種模型預(yù)測(cè)準(zhǔn)確率比較

全連接神經(jīng)網(wǎng)絡(luò)平均預(yù)測(cè)準(zhǔn)確率可達(dá) (72.3%+64.5%+63.85%)/3=66.85%， 僅由查詢計(jì)劃建立的全連接神經(jīng)網(wǎng)絡(luò)模型平均預(yù)測(cè)準(zhǔn)確率為 (56.2%+46.7%+58.89%)/3=53.93%， 相似性模型平均預(yù)測(cè)準(zhǔn)確率為 (62.1%+58.2%+53.2%)/3=57.8%。 在樣本覆蓋率較低的情況下，本文設(shè)計(jì)的全連接神經(jīng)網(wǎng)絡(luò)模型預(yù)測(cè)準(zhǔn)確率較相似性模型和僅由查詢計(jì)劃建立的全連接神經(jīng)網(wǎng)絡(luò)分別高12.92%、18.25%，說(shuō)明了本文選取查詢計(jì)劃與查詢交互共同作為輸入的合理性、必要性。

3.3.3 固定查詢組合預(yù)測(cè)準(zhǔn)確性

實(shí)驗(yàn)對(duì)待預(yù)測(cè)查詢模板為1、4、5、6、8、10、12、14、18選取并行程度為3組成84個(gè)查詢組合。由表2可知相似性模型與全連接神經(jīng)網(wǎng)絡(luò)模型隨著樣本數(shù)量的增加，模型準(zhǔn)確率有所提高。樣本數(shù)量為2300時(shí)，相似性模型的模型準(zhǔn)確率為86%，全連接神經(jīng)網(wǎng)絡(luò)模型準(zhǔn)確率93.79%。

表2 模型準(zhǔn)確率比較

全連接神經(jīng)網(wǎng)絡(luò)模型有較高的準(zhǔn)確率是由于全連接神經(jīng)網(wǎng)絡(luò)自學(xué)習(xí)、擬合能力強(qiáng)且本文的全連接神經(jīng)網(wǎng)絡(luò)模型輸入特征在相似性模型特征的基礎(chǔ)上增加了查詢計(jì)劃，使輸入特征能夠更好得表征查詢。

3.3.4 動(dòng)態(tài)估計(jì)可變查詢組合中查詢的剩余時(shí)間

實(shí)驗(yàn)采用并行程度為3，查詢模板為1、4、5、6、8、10、12、14、18的查詢并行運(yùn)行，如圖7所示。

圖7 隨機(jī)選取3個(gè)查詢并行執(zhí)行

由圖7可知，查詢模板構(gòu)成了7種并行程度為3的查詢組合，某一查詢結(jié)束時(shí)，對(duì)組合中其余查詢剩余時(shí)間進(jìn)行預(yù)測(cè)，其預(yù)測(cè)值與真實(shí)值見(jiàn)表3，其中模型剩余時(shí)間是指全連接神經(jīng)網(wǎng)絡(luò)模型與相似性模型對(duì)待預(yù)測(cè)查詢剩余時(shí)間的估計(jì)。經(jīng)計(jì)算，全連接神經(jīng)網(wǎng)絡(luò)模型預(yù)測(cè)準(zhǔn)確率為79.99%，相似性模型準(zhǔn)確率為73.75%。兩種模型在可變查詢情況下的準(zhǔn)確率均低于固定查詢組合是由于本文對(duì)可變查詢組合研究是基于查詢是勻速執(zhí)行的，勻速執(zhí)行的查詢難以精確估計(jì)查詢?cè)谝呀?jīng)歷的查詢組合中查詢完成的工作量占整個(gè)查詢的比例。

表3 模型剩余時(shí)間估計(jì)

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

本文以O(shè)LAP系統(tǒng)需要周期性運(yùn)行批量固定查詢?yōu)檠芯繉?duì)象，提出采用全連接神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)并行查詢響應(yīng)時(shí)間。全連接神經(jīng)網(wǎng)絡(luò)具有良好的自學(xué)習(xí)能力、擬合能力，且無(wú)須提前確定模型函數(shù)。除此之外，本文充分考慮了查詢交互的影響，結(jié)合查詢計(jì)劃信息能夠更為準(zhǔn)確的預(yù)測(cè)查詢組合中各查詢的響應(yīng)時(shí)間；實(shí)驗(yàn)結(jié)果表明，在10 GB數(shù)據(jù)集上，本文提出的模型可實(shí)現(xiàn)動(dòng)態(tài)預(yù)測(cè)；且無(wú)論樣本覆蓋率如何，全連接神經(jīng)網(wǎng)絡(luò)模型都優(yōu)于當(dāng)前代表性統(tǒng)計(jì)模型。在后續(xù)工作中，可在本文的基礎(chǔ)上對(duì)負(fù)載調(diào)度進(jìn)行研究，根據(jù)查詢響應(yīng)時(shí)間調(diào)整查詢的執(zhí)行順序，選取資源爭(zhēng)用小的查詢并行運(yùn)行，縮短整個(gè)查詢隊(duì)列的執(zhí)行時(shí)間，提高數(shù)據(jù)庫(kù)運(yùn)行效率。