人工神經網絡預測并行查詢響應時間

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

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

0 引 言

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

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

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

本文的主要貢獻如下：

(1)提出用全連接神經網絡預測并行查詢的響應時間。采用全連接神經網絡，訓練網絡建立模型，進行預測；

(2)采用查詢計劃特征分量描述查詢的資源需求、查詢交互特征分量描述查詢之間的資源爭用，共同構成神經網絡的輸入特征向量；

(3)本文所提全連接神經網絡模型可實現(xiàn)對并行查詢響應時間的動態(tài)預測，直接抽取包含新查詢查詢組合的查詢計劃特征、查詢交互特征，輸入到模型中實現(xiàn)動態(tài)預測。

訓練好全連接神經網絡后，進行了多組模型預測的實驗，結果表明全連接神經網絡模型預測準確率優(yōu)于代表性統(tǒng)計模型，一定程度上說明了全連接神經網絡模型的可行性。

1 相關研究

1.1 查詢響應時間預測模型

現(xiàn)有查詢響應時間預測模型分為：分析模型與統(tǒng)計模型。

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

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

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

1.2 模型特征的提取

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

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

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

1.3 模型動態(tài)性

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

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

2 問題與方法

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

表1 相關術語描述

2.1 問題與解決思路

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

圖1 3個查詢并行運行示例

查詢在當前組合中從開始一直運行到結束的時間，本文稱之為查詢在固定查詢組合中的響應時間。T1時刻，對查詢5的響應時間預測由兩部分組成：查詢5在組合(5，2，3) 中運行到結束的時間T2-T1，查詢5在組合 (5，1，3) 中已經運行的時間T1-T0。查詢5實際在組合(5，2，3)中的運行時間T2-T1是它在固定查詢組合 (5，2，3) 中的響應時間，減去它在組合(5，1，3)中已完成工作的時間。這要求計算查詢在前面組合中所完成工作占整個工作的比例。

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

進行預測之前，我們需要對全連接神經網絡進行設計。

2.2 全連接神經網絡

2.2.1 網絡結構設計

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

圖2 網絡結構

2.2.2 輸入特征、預測標簽設計

本文采集查詢計劃相關操作與查詢交互數(shù)據共同作為全連接神經網絡模型的輸入特征。查詢組合的輸入特征設計為QPF、QIF。

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

QueryRating是查詢兩兩并行運行時的響應時間與單獨運行響應時間的比值，可用如式(1)所示

ri/j=ti/j/ti

(1)

式中：ti/j表示查詢i與j并行時，i的響應時間；ti表示查詢i單獨運行時的響應時間；ri/j則是對查詢i的量化值，反映查詢之間資源爭用的強弱程度，當ri/j>1 說明查詢i與查詢j存在資源競爭關系，反之說明查詢i與查詢j存在資源合作關系。

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

訓練神經網絡模型時，除了需要特征向量，還需要預測標簽也就是模型的輸出，本文采用直接預測時間的方法。一個查詢組合有m個查詢，那么預測標簽則為與之對應的m個響應時間。

2.3 固定查詢組合預測

2.3.1 問題定義

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

圖3 固定查詢組合運行示例

根據上述問題，將預測問題定義為：

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

2.3.2 解決方案

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

圖4 模型框架

2.4 可變查詢組合預測

2.4.1 問題定義

由第2.1節(jié)圖1可知，查詢5經歷了(5,1,3)與(5,2,3)兩個查詢組合，在不同組合中資源的爭用情況不同，顯然在查詢組合(5,1,3)時采用全連接神經網絡模型給出查詢5響應時間不能準確反映其真實的響應時間。對可變查詢組合的預測問題就演變查詢1結束時，對查詢5的剩余時間估計。

根據以上描述，將預測問題定義為：

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

2.4.2 解決方案

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

(2)

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

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

(1)某一查詢結束，新查詢到來時判斷新查詢組合是否在固定查詢組合響應時間樣本庫中：如果在，取出樣本庫中的查詢的響應時間；如果不存在，調用全連接神經網絡模型給出預測；

(2)依據式(2)剩余時間估計方法，給出查詢組合中未運行完成查詢的剩余時間，加上查詢已運行的時間預測出查詢的剩余時間；

(3)判斷查詢隊列是否結束，若沒結束，循環(huán)上述兩步估計查詢的剩余時間，直到查詢結束。

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

算法1： 計算查詢響應時間的算法

輸入：

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

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

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

輸出：

{time}1i//time是i個查詢的響應時間

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 實驗分析與驗證

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

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

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

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

3.2 模型評價

實驗通過兩方面來實現(xiàn)對模型的評估：均方誤差(mean square error，MSE)、Acc。MSE用來對數(shù)據的變化情況進行評估，Acc用來對模型預測的準確率進行評估(并行度為3時準確率的計算公式)。具體實現(xiàn)如式(3)、式(4)所示

(3)

(4)

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

3.3 實驗設計與分析

3.3.1 全連接神經網絡模型收斂性

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

圖5 訓練集與有效集的損失

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

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

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

圖6 3種模型預測準確率比較

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

3.3.3 固定查詢組合預測準確性

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

表2 模型準確率比較

全連接神經網絡模型有較高的準確率是由于全連接神經網絡自學習、擬合能力強且本文的全連接神經網絡模型輸入特征在相似性模型特征的基礎上增加了查詢計劃，使輸入特征能夠更好得表征查詢。

3.3.4 動態(tài)估計可變查詢組合中查詢的剩余時間

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

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

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

表3 模型剩余時間估計

4 結束語

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