向量分組聚集計(jì)算技術(shù)研究

張 宇，張延松

1.國(guó)家衛(wèi)星氣象中心，北京100081 2.中國(guó)人民大學(xué) 信息學(xué)院，北京100872

數(shù)據(jù)庫(kù)的OLAP查詢主要由選擇、投影、連接、分組、聚集等基本關(guān)系操作組成，其中分組聚集操作需要對(duì)海量的事實(shí)數(shù)據(jù)按指定的屬性進(jìn)行分組并執(zhí)行聚集計(jì)算，是一個(gè)典型的數(shù)據(jù)密集型負(fù)載，也是一個(gè)對(duì)查詢性能有較大影響的操作符，但OLAP查詢性能并不是簡(jiǎn)單的關(guān)系操作符性能的疊加。通過(guò)實(shí)驗(yàn)測(cè)試發(fā)現(xiàn)，GPU數(shù)據(jù)庫(kù)MapD在連接、分組聚集等主要操作符的性能上較其CPU版本具有顯著的優(yōu)勢(shì)，但對(duì)于查詢操作整體而言，即使在查詢的數(shù)據(jù)量低于GPU本地內(nèi)存的情況下，GPU版本的查詢性能也要低于CPU版本。單純提高關(guān)系操作符在GPU上的執(zhí)行性能并不能最大化GPU數(shù)據(jù)庫(kù)整體性能，需要以異構(gòu)計(jì)算平臺(tái)作為數(shù)據(jù)庫(kù)新的硬件假設(shè)，優(yōu)化設(shè)計(jì)面向異構(gòu)計(jì)算平臺(tái)的查詢處理模型。通過(guò)定制面向異構(gòu)計(jì)算平臺(tái)特征的操作符優(yōu)化查詢算法以提高查詢算法與硬件特性的適應(yīng)性來(lái)提升查詢性能。

本文以O(shè)LAP中重要的分組聚集操作為研究對(duì)象，將傳統(tǒng)查詢處理模型中位于查詢樹末端的分組聚集操作拆分為分組和聚集計(jì)算兩個(gè)操作，分組操作采用“早分組（early grouping）”策略下推到表掃描階段并與維表綁定，聚集計(jì)算操作采用“晚聚集（late aggregation）”策略保留在查詢樹末端并與事實(shí)表綁定。分組操作融合到連接操作中，通過(guò)向量索引實(shí)現(xiàn)分組與聚集計(jì)算之間的映射。向量索引聚集技術(shù)將數(shù)據(jù)密集型的聚集計(jì)算從計(jì)算密集型的連接操作中分離出來(lái)，將傳統(tǒng)流水線查詢處理模型中的計(jì)算密集型操作與數(shù)據(jù)密集型操作分離，同時(shí)建立了聚集計(jì)算性能測(cè)試基準(zhǔn)，以便更加準(zhǔn)確地評(píng)估聚集計(jì)算性能并匹配最佳的計(jì)算平臺(tái)，實(shí)現(xiàn)在異構(gòu)計(jì)算平臺(tái)上負(fù)載的優(yōu)化分配。

本文的貢獻(xiàn)主要體現(xiàn)在以下幾個(gè)方面：

（1）提出了基于私有向量的向量分組聚集算法和基于共享向量的向量分組聚集算法，設(shè)計(jì)了cache-conscious vector grouping benchmark，分析了算法性能與硬件參數(shù)之間的關(guān)聯(lián)性，提出了算法優(yōu)化選擇策略。

（2）提出了將分組聚集操作從傳統(tǒng)的流水線中分離的策略，通過(guò)向量聚集技術(shù)實(shí)現(xiàn)數(shù)據(jù)密集型負(fù)載與計(jì)算密集型負(fù)載的分離，為準(zhǔn)確評(píng)估聚集計(jì)算代價(jià)和優(yōu)化配置硬件資源提供必要的條件。

（3）對(duì)比了向量分組聚集算法與當(dāng)前最優(yōu)的內(nèi)存數(shù)據(jù)庫(kù)Hyper、GPU數(shù)據(jù)庫(kù)MapD在不同分組勢(shì)集參數(shù)下的向量分組聚集操作性能，揭示了算法的性能特征，通過(guò)量化的向量分組聚集基準(zhǔn)性能測(cè)試提供硬件平臺(tái)最優(yōu)匹配策略。

1 相關(guān)工作

當(dāng)前高性能數(shù)據(jù)庫(kù)以內(nèi)存數(shù)據(jù)庫(kù)和基于硬件加速器的數(shù)據(jù)庫(kù)（如GPU數(shù)據(jù)庫(kù)）為代表，其性能的關(guān)鍵影響因素包括：關(guān)鍵算法性能、查詢處理模型性能、異構(gòu)平臺(tái)協(xié)同計(jì)算性能等。

在傳統(tǒng)的關(guān)系操作中，連接是查詢性能重要的影響因素，近年研究熱點(diǎn)問題之一是如何通過(guò)面向硬件特性的優(yōu)化技術(shù)提高連接操作性能。NPO（No-partitioning hash join）[1]、PRO（Radix-partitioning hash join）[2]和sortmerge[3]等代表了當(dāng)前最優(yōu)的內(nèi)存連接技術(shù)，其中以hardware-conscious的PRO算法性能最優(yōu)。哈希連接是數(shù)據(jù)庫(kù)中通用的算法，算法優(yōu)化涉及較多的影響因素，加大了優(yōu)化的難度[4]。Array Join[5]和AIR[6]是面向外鍵特性的定制化連接技術(shù)，針對(duì)OLAP特性的定制將哈希表簡(jiǎn)化為數(shù)組，將哈希探測(cè)操作優(yōu)化為數(shù)組地址訪問，通過(guò)面向負(fù)載與數(shù)據(jù)特征的定制優(yōu)化進(jìn)一步提高連接性能。

進(jìn)一步地，連接優(yōu)化技術(shù)從通用的多核CPU平臺(tái)擴(kuò)展到硬件加速器平臺(tái)，利用專用硬件的高性能來(lái)加速連接操作。近年來(lái)一系列面向?qū)Ｓ糜布铀倨鳎鏕PU[7-9]、Phi[10]、FPGA[11-12]以及多異構(gòu)加速器的連接優(yōu)化技術(shù)研究深入探索了如何基于硬件加速器的物理特性加速連接性能的優(yōu)化技術(shù)。已有的研究主要聚焦于如何挖掘特定硬件加速器的計(jì)算特性，但對(duì)硬件加速器存儲(chǔ)空間利用率在算法中的影響未賦予足夠的權(quán)重。當(dāng)前研究中性能最優(yōu)的PRO分區(qū)哈希連接算法需要付出額外的數(shù)據(jù)分區(qū)存儲(chǔ)和計(jì)算代價(jià)來(lái)?yè)Q取較高的性能，這在CPU平臺(tái)的內(nèi)存模式下以內(nèi)存足夠大的默認(rèn)假設(shè)為前提，但在硬件加速器平臺(tái)，較小的內(nèi)存容量破壞了這一基礎(chǔ)假設(shè)，使其理想性能可支持的數(shù)據(jù)量大幅削減。在文獻(xiàn)[13]中通過(guò)實(shí)驗(yàn)測(cè)試發(fā)現(xiàn)基于分區(qū)技術(shù)的PRO算法在Phi加速器上所支持的數(shù)據(jù)量是不分區(qū)技術(shù)的NPO算法的一半，而且性能低于面向OLAP定制的AIR算法。從硬件的發(fā)展趨勢(shì)來(lái)看，硬件加速器內(nèi)存與連接通道帶寬性能始終存在較大差距，提高硬件加速器內(nèi)存利用率、提高關(guān)鍵算法的數(shù)據(jù)局部性是兩個(gè)重要的優(yōu)化維度。連接技術(shù)的深入研究證明了在多核CPU和GPU等硬件加速器平臺(tái)上的性能優(yōu)化方法的效果，但這些研究通常面向獨(dú)立的連接操作，對(duì)于OLAP場(chǎng)景下的多表星形連接以及整個(gè)查詢執(zhí)行計(jì)劃中計(jì)算密集型的連接操作與數(shù)據(jù)密集型的分組聚集操作之間的優(yōu)化匹配涉及較少，而連接技術(shù)的選擇受分組聚集操作技術(shù)的影響較大，需要綜合考慮性能、數(shù)據(jù)效率、數(shù)據(jù)局部性等影響因素。

