鄔志罡 荊一楠 何震瀛 王曉陽,3

1(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203)2(上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室(復(fù)旦大學(xué)) 上海 200433)3(上海智能電子與系統(tǒng)研究院 上海 200433)

0 引 言

在數(shù)據(jù)探索性分析場(chǎng)景下，用戶將發(fā)起一系列查詢來探索數(shù)據(jù)集中的海量數(shù)據(jù)。然而，對(duì)整個(gè)海量數(shù)據(jù)集進(jìn)行完整掃描將導(dǎo)致用戶查詢緩慢且阻礙了系統(tǒng)交互性，嚴(yán)重影響了用戶的生產(chǎn)力甚至創(chuàng)造力[1]。因此，用戶通常借助抽樣系統(tǒng)來生成海量數(shù)據(jù)集上的一個(gè)樣本子集，并在樣本集上得到查詢的近似結(jié)果，以查詢結(jié)果精確度上的損失換取更快的查詢速度。

分組聚合查詢普遍存在于數(shù)據(jù)探索性分析場(chǎng)景中，例如當(dāng)用戶在保存商品交易記錄的數(shù)據(jù)集上進(jìn)行探索時(shí)，將會(huì)發(fā)起如下查詢：SELECT SUM(sales) FROM order GROUP BY type來分析各種種類的商品銷售情況。在這種情況下，如果在構(gòu)造樣本時(shí)采用隨機(jī)均勻抽樣策略(Uniform Sampling)，那么生成的樣本集中每種商品種類的樣本量將正比于該商品種類的交易記錄數(shù)量。這種均勻抽樣策略將導(dǎo)致從小眾的商品類別分組中收集到的樣本量不足，甚至導(dǎo)致交易數(shù)量非常稀缺的商品類別分組完全消失在最終結(jié)果中，從而產(chǎn)生很大的誤差[2]。為了能在相同抽樣率的限制條件下使得查詢結(jié)果擁有更高的精確度，現(xiàn)有系統(tǒng)通常采用分層抽樣策略(Stratified Sampling)[3]，即首先按照分組屬性的取值對(duì)數(shù)據(jù)集進(jìn)行劃分，進(jìn)而在劃分出的每個(gè)分組中進(jìn)行抽樣。例如在上述的示例中，首先按照商品種類type對(duì)數(shù)據(jù)集進(jìn)行分類，然后對(duì)每一類商品種類type中的數(shù)據(jù)分別進(jìn)行抽樣。設(shè)計(jì)一種有效的分層抽樣策略的關(guān)鍵在于：(1) 依據(jù)哪些屬性進(jìn)行分層；(2) 如何將固定的總樣本量具體分配到每一層中。針對(duì)第一個(gè)問題，現(xiàn)有分層抽樣系統(tǒng)通常利用到了用戶的歷史查詢記錄。此類系統(tǒng)基于用戶的歷史查詢記錄能被用來較為精準(zhǔn)地預(yù)測(cè)未來用戶查詢請(qǐng)求這一假設(shè)，針對(duì)用戶歷史查詢記錄中表現(xiàn)出的分組特征，篩選出頻率最高的幾組分組屬性列集合，然后在其上進(jìn)行分層抽樣。然而，在現(xiàn)實(shí)場(chǎng)景中，當(dāng)用戶查詢特征的穩(wěn)定性無法得到保證時(shí)，或是在用戶查詢歷史無法獲得的情況下，甚至是當(dāng)抽樣系統(tǒng)冷啟動(dòng)未運(yùn)行任何查詢時(shí)，現(xiàn)有的用戶查詢歷史驅(qū)動(dòng)的抽樣系統(tǒng)將無法達(dá)到預(yù)期的效果。另一方面，針對(duì)上述第二個(gè)問題，國會(huì)抽樣策略[4]一文中給出了當(dāng)查詢中分組條件確定時(shí)，最優(yōu)的分層抽樣策略對(duì)應(yīng)的總樣本量具體到每個(gè)分組的分配方案，即在各分組間完全均勻分配?；谶@一理論，該文作者進(jìn)一步提出了國會(huì)抽樣策略，即一種總樣本量分配方案優(yōu)化后的分層抽樣策略。然而，該抽樣策略雖然生成了一個(gè)面對(duì)任何分組查詢時(shí)能夠取得較優(yōu)的平均效果的樣本集，但其僅給出了在數(shù)據(jù)集上生成唯一一份樣本集的抽樣策略。然而，在現(xiàn)實(shí)場(chǎng)景中，如果抽樣系統(tǒng)能夠?yàn)橛脩羯啥喾蓦x線樣本集并支持在運(yùn)行時(shí)自動(dòng)從其中為用戶選擇出最匹配當(dāng)前查詢的樣本集，其效果顯然要好于用一份樣本集來應(yīng)對(duì)所有可能的用戶查詢[5]。

