基于隨機抽樣的近似聚集查詢處理綜述

胡 歡，李建中

（哈爾濱工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，哈爾濱 150001）

0 引言

近似查詢處理（approximate query processing，AQP）是數(shù)據(jù)庫領(lǐng)域中一個重要的研究方向，而近似聚集查詢是AQP 的核心研究問題。常用的處理近似聚集查詢的方法包括隨機抽樣、直方圖、小波變換、草圖等等。在這些方法中，只有隨機抽樣能夠應(yīng)對較復(fù)雜的聚集查詢（比如包含復(fù)雜的選擇條件、連接操作等等）。因此，本文將研究基于隨機抽樣的近似聚集查詢。文獻［1，3，5，6］總結(jié)了大量相關(guān)工作。隨機抽樣大體可分為在線隨機抽樣和離線隨機抽樣兩種方式。接下來，先分別概述基于在線隨機抽樣和基于離線隨機抽樣的近似聚集查詢的研究現(xiàn)狀，然后簡要探討近似聚集結(jié)果的誤差估計的主要方法。

1 聚集查詢

簡單來說，聚集查詢是返回一個或多個聚集值的SQL 查詢的統(tǒng)稱。聚集值可以是均值（AVG）、求和（SUM）、方差（VAR）、標(biāo)準(zhǔn)差（STDEV）、計數(shù)（COUNT）、最大值（MAX）、最小值（MIN）等等。文獻中提出的各種方法通常只適用于特定的一類聚集查詢。假設(shè)＄T ＄是一張有d＋d個屬性的表，D＝｛，，…，D｝ 為上的選擇屬性集合，D＝｛，，…，M｝為上的聚集屬性集合。那么，一個基本的聚集查詢?nèi)缦滤荆?/p>

其中，（D）是D上的一個謂詞，作為對表的選擇條件，（）是∈D上的一個聚集操作。該聚集查詢的語義是在＄T ＄的滿足選擇條件（D）的所有行上執(zhí)行聚集操作（）。通常，一個更復(fù)雜的聚集查詢可以在上述基本聚集查詢的基礎(chǔ)上進行如下擴展：

（1）增加分組操作（GROUP BY），對分組后的數(shù)據(jù)分別計算聚集值。

（2）增加連接操作（JOIN），對多個表連接后的結(jié)果計算聚集值。

（3）聚集操作，作用在不同列之間的計算結(jié)果之上，比如（），其中，∈D。

聚集查詢處理作為聯(lián)機分析處理（online analytical processing，OLAP）的一個基本組成部分，被廣泛運用于決策支持系統(tǒng)，以幫助企業(yè)進行商業(yè)決策。

2 基于在線隨機抽樣的近似聚集查詢研究

基于在線隨機抽樣的近似聚集查詢會在每個聚集查詢到來的時候進行抽樣，并且使用抽到的樣本集來處理當(dāng)前查詢。其優(yōu)點是可以根據(jù)不同查詢的特點有針對性地抽樣，比如使用索引結(jié)構(gòu)在滿足選擇條件的數(shù)據(jù)上進行抽樣，也可以自由控制樣本集的大小以保證聚集結(jié)果足夠準(zhǔn)確。但其缺點也很明顯，需要為每個查詢重新進行一次隨機抽樣，開銷比較大。下面擬對主要相關(guān)工作進行簡要回顧與論述。

