健壯且自適應(yīng)的學(xué)習(xí)型近似查詢處理方法研究

喬藝萌，荊一楠，張寒冰

（1.復(fù)旦大學(xué)軟件學(xué)院，上海 200441；2.復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院， 上海 200433）

0 引言

在交互式數(shù)據(jù)探索的過(guò)程中，用戶對(duì)數(shù)據(jù)查詢的響應(yīng)時(shí)間具有較高的要求，過(guò)長(zhǎng)的查詢延遲會(huì)影響用戶的分析行為和決策效果［1］。然而，隨著數(shù)據(jù)規(guī)模的爆炸式增長(zhǎng)，現(xiàn)有的分析系統(tǒng)很難在交互時(shí)間內(nèi)完成對(duì)大數(shù)據(jù)集的精確查詢。另一方面，在分析過(guò)程中用戶往往更關(guān)注數(shù)據(jù)的變化趨勢(shì)而非精確結(jié)果，因此，近似查詢處理（AQP）技術(shù)應(yīng)運(yùn)而生，其通過(guò)返回?cái)?shù)據(jù)集上查詢結(jié)果的近似估計(jì)來(lái)降低查詢時(shí)延，以滿足用戶對(duì)交互響應(yīng)時(shí)間的需求。

數(shù)據(jù)探索中的查詢請(qǐng)求多為聚合查詢，目前，面向聚合查詢的近似處理方法主要分為兩類，即基于抽樣的方法和基于機(jī)器學(xué)習(xí)的方法。基于抽樣的方法［2-4］是指通過(guò)在線或離線采樣構(gòu)建原始數(shù)據(jù)的樣本，用樣本數(shù)據(jù)的特征估計(jì)總體數(shù)據(jù)分布，此類方法能夠避免直接在原始數(shù)據(jù)上執(zhí)行查詢，從而降低查詢時(shí)延。但是當(dāng)數(shù)據(jù)量增加時(shí)，為了保證查詢結(jié)果的準(zhǔn)確性，需要維護(hù)的樣本數(shù)量也隨之增加，基于抽樣的方法仍存在查詢時(shí)延長(zhǎng)、占用存儲(chǔ)空間大等問(wèn)題［5-6］。

為了解決采樣方法中存在的上述問(wèn)題，文獻(xiàn)［7-9］使用機(jī)器學(xué)習(xí)模型代替原始數(shù)據(jù)或樣本，設(shè)計(jì)基于機(jī)器學(xué)習(xí)的近似查詢處理方法，以此減少對(duì)數(shù)據(jù)的依賴。此類方法主要基于數(shù)據(jù)驅(qū)動(dòng)的生成模型，包括變分自編碼器、和積網(wǎng)絡(luò)（SPN）、混合密度網(wǎng)絡(luò)、條件生成對(duì)抗網(wǎng)絡(luò)等，學(xué)習(xí)數(shù)據(jù)集的概率密度分布并使用模型推斷替代在數(shù)據(jù)集上的直接查詢，將I/O 密集型計(jì)算任務(wù)轉(zhuǎn)化為CPU 密集型計(jì)算任務(wù)，提高了查詢的計(jì)算速度。同時(shí)，模型只需要存儲(chǔ)參數(shù)而非數(shù)據(jù)記錄，因此，能夠減少存儲(chǔ)空間占用。

基于機(jī)器學(xué)習(xí)的近似查詢處理方法能夠提高查詢效率和準(zhǔn)確性，且模型較為輕量，然而，由于時(shí)間和空間資源限制，機(jī)器學(xué)習(xí)模型通常基于數(shù)據(jù)樣本進(jìn)行訓(xùn)練，數(shù)據(jù)樣本的質(zhì)量直接關(guān)系到模型的參數(shù)學(xué)習(xí)效果，對(duì)查詢預(yù)測(cè)的準(zhǔn)確性有很大影響，其原因在于，一個(gè)數(shù)據(jù)驅(qū)動(dòng)的模型只能捕捉到訓(xùn)練數(shù)據(jù)的概率密度分布，即在獲取數(shù)據(jù)樣本的過(guò)程中所丟失的數(shù)據(jù)信息是模型無(wú)法學(xué)習(xí)到的。常用的一般隨機(jī)采樣方法通常會(huì)導(dǎo)致原始數(shù)據(jù)集中稀有群組缺失過(guò)多，而基于分層采樣的方法則會(huì)保留分層屬性上的完整信息，因此，當(dāng)模型基于分層樣本訓(xùn)練時(shí)，只要學(xué)習(xí)過(guò)程中不出現(xiàn)過(guò)大偏差，則在相應(yīng)分層屬性上學(xué)習(xí)的數(shù)據(jù)分布將更準(zhǔn)確，以該模型來(lái)回答針對(duì)該分層屬性的查詢時(shí)，模型的預(yù)測(cè)準(zhǔn)確性會(huì)得到一定程度的提高。同時(shí)，此前的學(xué)習(xí)型近似查詢處理方法通?；陟o態(tài)場(chǎng)景，而實(shí)際分析應(yīng)用中數(shù)據(jù)往往處于頻繁變化之中，針對(duì)動(dòng)態(tài)場(chǎng)景下的數(shù)據(jù)更新問(wèn)題，模型應(yīng)該及時(shí)識(shí)別數(shù)據(jù)分布的變化，并具備自適應(yīng)更新的能力。