當(dāng)前的GPU連接優(yōu)化技術(shù)研究關(guān)注于連接操作性能問題，而在關(guān)系數(shù)據(jù)庫(kù)的Volcano查詢處理模型中連接操作處于查詢流水線中間，其性能受其他操作符影響較大。文獻(xiàn)[14]指出在實(shí)際的TPC-H查詢中單獨(dú)連接操作執(zhí)行時(shí)間占比僅為10%～15%，通過(guò)GPU僅加速連接操作對(duì)于提升整體查詢處理性能的作用受到一定限制。

分組聚集是OLAP查詢中另一個(gè)重要的操作符，主要的分組聚集方法包括排序分組聚集和哈希分組聚集兩大類。排序分組聚集適合于非常大的分組勢(shì)集并且需要將查詢樹前端的連接結(jié)果物化下來(lái)才能執(zhí)行，不適合流水查詢處理模型。哈希分組聚集適合OLAP查詢中分組勢(shì)集較小的場(chǎng)景，而且適應(yīng)流水線查詢模式，在數(shù)據(jù)庫(kù)中應(yīng)用較廣。哈希聚集又分為基于共享哈希表、獨(dú)立哈希表和分區(qū)哈希表三種方法[15]，其優(yōu)化技術(shù)原理也與哈希連接算法類似，不同之處在于分組聚集操作中的哈希分組表遠(yuǎn)小于哈希連接操作中的哈希表，而且分組聚集操作涉及的數(shù)據(jù)集遠(yuǎn)大于連接操作。除通用的哈希分組聚集算法之外，文獻(xiàn)[6]中使用了面向OLAP負(fù)載定制化的多維數(shù)組聚集計(jì)算方法，通過(guò)將各維表上的分組屬性映射為一個(gè)多維數(shù)組實(shí)現(xiàn)通過(guò)簡(jiǎn)單的多維數(shù)組代替哈希表的聚集計(jì)算。在Oracle內(nèi)存數(shù)據(jù)庫(kù)中使用的內(nèi)存聚集IMA算法[16]也使用了類似的方法，通過(guò)Key Vector映射連接鍵值和分組編碼，通過(guò)多維聚集器進(jìn)行分組聚集計(jì)算。從算法實(shí)現(xiàn)技術(shù)來(lái)看，哈希分組聚集方法通用性較強(qiáng)，多維數(shù)組和IMA算法面向OLAP負(fù)載特征定制化設(shè)計(jì)，在性能、代碼執(zhí)行效率等方面具有顯著的優(yōu)勢(shì)。

分組聚集計(jì)算也是GPU數(shù)據(jù)庫(kù)的重要操作，在GPU平臺(tái)上的分組聚集計(jì)算方法因GPU存儲(chǔ)層次的多樣性而產(chǎn)生不同的優(yōu)化技術(shù)[17]，分組聚集計(jì)算是典型的數(shù)據(jù)密集型負(fù)載，其綜合性能評(píng)估還需要增加PCIe通道數(shù)據(jù)傳輸代價(jià)。從處理模型來(lái)看，CPU平臺(tái)完成了從一次一列處理模型[18]向一次一向量[19]、實(shí)時(shí)編譯[20]查詢處理模型升級(jí)，但GPU數(shù)據(jù)庫(kù)通常采用一次一操作（一次一列）的處理模式，產(chǎn)生較高的中間結(jié)果物化代價(jià)，降低了GPU內(nèi)存的利用率。同時(shí)，傳統(tǒng)的流水處理模式中，分組聚集操作位于連接操作之后，難以從查詢計(jì)劃中有效地分離計(jì)算密集型與數(shù)據(jù)密集型負(fù)載。文獻(xiàn)[21]提出一種整合MOLAP多維計(jì)算與ROLAP關(guān)系存儲(chǔ)的OLAP實(shí)現(xiàn)技術(shù)，并將傳統(tǒng)的OLAP查詢計(jì)劃分解合為維映射、多維計(jì)算與聚集計(jì)算三個(gè)處理階段，實(shí)現(xiàn)以負(fù)載為粒度的異構(gòu)查詢處理。本文在此基礎(chǔ)上進(jìn)一步研究基于向量分組聚集計(jì)算實(shí)現(xiàn)技術(shù)，探索硬件參數(shù)對(duì)向量分組聚集算法性能的影響因素，以及分組聚集計(jì)算在CPU與GPU平臺(tái)的執(zhí)行策略。

2 異構(gòu)平臺(tái)OLAP計(jì)算框架

在CPU-GPU異構(gòu)平臺(tái)上，GPU并行計(jì)算能力強(qiáng)大，顯存帶寬更高，但容量相對(duì)較小，CPU與GPU之間的PCIe通道帶寬性能遠(yuǎn)低于內(nèi)存帶寬和GPU顯存帶寬。對(duì)于異構(gòu)平臺(tái)上的計(jì)算負(fù)載來(lái)說(shuō)，數(shù)據(jù)有多大，算得有多快，數(shù)據(jù)是否具有共享性等因素都是決定計(jì)算負(fù)載執(zhí)行場(chǎng)地的影響因素。

本章首先討論以分組聚集計(jì)算為中心的查詢處理策略，然后介紹面向異構(gòu)計(jì)算平臺(tái)的OLAP計(jì)算框架，實(shí)現(xiàn)基于負(fù)載特征和異構(gòu)計(jì)算平臺(tái)特征的定制化OLAP查詢處理模型。

2.1 以分組聚集計(jì)算為中心的查詢處理策略

在OLAP應(yīng)用中，分組聚集計(jì)算是在龐大的事實(shí)表上按GROUP BY屬性分組后進(jìn)行聚集計(jì)算，其依賴的數(shù)據(jù)集較大，而且分組操作依賴于前面連接操作的結(jié)果集，在CPU-GPU混合平臺(tái)上執(zhí)行時(shí)其執(zhí)行場(chǎng)地的選擇既受數(shù)據(jù)量的影響又受連接操作場(chǎng)地的影響。關(guān)系數(shù)據(jù)庫(kù)采用流水迭代查詢處理模型，在查詢優(yōu)化中主要采用將選擇、投影等操作下推到底層表掃描節(jié)點(diǎn)的優(yōu)化策略，分組操作涉及不同的表而通常采用后物化方式在連接操作之后實(shí)時(shí)執(zhí)行哈希分組并與聚集計(jì)算合并。OLAP查詢中分組數(shù)量遠(yuǎn)低于記錄數(shù)量的特征決定了后物化分組方法增加了重復(fù)的哈希分組探測(cè)計(jì)算代價(jià)并且與連接操作形成強(qiáng)依賴關(guān)系，連接操作的執(zhí)行場(chǎng)地通常就是分組聚集操作的執(zhí)行場(chǎng)地。在CPU-GPU異構(gòu)計(jì)算平臺(tái)上若連接操作與分組聚集操作分布于不同的處理器平臺(tái)時(shí)，在異構(gòu)計(jì)算平臺(tái)上連接結(jié)果物化后再執(zhí)行分組聚集操作方法產(chǎn)生較高的連接結(jié)果物化代價(jià)。