面對(duì)上文提到的這些挑戰(zhàn)，本文提出一種新的抽樣策略。本文主要貢獻(xiàn)包括：(1) 為任一具體分層抽樣策略，即其所生成的樣本集，與任意分組聚合查詢提供了一種匹配度評(píng)估的方法，并且提供了根據(jù)匹配度評(píng)估打分為用戶查詢選取最優(yōu)樣本集的方法。(2) 提出了一種基于用戶查詢與樣本間匹配度評(píng)估的分層抽樣策略，支持離線生成包含多份分層抽樣樣本集的抽樣組合。(3) 以限定相同樣本量評(píng)估近似結(jié)果精確度的方式，通過在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn)證明了本文提出的抽樣策略的有效性。

1 相關(guān)工作

BlinkDB[6]通過分析用戶的歷史查詢記錄，在篩選出的若干個(gè)熱點(diǎn)分組屬性集上進(jìn)行分層抽樣。當(dāng)用戶的歷史查詢記錄能很好地表征未來的查詢情況時(shí)，這種針對(duì)特定的查詢特征生成的特定抽樣策略顯然能夠獲得不錯(cuò)的效果。然而，在某些數(shù)據(jù)探索性分析場(chǎng)景下，由于不同用戶的探索目的各不相同且其探索意圖隨時(shí)間不斷改變，這種用戶查詢特征不隨時(shí)間變化的穩(wěn)定性假設(shè)通常無法得到保證，因此此類抽樣系統(tǒng)的效果也會(huì)受到很大影響。另一方面，BlinkDB需要在運(yùn)行時(shí)從多份預(yù)先準(zhǔn)備的離線樣本中選取出一份最適合當(dāng)前查詢的樣本，其選擇方法僅僅考慮了當(dāng)前分組聚合查詢的分組條件屬性集與某一離線分層抽樣策略的分層屬性集之間的集合包含關(guān)系，沒有給出一個(gè)具體的可供量化的評(píng)估標(biāo)準(zhǔn)。

ICICLES[7]在進(jìn)行抽樣時(shí)，對(duì)數(shù)據(jù)集中的每條記錄的抽取概率正比于該條記錄累計(jì)出現(xiàn)在用戶歷史查詢產(chǎn)生的結(jié)果集中的次數(shù)。該系統(tǒng)不斷更新維護(hù)一個(gè)根據(jù)用戶歷史查詢生成的多重集合，即一種允許相同元素重復(fù)出現(xiàn)的集合。每條用戶查詢結(jié)果中涉及到的數(shù)據(jù)記錄都會(huì)被存放在這個(gè)多重集合中。該系統(tǒng)將會(huì)在該多重集合上進(jìn)行隨機(jī)均勻抽樣，以期望生成的樣本集能匹配將來的用戶查詢。然而，這樣的方式不僅使其生成的樣本強(qiáng)依賴于用戶歷史查詢記錄，并且會(huì)使得那些還沒有被用戶探索到的區(qū)域樣本量極其匱乏，這將嚴(yán)重阻礙用戶探索數(shù)據(jù)集中新的區(qū)域以獲取新的發(fā)現(xiàn)或結(jié)論。

國會(huì)抽樣策略[4]通過優(yōu)化分層抽樣策略的總樣本量分配方式來提高針對(duì)用戶分組聚合查詢返回的近似結(jié)果的精確度。相較于其僅僅生成唯一一份樣本集，本文提出的抽樣策略可以支持生成多份離線樣本集并在運(yùn)行時(shí)自動(dòng)從多份離線樣本集中選出最匹配的一份樣本集進(jìn)行近似結(jié)果計(jì)算。由于準(zhǔn)備了多份離線樣本，從中選出一份更能匹配當(dāng)前用戶查詢特征的樣本的可能性將大大提升。

2 問題歸納