本文提出一種基于分層樣本學(xué)習(xí)的混合型和積網(wǎng)絡(luò)模型（SSSPN），并基于該模型設(shè)計(jì)一個(gè)近似查詢處理框架，根據(jù)用戶歷史工作負(fù)載構(gòu)建多個(gè)不同的分層樣本，以此訓(xùn)練多個(gè)SSSPN，動(dòng)態(tài)地選擇模型來(lái)回答用戶查詢，從而提高查詢預(yù)測(cè)的準(zhǔn)確性和健壯性。此外，針對(duì)數(shù)據(jù)更新可能導(dǎo)致的模型準(zhǔn)確性下降問(wèn)題，本文設(shè)計(jì)一種模型自適應(yīng)更新策略，通過(guò)數(shù)據(jù)分布檢驗(yàn)識(shí)別數(shù)據(jù)偏移現(xiàn)象，動(dòng)態(tài)確定數(shù)據(jù)和模型更新的頻率。

1 預(yù)備知識(shí)

1.1 問(wèn)題定義

本文研究的主要問(wèn)題是交互式數(shù)據(jù)探索場(chǎng)景下面向聚合查詢的近似處理，其基本形式是：

其中：X、Y均為表T中的屬性；AGG 為聚合函數(shù)；filters 為過(guò)濾條件。目前，本文方法所支持的聚合函數(shù)類型包括COUNT、AVG、SUM 等，同時(shí)支持常用算術(shù)運(yùn)算符和JOIN 連接操作。

以表1 中簡(jiǎn)化版的Flights 航班延誤數(shù)據(jù)集［10］為例，若用戶希望使用分析工具展示不同年份從LAX機(jī)場(chǎng)出發(fā)的航班總延誤里程，則該分析行為將被轉(zhuǎn)化為如下的面向底層數(shù)據(jù)庫(kù)的查詢：

表1 簡(jiǎn)化版的Flights 數(shù)據(jù)集示例Table 1 Example of simplified Flights dataset

對(duì)于一個(gè)包含5 億條數(shù)據(jù)記錄的Flights 數(shù)據(jù)集，在數(shù)據(jù)庫(kù)上執(zhí)行該精確查詢的耗時(shí)約為20 s，遠(yuǎn)超用戶的等待限度。因此，本文旨在通過(guò)近似查詢處理技術(shù)降低查詢延遲，并盡可能地減小查詢誤差。

1.2 混合型和積網(wǎng)絡(luò)模型

和積網(wǎng)絡(luò)［11］是為了解決概率模型中配分函數(shù)計(jì)算過(guò)于復(fù)雜的問(wèn)題而被提出的，通常以樹的形式呈現(xiàn)，其葉子節(jié)點(diǎn)表示隨機(jī)變量，內(nèi)部節(jié)點(diǎn)由乘積與求和2 種運(yùn)算組成。和積網(wǎng)絡(luò)執(zhí)行推斷的計(jì)算復(fù)雜度在多項(xiàng)式時(shí)間內(nèi)，與其他深度模型相比，其推斷速度具備明顯優(yōu)勢(shì)［12］。

混合型和積網(wǎng)絡(luò)（MSPN）［13］是為了處理混合屬性類型而提出的特殊和積網(wǎng)絡(luò)，其使用分段函數(shù)表示變量分布，使得葉子節(jié)點(diǎn)既能表示數(shù)值型屬性的分布，又能表示類別型屬性的分布。如圖1 所示，X1為數(shù)值型變量，X2為類別型變量，針對(duì)變量{X1,X2}訓(xùn)練的混合型和積網(wǎng)絡(luò)，其根節(jié)點(diǎn)可以表示{X1,X2}的聯(lián)合概率分布P(X1,X2)=0.4×p1(X1)×p2(X2)+0.6×p3(X1)×p4(X2)。例如，P(3,1)=0.4×0.7×0.5+0.6×0.8×0.25=0.26，該聯(lián)合概率可以自下而上地很快計(jì)算出來(lái)，且計(jì)算復(fù)雜度僅與樹的高度和節(jié)點(diǎn)數(shù)量有關(guān)。

圖1 混合型和積網(wǎng)絡(luò)示例Fig.1 Example of MSPN

本文選用混合型和積網(wǎng)絡(luò)模型來(lái)學(xué)習(xí)數(shù)據(jù)概率分布，原因是：一方面，關(guān)系型數(shù)據(jù)集中通常同時(shí)包含數(shù)值型屬性和類別型屬性，混合型和積網(wǎng)絡(luò)能較好地對(duì)它們進(jìn)行表征；另一方面，學(xué)習(xí)型數(shù)據(jù)庫(kù)任務(wù)中常用的深度模型（如自回歸模型、變分自編碼器、對(duì)抗神經(jīng)網(wǎng)絡(luò)等）大多是不可解的（intractable）［14］，即難以在多項(xiàng)式時(shí)間內(nèi)完成邊緣概率、期望等復(fù)雜查詢的精確推斷，這對(duì)近似查詢處理任務(wù)來(lái)說(shuō)時(shí)間復(fù)雜度過(guò)高，而混合型和積網(wǎng)絡(luò)可以在多項(xiàng)式時(shí)間內(nèi)完成精確推斷，在時(shí)間上占據(jù)更大優(yōu)勢(shì)。

