基于特征聚類的近似查詢分塊選擇方法

摘 要：大數(shù)據(jù)集群環(huán)境中，隨機訪問的低效性使得基于行級別抽樣的近似查詢處理方法在構建樣本時效率低下。該文將利用集群環(huán)境中數(shù)據(jù)分塊存儲的特性，以分塊級別來進行抽樣。在基準測試數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗，顯示此方法在降低數(shù)據(jù)讀取率，提高查詢響應速度的同時，保持較高的查詢精度。實驗中，僅需要讀取少于20%的數(shù)據(jù)就可以獲得低于5%的查詢誤差，且為數(shù)據(jù)集每個分塊的預計算的特征數(shù)據(jù)所需要的存儲空間小于數(shù)據(jù)集所占空間的0.04%。

關鍵詞：近似查詢處理；聚類；分塊抽樣；數(shù)據(jù)跳過；特征計算

中圖分類號：TP274 文獻標志碼：A 文章編號：2095-2945（2024）24-0019-05

Abstract： In big data cluster environment， the inefficiency of random access makes the approximate query processing method based on row-level sampling inefficient in constructing samples. This paper will make use of the characteristics of data block storage in the cluster environment to sample at the block level. Experiments on benchmark data sets and real data sets show that this method not only reduces the data reading rate and improves the query response speed， but also maintains high query accuracy. In the experiment， only less than 20% of the data need to be read to obtain a query error of less than 5%， and the storage space required for the precalculated feature data for each block of the dataset is less than 0.04% of the space occupied by the dataset.

Keywords： approximate query processing; clustering; block sampling; data skip; feature calculation

隨著近幾十年來數(shù)據(jù)存儲數(shù)量的指數(shù)級增長，單機數(shù)據(jù)庫逐漸不能滿足人們對于數(shù)據(jù)的存儲和查詢的需求，越來越多的人選擇將數(shù)據(jù)存儲到分布式的大數(shù)據(jù)集群中。但即便是配合一些大規(guī)模數(shù)據(jù)分析引擎，要處理數(shù)TB量級的數(shù)據(jù)，完整計算得到準確結果的時間消耗也常是無法接受的。通過使用近似查詢處理方法[1]，可以犧牲查詢結果的一部分準確性，來獲得更快的查詢響應。

在近似查詢處理方法中，抽樣是最常見的一種策略，它使用數(shù)據(jù)集中的一部分數(shù)據(jù)作為樣本來回答查詢。要為存儲在大數(shù)據(jù)集群上的數(shù)據(jù)集構建行級別抽樣的樣本，在讀取數(shù)據(jù)上的消耗很高，與掃描整個數(shù)據(jù)集無異。在HDFS文件系統(tǒng)中，數(shù)據(jù)被分塊存儲，行級別的隨機訪問十分低效。如果考慮到構建樣本的時間消耗，很多場景下，使用行級別抽樣的近似查詢并不能帶來速度上的提升。

與關系型數(shù)據(jù)庫將數(shù)據(jù)存儲在小塊中一樣，分布式文件系統(tǒng)也將數(shù)據(jù)存儲在可以單獨訪問的較大分塊中。在Hadoop中，文件的塊大小默認是128 MB。由于文件塊可以被獨立訪問，進行分塊級別的抽樣能夠帶來很大讀取效率的提升。構建樣本的數(shù)據(jù)讀取消耗只與抽樣率成正比。

以分塊級別抽樣構建合適的樣本來準確地回答查詢是一個很大的挑戰(zhàn)，樣本構建中只能完整選擇或忽略一個分塊。如果對于全部分塊進行均勻隨機抽樣，除非數(shù)據(jù)在整個數(shù)據(jù)集中均勻分布，構建的樣本對于原本的數(shù)據(jù)集是沒有代表性的。在大數(shù)據(jù)處理系統(tǒng)中，數(shù)據(jù)通常是被讀取或追加寫入，即數(shù)據(jù)按照到達數(shù)據(jù)庫的時間排序，手動調整數(shù)據(jù)順序來維持均勻分布的消耗一般是不能接受的。因此，隨機抽樣的做法在分塊級別抽樣中不可取。

本文提出一種根據(jù)查詢語句和分塊的特征信息，來選擇合適的分塊構建樣本，并回答查詢的方法。它在一個給定的抽樣率下，優(yōu)化查詢響應速度，同時盡可能保持查詢準確性。與存儲完整樣本需要比較大的存儲空間不同，本方法為每個分塊存儲預計算的特征信息，并利用其對分塊進行選擇性估計，聚類回答分塊選擇。實驗的結果表明，僅需要讀取少于20%的數(shù)據(jù)就可以獲得低于5%的查詢誤差。同時，為數(shù)據(jù)集每個分塊的預計算的特征數(shù)據(jù)所需要的存儲空間小于數(shù)據(jù)集所占空間的0.04%。