分層抽樣策略是一種先將整個(gè)數(shù)據(jù)集按照某些屬性上的取值分成若干層，然后再從每一層中隨機(jī)抽取樣本的抽樣方法。分層抽樣策略中，如何將總樣本量具體分配到每個(gè)分組中是影響最終生成的樣本集效果的最主要的問題。幸運(yùn)的是，關(guān)于分層抽樣策略的諸多特性已經(jīng)有多位學(xué)者進(jìn)行了研究總結(jié)。Acharya[4]證明了針對(duì)某一特定的用戶分組聚合查詢，即當(dāng)用戶查詢中的分組條件確定時(shí)，最優(yōu)的分層抽樣總樣本量分配方案就是在該分組查詢將會(huì)產(chǎn)生的所有分組間均勻分配樣本空間。

從上文提到的分層抽樣策略最優(yōu)總樣本量分配方案中，我們可以看出，包含不同分組條件組合的用戶查詢所對(duì)應(yīng)的最優(yōu)樣本集都是不同的。因此，抽樣系統(tǒng)希望通過僅僅一份離線樣本去應(yīng)對(duì)所有可能的用戶查詢并都能獲得較優(yōu)的效果的這一目標(biāo)是不現(xiàn)實(shí)的。如果系統(tǒng)可以在離線時(shí)生成多份樣本集，并且能夠在運(yùn)行時(shí)自動(dòng)根據(jù)當(dāng)前用戶分組聚合查詢?nèi)〕鲆环葑钇ヅ涞臉颖炯M(jìn)行近似結(jié)果計(jì)算，那么系統(tǒng)將有更大機(jī)會(huì)得到更為精確的近似結(jié)果。然而，在應(yīng)對(duì)實(shí)際場(chǎng)景時(shí)，我們顯然無法為用戶發(fā)起的每種可能的分組聚合查詢準(zhǔn)備一份最優(yōu)樣本。試想，當(dāng)用戶的查詢模式不具備時(shí)間上的穩(wěn)定性時(shí)，我們想要優(yōu)化的查詢集合將無法被縮小到一個(gè)預(yù)處理開銷可以承受的范圍內(nèi)。例如，當(dāng)數(shù)據(jù)集上共有20個(gè)分組屬性時(shí)，總共會(huì)產(chǎn)生220種分組條件組合情況。如果我們希望能在運(yùn)行時(shí)為任一可能的用戶查詢都匹配到最優(yōu)的離線樣本集，那么我們?cè)陬A(yù)處理階段需要對(duì)每種可能的分組條件組合都預(yù)先保存一份分層抽樣樣本。即使每份樣本集的抽樣率僅為0.1%，那么總的預(yù)生成樣本集合的數(shù)據(jù)量大小也將會(huì)超過原始數(shù)據(jù)集的1 000倍。本文中，我們將考慮更為實(shí)際的應(yīng)用場(chǎng)景，即用戶可提供的用于生成離線樣本集的存儲(chǔ)空間是有限的。因此，本文提出的抽樣系統(tǒng)的設(shè)計(jì)目標(biāo)可具體定義為：針對(duì)某一特定的數(shù)據(jù)集，如何生成k份分層抽樣樣本集，使得在運(yùn)行時(shí)能從k份樣本集中挑選出最合適的一份，從而期望能在所有可能的用戶分組查詢上的平均誤差達(dá)到最小值。

3 基于匹配度評(píng)估的分層抽樣策略

3.1 抽樣策略間的匹配度評(píng)估

上節(jié)中，我們已經(jīng)闡述了用戶發(fā)起的每一類分組聚合查詢都具有相對(duì)應(yīng)且確定的最優(yōu)分層抽樣總樣本量分配方案這一理論基礎(chǔ)。并且，任意樣本集都能根據(jù)其在每個(gè)分層上保存的樣本點(diǎn)個(gè)數(shù)回溯到一個(gè)具體的分層抽樣總樣本量分配方案。那么，如果我們能夠?yàn)榉謱映闃硬呗匀我鈨煞N總樣本量分配方案間提供一種匹配度評(píng)估的方法，我們就能將任意用戶查詢與樣本集之間的匹配度評(píng)估轉(zhuǎn)換為該用戶查詢對(duì)應(yīng)的最優(yōu)抽樣策略與生成該樣本集的具體抽樣策略這兩種不同的分層抽樣總樣本量分配方案之間的匹配度評(píng)估。我們也就能將上節(jié)中提出的實(shí)際場(chǎng)景下的抽樣系統(tǒng)設(shè)計(jì)目標(biāo)形式化地定義為一個(gè)優(yōu)化問題。該優(yōu)化問題的損失函數(shù)即為使用k份離線樣本集來應(yīng)對(duì)所有可能的用戶分組查詢時(shí)將會(huì)產(chǎn)生的匹配度損失的總和。接下來，本節(jié)將先介紹任意分層抽樣總樣本量分配方案的形式化表示公式并進(jìn)一步提出任意兩種抽樣策略間匹配度損失的形式化評(píng)估方法。