1.3 分層抽樣

分層抽樣（Stratified Sampling）是指將總體數(shù)據(jù)按一定特征劃分成互不重疊的層，在每個(gè)層內(nèi)按照規(guī)定比例抽取樣本［15］。給定總體數(shù)據(jù)集T，要在其中抽取n個(gè)樣本，假設(shè)一共可以分為r個(gè)層，那么每個(gè)層中抽取的樣本數(shù)Si滿足S1+S2+…+Sr=n，即每個(gè)層中的樣本匯總后可以構(gòu)成整體樣本。

分層抽樣的優(yōu)點(diǎn)是抽取的數(shù)據(jù)樣本更能體現(xiàn)所選特征上的數(shù)據(jù)分布，并減少在稀有群組上的信息缺失。以表2 中的國(guó)家和年齡數(shù)據(jù)為例，若希望從中抽取5 條數(shù)據(jù)樣本，當(dāng)采用均勻抽樣的方法時(shí)，由于該類方法具有隨機(jī)性，其選取的數(shù)據(jù)記錄不能很好地表征不同國(guó)家的數(shù)據(jù)分布，例如樣本中大多是國(guó)家為“美國(guó)”的數(shù)據(jù)。而當(dāng)基于國(guó)家屬性分層進(jìn)行抽樣時(shí)，每個(gè)國(guó)家的數(shù)據(jù)按比例被抽取，更具備一般性和代表性。

表2 不同抽樣方法的對(duì)比Table 2 Comparison of different sampling methods

2 基于SSSPN 的近似查詢處理方法

本節(jié)首先提出基于分層樣本學(xué)習(xí)的混合型和積網(wǎng)絡(luò)模型SSSPN，闡述如何使用該模型學(xué)習(xí)數(shù)據(jù)的概率密度分布；然后基于該模型設(shè)計(jì)近似查詢處理框架，通過(guò)用戶歷史工作負(fù)載訓(xùn)練多個(gè)SSSPN，并針對(duì)不同查詢選擇不同模型來(lái)回答聚合SQL 查詢，以提高查詢預(yù)測(cè)的準(zhǔn)確性。

2.1 混合型和積網(wǎng)絡(luò)模型SSSPN

由于計(jì)算資源的限制，此前的學(xué)習(xí)型近似查詢處理方法［7-9］通?；陔S機(jī)樣本數(shù)據(jù)訓(xùn)練模型，而事實(shí)上，樣本數(shù)據(jù)的選取對(duì)模型的準(zhǔn)確性有很大影響。一個(gè)數(shù)據(jù)驅(qū)動(dòng)的模型會(huì)以輸入數(shù)據(jù)為基準(zhǔn)學(xué)習(xí)數(shù)據(jù)分布，無(wú)法掌握獲取訓(xùn)練數(shù)據(jù)時(shí)所丟失的數(shù)據(jù)信息，即抽樣時(shí)所忽略的數(shù)據(jù)信息是模型無(wú)法學(xué)習(xí)到的。采用簡(jiǎn)單隨機(jī)抽樣方法會(huì)使缺失的稀有群組偏多，從而導(dǎo)致模型對(duì)于與該部分?jǐn)?shù)據(jù)相關(guān)的查詢預(yù)測(cè)準(zhǔn)確性偏低。利用基于分層抽樣的方法抽取訓(xùn)練數(shù)據(jù)，則訓(xùn)練樣本在相應(yīng)分層屬性上的數(shù)據(jù)信息是完整的，即模型在該屬性上的概率分布預(yù)測(cè)更為準(zhǔn)確。鑒于此，本文提出基于分層樣本訓(xùn)練的混合型和積網(wǎng)絡(luò)模型SSSPN，通過(guò)提高訓(xùn)練數(shù)據(jù)樣本的質(zhì)量來(lái)提升模型的預(yù)測(cè)準(zhǔn)確性?；诜謱訕颖镜幕旌闲秃头e網(wǎng)絡(luò)訓(xùn)練算法描述如算法1 所示。

算法1基于分層樣本的混合型和積網(wǎng)絡(luò)訓(xùn)練算法

輸入分層樣本D，D中的屬性集合V，相關(guān)性閾值τ，最小數(shù)據(jù)記錄條數(shù)η，D中數(shù)據(jù)記錄對(duì)應(yīng)的采樣率R

輸出能夠表征數(shù)據(jù)集D中屬性集合V聯(lián)合概率分布的和積網(wǎng)絡(luò)S

如算法1 描述，一個(gè)基于分層樣本訓(xùn)練的混合型和積網(wǎng)絡(luò)遵循混合型和積網(wǎng)絡(luò)的一般訓(xùn)練流程，但是對(duì)數(shù)據(jù)集的處理及概率的學(xué)習(xí)方式有所不同?；诜謱訕颖镜腟SSPN 訓(xùn)練是一個(gè)遞歸的構(gòu)建過(guò)程，首先使用K-Means 算法［16］對(duì)數(shù)據(jù)集進(jìn)行聚類，將數(shù)據(jù)集按行劃分為2 個(gè)簇并用求和節(jié)點(diǎn)組合；然后針對(duì)每個(gè)數(shù)據(jù)簇，使用RDC 相關(guān)系數(shù)［17］度量屬性之間的相關(guān)性，相關(guān)性低于指定閾值τ時(shí)將數(shù)據(jù)集按列劃分。重復(fù)上述步驟，直至數(shù)據(jù)集中只存在單個(gè)變量的部分?jǐn)?shù)據(jù)（數(shù)據(jù)記錄條目小于閾值η），則將該變量的分布記錄在單個(gè)葉子節(jié)點(diǎn)中，針對(duì)單個(gè)葉子節(jié)點(diǎn)構(gòu)造CreateLeaf（第5 行），首先將每個(gè)值的頻率除以其對(duì)應(yīng)的采樣率Ri，將有偏數(shù)據(jù)復(fù)原為無(wú)偏數(shù)據(jù)，然后構(gòu)造該變量的數(shù)據(jù)分布直方圖。