1 相關工作

1.1 行級別抽樣方法

基于抽樣的近似查詢處理方法已經(jīng)被廣泛的研究，常見的做法是在特地選擇的樣本上來計算查詢結果[1]。隨著研究的發(fā)展，更多的方法被用于改善行級別的抽樣，如利用輔助的數(shù)據(jù)結構（如異常點索引）[2]，又或者是將抽樣選擇偏向于少見分組。但是，研究[3]同樣表明，要在有限的存儲空間前提下提前構建抽樣樣本來回答任意查詢，效果一般不理想。

1.2 分塊級別抽樣方法

在線聚合方法使得查詢結果可以被漸進式地計算。在在線聚合將數(shù)據(jù)加載之前，先以分塊級別隨機打亂，使得數(shù)據(jù)分布更均勻，減少偏重，然后可以使用均勻抽樣的方式來進行抽樣[4]。打亂分塊操作的消耗取決于具體的實現(xiàn)。

相對更合適的做法是不依賴于打亂分塊的做法。通過為每個分塊計算構建特征摘要信息，再訓練一個使用分塊特征的監(jiān)督回歸模型，在查詢到來時，使用模型來選擇作為樣本的分區(qū)[5]。這種方法的問題是它依賴于查詢和分塊的特征來訓練模型，模型需要不斷地被重新訓練。關于摘要信息的計算，通過預訓練模型，將結構化數(shù)據(jù)集轉換為可用于回答基數(shù)估計查詢的簡潔摘要[6]。避免了每個數(shù)據(jù)集的訓練的同時，減少了構建摘要的時間。當數(shù)據(jù)集發(fā)生變化時，摘要也可以增量更新。

另一種離線的分塊抽樣方法[7]引入Random Sample Partition的數(shù)據(jù)模型，它將數(shù)據(jù)集用一組不相交的數(shù)據(jù)塊來表示，每一個RSP塊都有著和整個數(shù)據(jù)集相似的數(shù)據(jù)分布。因此，可以直接將查詢作用到一部分RSP塊上來獲得結果。

2 基于特征聚類的近似查詢分塊選擇

2.1 適用前提

本方法與工作[5]中的適用前提類似，適用于數(shù)據(jù)分布無關的大數(shù)據(jù)集群環(huán)境中的單表查詢。記數(shù)據(jù)集整體為T，其中包含k個分塊，第i個分塊記為ti。其中的列表示為{C1，…，Cn}，每列計算的特征維度為m，則預計算出的特征信息為k個m×n的特征矩陣集合U。

特征矩陣表示為 ，fmn表示第n列的第

m個特征的值。對于查詢Q，G為查詢中包含的分組，A為查詢中的聚合函數(shù)結果，則Ag，i為聚合函數(shù)在分塊i中作用到分組g上的結果，其中g∈G。對于給定的輸入：聚合查詢Q，期望抽取的分塊數(shù)p，特征矩陣集合U，需要輸出一組分塊選擇S={（t1，w1），（t2，w2），…（tp，wp）}，則最終的近似查詢結果如公式（1）所示。

=wi Ag，i，g∈G 。 （1）

本文的工作就是要根據(jù)給定的輸入輸出一個分塊選擇方案，使得近似查詢結果的誤差盡量小。

2.2 支持的查詢

本方法支持常見的聚合查詢，包含WHERE和GROUP BY子句。盡管只支持單表，但是可以通過將部分查詢改寫成對于中間視圖的查詢來間接提供支持。

1）聚合函數(shù)支持任意數(shù)量的COUNT，SUM，AVG函數(shù)。

2）GROUP BY子句支持任意多的表達式。但是作用的列的基數(shù)不應當過大，否則表現(xiàn)不佳。

3）WHERE子句支持多種形式，包含的運算符有“=，！=，>，<，between，in（類別列）”。

4）不支持JOIN從句。

2.3 方法概覽

如圖1所示。離線部分中為每個分塊構建靜態(tài)的特征統(tǒng)計信息并將結果存儲。在查詢到來時，接收查詢語句，特征信息，抽樣率作為輸入。計算選擇性估計，過濾掉不參與查詢的分塊。識別查詢中相關的列，讀取相關的特征信息數(shù)據(jù)，構建特征向量。利用特征向量進行聚類，得到聚類結果。根據(jù)抽樣率進行分塊選擇，輸出選擇的分塊以及每個分塊所占的權重。最后在每個分塊上執(zhí)行查詢得到結果，結合每個分塊的權重，計算最終的近似查詢結果。

2.4 特征的選擇和計算

2.4.1 選取要求

