CSSAQP：一種基于聚類的分層抽樣近似查詢處理算法

謝金星李暉陳梅戴振宇

（貴州大學先進計算與醫療信息服務工程實驗室貴陽550025）

CSSAQP：一種基于聚類的分層抽樣近似查詢處理算法

謝金星李暉陳梅戴振宇

（貴州大學先進計算與醫療信息服務工程實驗室貴陽550025）

近似查詢處理技術常被應用于海量數據的多維分析，以縮短查詢執行的時間，同時返回盡可能準確的結果。由于海量數據中常存在許多極端值，會嚴重影響近似查詢處理的結果。因此針對海量數據的聚集操作，論文提出CSSAQP算法，先將原始數據集按某一數值列直觀的聚為三類，分別代表大值簇、小值簇和常值簇，再對各簇按分組屬性分別進行分層抽樣，構建總體樣本集，最后通過查詢重寫在總體樣本集上執行查詢，以縮短海量數據聚集操作的查詢時間，同時提高查詢任務的準確性。通過實驗驗證，證明了該算法不僅可以縮短聚集查詢的時間，同時還能有效提高查詢結果的精度。

近似查詢處理；聚集查詢；聚類；分層抽樣

Class NumberTP311.13

1 引言

對海量數據進行多維分析，常伴隨大量的聚集操作，如在一個或多個維度上進行group-by聚集查詢，通常需要較長的執行時間。而在進行業務分析時，用戶往往僅需了解大致的趨勢，查詢的響應時間相對于完全準確的查詢結果更為重要。因此為了快速返回分析結果，可以將數據倉庫中常使用的近似查詢處理技術，應用到該類場景中，在縮短查詢執行時間的同時，提供一個盡可能精確的近似結果。

近似查詢處理有兩類基本方法：聯機查詢處理和預計算方法［1］。前者不需要預先進行數據處理，在查詢執行過程中對數據進行動態抽樣，動態計算和聚集返回當前近似結果和置信區間；后者是對數據庫中的數據事先進行預處理，生成能代表原來數據并且數據量小得多的樣本集或初步聚集結果，在查詢時使用這些數據集合獲取近似結果。常使用的具體技術有：直方圖、小波變換、抽樣等［2］。

在對海量數據近似查詢處理時，常使用抽樣技術。通過抽取部分能代表整體數據集特征的子集，在該子集上執行查詢，并將查詢結果按照抽取比率放大，以此作為整體數據集上查詢結果的近似值。

由于海量數據中通常存在許多極端值的情況，將嚴重影響近似處理的效果。為進一步提高近似結果的準確性，本文采用預計算樣本的方式，提出基于聚類的分層抽樣算法。直觀上將某一數值列聚為三類，分別代表大值簇、小值簇和常值簇，再根據聚類結果對各個簇按照分組屬性分層抽樣，構建總體樣本集。最后通過查詢重寫在總體樣本集上執行查詢，并返回查詢結果。既縮短了多維分析任務的執行時間，又提高了任務的準確度。

本文工作如下：

1）研究了基于抽樣的近似查詢處理技術，并介紹各自的適用情況；

2）針對海量數據group-by的聚集查詢，提出基于聚類的分層抽樣近似查詢處理算法；

3）利用TPC-H生成測試數據，對聚集查詢進行實驗測試；

4）對實驗結果進行分析。

2 基于抽樣的近似查詢處理技術

所謂近似查詢處理技術，就是對提交的查詢給出一個近似的合理的查詢結果。其基本思路是通過查詢更少量的數據，獲取盡可能準確的結果。

本文重點討論近似查詢處理技術中的抽樣技術。抽樣技術的基本思想是：通過適當的方法，從海量原始記錄中按一定比率抽取能代表整體數據特征的子集，構建樣本集。通過在樣本集上執行查詢，并將查詢結果按抽樣比率等比例放大，就可獲得與準確值的估計值。