在上世紀(jì)80 年代，Olken 等人就已經(jīng)開始研究基于在線隨機抽樣的近似聚集查詢了。到了上世紀(jì)90 年代末，Hellerstein 等人提出了眾所周知的在線聚集，是以交互的方式處理聚集查詢。舉例來說，一個支持在線聚集的系統(tǒng)會在一個聚集查詢被提交后不斷進行抽樣、更新近似聚集結(jié)果并將其連同誤差一起反饋給用戶。一旦用戶對當(dāng)前近似聚集結(jié)果滿意，就可以手動提前終止該查詢，從而節(jié)省時間。在線聚集一經(jīng)提出就引起了學(xué)術(shù)界的廣泛關(guān)注。此后出現(xiàn)了大量在線聚集相關(guān)的工作。比如，Qin 等人提出了第一個并行計算環(huán)境下的在線聚集框架PF-OLA。PF-OLA 將計算近似聚集結(jié)果和估計誤差兩項任務(wù)并行，以提高查詢的響應(yīng)速度。Zhang 等人利用多核CPU 與多核GPU 的并行計算能力加快在線聚集的處理。此外，Condie 等人修改了Hadoop 上的MapReduce 框架以支持分布式在線聚集，而Pansare 等人提出了一個適合于MapReduce 框架的在線聚集模型并且在一個開源項目Hyracks 上實現(xiàn)了該模型。Zeng 等人提出了一個在線聚集模型G-OLA，以有效處理任意嵌套的聚集查詢。

當(dāng)聚集查詢涉及多個表之間的連接時，在線聚集變得復(fù)雜多了。Haas 等人提出的Ripple Join方法簡單地先從要做連接的每個表中隨機抽取一個樣本集，然后在這些樣本集上進行連接。這種盲目的抽樣方法很容易使得某些聚集結(jié)果缺失或者聚集結(jié)果誤差很大。Acharya 等 人提出的 Join Synopses 方法只在第一個表上抽取一個樣本集，然后將之與其他表進行連接。當(dāng)其他表很大時，這種方法效率會很低。稍后，Li 等人提出的Wander Join 方法以隨機游走的方式有選擇性地抽樣，能夠取得較高的效率。但是，這種方法需要大量索引結(jié)構(gòu)，因此預(yù)處理開銷和存儲開銷大。Zhao 等人指出通過Ripple Join 方法得到的一個多表連接結(jié)果的樣本集是均勻、但非獨立的，而通過Wander Join 方法得到的一個多表連接結(jié)果的樣本集是獨立、但非均勻的，進而又提出了一個生成均勻獨立樣本集的框架。

3 基于離線隨機抽樣的近似聚集查詢研究

基于離線隨機抽樣的近似聚集查詢會在預(yù)處理階段從原始數(shù)據(jù)上抽取一個隨機樣本集并保存起來以用于處理之后到來的多個查詢?？梢姡噍^于基于在線隨機抽樣的近似聚集查詢，基于離線隨機抽樣的近似聚集查詢不需要為每個查詢進行一次抽樣，因此具有響應(yīng)速度快的特點。不過，后者由于使用同一個樣本集來處理多個不同的查詢，可能導(dǎo)致這些查詢的近似聚集結(jié)果之間具有相關(guān)性，從而出現(xiàn)誤差傳播問題。下面將對主要相關(guān)工作做簡要回顧與論述。

基于離線隨機抽樣的近似聚集查詢通常假設(shè)聚集查詢?nèi)蝿?wù)是相對固定的（試想一下，如果聚集查詢?nèi)蝿?wù)不固定，那么幾乎需要把整個數(shù)據(jù)集當(dāng)作樣本集才能保證任意查詢的聚集結(jié)果誤差足夠?。＿@樣一來，研究的基本思想是根據(jù)給定的聚集查詢?nèi)蝿?wù)有針對性地使用各種非均勻抽樣方法進行抽樣，使得得到的樣本集盡可能小，而且在此之上估計出來的近似聚集結(jié)果誤差盡可能小。在現(xiàn)有相關(guān)文獻中，比較受歡迎的處理方法是基于查詢列集（query column set，QCS）的方法。這種方法在具有相同QCS 的聚集查詢之間共享一個樣本集。這個樣本集可能不大，卻能夠保證查詢結(jié)果的準(zhǔn)確度足夠高。然而，這種方法的不足也是顯而易見的：QCS 的個數(shù)可能很大，因此為每個QCS 抽一個樣本集可能需要大量預(yù)處理時間，而且存儲這些樣本集也可能需要大量空間開銷。