表1 中簡(jiǎn)化版的Flights 航班延誤數(shù)據(jù)集是按年份分層抽樣而得到的，除原有屬性外，在構(gòu)建SSSPN時(shí)，需要額外增加sampling ratio 屬性以輔助記錄每條數(shù)據(jù)樣本獲取時(shí)在相應(yīng)層內(nèi)的抽樣率。按照上述訓(xùn)練算法，表中的數(shù)據(jù)首先使用K-Means 聚類算法劃分為左右2 個(gè)簇，使用求和節(jié)點(diǎn)連接，其左右子樹中的數(shù)據(jù)占比分別為0.3 和0.7；然后針對(duì)每個(gè)簇的數(shù)據(jù)，計(jì)算其涉及的屬性的相關(guān)性，經(jīng)計(jì)算后得origin 和distance 屬性之間的相關(guān)性低，可以認(rèn)為彼此相互獨(dú)立，因此，將數(shù)據(jù)按列劃分并用乘積節(jié)點(diǎn)連接；經(jīng)過(guò)劃分后的數(shù)據(jù)僅涉及單變量數(shù)據(jù)，且數(shù)據(jù)條目較少，因此，各自生成相應(yīng)的葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)用直方圖表示每個(gè)數(shù)據(jù)子集的分布。值得注意的是，sampling ratio 屬性為輔助屬性，不參與訓(xùn)練過(guò)程中劃分算法的計(jì)算，也不參與葉子節(jié)點(diǎn)的表征，僅用于將有偏數(shù)據(jù)轉(zhuǎn)化為無(wú)偏數(shù)據(jù)。

經(jīng)由上述過(guò)程訓(xùn)練好的SSSPN 如圖2 所示，其可以表示為針對(duì)origin 和distance 的聯(lián)合概率分布，并通過(guò)自底向上地計(jì)算概率和期望來(lái)求解查詢。對(duì)于一個(gè)訓(xùn)練好的SSSPN，其執(zhí)行推斷的時(shí)間復(fù)雜度僅與模型中的節(jié)點(diǎn)個(gè)數(shù)呈線性關(guān)系，與其他因素?zé)o關(guān)［12］。

圖2 基于Flights 數(shù)據(jù)集分層樣本構(gòu)建的SSSPNFig.2 SSSPN constructed based on stratified samples of Flights dataset

例1 給定上述訓(xùn)練好的SSSPN，用戶希望查詢飛行始發(fā)地為L(zhǎng)AX 機(jī)場(chǎng)的航班數(shù)量：SELECT COUNT（*）FROM Flights WHERE origin=’LAX’。該查詢可以轉(zhuǎn)化為計(jì)算P(origin='LAX')，假設(shè)涉及origin 屬性的2 個(gè)葉子節(jié)點(diǎn)中值為L(zhǎng)AX 的概率分別為0.4 和0.6，那么就可以自底向上地計(jì)算P(origin='LAX')=0.3×0.4×1+0.7×0.6×1=0.54，則始發(fā)地為L(zhǎng)AX 機(jī)場(chǎng)的航班數(shù)量為總的航班數(shù)乘以此概率值。類似地，其他常用聚合查詢（如AVG、SUM 等）也可以由此模型推斷得到，即單個(gè)SSSPN 可以實(shí)現(xiàn)針對(duì)數(shù)據(jù)集的近似查詢。

2.2 基于SSSPN 的近似查詢處理框架

基于SSSPN 模型設(shè)計(jì)的近似查詢處理框架如圖3所示。在離線學(xué)習(xí)階段，系統(tǒng)根據(jù)歷史工作負(fù)載的查詢列集（QCS）和用戶的資源限制選取合適的分層屬性及樣本數(shù)量以生成多個(gè)分層樣本，并基于這些分層樣本訓(xùn)練多個(gè)SSSPN 模型；在在線查詢階段，用戶與分析系統(tǒng)進(jìn)行交互，用戶的分析查詢被重寫為模型可計(jì)算的概率表達(dá)式，系統(tǒng)選取合適的模型并將查詢交給選中的模型，該模型自下而上地執(zhí)行推斷，得到相應(yīng)的查詢結(jié)果并返回到前端界面；當(dāng)發(fā)生數(shù)據(jù)更新時(shí)，系統(tǒng)檢測(cè)是否發(fā)生數(shù)據(jù)分布的偏移，并確定模型自適應(yīng)更新的時(shí)機(jī)。由此，用戶不需要與模型進(jìn)行交互就能得到近似查詢結(jié)果，而模型不需要依賴底層數(shù)據(jù)就能為用戶提供對(duì)數(shù)據(jù)的預(yù)測(cè)結(jié)果，基于多個(gè)SSSPN 模型的預(yù)測(cè)準(zhǔn)確性更高，模型也更加健壯。