考慮某數(shù)據(jù)集D，可用作用戶查詢分組條件的類別分組屬性為A1,A2,…,Aα。其中，又有每個(gè)類別所對(duì)應(yīng)的值域上取值的數(shù)量大小為N1,N2,…,Nα。那么用戶在該數(shù)據(jù)集上發(fā)起的分組聚合查詢所產(chǎn)生的最小分組單位g的總數(shù)量為N1×N2×…×Nα。例如，考慮包含某國人口調(diào)查數(shù)據(jù)的數(shù)據(jù)集，其中共有兩個(gè)分組屬性A1和A2，分組屬性A1為性別，分組屬性A2為學(xué)歷。考慮每種分組屬性值域上取值的數(shù)量，分組屬性A1對(duì)應(yīng)的取值可能為“男性”或“女性”，即N1為2，分組屬性A2對(duì)應(yīng)的取值可能為“本科”、“碩士”或“博士”，即N2為3。那么，總共將產(chǎn)生6個(gè)最小分組單位gi(1≤i≤6)，分別為：g1:(“男性”，“本科”)、g2:(“男性”，“碩士”)、g3:(“男性”，“博士”)、g4:(“女性”，“本科”)、g5:(“女性”，“碩士”)、g6:(“女性”，“博士”)。

定義一種離散概率分布，其在任意最小分組單位g上的概率取值為p(g)，代表從生成的離線樣本集中任意取出一條記錄，該記錄屬于最小分組單位g的概率。那么有：

式中：S為總抽樣數(shù)量大小，Sg為總抽樣數(shù)量S分配到最小分組單位g上的抽樣數(shù)量大小，且∑p(g)=1。由此，我們可以將任意分層抽樣策略總樣本量分配方案轉(zhuǎn)化為離散概率分布的形式。至此，我們得以通過衡量?jī)蓚€(gè)離散概率分布間差異的距離函數(shù)，正式定量地評(píng)估任一總樣本量分配方案與用戶分組聚合查詢確定下的最優(yōu)樣本量分配方案間的匹配度損失程度。本文選取Jensen-Shannon散度[8]來衡量?jī)煞N抽樣策略間的匹配度損失程度。對(duì)于在同一值域Y上的概率分布P和Q，Jensen-Shannon散度定義如下：

式中：M定義如下：

公式中的KL是Kullback-Leibler散度[9]，是一種可用來測(cè)量?jī)山M概率分布間差異性的非對(duì)稱性指標(biāo)，定義如下：

當(dāng)兩個(gè)概率分布相同時(shí)JS取值為0，兩個(gè)概率分布間的匹配度損失越大，則JS取值也將會(huì)增大。

3.2 抽樣策略的設(shè)計(jì)與實(shí)現(xiàn)

式中：U代表在該數(shù)據(jù)集上用戶發(fā)起的分組聚合查詢中，所有可能的分組條件組合的集合。PU代表的是，依據(jù)Acharya證明的分層抽樣總樣本量分配方案理論[4]所得到的最優(yōu)抽樣策略對(duì)應(yīng)的概率分布。

為了解決上述優(yōu)化問題，我們?cè)O(shè)計(jì)了一種自適應(yīng)的優(yōu)化算法，該算法基于優(yōu)化問題中的一種經(jīng)典隨機(jī)爬山算法(Stochastic Hill Climbing)[10]。該算法的主要流程如算法1所示。

算法1生成包含k組概率分布的最優(yōu)解集

輸入:迭代次數(shù)閾值tIteration，優(yōu)化目標(biāo)損失值閾值tError

輸出:包含k組概率分布的最優(yōu)解集：solutionSet