抽樣技術的難點在于如何制定合適的抽樣條件，以構建能代表整體數據特征的樣本集。其結果的精度可能受到查詢類型、查詢選擇率、數據分布和樣本大小等因素的影響。常用的抽樣技術主要有：簡單隨機抽樣、偏倚抽樣、分層抽樣、國會抽樣等［3～4］。

2.1 簡單隨機抽樣

按照等概率的原則，簡單隨機抽樣直接從含有r條記錄的原始數據集中隨機抽取s（s≤r）條記錄，構成樣本集，適用于數據均勻分布的情況。其優點是簡單易操作。但是在真實的生產環境下，數據往往非均勻分布，具備較大的數據傾斜，簡單隨機抽樣會導致較大的誤差。另外，在查詢選擇率較低時，如處理涉及group-by的查詢，在簡單隨機抽樣構建的樣本集中，記錄數比較少的組不能夠得到充分的體現，會造成數據量較少的組查詢結果嚴重失真［5］。

在簡單隨機抽樣過程中，為了保證每條記錄被抽中的概率相等，可使用伯努利抽樣或蓄水池抽樣。

2.2 偏倚抽樣

針對簡單隨機抽樣的不足，出現了偏倚抽樣，每條記錄被抽到的概率可能不同。偏倚抽樣結合以往分析任務的信息（如歷史查詢、查詢日志），可以很好預測將來的查詢，因此可以加大相對重要記錄的抽取比例，降低相對不重要記錄的抽取比例。

偏倚抽樣和簡單隨機抽樣是其他抽樣技術的基礎。

2.3 分層抽樣

分層抽樣按照某些規則或某種特征，將原始數據集劃分成互不重疊的若干層，在每層內獨立、隨機地抽樣。假設總體被分為d層，總體樣本S大小為|S|，第i層的樣本大小為Si，則|S|=S1+S2+…+ Si+…+Sd，即總體的樣本由每層抽取的樣本構成。因此總體指標的估計值可由每層樣本估計值匯總求得。所以分層抽樣既可以對各層的指標進行估計，也可以對總體指標進行估計。

使用分層抽樣技術，可以在不增加樣本大小的前提下，提高查詢結果的精度，降低抽樣的誤差。但是，需要掌握查詢的一些信息，并基于此確定分層的標準［6～7］。

2.4 國會抽樣

在分析任務中，常伴隨大量的聚集查詢。國會抽樣是針對帶group-by的聚集查詢所提出，其主要思想是根據group-by可能涉及的屬性將原始數據分割為若干組，在總體樣本量已確定的前提下，每組利用隨機抽樣，抽取一定量的分樣本，并由分樣本構成總體樣本。

在基本國會抽樣中，為了更合理的分配各組樣本數，使樣本總體和分組樣本上執行的查詢結果達到較小誤差，第g分組抽取的樣本數Sg公式如下［8］：

表1 參數說明

3 CSSAQP算法設計

用近似查詢處理技術處理海量數據的聚集操作，常面臨數據傾斜的問題。海量原始數據中存在一些嚴重影響聚集查詢結果的記錄，即極端值。由于極端值的存在，使得對原始數據進行簡單隨機抽樣獲取的查詢結果可能會嚴重偏離真實值，導致很大的誤差。因此本文提出基于聚類的分層抽樣近似查詢處理算法。先利用k-means聚類算法，按某個數值屬性將原始記錄直觀地劃分為大值簇、小值簇、常值簇三個簇，再對三個簇按照分組屬性分別分層抽樣，構建總體數據集的樣本集；最后通過查詢重寫，在總體樣本集上執行查詢，返回近似結果。

3.1 極端值問題描述

假設關系R含字符屬性ItemNO，指標屬性Profit共4條記錄，如下所示：

關系R：

Record：｛<1，800>，<2，900>，<3，800>，<4，10000>｝