基于異構(gòu)計(jì)算平臺(tái)的存儲(chǔ)與計(jì)算資源不均衡的特性，本文采用以數(shù)據(jù)局部性優(yōu)化為中心、以計(jì)算獨(dú)立性為基礎(chǔ)的異步OLAP查詢優(yōu)化策略，通過(guò)反向查詢樹優(yōu)化方法優(yōu)化異構(gòu)計(jì)算平臺(tái)上的關(guān)系操作實(shí)現(xiàn)技術(shù)。分組聚集操作應(yīng)用于事實(shí)表大數(shù)據(jù)集，在CPU-GPU混合平臺(tái)數(shù)據(jù)移動(dòng)代價(jià)最高，從數(shù)據(jù)局部性的角度來(lái)看最優(yōu)的計(jì)算平臺(tái)是CPU；從性能的角度來(lái)看，關(guān)鍵問題是CPU分組聚集計(jì)算最優(yōu)性能在什么負(fù)載區(qū)間能超過(guò)GPU計(jì)算以及分組聚集計(jì)算選擇CPU或GPU作為計(jì)算平臺(tái)的優(yōu)化選擇策略。本節(jié)介紹了分組聚集計(jì)算的優(yōu)化方法，以及受優(yōu)化的分組聚集計(jì)算反向傳播而影響的相關(guān)關(guān)系操作實(shí)現(xiàn)技術(shù)，提出了以分組聚集計(jì)算為核心的OLAP查詢優(yōu)化方法，并在實(shí)驗(yàn)部分給出了分組聚集計(jì)算對(duì)CPU和GPU平臺(tái)的優(yōu)化選擇策略。

（1）分組聚集優(yōu)化

從OLAP邏輯數(shù)據(jù)模型的角度來(lái)看，OLAP操作可以抽象為在事實(shí)數(shù)據(jù)上按給定的選擇策略和分組策略進(jìn)行聚集計(jì)算。從關(guān)系角度看，OLAP操作最理想的方法是直接執(zhí)行事實(shí)表上的索引分組聚集計(jì)算，即每一條事實(shí)記錄根據(jù)一種特定的索引結(jié)構(gòu)確定自己是否參與查詢的聚集計(jì)算，并且可以直接訪問用于聚集計(jì)算的累加器地址。從索引實(shí)現(xiàn)技術(shù)的角度看，實(shí)現(xiàn)理想的分組聚集計(jì)算需要將分組屬性向量化并且將分組向量映射到事實(shí)表位圖索引中實(shí)現(xiàn)直接的分組聚集計(jì)算。

圖1為向量分組聚集計(jì)算操作示意圖，右側(cè)分組向量為基于SQL命令中GROUP BY語(yǔ)句構(gòu)造的分組向量，每個(gè)分組值對(duì)應(yīng)向量中的一個(gè)單元，分組ID為向量單元地址（數(shù)組下標(biāo)）。相應(yīng)地，事實(shí)記錄上的向量分組聚集操作基于向量索引實(shí)現(xiàn)。左側(cè)為向量索引結(jié)構(gòu)示意圖，向量索引是一種多位位圖結(jié)構(gòu)，非空值代表相應(yīng)位置的事實(shí)記錄參與查詢最終的分組聚集計(jì)算，向量索引值為最終分組向量單元ID，通過(guò)向量索引實(shí)現(xiàn)對(duì)事實(shí)記錄按位置訪問并按向量索引值直接映射到分組向量單元聚集計(jì)算。向量索引的基本結(jié)構(gòu)為與事實(shí)記錄等長(zhǎng)的定長(zhǎng)向量，向量寬度最小為向量索引中非空值數(shù)量（分組向量勢(shì)集）對(duì)應(yīng)的最小二進(jìn)制位，即lb|分組向量|，向量索引的單元地址與事實(shí)記錄地址為一一映射關(guān)系。當(dāng)向量索引中非空值數(shù)量較少，即查詢選擇率較低時(shí)，向量索引可以采用壓縮的二元組key/value結(jié)構(gòu)，key值為非空向量索引單元的記錄位置，value為該向量索引單元存儲(chǔ)的分組ID。在應(yīng)用中，定長(zhǎng)向量索引可以選擇一個(gè)適合的公共寬度，如int_16（對(duì)應(yīng)最大216個(gè)分組），不同的OLAP查詢可以共享該向量索引結(jié)構(gòu)，減少多查詢處理時(shí)的動(dòng)態(tài)內(nèi)存分配代價(jià)。壓縮向量索引在低選擇率查詢執(zhí)行時(shí)降低了向量索引掃描代價(jià)，不同查詢需要生成不同長(zhǎng)度的壓縮向量索引，需要為壓縮向量索引動(dòng)態(tài)分配內(nèi)存。

圖1 向量分組聚集操作

從算法設(shè)計(jì)的角度來(lái)看，本文提出的向量分組聚集操作在分組向量存儲(chǔ)結(jié)構(gòu)上達(dá)到了最小化存儲(chǔ)空間，直接映射到分組向量單元的聚集計(jì)算達(dá)到了分組計(jì)算的最小化CPU計(jì)算時(shí)間，在聚集數(shù)據(jù)掃描操作上通過(guò)壓縮向量索引達(dá)到最高訪問效率，在獨(dú)立的分組聚集操作實(shí)現(xiàn)技術(shù)上達(dá)到了局部最優(yōu)。從數(shù)據(jù)庫(kù)查詢處理模型的角度來(lái)看，關(guān)鍵問題是如何優(yōu)化數(shù)據(jù)庫(kù)查詢處理模型以創(chuàng)建最優(yōu)的分組聚集計(jì)算所需的分組向量和壓縮向量索引數(shù)據(jù)結(jié)構(gòu)，來(lái)最大化分組聚集操作性能，從而為分組聚集操作的執(zhí)行場(chǎng)地選擇提供支持。

向量分組聚集操作基于向量索引順序掃描和事實(shí)數(shù)據(jù)按位置訪問操作，是一種線性的處理方式，適合于多核CPU并行處理。圖2顯示多核并行向量聚集操作的基本實(shí)現(xiàn)方法：若向量索引為定長(zhǎng)向量，按線程數(shù)量邏輯劃分向量索引分區(qū)，并按相同的位置邏輯劃分事實(shí)數(shù)據(jù)分區(qū)，每個(gè)線程并行掃描向量索引分區(qū)并執(zhí)行在對(duì)應(yīng)事實(shí)數(shù)據(jù)分區(qū)上的向量聚集操作；若向量索引為壓縮格式，采用與定長(zhǎng)向量索引相同的邏輯分區(qū)一方面需要掃描壓縮向量索引的key值確定分區(qū)位置，另一方面當(dāng)向量索引中非空值分布不均衡時(shí)定長(zhǎng)邏輯分區(qū)導(dǎo)致不同線程中實(shí)際執(zhí)行的聚集計(jì)算代價(jià)不同，負(fù)載難以均衡，采用在壓縮向量索引上均衡邏輯分區(qū)策略，簡(jiǎn)化邏輯分區(qū)的位置計(jì)算并使各線程對(duì)應(yīng)邏輯分區(qū)上的聚集計(jì)算代價(jià)較為均衡。

圖2 多核并行向量分組聚集操作