1: solutionSet←insertkinitial probability distributions

2:t:iteration times←0

3:whileLOSS(solutionSet)>tErrorANDt

4: Generate solutionSetNew based on solutionSet

5:ifLOSS(solutionSetNew)

6: solutionSet←solutionSetNew

7:endif

8:t←t+1

9:endwhile

10:returnsolutionSet

在算法1中，主要包含了如下三個(gè)關(guān)鍵步驟:

(1) 第1行。在算法的初始化階段，我們?yōu)閗組抽樣策略，即為其分別對(duì)應(yīng)的k個(gè)概率分布選擇k組合適的初始解集。

(2) 第4～7行。每輪迭代產(chǎn)生一組新的解集，并重新評(píng)估新的解集在優(yōu)化目標(biāo)查詢集合上的損失值。若新的解集相比于當(dāng)前解集能夠使得系統(tǒng)總優(yōu)化目標(biāo)的損失值降低，則保留新的解集作為當(dāng)前解集，反之則丟棄。

(3) 第3行。當(dāng)系統(tǒng)總優(yōu)化目標(biāo)損失值低于閾值tError時(shí)，或當(dāng)?shù)螖?shù)大于閾值tIteration時(shí)，終止算法。否則，重復(fù)執(zhí)行步驟(2)。

其中，損失函數(shù)定義如下：

對(duì)于步驟(1)，一個(gè)合適的初始解集可以幫助優(yōu)化算法更快地終止。雖然隨機(jī)均勻抽樣策略在面對(duì)用戶分組聚合查詢時(shí)不是最優(yōu)解，但其得到的樣本保留了數(shù)據(jù)集原始的數(shù)據(jù)分布特征，并且是應(yīng)對(duì)非分組查詢時(shí)的最優(yōu)抽樣策略。因此，在沒有任何額外信息的情況下，為了避免生成更糟糕的初始解集，我們就將隨機(jī)均勻抽樣策略選做初始解集。對(duì)于步驟(2)，由于我們已經(jīng)明確定義了系統(tǒng)的總體優(yōu)化目標(biāo)，因此可以直接使用總體目標(biāo)的衡量公式來對(duì)生成的中間解進(jìn)行效果評(píng)估。在生成新的解集時(shí)，每個(gè)分組增大或減小樣本空間的概率將反比于該分組的大小。這是由于近似結(jié)果的誤差更多來源于樣本量更小的分組，調(diào)整此類分組使得我們的算法更有可能更快地向接近總體優(yōu)化目標(biāo)的方向移動(dòng)。

本文所述系統(tǒng)將在離線狀態(tài)下，按照上文所描述的優(yōu)化算法，生成一組各自代表不同分層抽樣策略總樣本量分配方案的概率分布。在分布式數(shù)據(jù)倉庫Hive[11]上，本系統(tǒng)將按照概率分布中所指示的各最小分組單位g上的抽樣率在各個(gè)分組上進(jìn)行隨機(jī)均勻抽樣，并將生成的樣本集保存在數(shù)據(jù)倉庫Hive中。與此同時(shí)，系統(tǒng)將會(huì)記錄下與當(dāng)前系統(tǒng)中保存的每份離線樣本集一一對(duì)應(yīng)的概率分布描述。這些概率分布所代表的各最小分組單位上的抽樣率信息將會(huì)在系統(tǒng)在線運(yùn)行時(shí)被用來進(jìn)行與當(dāng)前用戶查詢進(jìn)行匹配度評(píng)估，并且用來縮放在樣本集上得到的用戶查詢結(jié)果，以生成最終需要返回的近似用戶查詢結(jié)果。

3.3 系統(tǒng)運(yùn)行時(shí)的樣本選擇與查詢重寫

至此，本系統(tǒng)在運(yùn)行時(shí)仍有兩個(gè)問題需要解決：

