胡 歡，李建中

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

0 引言

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

1 聚集查詢

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 誤差估計(jì)方法

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

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

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

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

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

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

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