分塊的特征信息應當能夠有助于后續(xù)的分塊選擇，有效區(qū)別分布不同的分塊，或是能衡量不同分塊在查詢中的貢獻程度。

特征不宜在查詢中動態(tài)構建，需要提前計算并存儲，所以要考慮到計算的時間和空間復雜度。

2.4.2 預計算特征

對于數(shù)值列，計算最大值、最小值、均值、方差和標準差，構建等深直方圖。默認情況下，直方圖有10個桶。將時間列轉換為時間戳來計算此特征。對于類別列（包括數(shù)值和字符串），由于類別個數(shù)有限，計算總共的類別個數(shù)和每個類別的出現(xiàn)次數(shù)。表1總結了全部特征計算和存儲的復雜度。后續(xù)實驗中對比驗證了選擇的高級特征對于分塊的選擇有明顯幫助。

2.5 查詢特定的選擇性估計

選擇性估計是0到1之間的數(shù)值，它反映分塊中滿足查詢謂詞的行的比例。如果選擇性估計為0，則表示該分塊對于查詢完全沒有貢獻；選擇性估計為1，表示分塊中的全部行都滿足查詢條件。

使用查詢謂詞作用的列的直方圖來計算選擇性估計。為分塊結合查詢語句計算選擇性估計，可以估計查詢謂詞對分塊種數(shù)據(jù)的選擇性。根據(jù)選擇性估計，對于不存在符合查詢的行的分塊，執(zhí)行數(shù)據(jù)跳過的優(yōu)化策略，使其不參與分塊選擇和后續(xù)的查詢計算。

2.6 分塊聚類

對于分塊進行聚類，可以有效地區(qū)別開數(shù)據(jù)分布不同的分塊，作用效果類似于分層抽樣中的分層。使用為每個分塊計算出的特征矩陣來構建特征向量。特征向量的組成不包含與當前查詢無關的列，使得無關列的特征對于聚類結果無影響。對特征向量進行標準化使得聚類結果與列特征的值大小無關。

2.7 基于抽樣的分塊選擇

記總類別數(shù)為l，類別i的分塊數(shù)為mi，總分塊數(shù)m，總樣本分塊數(shù)n，則每個類別抽取的分塊數(shù)計算如公式（2）所示。

ni=n/l n/l<mimi n/l>=mi。 （2）

在類別中包含的分塊數(shù)小于需抽取的分塊數(shù)時，固定全部選取。對于每個類別內的分塊，進行系統(tǒng)抽樣來選擇。

2.8 分塊權重確定和最終計算

如果一個類別中的分塊全部被選擇參與樣本組成，則此類別組成的部分樣本權重為1。否則，按照此類別選擇的分塊比例來設置權重。在選擇的分塊上執(zhí)行查詢，結合權重得到最終的近似查詢結果=wi Ag，i，g∈G。

3 實驗評價

3.1 實驗設計

3.1.1 數(shù)據(jù)集

實驗在2種數(shù)據(jù)集上進行，包含TPC-H測試數(shù)據(jù)集和某大城市的交通車牌識別真實數(shù)據(jù)集。TPC-H測試數(shù)據(jù)集從Zipfian分布生成，偏度為1，比例因子為10。結果表有5億9千萬行，占據(jù)存儲空間約53.4 GB。每個分塊大小為128 MB，總計428個分區(qū)。交通車牌識別數(shù)據(jù)集包含從2023年2月23日到2023年3月5日記錄的卡口車牌識別數(shù)據(jù)。數(shù)據(jù)集包含5列數(shù)據(jù)，共約9億2千萬條數(shù)據(jù)，占據(jù)存儲空間約113.14 GB。每個分塊大小為128 MB，總計843個分區(qū)。

3.1.2 查詢語句

總共使用10條生成的測試查詢語句，其中一個示例查詢如下。

select count（l_partkey）， sum（l_quantity）， l_ship

mode， l_linenumber from df_full where l_shipmode='MAIL' and l_extendedprice > 14601.21 and l_extend

edprice < 17914.58 group by l_shipmode， l_linenumber order by l_linenumber

至于交通車牌識別數(shù)據(jù)集，則使用真實場景中需要執(zhí)行的查詢來進行測試。例如查詢計算一段時間內各個監(jiān)測點的車流量，查詢語句如下。

SELECT recv_devicecode， count（recv_plateno） FROM kksj where recv_date between $1 and $2 group by recv_devicecode;

3.1.3 參與比較的方法

隨機抽樣：分塊被均勻地隨機抽樣，最終的查詢結果按照抽樣率進行縮放。由于隨機抽樣的查詢結果受分塊選擇影響波動較大，最終比較查詢結果誤差時取10次查詢的平均結果。