圖3 基于SSSPN 的近似查詢處理框架Fig.3 Approximate query-processing framework based on SSSPN

本文所提框架訓(xùn)練多個(gè)SSSPN 模型的動(dòng)機(jī)是，基于不同屬性集合構(gòu)建的分層樣本及訓(xùn)練的不同模型適合于回答不同查詢。如表3 所示，在Flights 數(shù)據(jù)集中根據(jù)不同的分層屬性進(jìn)行抽樣，獲取3 個(gè)分層樣本并各自訓(xùn)練SSSPN，在其上執(zhí)行近似查詢預(yù)測(cè)時(shí)，不同模型針對(duì)不同查詢的預(yù)測(cè)準(zhǔn)確性不盡相同，即根據(jù)查詢特點(diǎn)選擇不同的模型進(jìn)行預(yù)測(cè)，可以有效發(fā)揮多個(gè)樣本的優(yōu)勢(shì)，提高查詢預(yù)測(cè)的準(zhǔn)確性。

表3 不同查詢?cè)诓煌Ｐ蜕系南鄬?duì)誤差Table 3 The relative error of different queries on different models %

在上述過(guò)程中，如何選取合適的分層樣本來(lái)訓(xùn)練模型是一個(gè)很大的挑戰(zhàn)。本文使用AQUA［18］提出的查詢列集QCS 來(lái)表征一段時(shí)間內(nèi)的工作負(fù)載特征，即對(duì)于一個(gè)相對(duì)穩(wěn)定的工作負(fù)載來(lái)說(shuō)，其中所包含的查詢通?；谀承┫鄬?duì)固定的列進(jìn)行過(guò)濾和篩選，出現(xiàn)在WHERE、GROUP BY、HAVING 語(yǔ)句中的列組成了工作負(fù)載的查詢列集QCS，基于QCS 的查詢優(yōu)化在AQUA、BlinkDB［2］中都表現(xiàn)出了很好的效果。由于用戶時(shí)間和空間資源的限制，系統(tǒng)無(wú)法用QCS 中的所有屬性構(gòu)建不同的分層樣本，本文默認(rèn)使用Top3 的QCS 來(lái)構(gòu)建模型，用戶也可根據(jù)不同的空間預(yù)算來(lái)增加或減少模型數(shù)量。

此外，如何針對(duì)不同查詢選取合適的模型進(jìn)行預(yù)測(cè)也是一個(gè)較大的挑戰(zhàn)。本文模型的選取策略如算法2 描述，給定一個(gè)模型集合M，需要回答的查詢?yōu)閝，構(gòu)建模型時(shí)對(duì)應(yīng)的分層屬性集合為Φ，查詢q對(duì)應(yīng)的查詢列集為φ，取分層屬性為φ的超集、分層屬性數(shù)目最小的模型來(lái)回答查詢。如果同時(shí)有多個(gè)候選模型，則首先計(jì)算該查詢?cè)诟鱾€(gè)模型上的選擇性，然后選取預(yù)測(cè)選擇性最高的模型進(jìn)行預(yù)測(cè)，原因是查詢誤差會(huì)隨著查詢中WHERE 或GROUP BY 子句選擇行數(shù)的減少而降低，預(yù)測(cè)準(zhǔn)確性隨之提高。

算法2模型選取算法

輸入模型集合M，查詢q，構(gòu)建模型時(shí)對(duì)應(yīng)的分層屬性集合Φ，查詢q對(duì)應(yīng)的查詢列集φ

3 數(shù)據(jù)更新下的模型自適應(yīng)更新策略

3.1 數(shù)據(jù)更新下的數(shù)據(jù)偏移

真實(shí)的數(shù)據(jù)庫(kù)使用過(guò)程是一個(gè)動(dòng)態(tài)的場(chǎng)景［19］，數(shù)據(jù)更新時(shí)有發(fā)生，對(duì)于一個(gè)學(xué)習(xí)型近似查詢處理方法而言，插入新的數(shù)據(jù)記錄后，數(shù)據(jù)的分布可能會(huì)發(fā)生偏移，使得模型所學(xué)習(xí)的概率分布與變化后的數(shù)據(jù)分布不一致，從而導(dǎo)致查詢準(zhǔn)確性降低。

此前的學(xué)習(xí)型近似查詢處理方法只考慮查詢處理的靜態(tài)場(chǎng)景，在發(fā)生數(shù)據(jù)偏移后只能重新訓(xùn)練模型或者對(duì)模型進(jìn)行微調(diào)［20］，造成計(jì)算資源的浪費(fèi)且健壯性不夠，這也是機(jī)器學(xué)習(xí)領(lǐng)域面臨的一個(gè)共同問(wèn)題［21］。針對(duì)本文提出的近似查詢處理框架，設(shè)計(jì)數(shù)據(jù)動(dòng)態(tài)更新場(chǎng)景下的模型自適應(yīng)更新策略，對(duì)數(shù)據(jù)偏移進(jìn)行檢測(cè)，并在檢測(cè)到明顯的數(shù)據(jù)偏移時(shí)對(duì)模型進(jìn)行更新。