查詢Q：SELECT AVG（Profit）FROM R

采用隨機抽樣技術，抽取兩條記錄構成樣本集并執行Q。假設構成的隨機樣本S1為：｛<1，800>，<3，800>｝。原始記錄查詢結果Result=3125，S1上的近似結果Result'=800。由于極端值的存在，嚴重影響了近似查詢的結果。

3.2 CSSAQP算法

為了克服極端值對基于抽樣的近似查詢結果的影響，本文針對帶group-by的聚集操作提出基于聚類的分層抽樣近似處理算法CSSAQP。

預構建樣本集，需假設已知將來分析任務的一些信息。通過研究發現，分析任務中的查詢所涉及的列（如分組屬性列）通常比較穩定，在將來的查詢中也有很大的概率被用于構建查詢［9～10］。對關系表R，可將屬性劃分為字符屬性C和指標屬性V，其分組屬性G?C。在進行數據分析時，分析人員也通常已知需要計算的指標屬性。因此我們假設查詢的分組屬性和指標屬性已知。

指定關系表R、分組屬性G、指標屬性V、抽樣率f，CSSAQP即可構成樣本集S，當查詢到來時可通過查詢重寫在S上執行查詢，并返回真實值的近似結果。

CSSAQP分為兩個階段，分別為預構建樣本階段和查詢執行階段，如圖1所示。

圖1 CSSAQP算法圖解

第一階段：預構建樣本階段

利用K-means聚類算法將R按照V劃分為3個簇，各簇內再根據分組屬性G劃分為互不相交的若干層，然后在各層內按抽樣率f隨機抽樣，構建總的樣本表S。

第二階段：查詢執行階段

當查詢到來，經過查詢解析層獲取查詢語句Q中涉及的G、V，再通過樣本選擇器匹配相應的S并執行查詢，輸出查詢結果的近似值；如果樣本匹配失敗，則在R上執行查詢，輸出查詢結果的準確值。

表2 CSSAQP算法的主要符號及含義，表3算法1：CSSAQP的偽代碼表述。

表2 CSSAQP算法符號說明

表3 算法1：CSSAQP偽代碼表述

4 實驗結果與分析

4.1 實驗環境

本實驗在CentOS7操作系統上，搭建Hadoop集群，該集群包括1個master節點（用以運行namenode與jobtracker服務）和4個slave節點（用以運行datanode與tasktarcker服務），在此集群上搭建了Hive系統。集群中各個節點配置相同，均搭建在一個機架上。每個節點詳細軟件、硬件配置如表4所示。

表4 節點軟硬件配置

4.2 實驗分析

4.2.1 實驗設計

本文通過TPC-H生成測試數據。TPC-H定義了8張表，共22條查詢。可以通過設置scale參數生成總體數據量為指定大小的數據集，如設置salce=30，則生成總量為30G的數據。同時TPC-H還可以只生成某一張表［11］。

本實驗設置scale分別為1、5、15、30、50，只生成lineitem事實表，用以對多維分析中常用的帶group-by的聚集函數sum（）、avg（）進行測試，并從查詢結果的準確性和查詢執行的時間兩個方面驗證算法的有效性。

由于對多個指標屬性的聚集查詢，可以分解為多次單指標屬性的聚集查詢，因此定義以下查詢：

Q1：select l_returnflag,l_linestatus,sum(l_quantity)as sum_qty from lineitem group by l_returnflag, l_linestatus；

Q2：Select l_returnflag,l_linestatus,avg(l_quantity)as avg_qty from lineitem group by l_returnflag, l_linestatus；

在準確性驗證實驗中，數據分布對基于抽樣的近似處理結果影響很大，而TPC-H生成的數據服從均勻分布，因此在實驗開始前，先對數據進行預處理。