在本文提出的在并行向量分組聚集操作執(zhí)行時(shí)實(shí)現(xiàn)技術(shù)中，可以采用三種聚集計(jì)算方法：多線程共享統(tǒng)一的分組向量，執(zhí)行基于并發(fā)控制機(jī)制的全局分組聚集計(jì)算；每個(gè)線程使用私有分組向量完成本線程邏輯事實(shí)數(shù)據(jù)分片上的分組聚集計(jì)算操作，各線程處理完畢后執(zhí)行線程間分組向量的歸并計(jì)算，生成最終的分組向量；當(dāng)分組向量勢(shì)值非常大時(shí)，采用基于分組向量ID的Radix分區(qū)方法對(duì)分組向量和相應(yīng)的事實(shí)數(shù)據(jù)進(jìn)行分區(qū)，使每個(gè)分區(qū)的分組向量小于私有cache，然后在每個(gè)分區(qū)上執(zhí)行基于私有分組向量的向量分組聚集計(jì)算或哈希分組聚集計(jì)算。當(dāng)分組向量比CPU線程私有cache（L1 cache、L2 cache、L3 cache slice）小時(shí)，分組聚集計(jì)算具有較高的數(shù)據(jù)局部性，私有分組向量提高了并行計(jì)算效率。當(dāng)分組向量超過(guò)CPU線程私有cache時(shí)，私有分組向量產(chǎn)生較高的cache miss，共享分組向量具有較好的效率。基于Radix分區(qū)的分組聚集方法加倍了內(nèi)存開銷，在GPU使用較小內(nèi)存執(zhí)行大數(shù)據(jù)分組聚集計(jì)算時(shí)進(jìn)一步降低了GPU內(nèi)存利用率，因此本文中暫未對(duì)Radix分區(qū)分組聚集計(jì)算進(jìn)行深入的研究，在對(duì)比實(shí)驗(yàn)中主要選擇代表性的GPU數(shù)據(jù)庫(kù)MapD的分組聚集實(shí)現(xiàn)技術(shù)作為GPU上分組聚集操作的代表性實(shí)現(xiàn)技術(shù)。在實(shí)驗(yàn)部分測(cè)試前兩種多核并行向量分組聚集計(jì)算的性能，通過(guò)實(shí)驗(yàn)確定兩種方法的適用范圍。在性能指標(biāo)的選擇上，創(chuàng)造性地設(shè)計(jì)了數(shù)據(jù)處理帶寬指標(biāo)，即用分組聚集計(jì)算操作涉及的數(shù)據(jù)量除以查詢處理時(shí)間以獲得數(shù)據(jù)處理的帶寬性能，將PCIe帶寬作為一個(gè)閾值來(lái)決定分組聚集計(jì)算的執(zhí)行場(chǎng)地選擇策略：

①當(dāng)數(shù)據(jù)處理帶寬>PCIe帶寬時(shí)，分組聚集操作的執(zhí)行場(chǎng)地為CPU。

②當(dāng)數(shù)據(jù)處理帶寬

執(zhí)行場(chǎng)地選擇策略確定了在向量分組聚集操作下選擇CPU作為執(zhí)行場(chǎng)地的規(guī)則，但對(duì)于是否在GPU端執(zhí)行還需要額外的選擇策略，如GPU端分組聚集操作的性能、基于數(shù)據(jù)移動(dòng)的GPU分組聚集操作是否優(yōu)于CPU端分組聚集操作性能、GPU端數(shù)據(jù)存儲(chǔ)策略、GPU分組計(jì)算方法等因素的影響，將在未來(lái)的工作中繼續(xù)深入探索完整的執(zhí)行場(chǎng)地選擇優(yōu)化策略。本文采用的執(zhí)行場(chǎng)地優(yōu)化選擇策略在實(shí)驗(yàn)部分SSB基準(zhǔn)數(shù)據(jù)集上的測(cè)試結(jié)果表明，在典型的OLAP負(fù)載中該規(guī)則已準(zhǔn)確選擇分組聚集操作執(zhí)行的最優(yōu)場(chǎng)地。

（2）星形連接操作優(yōu)化

在查詢處理模型的優(yōu)化設(shè)計(jì)中采用反向貪心算法，即從查詢樹末端操作開始設(shè)計(jì)最優(yōu)的實(shí)現(xiàn)方法，然后反向傳播，確定前一操作相對(duì)應(yīng)的最優(yōu)實(shí)現(xiàn)技術(shù)，以保證以分組聚集計(jì)算為中心的查詢處理達(dá)到最優(yōu)。

確定OLAP查詢處理末端分組聚集操作的最優(yōu)模式后，需要反向優(yōu)化前端的星形連接操作，要求星形連接操作輸出向量索引。

圖3給出星形連接操作的幾種實(shí)現(xiàn)方法。本文的星形連接操作只涉及較小的維表輸出數(shù)據(jù)結(jié)構(gòu)（向量或哈希表）、中等大小的事實(shí)表外鍵和向量索引，不涉及龐大的事實(shí)數(shù)據(jù)，在連接操作中消除傳統(tǒng)事實(shí)表和事實(shí)數(shù)據(jù)之間的關(guān)聯(lián)性，從而使連接操作可以在較小的事實(shí)表外鍵列上獨(dú)立執(zhí)行，也使連接操作可以與分組聚集操作分離，成為兩個(gè)獨(dú)立執(zhí)行的操作，在執(zhí)行場(chǎng)地的選擇上消除強(qiáng)關(guān)聯(lián)。當(dāng)維表采用代理鍵（surrogate key，連續(xù)的自然數(shù)列）時(shí)，可以使用優(yōu)化的AIR[13]（vector referencing[21]）算法執(zhí)行連接及星形連接操作，外鍵值直接映射到維向量的數(shù)組地址。當(dāng)維表主鍵不能直接映射為地址時(shí)，可以采用傳統(tǒng)的哈希連接方法，為維表（主鍵，維分組ID）創(chuàng)建哈希表。本文采用cube映射方式將GROUP-BY屬性映射為分組向量，即將各維表上的GROUP-BY屬性映射為一個(gè)多維cube的各維ID，當(dāng)一個(gè)維表上存在多個(gè)維屬性時(shí)則通過(guò)降維方法將多個(gè)屬性的distinct值映射為該維的復(fù)合ID。使用該多維cube分組時(shí)稱為cube分組，將該多維cube映射為一個(gè)一維向量分組稱為向量分組，執(zhí)行星形連接時(shí)需要迭代地通過(guò)各維表的分組ID計(jì)算出在多維cube上一維地址，作為后一階段向量分組聚集操作中的分組向量ID。cube分組對(duì)應(yīng)了GROUP-BY屬性映射出的多維空間，在連接操作執(zhí)行時(shí)可能部分單元在事實(shí)表上沒有實(shí)際對(duì)應(yīng)的數(shù)據(jù)，可以通過(guò)向量緊縮方式進(jìn)一步壓縮向量大小，生成與最終查詢結(jié)果GROUP-BY屬性對(duì)等的向量分組。具體方法是通過(guò)一個(gè)全局遞增序列在執(zhí)行星形連接時(shí)為每個(gè)實(shí)際向量分組單元分配唯一的ID，并將此ID作為最終向量索引中的分組ID值，原始向量分組作為最終向量與GROUP-BY屬性cube分組的映射表。

圖3 星形連接操作

當(dāng)維表不滿足主鍵-地址映射或者使用代理鍵主鍵但維向量很稀疏時(shí)使用哈希連接方法，圖3中哈希分組中的鍵值為各維表分組ID，執(zhí)行星形連接時(shí)基于全局遞增序列為相同分組ID的哈希記錄分配全局分組ID，并作為星形連接的結(jié)果記錄在向量索引對(duì)應(yīng)的單元中，哈希分組中的哈希表作為原始多維cube與分組向量的映射表。

內(nèi)存數(shù)據(jù)庫(kù)較高的性能支持用戶細(xì)粒度的交互式OLAP查詢，查詢結(jié)果的分組數(shù)量通常較低，采用cube分組可以簡(jiǎn)化星形連接算法實(shí)現(xiàn)并滿足大部分OLAP查詢需求。