3.2 模型自適應(yīng)更新策略

如圖3 所示，在第2.2 節(jié)近似查詢處理框架的基礎(chǔ)上，當(dāng)向底層數(shù)據(jù)庫(kù)中插入新的數(shù)據(jù)時(shí)，即時(shí)執(zhí)行數(shù)據(jù)偏移檢測(cè)算法，判斷新插入的數(shù)據(jù)是否導(dǎo)致數(shù)據(jù)分布發(fā)生了偏移：若偏移程度較高，則更新相應(yīng)的模型；否則，仍然使用原有模型進(jìn)行預(yù)測(cè)。

本文提出的模型自適應(yīng)更新策略主要考慮插入新數(shù)據(jù)后數(shù)據(jù)分布與原分布是否一致。如算法3 所描述，給定初始數(shù)據(jù)集D、初始模型集合M、待插入的數(shù)據(jù)集Dnew，構(gòu)建模型時(shí)對(duì)應(yīng)的分層屬性集合為Φ，M中的每個(gè)模型Mi都將維護(hù)一個(gè)單獨(dú)的數(shù)據(jù)緩沖區(qū)Bi，用于記錄尚未被對(duì)應(yīng)模型更新的數(shù)據(jù)記錄。每次向底層數(shù)據(jù)庫(kù)中插入新的數(shù)據(jù)時(shí)，新數(shù)據(jù)首先被添加到每個(gè)模型對(duì)應(yīng)的數(shù)據(jù)緩沖區(qū)Bi中，同時(shí)計(jì)算在當(dāng)前模型Mi上對(duì)應(yīng)的分層屬性的數(shù)據(jù)分布est_dist 和插入新數(shù)據(jù)后在數(shù)據(jù)集D+Dnew上的真實(shí)數(shù)據(jù)分布true_dist，通過(guò)兩樣本KS（Kolmogorov-Smirnov）檢驗(yàn)［22］檢測(cè)數(shù)據(jù)分布是否發(fā)生偏移：若KS檢驗(yàn)的顯著性水平超過(guò)給定閾值θ，則認(rèn)為數(shù)據(jù)分布發(fā)生偏移，相應(yīng)的模型Mi將基于Bi進(jìn)行更新，并將數(shù)據(jù)緩沖區(qū)清零；否則，認(rèn)為數(shù)據(jù)未發(fā)生明顯偏移，仍然使用原模型對(duì)查詢進(jìn)行預(yù)測(cè)。

算法3基于SSSPN 的模型自適應(yīng)更新策略

輸入初始模型集合M，原始數(shù)據(jù)集D，待插入的數(shù)據(jù)集Dnew，數(shù)據(jù)緩沖區(qū)集合B，數(shù)據(jù)偏移度閾值θ，構(gòu)建模型時(shí)對(duì)應(yīng)的分層屬性集合Φ

此外，針對(duì)單個(gè)SSSPN 的更新，由于和積網(wǎng)絡(luò)模型以樹狀結(jié)構(gòu)存在，因此當(dāng)插入新數(shù)據(jù)時(shí)，可以保持其結(jié)構(gòu)不變，基于新插入的數(shù)據(jù)從根節(jié)點(diǎn)自頂向下地更新模型權(quán)重。對(duì)于求和節(jié)點(diǎn)，只需判斷數(shù)據(jù)記錄屬于其初始聚類中心中的哪一個(gè)簇，然后更新數(shù)據(jù)權(quán)重；對(duì)于乘積節(jié)點(diǎn)，直接按照原始的屬性劃分標(biāo)準(zhǔn)進(jìn)行劃分；對(duì)于葉子節(jié)點(diǎn)，基于新數(shù)據(jù)來(lái)更新數(shù)據(jù)直方圖即可。

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

4.1 實(shí)驗(yàn)設(shè)置

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

實(shí)驗(yàn)運(yùn)行環(huán)境為Ubuntu Linux 18.04.4 LTS 操作系統(tǒng)，配置2.10 GHz Intel Xeon Silver 4208 CPU，256 GB 內(nèi)存。實(shí)驗(yàn)算法由Python3.7 編寫，所使用的和積網(wǎng)絡(luò)模型基于SPFlow 庫(kù)實(shí)現(xiàn)［23］。

4.1.2 實(shí)驗(yàn)數(shù)據(jù)集

如表4 所示，實(shí)驗(yàn)使用2 個(gè)公開(kāi)數(shù)據(jù)集進(jìn)行測(cè)試：Flights 數(shù)據(jù)集包含1995—2015 年間美國(guó)航班延誤的真實(shí)數(shù)據(jù)記錄，實(shí)驗(yàn)中使用文獻(xiàn)［24］的方法將數(shù)據(jù)記錄擴(kuò)增到5 億條，共43 GB；SSB［25］是一個(gè)多表合成數(shù)據(jù)集，包括1 個(gè)事實(shí)表和4 個(gè)連接表，常被用于OLAP 數(shù)據(jù)庫(kù)的基準(zhǔn)測(cè)試，本次實(shí)驗(yàn)中生成了3 億條數(shù)據(jù)，共33 GB。

表4 數(shù)據(jù)集詳細(xì)信息Table 4 Dataset details