隨機抽樣+選擇性估計：與隨機抽樣相同，過濾選擇性估計為0的分塊。

聚類+選擇性估計：本文中描述的方法實現(xiàn)，不使用模型來確定分塊選擇。

3.1.4 評價指標

關于查詢結果準確性的評價，使用平均相對誤差，即抽樣查詢結果與完全查詢結果相比，全部聚合函數(shù)結果的相對誤差平均值。記查詢聚合函數(shù)個數(shù)為m，抽樣查詢第i個聚合函數(shù)結果為Pi，完全查詢第i個聚合函數(shù)結果為Fi，則此抽樣查詢的平均相對誤差ARE計算如公式（3）所示。

ARE=。（3）

3.2 實驗結果分析

3.2.1 查詢誤差

實驗在比較各種方法在不同數(shù)據(jù)集和不同抽樣率下的查詢誤差表現(xiàn)，曲線整體越低，說明方法表現(xiàn)越好。如圖2所示，本文中的方法整體表現(xiàn)最優(yōu)。結果顯示：①由于數(shù)據(jù)分布非均勻，隨機抽樣查詢的結果取決于是否選擇到有效參與查詢的分塊，不隨抽樣率的增加而變好，誤差波動明顯。②利用查詢的選擇性估計來過濾不參與查詢分塊，能得到更好更穩(wěn)定的誤差表現(xiàn)。③通過對分塊進行聚類，在讀取分塊很少的情況下就能得到更好的誤差表現(xiàn)。且隨著更多分塊的讀取，查詢誤差也能得到有效的降低。

3.2.2 查詢時間消耗

實驗比較查詢在不同抽樣率下查詢的時間消耗，這也能有效地反應讀取的數(shù)據(jù)量大小。由表1可知，關于車流量的查詢，執(zhí)行時間與分塊抽樣率成正比，抽取的分塊越多，執(zhí)行查詢的時間越長。

3.2.3 預計算存儲占用

預計算特征為數(shù)據(jù)集的每一列構建，每個分塊計算出的特征數(shù)據(jù)總量一致，存儲消耗取決于數(shù)據(jù)表列數(shù)和列值長度。由表2可知，為每個數(shù)據(jù)集預計算特征的存儲占用小于數(shù)據(jù)集本身存儲占用的0.04%，屬于可以接受的范圍。

4 結束語

本文介紹了一種在大數(shù)據(jù)集群環(huán)境中利用分塊特征信息進行抽樣樣本的分塊選擇的方法。它對分塊進行特征預計算，借助分塊的聚類結果和其在查詢下的選擇性估計來進行分塊選擇。取決于是否已知查詢，選用模型預測或隨機抽樣的方法。最終在選擇的分塊上執(zhí)行查詢，計算出最終的近似查詢結果。實驗結果顯示，由于顯著減少了數(shù)據(jù)讀取，這種方法與行級別抽樣方法相比能夠明顯提升查詢速度，并且能夠獲得使人滿意的誤差表現(xiàn)，同時存儲開銷也很小。同時，此方法的研究仍然有著許多工作需要完成，比如將方法應用到多數(shù)據(jù)集，提供對于多表查詢的支持。

參考文獻：

[1] CHAUDHURI S， DING B，KANDULA S.Approximate Query Processing：No Silver Bullet[C]//the 2017 ACM International Conference.ACM，2017.

[2] CHAUDHURI S，DAS G，DATAR M，et al. Overcoming Limitations of Sampling for Aggregation Queries[C]//International Conference on Data Engineering.IEEE，２001.

[3] KANDULA S， SHANBHAG Ａ， ＶＩＴＯＲＯＶＩＣ Ａ，ｅｔ al. Quickr：Lazily Approximating Complex AdHoc Queries in BigData Clusters[C]//the 2016 International Conference.ACM，2016.

[4] KALAVRI V， BRUNDZA V， VLASSOV V. Block Sampling： Efficient Accurate Online Aggregation in MapReduce[C]//IEEＥ Fifth International Conference on Cloud Computing Technology and Science，２013.

[5] RONG K， LU Y， BAILIS P， et al. Approximate Partition Selection for Big-Data Workloads using Summary Statistics[J].arxiv，2020.

[6] LＵ Ｙ， ＫＡＮＤＵＬＡ Ｓ， ＫＮＩＧ Ａ Ｃ， ｅｔ ａｌ． Ｐｒｅ-training summarization models of structured datasets for cardinality estimation[J].Proceedings of the VLDB Endowment，2021.

[7] SALLOUM S， HUANG Z J， HE Y. Random Sample Partition： A Distributed Data Model for Big Data Analysis[J].IEEE Trans. Industrial Infｏｒｍａｔｉｃｓ，２０１９，１５（１１）：５８４６－５８54.