星形連接操作是一個(gè)獨(dú)立的計(jì)算階段，可以獨(dú)立選擇適合的優(yōu)化實(shí)現(xiàn)技術(shù)及執(zhí)行場(chǎng)地。文獻(xiàn)[22]給出了一個(gè)星形連接操作實(shí)現(xiàn)方法，通過(guò)將連接所需的外鍵列駐留存儲(chǔ)于GPU顯存，通過(guò)動(dòng)態(tài)傳入較小的維向量調(diào)用高效的GPU星形連接計(jì)算并輸出較小的向量索引的方法提供了自治的星形連接計(jì)算服務(wù)。該方法可以作為本文所提出的查詢處理模型優(yōu)化的星形連接階段的一個(gè)定制化的實(shí)現(xiàn)方法，可以通過(guò)擴(kuò)展本文所提的哈希表星形連接方法使其進(jìn)一步通用化。

星形連接階段需要輸出向量索引，向量索引中分組向量的構(gòu)建需要在星形連接之前的維表處理階段實(shí)現(xiàn)GROUP-BY屬性與多維分組cube的映射。

（3）維處理優(yōu)化

在維表處理階段，如圖4所示，SQL命令改寫為分解到各維表的選擇、投影操作，過(guò)濾后投影出的GROUP BY屬性通過(guò)字典表壓縮將該維表上的分組值映射到數(shù)組字典表并使用數(shù)組下標(biāo)作為分組ID，分組字典表數(shù)組在邏輯上映射為查詢最終分組多維cube的一個(gè)維度。維表過(guò)濾、投影后的壓縮分組ID構(gòu)成一個(gè)維向量，用于后一階段事實(shí)表與該維表的連接過(guò)濾操作。當(dāng)維向量大小低于CPU的LLC大小或維向量超過(guò)LLC大小且選擇率較低時(shí)，維向量連接過(guò)濾性能較高[13]，當(dāng)維向量上選擇率很低時(shí)，可以將維向量中非空單元通過(guò)key/value二元組存儲(chǔ)為哈希表，通過(guò)哈希連接完成連接過(guò)濾。

圖4 維處理

從OLAP查詢特點(diǎn)來(lái)看，分組聚集計(jì)算是邏輯多維數(shù)據(jù)集上的核心操作，而其他關(guān)系操作則為保障分組聚集計(jì)算的輔助及預(yù)處理操作。以分組聚集計(jì)算為中心的優(yōu)化技術(shù)通過(guò)向量索引保證最優(yōu)的按位置事實(shí)數(shù)據(jù)檢索及基于最小向量的分組聚集計(jì)算，而向量索引則反向優(yōu)化星形連接操作，通過(guò)迭代多維cube地址計(jì)算最小化星形連接操作中間結(jié)果集為單一的向量索引列，優(yōu)化了operator（column）-at-a-time查詢處理模型的中間結(jié)果物化代價(jià)，星形連接操作中的多維cube機(jī)制反向優(yōu)化了維表處理階段輸出數(shù)據(jù)結(jié)構(gòu)，以優(yōu)化的維向量和分組向量?jī)?yōu)化維表輸出數(shù)據(jù)結(jié)構(gòu)大小，也進(jìn)一步優(yōu)化了后一階段的連接性能。

2.2 面向異構(gòu)計(jì)算平臺(tái)的OLAP計(jì)算框架

傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)中使用基于查詢樹的迭代查詢處理模型，查詢樹中的節(jié)點(diǎn)為表或中間結(jié)果，表上關(guān)系操作的結(jié)果在查詢樹之間流水處理，這種查詢處理模型構(gòu)成了一種強(qiáng)耦合的處理模式，不同節(jié)點(diǎn)之間的操作具有較強(qiáng)的關(guān)聯(lián)性。

本文通過(guò)對(duì)關(guān)系操作的優(yōu)化設(shè)計(jì)，將查詢樹轉(zhuǎn)換為扁平的結(jié)構(gòu)，以負(fù)載為粒度將查詢樹劃分為線性的計(jì)算模塊，各模塊之間執(zhí)行以負(fù)載為粒度的異步流水處理模式，將結(jié)構(gòu)緊密的查詢樹分解為松耦合的負(fù)載計(jì)算模塊。從查詢處理過(guò)程來(lái)看，本文提出的OLAP處理框架將傳統(tǒng)的查詢處理過(guò)程分解為三個(gè)獨(dú)立的計(jì)算階段，將同構(gòu)計(jì)算平臺(tái)上以消除物化代價(jià)為目標(biāo)的流水線處理模型轉(zhuǎn)換為適合異構(gòu)CPU-GPU計(jì)算平臺(tái)的、基于物化的向量索引的串行計(jì)算負(fù)載處理過(guò)程，通過(guò)數(shù)據(jù)的優(yōu)化分布策略最大化計(jì)算的數(shù)據(jù)局部性，減少CPU與GPU之間PCIe數(shù)據(jù)傳輸代價(jià)。通過(guò)查詢處理過(guò)程的分解，計(jì)算密集型的星形連接操作和數(shù)據(jù)密集型的分組聚集操作獨(dú)立選擇最適合的處理器平臺(tái)，簡(jiǎn)化了異構(gòu)CPUGPU平臺(tái)上的優(yōu)化策略。

圖5顯示了面向異構(gòu)計(jì)算平臺(tái)的OLAP計(jì)算框架。OLAP典型的邏輯模型是星形模型，由多個(gè)維表和事實(shí)表組成，OLAP查詢是在維表與事實(shí)表多維連接的基礎(chǔ)上執(zhí)行的分組聚集分析處理。傳統(tǒng)的數(shù)據(jù)庫(kù)將OLAP查詢轉(zhuǎn)換為查詢樹，每個(gè)表上的記錄通過(guò)查詢樹流水迭代處理。本文將查詢樹轉(zhuǎn)換為扁平的三個(gè)查詢階段：維處理、星形連接和向量聚集，形成三個(gè)獨(dú)立的計(jì)算階段，分別對(duì)應(yīng)OLAP數(shù)據(jù)庫(kù)中的維表、外鍵和事實(shí)數(shù)據(jù)三個(gè)獨(dú)立的數(shù)據(jù)集，各計(jì)算階段可以根據(jù)計(jì)算特征分配不同的處理器平臺(tái)，如本例中使用CPU平臺(tái)執(zhí)行維處理和向量聚集計(jì)算，GPU執(zhí)行星形連接計(jì)算。

圖5 OLAP處理框架

以Star Schema Benchmark（SSB）基準(zhǔn)數(shù)據(jù)集為例，在SF=100時(shí)維表、外鍵和事實(shí)數(shù)據(jù)大小分別為1%、19%和80%，而三個(gè)數(shù)據(jù)集上的計(jì)算時(shí)間占比約為7%、85%和8%[6]。在OLAP查詢中分組聚集計(jì)算是一種典型的數(shù)據(jù)密集型負(fù)載，在異構(gòu)OLAP計(jì)算平臺(tái)上不僅需要分析分組聚集計(jì)算的性能，還要將分組聚集計(jì)算的數(shù)據(jù)量作為一個(gè)參數(shù)，評(píng)估在PCIe通道的傳輸代價(jià)，作為分組聚集計(jì)算平臺(tái)選擇的考慮因素。本文在實(shí)驗(yàn)部分通過(guò)分組聚集操作帶寬性能與PCIe帶寬性能的閾值比較給出了分組聚集操作優(yōu)化執(zhí)行場(chǎng)地的選擇。