(1) 當(dāng)某個(gè)具體的用戶分組聚合查詢請(qǐng)求到來時(shí)，系統(tǒng)將如何從離線生成的多份樣本集中選取出最優(yōu)的一份樣本，進(jìn)行近似結(jié)果計(jì)算。正如3.1節(jié)中所述，任意的分層抽樣總樣本量分配方案可以被轉(zhuǎn)化成一個(gè)概率分布。同時(shí)，對(duì)于每個(gè)到來的用戶查詢，我們都可以相應(yīng)地通過考慮查詢中的分組條件來計(jì)算出最匹配該查詢的概率分布。由于我們?cè)陔x線時(shí)保存了每份樣本集對(duì)應(yīng)的概率分布信息，因此我們有理由從中選出一份與當(dāng)前用戶查詢所對(duì)應(yīng)的最優(yōu)概率分布匹配度最高的樣本集進(jìn)行近似結(jié)果計(jì)算。唯一需要注意的是，系統(tǒng)在運(yùn)行時(shí)使用的匹配度評(píng)估函數(shù)應(yīng)當(dāng)與系統(tǒng)在離線生成樣本集時(shí)，運(yùn)行的優(yōu)化算法中所使用的匹配度評(píng)估函數(shù)保持一致。

(2) 由于本系統(tǒng)使用的是分層抽樣策略，并且對(duì)每個(gè)分組的抽樣率不同，是一種有偏的抽樣方法，因此，系統(tǒng)需要重寫用戶查詢以生成無偏的近似結(jié)果。在離線生成樣本時(shí)，當(dāng)系統(tǒng)從不同分組中按照抽樣率隨機(jī)均勻抽取不同數(shù)量的樣本時(shí)，系統(tǒng)同時(shí)已經(jīng)為每條樣本記錄保存了一個(gè)縮放因子。由于同一分組中的所有樣本記錄對(duì)應(yīng)著相同的抽樣率，因此同一分組中生成的樣本記錄將共享相同的縮放因子，即為該樣本記錄所歸屬的分組上的抽樣率的倒數(shù)。在運(yùn)行時(shí)，本系統(tǒng)將利用這些縮放因子來對(duì)每條樣本記錄進(jìn)行加權(quán)處理，以得到無偏近似結(jié)果。具體來說，對(duì)于求和操作(SUM)，近似結(jié)果將會(huì)是所有相關(guān)的樣本記錄與相應(yīng)的縮放因子的乘積的和。對(duì)于計(jì)數(shù)操作(COUNT)，近似結(jié)果為所有相關(guān)的樣本記錄對(duì)應(yīng)的縮放因子的和。相應(yīng)地，求平均值操作(AVG)通過將SUM與COUNT的結(jié)果相除計(jì)算得出。

4 實(shí) 驗(yàn)

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

本文的實(shí)驗(yàn)環(huán)境為包含1個(gè)master節(jié)點(diǎn)和9個(gè)slave節(jié)點(diǎn)的Spark集群。每一臺(tái)機(jī)器分別搭載主頻為2.1 GHz的Intel Xeon E5-2600處理器和64 GB內(nèi)存，運(yùn)行在64位Ubuntu 14.04 Server系統(tǒng)上。集群上運(yùn)行Spark 2.0.0和Hive 1.2.1。

(1) 模擬數(shù)據(jù)集 我們?cè)赥PC-H數(shù)據(jù)庫基準(zhǔn)測(cè)試數(shù)據(jù)集[12]上生成模擬數(shù)據(jù)集及測(cè)試查詢模板。在原始的TPC-H數(shù)據(jù)集中，分組的數(shù)量及各分組的大小分布都相對(duì)較為均勻。為了能更好地模擬出真實(shí)情況下的數(shù)據(jù)集，并且為了能夠更好地對(duì)比不同抽樣策略在應(yīng)對(duì)更具挑戰(zhàn)的傾斜數(shù)據(jù)集時(shí)性能上的差異性，我們利用了一個(gè)經(jīng)過版本修改的dbgen工具[13]生成非均勻分布的數(shù)據(jù)集。該工具將根據(jù)Zipf分布生成傾斜數(shù)據(jù)。在本實(shí)驗(yàn)中，Zipf分布的特征指數(shù)z被設(shè)置為1.5。我們選取了TPC-H數(shù)據(jù)集中的lineitem表，并將擴(kuò)展因子設(shè)置為100，最終得到了總大小為74.7 GB的模擬數(shù)據(jù)集。在構(gòu)造用于實(shí)驗(yàn)測(cè)試用的模擬用戶分組聚合查詢時(shí)，我們通過隨機(jī)生成若干分組屬性并進(jìn)行隨機(jī)組合的方式來生成模擬用戶分組聚合查詢，以達(dá)到模擬測(cè)試現(xiàn)實(shí)場(chǎng)景中抽樣系統(tǒng)應(yīng)對(duì)Ad-Hoc查詢時(shí)表現(xiàn)出的性能效果。