最近，有不少工作通過結(jié)合離線抽樣和其他技術(shù)進一步提高了近似聚集查詢處理的性能。Galakatos 等人通過在交互式分析中結(jié)合離線樣本集和先前計算出的近似聚集結(jié)果來加速當(dāng)前聚集查詢的計算，從而節(jié)省查詢處理時間。Peng 等人通過結(jié)合離線樣本集和精確的預(yù)聚集結(jié)果來提高查詢響應(yīng)速度和聚集結(jié)果準(zhǔn)確度。Ding 等人不僅離線地抽取一個樣本集用于處理查詢，而且在離線樣本集不足以保證給定的聚集結(jié)果準(zhǔn)確度時會臨時再通過在線抽樣得到更多的樣本。

4 誤差估計方法

在基于隨機抽樣的近似聚集查詢研究中，近似聚集值的誤差通常用一個置信區(qū)間來表示。文獻［25］強調(diào)了準(zhǔn)確估計誤差的重要性并探討了大量誤差估計方法的優(yōu)缺點。最主要的3 種誤差估計方法分別是基于中心極限定理的方法、基于大偏差界（large deviation bounds）的方法和拔靴法（bootstrap）。對此將給出研究分述如下。

基于中心極限定理的方法不適用于聚集值MIN、MAX 和由用戶自定義聚集函數(shù)計算出的結(jié)果的誤差估計。由于中心極限定理依賴于數(shù)據(jù)總體方差而通常數(shù)據(jù)總體方差未知，該方法需要假設(shè)樣本方差等于數(shù)據(jù)總體方差，進而用樣本方差代替數(shù)據(jù)總體方差。因此，當(dāng)數(shù)據(jù)傾斜度很大時該方法不能夠準(zhǔn)確估計誤差。此外，該方法要求數(shù)據(jù)服從正態(tài)分布，除非抽取的樣本量“足夠”大。

基于大偏差界的方法是一大類誤差估計方法，最常用的2 種分別是基于切比雪夫不等式的方法和基于霍夫丁不等式的方法。與基于中心極限定理的方法一樣，這類方法也不適用于聚集值MIN、MAX 和由用戶自定義聚集函數(shù)計算出的結(jié)果的誤差估計?；谇斜妊┓虿坏仁降姆椒ㄐ枰龀龈谥行臉O限定理的方法相同的假設(shè)，而基于霍夫丁不等式的方法不需要做出任何假設(shè)。相比于基于中心極限定理的方法和基于切比雪夫不等式的方法，基于霍夫丁不等式的方法的缺點是對離群點很敏感。如果離群點偏離很大，那么該方法會表現(xiàn)得很差。

拔靴法通過不斷地重采樣來估計聚集值的分布情況進而估計出近似聚集值的誤差。該方法的優(yōu)點是能夠適用于比上述2 種方法更多種類的聚集值的誤差估計，比如中位數(shù)。但是，方法的缺點有2 個。第一是需要不斷重采樣，時間開銷大；第二是依賴于很強的假設(shè)，導(dǎo)致估計出來的誤差經(jīng)常不準(zhǔn)確。

5 結(jié)束語

近二十年來，基于隨機抽樣的近似聚集查詢一直都是學(xué)術(shù)界的研究熱點。在線隨機抽樣和離線隨機抽樣這2 種抽樣方式在處理近似聚集查詢時各有優(yōu)缺點。樣本集大小和聚集結(jié)果準(zhǔn)確度是評價一個抽樣方法好壞的關(guān)鍵指標(biāo)?，F(xiàn)有工作中不同的抽樣方法可能基于不同的假設(shè)、采用不同的技術(shù)、能有效處理不同類型的聚集查詢。

當(dāng)前研究面臨若干重大挑戰(zhàn)，其中包括沒有統(tǒng)一的AQP 模型、沒有可靠的查詢優(yōu)化策略、在傾斜數(shù)據(jù)上難以保證給定的誤差界等等。目前，雖然已經(jīng)開發(fā)了一些原型系統(tǒng)，如BlinkDB、SnappyData、Quickr、VerdictDB，但是距離開發(fā)出真正成熟的系統(tǒng)卻仍有待更進一步的探索和研究。