本文將SQL命令中的分組聚集計(jì)算從傳統(tǒng)的查詢樹中分離為獨(dú)立的計(jì)算階段，采用基于共享向量索引的物化機(jī)制降低了operator-at-a-time查詢處理模型的物化代價(jià)，最大限度降低了分組聚集操作與其他操作和數(shù)據(jù)的依賴度。同時(shí)，向量分組聚集算法只使用簡(jiǎn)單的數(shù)組數(shù)據(jù)結(jié)構(gòu)和數(shù)組地址訪問操作，易于綁定到特定硬件平臺(tái)，實(shí)現(xiàn)分組聚集計(jì)算向硬件平臺(tái)的下壓，使計(jì)算更加靠近存儲(chǔ)平臺(tái)，提高計(jì)算效率。

3 實(shí)驗(yàn)與結(jié)果

本文聚焦于OLAP中計(jì)算代價(jià)較大的分組聚集操作，重點(diǎn)比較本文提出的向量分組聚集算法與主流數(shù)據(jù)庫(kù)的分組聚集實(shí)現(xiàn)技術(shù)在性能上的差異，包括CPU與GPU平臺(tái)數(shù)據(jù)庫(kù)中的分組聚集計(jì)算性能，通過(guò)對(duì)向量分組聚集算法性能的綜合測(cè)試分析分組聚集計(jì)算在CPU和GPU平臺(tái)執(zhí)行的不同策略。

3.1 實(shí)驗(yàn)平臺(tái)和實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)平臺(tái)為一臺(tái)Supermicro Super Workstation 7047GR-TPRF服務(wù)器，配置一塊Intel Xeon E5-2699 v4@2.2 GHz多核處理器，CPU核心數(shù)量為22，支持44個(gè)物理線程，內(nèi)存為256 GB DDR4。服務(wù)器操作系統(tǒng)為CentOS 7，Linux內(nèi)核版本3.10.0-514.16.1.el7.x86_64，gcc編譯器版本為4.8.5。服務(wù)器配置一塊NVIDIA K80 GPU，cuda核心數(shù)量為4 992，顯存容量為24 GB，顯存帶寬為480 GB/s。

實(shí)驗(yàn)中使用文獻(xiàn)[3]提供的開源哈希連接代碼為實(shí)驗(yàn)床，使用相同的多線程并行處理和對(duì)共享向量的latch并發(fā)訪問控制機(jī)制。在開源代碼中增加了向量聚集算法，生成兩個(gè)列作為度量列M1、M2，模擬兩個(gè)度量列上的聚集計(jì)算；算法中設(shè)置線程數(shù)量、選擇率和分組數(shù)量參數(shù)，用于模擬不同查詢選擇率和分組勢(shì)集下的聚集計(jì)算性能，算法執(zhí)行命令示例腳本如下：

當(dāng)前實(shí)現(xiàn)了2.1節(jié)中介紹的兩種向量分組聚集算法：多線程共享分組向量聚集算法和線程私有分組向量聚集算法。當(dāng)前分組聚集算法的研究中還沒有較權(quán)威的開源代碼，難以進(jìn)行不同研究之間的橫向比較。Hyper和MapD是內(nèi)存數(shù)據(jù)庫(kù)和GPU數(shù)據(jù)庫(kù)的代表性系統(tǒng)，其性能代表了CPU和GPU上關(guān)系操作的最高水平，在實(shí)驗(yàn)中使用Hyper和MapD的CPU與GPU版本作為性能參照，通過(guò)SQL命令模擬分組聚集操作，相對(duì)于Hyper和MapD的性能也可以作為其他相關(guān)研究的量化參考。實(shí)驗(yàn)中使用OLAP測(cè)試基準(zhǔn)SSB（Star Schema Benchmark，SF=100，事實(shí)表記錄行數(shù)為6億條），通過(guò)SQL命令模擬基于不同分組勢(shì)集列的聚集計(jì)算操作。

如在Hyper數(shù)據(jù)庫(kù)中使用lo_ordertotalprice%512作為分組屬性，分組勢(shì)集為512，使用top 1命令只輸出每一行分組聚集計(jì)算結(jié)果，最小化記錄輸出時(shí)間的影響。Hyper數(shù)據(jù)庫(kù)模擬測(cè)試SQL命令如下：

在MapD數(shù)據(jù)庫(kù)中使用mod（lo_ordertotalprice，512）函數(shù)對(duì)lo_ordertotalprice列按512生成分組ID.MapD支持CPU-only的純內(nèi)存計(jì)算模式和使用GPU的GPU計(jì)算模式，在實(shí)驗(yàn)中通過(guò)SQL命令分別測(cè)試CPU和GPU模式下的模擬向量分組聚集計(jì)算性能。MapD數(shù)據(jù)庫(kù)模擬測(cè)試SQL命令如下：

測(cè)試時(shí)每個(gè)查詢連續(xù)執(zhí)行三遍，取最短時(shí)間作為內(nèi)存分組聚集計(jì)算時(shí)間，MapD GPU模式在第一次查詢執(zhí)行時(shí)間較長(zhǎng)，主要原因是查詢產(chǎn)生的從CPU內(nèi)存到GPU內(nèi)存的PCIe數(shù)據(jù)傳輸代價(jià)，通過(guò)連續(xù)執(zhí)行消除查詢執(zhí)行時(shí)的數(shù)據(jù)傳輸代價(jià)，以準(zhǔn)確反映MapD在GPU上的分組聚集計(jì)算性能。

3.2 分組聚集計(jì)算性能對(duì)比

實(shí)驗(yàn)首先測(cè)試不同分組勢(shì)集下的基準(zhǔn)分組聚集計(jì)算性能，分組勢(shì)集從32（25）起依次加倍，直到67 108 864（226），分組數(shù)量覆蓋OLAP查詢的應(yīng)用范圍。

表1 基準(zhǔn)分組聚集操作性能

分組聚集基準(zhǔn)計(jì)算性能如表1所示，表中下劃線代表當(dāng)前分組數(shù)量下的最短執(zhí)行時(shí)間。從整體上看，向量分組聚集算法優(yōu)于Hyper和MapD數(shù)據(jù)庫(kù)中的分組聚集操作性能，主要原因是數(shù)據(jù)庫(kù)使用哈希分組聚集算法，相對(duì)于向量分組聚集算法使用了更大的哈希表和CPU代價(jià)更高的哈希探測(cè)方法，因此總體性能低于向量分組聚集算法。Hyper采用JIT實(shí)時(shí)編譯技術(shù)和面向寄存器的優(yōu)化技術(shù)，相對(duì)于采用向量處理技術(shù)的MapD CPU版本具有更優(yōu)的性能。MapD GPU版本的分組聚集操作性能顯著優(yōu)于CPU版本，體現(xiàn)在了相同的MapD算法框架下GPU對(duì)分組聚集操作的加速能力，MapD GPU版本的分組聚集操作性能在分組數(shù)量界于256（28）和4 194 304（222）之間時(shí)優(yōu)于Hyper，最大性能提升達(dá)到61%。當(dāng)分組勢(shì)集高于8 388 608（223）時(shí)，MapD GPU版本的分組聚集操作性能低于Hyper，在本文最大分組測(cè)試用例67 108 864（226）時(shí)分組聚集操作執(zhí)行時(shí)間是Hyper的2.17倍，表明分組聚集計(jì)算在極大分組勢(shì)集時(shí)MapD GPU算法性能低于CPU。

