健壯且自適應的學習型近似查詢處理方法研究

喬藝萌，荊一楠，張寒冰

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

0 引言

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

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

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

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

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

1 預備知識

1.1 問題定義

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

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

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

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

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

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

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

混合型和積網(wǎng)絡（MSPN）［13］是為了處理混合屬性類型而提出的特殊和積網(wǎng)絡，其使用分段函數(shù)表示變量分布，使得葉子節(jié)點既能表示數(shù)值型屬性的分布，又能表示類別型屬性的分布。如圖1 所示，X1為數(shù)值型變量，X2為類別型變量，針對變量{X1,X2}訓練的混合型和積網(wǎng)絡，其根節(jié)點可以表示{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)合概率可以自下而上地很快計算出來，且計算復雜度僅與樹的高度和節(jié)點數(shù)量有關(guān)。

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

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

1.3 分層抽樣

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

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

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

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

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

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

由于計算資源的限制，此前的學習型近似查詢處理方法［7-9］通常基于隨機樣本數(shù)據(jù)訓練模型，而事實上，樣本數(shù)據(jù)的選取對模型的準確性有很大影響。一個數(shù)據(jù)驅(qū)動的模型會以輸入數(shù)據(jù)為基準學習數(shù)據(jù)分布，無法掌握獲取訓練數(shù)據(jù)時所丟失的數(shù)據(jù)信息，即抽樣時所忽略的數(shù)據(jù)信息是模型無法學習到的。采用簡單隨機抽樣方法會使缺失的稀有群組偏多，從而導致模型對于與該部分數(shù)據(jù)相關(guān)的查詢預測準確性偏低。利用基于分層抽樣的方法抽取訓練數(shù)據(jù)，則訓練樣本在相應分層屬性上的數(shù)據(jù)信息是完整的，即模型在該屬性上的概率分布預測更為準確。鑒于此，本文提出基于分層樣本訓練的混合型和積網(wǎng)絡模型SSSPN，通過提高訓練數(shù)據(jù)樣本的質(zhì)量來提升模型的預測準確性。基于分層樣本的混合型和積網(wǎng)絡訓練算法描述如算法1 所示。

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

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

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

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

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

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

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

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

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

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

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

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

表3 不同查詢在不同模型上的相對誤差Table 3 The relative error of different queries on different models %

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

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

算法2模型選取算法

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

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

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

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

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

3.2 模型自適應更新策略

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

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

算法3基于SSSPN 的模型自適應更新策略

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

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

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

4.1 實驗設置

4.1.1 實驗環(huán)境

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

4.1.2 實驗數(shù)據(jù)集

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

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

實驗中所使用的工作負載為隨機生成的1 000 條聚合SQL 查詢，覆蓋了不同的過濾條件、屬性組合及查詢選擇性范圍。

4.1.3 實驗對比方法

將本文所提基于SSSPN 的方法與基于采樣的方法和基于機器學習的方法進行對比。對比方法具體如下：

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

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

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

4.1.4 評估指標

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

4.2 方法準確性和性能評估

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

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

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

4.3 模型自適應更新效果分析

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

圖6 模型自適應更新過程中查詢準確性的變化Fig.6 Changes in query accuracy during model adaptive update process

圖7 模型自適應更新過程中查詢時延的變化Fig.7 Changes in query latency during model adaptive update process

4.4 對比分析

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

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

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

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

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

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

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

5 結(jié)束語

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