(2) 真實(shí)數(shù)據(jù)集 我們從公開的斯隆數(shù)字巡天數(shù)據(jù)集SDSS網(wǎng)站[14]上下載了真實(shí)數(shù)據(jù)集和真實(shí)的用戶查詢記錄。我們從SDSS數(shù)據(jù)集的BestDr8版本中選用了PhotoPrimary視圖，獲取了總共101.45 GB的數(shù)據(jù)。下載到的用戶查詢記錄被進(jìn)行了一定修改以使其符合Spark SQL的語法定義。

在整個(gè)實(shí)驗(yàn)過程中，我們對(duì)比了隨機(jī)均勻抽樣策略、國會(huì)抽樣策略和本文提出的匹配度分層抽樣策略。每種策略都在離線時(shí)都生成了抽樣率為1%的樣本。對(duì)于匹配度分層抽樣策略，默認(rèn)用戶設(shè)置的離線樣本集個(gè)數(shù)k為5。

4.2 模擬數(shù)據(jù)集上精確度的表現(xiàn)

實(shí)驗(yàn)一中，我們?cè)谀M數(shù)據(jù)集TPC-H上總共生成了30條隨機(jī)用戶查詢，并且對(duì)每條用戶查詢運(yùn)行在三種不同的抽樣策略生成的樣本集上得到的近似結(jié)果的相對(duì)誤差做了統(tǒng)計(jì)。我們根據(jù)用戶查詢中分組條件屬性的個(gè)數(shù)將用戶查詢分為了五類，以便能夠更為細(xì)致地考察不同抽樣策略在分組條件數(shù)量不同的情況下的表現(xiàn)。在TPC-H模擬數(shù)據(jù)集上的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果如圖1所示。

圖1 TPC-H數(shù)據(jù)集上三種抽樣策略的平均相對(duì)誤差

由圖1可知，當(dāng)分組屬性個(gè)數(shù)為0時(shí)，代表當(dāng)前測(cè)試用戶分組聚合查詢?yōu)椴话纸M條件的非分組查詢。由于隨機(jī)均勻抽樣策略完全保留了整個(gè)數(shù)據(jù)集上底層的數(shù)據(jù)分布特征，因此其在非分組用戶查詢下的表現(xiàn)自然會(huì)優(yōu)于分層抽樣策略。在國會(huì)抽樣策略中，由于抽樣策略更傾向于補(bǔ)償小的分組因此會(huì)破壞整個(gè)生成的樣本的均勻性，導(dǎo)致其在應(yīng)對(duì)非分組查詢時(shí)效果不佳，相較均勻抽樣策略誤差率提高了39.4%。而在本文提出的匹配度抽樣策略中，由于非分組用戶查詢相較于其他分組用戶查詢的特殊性，其在系統(tǒng)的總優(yōu)化目標(biāo)中往往會(huì)產(chǎn)生很大影響。因此，在最后生成的多份離線樣本集中將會(huì)有一份樣本傾向于對(duì)非分組用戶查詢更加友好，使得本系統(tǒng)在面對(duì)非分組用戶查詢時(shí)也能獲得較好的效果。相較于國會(huì)抽樣策略，針對(duì)非分組用戶查詢，本文提出的匹配度分層抽樣策略在平均相對(duì)誤差上降低了16.6%。

從圖中的統(tǒng)計(jì)結(jié)果可以看出，隨著分組屬性個(gè)數(shù)的增長(zhǎng)，各系統(tǒng)產(chǎn)生的近似結(jié)果的誤差也在隨之增長(zhǎng)。這是由于當(dāng)分組屬性個(gè)數(shù)增加時(shí)，用戶查詢產(chǎn)生的結(jié)果中將包含更多的分組數(shù)量并且各分組中包含的記錄數(shù)量的大小分布也將變得更加不平衡。分層抽樣策略在應(yīng)對(duì)這種條件下的用戶查詢時(shí)，效果要顯著好于隨機(jī)均勻抽樣策略。而由于本系統(tǒng)通過衡量不同分組查詢對(duì)應(yīng)的最優(yōu)分層抽樣總樣本量分配方案，將匹配度較高的總樣本量分配方案進(jìn)行聚合，因此可以通過離線保存為數(shù)不多的多份樣本集的方式，優(yōu)化絕大部分的分組查詢。實(shí)驗(yàn)結(jié)果也表明，當(dāng)用戶查詢中分組屬性個(gè)數(shù)增加時(shí)，本系統(tǒng)生成的近似查詢結(jié)果的誤差的增加呈現(xiàn)出放緩的趨勢(shì)。相比于國會(huì)抽樣，本文提出的匹配度分層抽樣策略在模擬數(shù)據(jù)集TPC-H上的平均相對(duì)誤差降低了25.4%。