向量分組聚集算法的性能主要取決于向量大小與CPU cache大小之間的關(guān)系。向量長(zhǎng)度低于524 288（219）時(shí)，對(duì)應(yīng)的線程私有向量大小低于2 MB（低于CPU每核心2.5 MB的L3 cache slice），基于線程私有向量的向量分組聚集算法性能優(yōu)于基于共享向量的向量分組聚集算法。當(dāng)向量大小超過(guò)線程私有cache大小時(shí)，基于線程私有向量的向量分組聚集算法性能開始低于基于共享向量的向量分組聚集算法，而且較大向量也導(dǎo)致私有向量存儲(chǔ)空間開銷指數(shù)增長(zhǎng)，如分組數(shù)為67 108 864（226）時(shí)44線程所需創(chuàng)建的私有向量產(chǎn)生內(nèi)存空間不足錯(cuò)誤。

總體而言，向量分組聚集算法性能優(yōu)于代表性內(nèi)存數(shù)據(jù)庫(kù)Hyper、GPU數(shù)據(jù)庫(kù)MapD的相應(yīng)性能，最大性能提升分別達(dá)到695%和481%，相對(duì)于最優(yōu)數(shù)據(jù)庫(kù)分組聚集操作性能的最大性能提升達(dá)到481%。

3.3 分組聚集計(jì)算性能分析

向量分組聚集算法通過(guò)對(duì)OLAP查詢處理模型的優(yōu)化將分組聚集操作從查詢樹中獨(dú)立出來(lái)，基于向量的分組聚集計(jì)算最小化分組聚集器的內(nèi)存空間，最大化分組聚集計(jì)算時(shí)的cache局部性，基于向量地址直接訪問的分組定位機(jī)制最小化分組操作的CPU代價(jià)。向量分組聚集計(jì)算在算法上的簡(jiǎn)化將性能影響因素簡(jiǎn)化為單一的向量大小，與各級(jí)cache大小的相對(duì)關(guān)系決定了其性能特征。

實(shí)驗(yàn)中設(shè)計(jì)了cache-conscious vector grouping benchmark（cache敏感的向量分組基準(zhǔn)測(cè)試），測(cè)試當(dāng)向量長(zhǎng)度為各級(jí)cache大小不同百分比時(shí)的向量分組聚集計(jì)算性能。實(shí)驗(yàn)中向量設(shè)置為int_32類型，以各級(jí)cache容量的10%為步長(zhǎng)設(shè)置向量長(zhǎng)度，向量大小設(shè)置為各級(jí)cache大小的10%～200%，量化分析向量的cache局部性對(duì)向量分組聚集計(jì)算性能的影響。

表2顯示了當(dāng)向量大小為L(zhǎng)1 cache大?。?2 KB）的10%～200%時(shí)向量分組聚集與共享向量分組聚集算法性能。當(dāng)向量小于L1 cache大小時(shí)，線程私有向量分組聚集算法性能高于共享向量分組聚集算法并且執(zhí)行時(shí)間較為穩(wěn)定；當(dāng)向量較小時(shí)，共享向量分組聚集算法各線程并發(fā)訪問共享向量產(chǎn)生較高的向量單元更新的latch并發(fā)訪問控制代價(jià)，隨向量長(zhǎng)度的增長(zhǎng)latch并發(fā)訪問控制代價(jià)逐漸降低。共享向量分組聚集算法與向量分組聚集算法執(zhí)行時(shí)間比最大為22.37倍，隨向量長(zhǎng)度的增長(zhǎng)逐漸降低為6.17倍。

表2 L1 cache大小相關(guān)的向量分組性能

表3顯示向量大小為L(zhǎng)2 cache大?。?56 KB）的10%～200%時(shí)向量分組聚集與共享向量分組聚集算法性能。10%L2 cache時(shí)向量實(shí)際大小小于L1 cache，向量分組聚集執(zhí)行時(shí)間較短，隨向量長(zhǎng)度的增長(zhǎng)，私有向量分組聚集算法時(shí)間逐漸增長(zhǎng)，而共享向量分組聚集算法執(zhí)行時(shí)間逐漸減少，二者執(zhí)行時(shí)間倍數(shù)從9.04倍逐漸下降到2.9倍。

表3 L2 cache大小相關(guān)的向量分組性能

多核處理器每個(gè)核心直接連接2.5 MB的L3 cache slice，處理核心訪問私有cache slice延遲低于訪問共享L3 cache中其他核心的L3 cache slice，因此L3 cache slice可以看作處理核心的最后一級(jí)私有cache。表4顯示了向量大小為L(zhǎng)3 cache slice的10%～200%時(shí)兩種向量分組聚集算法的性能。當(dāng)私有向量大小超過(guò)L3 cache slice的50%時(shí)，私有向量分組聚集算法執(zhí)行時(shí)間開始高于共享向量分組聚集算法，此時(shí)每核心2個(gè)線程私有向量總和達(dá)到L3 cache slice，私有向量訪問cache局部性達(dá)到臨界值，當(dāng)向量繼續(xù)增大時(shí)，向量訪問的cache miss增加，查詢延遲增長(zhǎng)。共享分組向量仍然有較高的cache局部性，較大的向量也減少了每個(gè)向量單元并發(fā)訪問沖突，查詢性能逐漸提升。

表4 L3 cache slice大小相關(guān)的向量分組性能

當(dāng)向量大小在L3 cache的10%～200%之間時(shí)，如表5所示，共享向量分組聚集算法具有一定的cache局部性，兩種算法隨向量長(zhǎng)度的增長(zhǎng)執(zhí)行時(shí)間均增長(zhǎng)，算法執(zhí)行時(shí)間比緩慢降低。

綜上所述，私有向量分組聚集算法在向量具有較高的cache局部性時(shí)有較高的性能，即每線程私有向量長(zhǎng)度小于50%×L3 cache slice時(shí)基于線程私有分組向量的向量分組聚集算法性能較優(yōu)，當(dāng)向量長(zhǎng)度繼續(xù)增長(zhǎng)時(shí)，基于共享向量的向量分組聚集算法性能逐漸優(yōu)于私有向量分組聚集算法。

3.4 基于壓縮向量索引的向量分組聚集算法性能

如圖1所示，當(dāng)查詢選擇率較低時(shí)向量索引中非空值單元較為稀疏，壓縮向量索引不僅減少了向量索引非空單元的存儲(chǔ)空間開銷而且將向量索引的順序掃描轉(zhuǎn)換成更為高效的壓縮向量索引掃描。

表5 L3 cache大小相關(guān)的向量分組性能

表6 基于壓縮向量索引的向量分組性能

表6顯示了不同選擇率下的向量分組聚集算法和基于壓縮向量索引的向量分組聚集算法性能，分組數(shù)固定設(shè)置為65 536，采用私有向量分組聚集算法，壓縮向量索引存儲(chǔ)為key/value序列，key值為非空向量索引單元下標(biāo)，value為非空向量索引單元存儲(chǔ)的分組ID。當(dāng)選擇率為100%時(shí)，壓縮向量索引實(shí)際存儲(chǔ)空間大于非壓縮向量索引，其執(zhí)行時(shí)間稍長(zhǎng)；隨著選擇率的降低，基于壓縮向量索引的向量分組聚集算法執(zhí)行時(shí)間開始低于原始向量分組聚集算法但兩種算法之間的執(zhí)行時(shí)間差異并不顯著，在選擇率為10%時(shí)非壓縮與壓縮向量索引向量分組聚集算法執(zhí)行時(shí)間比為1.63，當(dāng)選擇率為1%時(shí)二者執(zhí)行時(shí)間比為3.62；當(dāng)選擇率繼續(xù)以10倍的速度遞減時(shí)，兩種算法執(zhí)行時(shí)間比逐漸增大，但執(zhí)行時(shí)間比增長(zhǎng)速度遠(yuǎn)低于選擇率增長(zhǎng)速度。由實(shí)驗(yàn)結(jié)果可以得到這樣的策略：當(dāng)OLAP查詢選擇率較高時(shí)（大于1%）可以采用定向向量索引策略，定長(zhǎng)向量索引可以被不同的查詢共享以簡(jiǎn)化內(nèi)存管理；當(dāng)OLAP查詢選擇率低于較低時(shí)（低于1‰）使用壓縮向量索引以提高向量分組聚集計(jì)算性能。