實(shí)驗(yàn)中所使用的工作負(fù)載為隨機(jī)生成的1 000 條聚合SQL 查詢，覆蓋了不同的過(guò)濾條件、屬性組合及查詢選擇性范圍。

4.1.3 實(shí)驗(yàn)對(duì)比方法

將本文所提基于SSSPN 的方法與基于采樣的方法和基于機(jī)器學(xué)習(xí)的方法進(jìn)行對(duì)比。對(duì)比方法具體如下：

1）Stratified Sampling：基于采樣的近似查詢處理方法通常都是基于分層抽樣，實(shí)驗(yàn)選用在第2.2 節(jié)構(gòu)建的多個(gè)分層樣本執(zhí)行近似查詢，樣本選取策略與本文模型選取策略相同。

2）DeepDB［26］：目前效果較好的學(xué)習(xí)型近似查詢處理方法，其基于單個(gè)混合型和積網(wǎng)絡(luò)模型進(jìn)行預(yù)測(cè)，且模型基于簡(jiǎn)單隨機(jī)樣本構(gòu)建。

3）SSSPN：本文提出的近似查詢處理方法，所使用的模型為3 個(gè)基于分層樣本訓(xùn)練的混合型和積網(wǎng)絡(luò)和1 個(gè)基于均勻樣本訓(xùn)練的混合型和積網(wǎng)絡(luò)，構(gòu)建樣本時(shí)抽樣率為1%。

4.1.4 評(píng)估指標(biāo)

使用查詢準(zhǔn)確性和查詢時(shí)延對(duì)實(shí)驗(yàn)效果進(jìn)行評(píng)估。查詢時(shí)延是指方法執(zhí)行查詢的總耗時(shí)。查詢準(zhǔn)確性使用相對(duì)誤差來(lái)度量，對(duì)于一個(gè)給定的聚合SQL 查詢q，若其在數(shù)據(jù)集上的真實(shí)查詢結(jié)果為a，基于模型的預(yù)測(cè)結(jié)果為，那么該查詢的相對(duì)誤差為：

4.2 方法準(zhǔn)確性和性能評(píng)估

實(shí)驗(yàn)對(duì)比本文方法和分層采樣的方法以及DeepDB 在Flights 和SSB 數(shù)據(jù)集上的表現(xiàn)。圖4 所示為3 種方法在查詢準(zhǔn)確性上的表現(xiàn)，從中可以看出：基于分層抽樣的方法在2 個(gè)數(shù)據(jù)集上的平均相對(duì)誤差均超過(guò)20%，這是因?yàn)榉謱映闃与m然能夠在一定程度上避免隨機(jī)抽樣中的稀有群組缺失問(wèn)題，但是依然難以僅靠樣本來(lái)估計(jì)數(shù)據(jù)整體分布；SSSPN 方法在2 個(gè)數(shù)據(jù)集上的平均相對(duì)誤差均為最低，分別為5.33%和7.31%，這是因?yàn)槠洳粌H發(fā)揮了混合型和積網(wǎng)絡(luò)能夠?qū)W習(xí)數(shù)據(jù)概率密度分布的優(yōu)勢(shì)，又通過(guò)分層樣本提高了訓(xùn)練數(shù)據(jù)的質(zhì)量，使得模型的學(xué)習(xí)更為準(zhǔn)確。

3 種方法的查詢時(shí)延如圖5 所示，從中可以看出：基于分層抽樣的方法查詢時(shí)延均達(dá)到秒級(jí)，而基于混合型和積網(wǎng)絡(luò)的方法均在500 ms 以內(nèi)，可見(jiàn)用模型推斷代替針對(duì)樣本數(shù)據(jù)的統(tǒng)計(jì)計(jì)算可以大幅降低查詢時(shí)延；SSSPN 方法雖然增加了模型選擇的時(shí)間，但是整體查詢時(shí)延與DeepDB 相比并無(wú)較大增加，在Flights 數(shù)據(jù)集上甚至略低于DeepDB，這是因?yàn)榛诜謱訕颖緦W(xué)習(xí)的和積網(wǎng)絡(luò)模型結(jié)構(gòu)更為平衡，導(dǎo)致部分查詢推斷開(kāi)銷更低。

圖5 Flights 和SSB 數(shù)據(jù)集上的平均查詢時(shí)延Fig.5 Average query latency on Flights and SSB datasets

4.3 模型自適應(yīng)更新效果分析

對(duì)模型自適應(yīng)更新策略的效果進(jìn)行分析，具體的更新過(guò)程為：實(shí)驗(yàn)分10 次向Flights 數(shù)據(jù)集中插入共計(jì)5×107行與原始數(shù)據(jù)分布不完全一致的新數(shù)據(jù)記錄，對(duì)比每次插入后基于上述模型更新策略的查詢準(zhǔn)確性及查詢時(shí)延變化情況，并將本文方法（用Adaptive Update 表示）與持續(xù)更新的方法（用Always Update 表示，只要發(fā)生數(shù)據(jù)更新即更新模型）進(jìn)行對(duì)比。從圖6 可以看出，在插入新數(shù)據(jù)的過(guò)程中，本文自適應(yīng)更新策略與持續(xù)更新策略相比，查詢的平均相對(duì)誤差差距不大，均保持相對(duì)穩(wěn)定，這是因?yàn)楫?dāng)新插入的數(shù)據(jù)未導(dǎo)致整體數(shù)據(jù)分布發(fā)生較大偏移時(shí)，使用原有模型就能較好地保證查詢的準(zhǔn)確性，而不必時(shí)刻更新。從圖7 可以看出，在更新過(guò)程中模型的查詢時(shí)延也依然保持穩(wěn)定，這是由于更新過(guò)程中和積網(wǎng)絡(luò)的結(jié)構(gòu)并未發(fā)生明顯變化，因此對(duì)推斷過(guò)程影響不大，自適應(yīng)更新方法的查詢時(shí)延略低于持續(xù)更新，這與具體數(shù)據(jù)分布有關(guān)。