通過觀察發現TPC-H生成的lineitem表，其l_quantity屬性取值為1-50的整數值，由于服從均勻分布，每個值的數量大致相同。因此通過計算1-50正態分布的概率（平均值=25.5，方差=14.6），再與其對應數量做乘積，獲得1-50內大致服從正態分布的數據集，分別得到1200000～60000000條不等的五組數據，按1%的抽樣率對隨機抽樣（RS）、分層抽樣（SS）、聚類抽樣（CS）、聚類分層抽樣（CSS）構建樣本集，進行試驗對比。CS是直接將聚類結果進行隨機抽樣，即對聚類所得的簇分別進行隨機抽樣，對應算法1中分組屬性為?的情況，為說明該種情況下CSSAQP算法設計的合理性，故此也將其加入對比實驗。

衡量近似結果好壞的標準有許多，這里我們采用相對誤差率（以下簡稱誤差率）衡量誤差的高低。假設分組i的準確聚集值為ci，其近似值為

ci

′，則ci的誤差率εi定義如下［8］：

針對海量數據多維分析中含group-by的聚集操作，對其進行近似處理需要滿足以下兩個方面的要求：

一是近似查詢的結果要包含所有的分組。由于CSSAQP會對分組屬性先進行分層，并在各層內實施隨機抽樣，所以本條要求已具備。

二是每個分組的查詢結果要盡可能準確。因此可用所有分組的近似結果的最大誤差率來衡量整體近似結果的好壞。對含有n個分組的group-by聚集查詢引用以下定義［8］：

4.2.2 實驗分析

Q1執行結果如圖2所示。

圖2 Q1查詢執行結果圖

通過實驗發現，總體而言隨著數據量的增大，所有抽樣算法的誤差率都在逐步降低。說明在基于抽樣的近似查詢中，樣本量越大，近似結果越好；同時，CS和CSS算法的結果，也隨著數據量的增大逐步優于RS與CS抽樣算法。驗證了CSS算法在處理帶group-by的sum（）聚集查詢時具有一定的優勢。

圖3為Q2的執行結果。結果表明，對帶group-by的avg（）聚集運算，隨機抽樣在所有算法中所造成的誤差最大；隨著數據量的增大，CSS和CS比RS與SS具有更高的準確性。

綜合以上兩個實驗，隨著數據量的增大，CS算法都有比較好的效果，同時CSSAQP的誤差率明顯低于RS和SS算法，從而驗證了CSSAQP算法設計的合理性與有效性。

圖3 Q2查詢執行結果圖

在執行時間有效性的驗證中，準確值是在TPC-H生成的原始數據集上進行查詢，數據量大小分別為0.76G、3.6G、11.59G、23.63G、39.53G，查詢執行時間記作實際執行時間；近似結果是用CSSAQP算法按1%的抽樣率構建的樣本集求取，查詢執行時間記作近似計算執行時間。由于各種抽樣算法的查詢執行時間大體相同，因此僅以CSSAQP和實際執行時間做比較，結果如圖4、圖5所示。

圖4 Q1查詢執行時間圖

圖5 Q2查詢執行時間圖

隨著數據量的增大，所需的實際執行時間越來越長，且增幅較大。當數據量達到約11.59G時，Q1和Q2的實際執行時間已經超過200s；當數據量達到39.53G（集群總的內存大小）時，Q2的實際執行時間約10min，Q1的實際執行時間約25min。而使用CSSAQP算法的近似計算執行時間比較穩定，且遠低于實際執行時間，從而證明了CSSAQP算法的時間有效性。

5 結語

在海量數據進行多維分析中，研究如何既快又準地獲取分析結果是比較有意義的問題。本文提出基于聚類的分層抽樣算法，并通過對比實驗，從算法的時間有效性和結果準確性兩個角度，驗證該算法既能有效降低查詢的執行時間，同時較之隨機抽樣、分層抽樣算法又能提供一個更準確的近似結果。

［4］Liu Q.Approximate query processing［M］//Encyclopedia of Database Systems.Springer US，2009：113-119.