3.5 分組聚集計(jì)算的平臺(tái)選擇策略

分組聚集計(jì)算是OLAP查詢中重要的操作，也是OLAP查詢性能的主要決定因素之一。分組聚集操作需要在較大的事實(shí)數(shù)據(jù)上執(zhí)行分組與聚集計(jì)算，本文通過(guò)將分組操作下推到維表處理階段實(shí)現(xiàn)基于向量的分組聚集計(jì)算，最小化了分組計(jì)算代價(jià)，使分組聚集計(jì)算成為一種數(shù)據(jù)密集型任務(wù)，即在大數(shù)據(jù)上的低CPU代價(jià)計(jì)算?；谙蛄康姆纸M操作具有較好的cache局部性，在CPU平臺(tái)也具有較高的性能。

將查詢中不同的操作優(yōu)化分配給CPU或GPU平臺(tái)以獲得最高的整體性能是GPU查詢優(yōu)化的核心任務(wù)，需要設(shè)計(jì)將什么樣的查詢操作及以該查詢操作在什么情況下分配給CPU或GPU的優(yōu)化策略。

GPU上的計(jì)算包括本地靜態(tài)數(shù)據(jù)計(jì)算和動(dòng)態(tài)數(shù)據(jù)計(jì)算兩種類型：本地靜態(tài)數(shù)據(jù)計(jì)算指通過(guò)數(shù)據(jù)庫(kù)的數(shù)據(jù)分布策略將一部分?jǐn)?shù)據(jù)預(yù)先分配在GPU內(nèi)存，執(zhí)行GPU內(nèi)存上的本地化計(jì)算；動(dòng)態(tài)數(shù)據(jù)計(jì)算指數(shù)據(jù)存儲(chǔ)在CPU端，在計(jì)算時(shí)實(shí)時(shí)通過(guò)PCIe通道傳輸?shù)紾PU內(nèi)存后執(zhí)行GPU數(shù)據(jù)復(fù)本上的計(jì)算，GPU內(nèi)存緩存CPU端數(shù)據(jù)但不持久存儲(chǔ)CPU端數(shù)據(jù)集。

由于GPU內(nèi)存容量相對(duì)CPU內(nèi)存較小且OLAP數(shù)據(jù)集的事實(shí)數(shù)據(jù)極為龐大，因此在事實(shí)數(shù)據(jù)上的分組計(jì)算操作主要考慮動(dòng)態(tài)數(shù)據(jù)計(jì)算模式。GPU端優(yōu)化執(zhí)行分組聚集計(jì)算時(shí)需要滿足TGPUAgg+TTrans

圖6 模擬GPU聚集計(jì)算性能

隨著GPU上算法優(yōu)化技術(shù)的深入和GPU擴(kuò)展性的提升（通過(guò)配置多塊GPU卡），GPU數(shù)據(jù)庫(kù)在GPU端的分組聚集計(jì)算性能可能進(jìn)一步提升，從而使GPU分組聚集計(jì)算代價(jià)模型難以直接應(yīng)用，從PCIe帶寬性能出發(fā)提出GPU分組聚集計(jì)算的選擇策略。圖7給出了私有和共享向量分組聚集算法的數(shù)據(jù)帶寬性能（分組聚集計(jì)算數(shù)據(jù)量/執(zhí)行時(shí)間），虛線為PCIe 3.0的帶寬（16 GB/s），若CPU端的向量分組聚集算法帶寬性能超過(guò)PCIe帶寬性能時(shí)，則CPU端執(zhí)行分組聚集計(jì)算性能肯定優(yōu)于GPU端，否則GPU端執(zhí)行分組聚集計(jì)算性能可能優(yōu)于CPU端。

圖7 向量分組聚集計(jì)算帶寬性能

從圖7中可以看到，當(dāng)分組數(shù)量低于131 072（217）時(shí)，在CPU端執(zhí)行向量分組聚集計(jì)算帶寬性能超過(guò)26 GB/s，遠(yuǎn)高于數(shù)據(jù)從PCIe通道傳輸?shù)紾PU的時(shí)間，因此適合CPU端執(zhí)行。從SSB、TPC-H、TPC-DS等典型OLAP負(fù)載的查詢命令來(lái)看，GROUP-BY屬性通常為低勢(shì)集屬性，適合于向量分組聚集算法的應(yīng)用場(chǎng)景，也適合在CPU執(zhí)行。

綜上所述，OLAP是適合使用GPU加速的計(jì)算密集型負(fù)載，但使用GPU加速通用的關(guān)系操作和查詢處理模型難以獲得最優(yōu)的性能。通對(duì)OLAP查詢中關(guān)鍵的分組聚集計(jì)算的優(yōu)化設(shè)計(jì)，查詢優(yōu)化器可以根據(jù)分組聚集計(jì)算優(yōu)化規(guī)則精確地根據(jù)查詢輸入?yún)?shù)（如分組數(shù)量等）確定分組聚集操作在CPU端還是GPU端執(zhí)行，生成最優(yōu)的異構(gòu)計(jì)算平臺(tái)OLAP查詢執(zhí)行計(jì)劃。

實(shí)驗(yàn)部分通過(guò)cache-conscious vector grouping benchmark實(shí)驗(yàn)設(shè)計(jì)量化地給出了2.1節(jié)兩種向量分組聚集方法的性能變化區(qū)間和性能變化的閾值，可以根據(jù)分組向量大小以及各級(jí)cache容量參數(shù)確定根據(jù)負(fù)載選擇優(yōu)化向量分組聚集操作方法的策略。進(jìn)一步地，通過(guò)帶寬性能指標(biāo)可以進(jìn)一步明確分組聚集操作選擇CPU作為執(zhí)行場(chǎng)地的分組閾值，實(shí)現(xiàn)了基于硬件參數(shù)確定分組聚集操作執(zhí)行場(chǎng)地優(yōu)化選擇策略。

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

本文提出了面向異構(gòu)計(jì)算平臺(tái)的OLAP分組聚集計(jì)算實(shí)現(xiàn)技術(shù)，通過(guò)向量分組技術(shù)實(shí)現(xiàn)了將數(shù)據(jù)密集型的分組聚集計(jì)算從傳統(tǒng)的查詢處理模型中分離出來(lái)，獨(dú)立地根據(jù)算法和硬件參數(shù)特性優(yōu)化選擇適合其執(zhí)行的計(jì)算平臺(tái)?；谙蛄糠纸M的聚集計(jì)算方法通過(guò)“早分組、晚聚集”策略獲得了最優(yōu)的分組聚集計(jì)算性能，與當(dāng)前最優(yōu)的內(nèi)存數(shù)據(jù)庫(kù)Hyper、GPU數(shù)據(jù)庫(kù)MapD相比有顯著的性能提升，基于cache-conscious的向量分組聚集計(jì)算基準(zhǔn)測(cè)試精確地描述了算法的性能特征，使查詢優(yōu)化器可以根據(jù)查詢與硬件參數(shù)準(zhǔn)確地估算其性能及執(zhí)行異構(gòu)計(jì)算平臺(tái)選擇策略。實(shí)驗(yàn)結(jié)果表明，向量分組聚集算法相對(duì)于當(dāng)前主流數(shù)據(jù)庫(kù)的實(shí)現(xiàn)技術(shù)有顯著的性能優(yōu)勢(shì)，而且易于在異構(gòu)計(jì)算平臺(tái)上的實(shí)時(shí)OLAP分析處理應(yīng)用中實(shí)現(xiàn)。