圖6 模型自適應(yīng)更新過(guò)程中查詢準(zhǔn)確性的變化Fig.6 Changes in query accuracy during model adaptive update process

圖7 模型自適應(yīng)更新過(guò)程中查詢時(shí)延的變化Fig.7 Changes in query latency during model adaptive update process

4.4 對(duì)比分析

4.4.1 不同模型選取策略的影響

如表5 所示，實(shí)驗(yàn)對(duì)比不同模型選取策略對(duì)模型準(zhǔn)確性和查詢時(shí)延的影響。其中：策略1 為在選取候選模型時(shí)只精確匹配GROUP BY 中出現(xiàn)的屬性，若無(wú)候選模型時(shí)直接選用基于均勻樣本訓(xùn)練的模型；策略2 為選取候選模型時(shí)同時(shí)精確匹配GROUP BY 和WHERE 中出現(xiàn)的屬性，若無(wú)候選模型，則直接選用基于均勻樣本訓(xùn)練的模型；策略3 為本文中使用的模型選取策略。從表5 可以看出：策略1～策略3 的平均相對(duì)誤差逐步遞減，平均查詢時(shí)延基本一致，這是因?yàn)镼CS 能對(duì)查詢進(jìn)行較好地表征，并從一定程度上驗(yàn)證了查詢選擇性與預(yù)測(cè)準(zhǔn)確性之間的關(guān)系。

表5 不同模型選取策略的對(duì)比Table 5 Comparison of different model selection strategies

4.4.2 不同模型數(shù)量的影響

實(shí)驗(yàn)還對(duì)比了不同模型數(shù)量對(duì)預(yù)測(cè)準(zhǔn)確性和查詢時(shí)延的影響。由于時(shí)間和空間資源的限制，用戶可能構(gòu)建不同數(shù)量的模型以進(jìn)行查詢預(yù)測(cè)，如圖8所示，本次實(shí)驗(yàn)對(duì)比了不同空間預(yù)算下使用不同數(shù)量的模型對(duì)查詢預(yù)測(cè)準(zhǔn)確性的影響，其中，US 表示基于均勻樣本訓(xùn)練的和積網(wǎng)絡(luò)，SS 表示基于分層樣本訓(xùn)練的和積網(wǎng)絡(luò)，數(shù)字表示對(duì)應(yīng)模型的個(gè)數(shù)。從圖8 可以看出，當(dāng)基于分層樣本訓(xùn)練的模型數(shù)量增加時(shí)，查詢準(zhǔn)確性有明顯提升，這是因?yàn)椴煌姆謱訕颖居?xùn)練的模型針對(duì)不同類型的查詢有各自不同的表現(xiàn)。如圖9 所示，不同模型數(shù)量下查詢時(shí)延沒(méi)有發(fā)生明顯變化，這是因?yàn)橛刹煌謱訕颖居?xùn)練的模型深度和節(jié)點(diǎn)數(shù)量差異不大，導(dǎo)致模型推斷速度都較為相近。

圖8 不同模型數(shù)量下的查詢準(zhǔn)確性對(duì)比Fig.8 Comparison of query accuracy under different model numbers

圖9 不同模型數(shù)量下的平均查詢時(shí)延對(duì)比Fig.9 Comparison of average query latency under different model numbers

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

現(xiàn)有學(xué)習(xí)型近似查詢處理方法大多基于隨機(jī)樣本進(jìn)行訓(xùn)練，導(dǎo)致預(yù)測(cè)準(zhǔn)確性不高。為此，本文提出一種基于分層樣本學(xué)習(xí)的混合型和積網(wǎng)絡(luò)模型SSSPN，通過(guò)分層抽樣提高樣本質(zhì)量，減少稀有群組缺失現(xiàn)象，使得模型學(xué)習(xí)到的數(shù)據(jù)分布準(zhǔn)確性更高。此外，為了應(yīng)對(duì)真實(shí)場(chǎng)景下的數(shù)據(jù)動(dòng)態(tài)更新問(wèn)題，本文設(shè)計(jì)一種模型自適應(yīng)更新策略，通過(guò)檢測(cè)數(shù)據(jù)偏移水平并在發(fā)生較大的數(shù)據(jù)偏移時(shí)執(zhí)行模型自適應(yīng)更新策略，以提高模型的穩(wěn)定性并節(jié)約計(jì)算資源。實(shí)驗(yàn)結(jié)果驗(yàn)證了SSSPN 的可行性和高效性。本文主要考慮常用聚合SQL 查詢上的近似計(jì)算問(wèn)題，下一步嘗試將查詢拓展到其他類型，如MAX、MIN 等，構(gòu)建更全面的近似查詢處理方案。