［5］Das G.Sampling methods in approximate query answering systems［M］//Encyclopedia of Data Warehousing and Mining，Second Edition.IGI Global，2009：1702-1707.

［6］Mehanna Y S，Mahmuddin M，Abdelaziz H S.Approximate Query Processing Concepts and Techniques［J］.Information Processing&Management，2015：453-468.

［7］金勇進，杜子芳，蔣妍.抽樣技術.第3版［M］.中國人民大學出版社，2012.

J

IN Yongjin，DU Zifang，JIANG Yan.Sampling Technology.3rd edition［M］.Renmin University of China Press，2012.

［8］Acharya S，Gibbons P B，Poosala V.Congressional samples for approximate answering of group-by queries［C］// ACM SIGMOD Record.ACM，2000，29（2）：487-498.

［9］Ganti V，Lee M L，Ramakrishnan R.ICICLES：Self-Tuning Samples for Approximate Query Answering［C］// VLDB.2000，176（187）.

［10］Agarwal S，Mozafari B，Panda A，et al.BlinkDB：queries with bounded errors and bounded response times on very large data［C］//Proceedings of the 8th ACM European Conference on Computer Systems.ACM，2013：29-42.

［11］http：//www.tpc.org/tpch/

［1］馮玉.數據倉庫環境中近似查詢處理技術研究［D］.北京：中國科學院研究生院（計算技術研究所），2002.

FENG Yu.Study on Approximate Query Processing Technology in Data Warehouse Environment［D］.Beijing：Graduate School of Computing Technology（Institute of Computing Technology），2002.

［2］高雅卓.多維聯機分析處理中的高效查詢關鍵方法研究［D］.合肥：合肥工業大學，2012.

GAO Yazhuo.Research on Key Methods of High Efficiency Query in Multi-dimensional Online Analysis and Processing［D］.Hefei：Hefei University of Technology，2012.

［3］Madria S K，Mohania M，Roddick J F.APPROXIMATE QUERY PROCESSING［J］.Information Organization and Databases：Foundations of Data Organization，2012，579：207.

CSSAQP：An Approximate Query Algorithm Based On Clustering Stratified Samping

XIE JinxingLI HuiCHEN MeiDAI Zhenyu
（Guizhou Engineering Lab for ACMIS，Guizhou University，Guiyang550025）

The approximate query processing technique is often applied to multidimensional analysis of massive data to shorten the execution time of the query and return the results as accurate as possible.Because of many extreme values in massive data，it will seriously affect the results of approximate query processing.Therefore，for the aggregation of massive data，this paper proposes a algorithm CSSAQP，which first clustered the original data set into three categories by a column，representing large clusters，small clusters and constant clusters，then use stratified sampling for each cluster by the group attribute，and constructed the overall sample，finally，the query is rewritten on the overall sample set to reduce the query time of the massive data aggregation operation，and improve the accuracy of the query task.Experiments show that the algorithm can not only shorten the time of aggregation query，but also improve the accuracy of query results.

AQP，aggregate query，clustering，stratified sampling

TP311.13

10.3969/j.issn.1672-9722.2017.06.023

2016年12月1日，

2017年1月27日

國家自然科學基金項目（編號：61462012，61562010，U1531246）；基于云計算的醫療信息管理系統關鍵技術研究及應用（編號：GY［2014］3018）；貴州省重大應用基礎研究項目（編號：JZ20142001）；貴州省教育廳自然科學項目（編號：黔科合人才團隊字［2015］53號）；貴州大學研究生創新基金（院級）資助。

謝金星，男，碩士研究生，研究方向：大數據管理與應用。李暉，男，副教授，碩士生導師，研究方向：大規模數據管理與分析，高性能數據庫，云計算。陳梅，女，碩士生導師，研究方向：數據庫技術、計算機應用技術。戴震宇，男，實驗師，研究方向：數據庫技術、計算機應用技術。