4.3 真實(shí)數(shù)據(jù)集上精確度的表現(xiàn)

實(shí)驗(yàn)二中，我們選取了SDSS真實(shí)數(shù)據(jù)集并下載了真實(shí)的用戶查詢。我們同樣對(duì)這些真實(shí)用戶查詢按照分組屬性個(gè)數(shù)進(jìn)行了分類，實(shí)驗(yàn)獲得的統(tǒng)計(jì)結(jié)果如圖2所示。

圖2 SDSS數(shù)據(jù)集上三種抽樣策略的平均相對(duì)誤差

在真實(shí)數(shù)據(jù)集上，三種抽樣策略的表現(xiàn)與我們?cè)谀M數(shù)據(jù)集上得出的結(jié)果非常相似。對(duì)于非分組用戶查詢，相較于國會(huì)抽樣，本文提出的匹配度分層抽樣將近似結(jié)果的精確度提高了12.4%。相比于國會(huì)抽樣，本文提出的匹配度抽樣策略在真實(shí)數(shù)據(jù)集SDSS上的平均相對(duì)誤差降低了26.3%。

4.4 離線樣本集個(gè)數(shù)k的影響

實(shí)驗(yàn)三在TPC-H模擬數(shù)據(jù)集上進(jìn)一步考察了本文提出的匹配度分層抽樣系統(tǒng)中，用戶允許存儲(chǔ)的離線樣本集個(gè)數(shù)k對(duì)于近似結(jié)果精確度的影響。圖3展示了在不同的k值情況下，用戶查詢的平均相對(duì)誤差隨分組屬性個(gè)數(shù)的變化情況。從圖中可以看出，當(dāng)k為1時(shí)，即系統(tǒng)僅能保存一份離線樣本時(shí)，本文系統(tǒng)產(chǎn)生的離線樣本集將接近于國會(huì)抽樣策略所生成的樣本集，誤差較大。而當(dāng)k不為1時(shí)，即用戶允許系統(tǒng)保存多份離線樣本時(shí)，由于系統(tǒng)可以通過數(shù)據(jù)特征預(yù)存多份離線樣本并且在運(yùn)行時(shí)選擇出一份最優(yōu)樣本進(jìn)行近似結(jié)果計(jì)算，其產(chǎn)生的近似結(jié)果的精確度相較于僅保存一份離線樣本時(shí)有著明顯提升。另外，可以看到當(dāng)k值為5時(shí)，系統(tǒng)已經(jīng)能夠達(dá)到一個(gè)較好的性能，說明本文提出的優(yōu)化算法能夠很好地將具有相似數(shù)據(jù)分布特征的多種用戶分組查詢經(jīng)優(yōu)化后聚合到一份離線樣本集中。因此僅僅用少量的離線樣本集就能在大量的用戶查詢上達(dá)到較為出色的抽樣效果。

圖3 離線樣本集個(gè)數(shù)k對(duì)用戶查詢平均誤差的影響

5 結(jié) 語

本文提出了一種基于用戶查詢與各分層間總樣本量分配方案匹配度評(píng)估的分層抽樣策略，系統(tǒng)在運(yùn)行時(shí)可以從多份離線樣本中選出一份最匹配當(dāng)前查詢的樣本進(jìn)行近似結(jié)果計(jì)算。同時(shí)，本文還為任一分層抽樣策略與任意用戶分組聚合查詢的匹配度提供了一種基于概率分布和數(shù)據(jù)特征的形式化定量評(píng)估方法。通過在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的廣泛實(shí)驗(yàn)，本文驗(yàn)證了數(shù)據(jù)驅(qū)動(dòng)的基于匹配度評(píng)估的分層抽樣策略相較于傳統(tǒng)抽樣策略在用戶查詢近似結(jié)果的精確度上有了明顯提升。