，3*

（1.數(shù)據(jù)工程與知識工程教育部重點實驗室（中國人民大學），北京 100872；2.中國人民大學信息學院，北京 100872；3.中國人民大學中國調查與數(shù)據(jù)中心，北京 100872；4.中國氣象局國家衛(wèi)星氣象中心，北京 100081）

0 引言

連接操作是關系數(shù)據(jù)庫中最重要的操作之一，也是執(zhí)行代價最大的操作之一，一直是數(shù)據(jù)庫查詢優(yōu)化的核心問題。在典型聯(lián)機分析處理（On-Line Analytical Processing，OLAP）負載中，事實表與維表之間的星形連接操作執(zhí)行時間占到全部查詢處理時間的80%左右［1］，提高星形連接操作性能是提高OLAP 查詢處理性能的決定因素。當前研究熱點主要集中在連接操作性能優(yōu)化方面，對多表星形連接優(yōu)化技術研究相對較少，而兩表連接與多表連接在優(yōu)化算法選擇策略上有較大的差異［2］。分區(qū)Radix join 連接算法性能優(yōu)于無分區(qū)的哈希連接算法，但在多表連接操作中Radix join 算法由于需要多次物化無法流水處理而失去性能優(yōu)勢［3］。另一方面，多表連接時需要通過不同的策略優(yōu)化中間連接結果，需要結合細粒度記錄級流水處理、粗粒度列級處理和向量化處理策略進行優(yōu)化設計，同時面向中央處理器（Central Processing Unit，CPU）cache 或圖形處理器（Graphics Processing Unit，GPU）shared memory 優(yōu)化多表連接中間結果的物化和訪問策略，提高多表連接整體性能。

本文通過面向多核CPU 平臺上L1 cache級的連接中間結果緩存和壓縮技術，以及面向GPU 多cuda 核心共享Shared memory 的向量化處理技術使多表星形連接的中間結果物化和訪問發(fā)生在訪問性能較好的L1 cache 和Shared memory，減少延遲較高的內存物化和訪問代價，從而提高整體連接性能。本文的貢獻主要體現(xiàn)在以下三個方面：

1）提出了基于壓縮向量的星形連接算法，優(yōu)化連接中間結果的存儲效率和連接列的掃描效率；

2）設計了面向多核CPU 平臺和GPU 平臺的向量化星形連接算法，優(yōu)化了連接中間結果在CPU 的L1 cache 和GPU 的shared memory上的物化和訪問效率；

3）綜合對比了不同的星形連接算法性能，以及當前主流的內存數(shù)據(jù)庫和GPU 數(shù)據(jù)庫多表連接性能，驗證了本文提出的星形連接算法性能的優(yōu)化程度。

本文所使用的算法名稱及簡稱規(guī)則，行式關鍵字是R（Row），列式關鍵字C（Col），壓縮關鍵字P（comPress），向量化處理關鍵字V（Vector），GPU 關鍵字G（GPU），星形連接關鍵字SJ（StarJoin）；例如RSJ 代表CPU 行式處理星形連接算法，GVSJ代表GPU下的向量星形連接算法。

1 相關工作

連接操作是關系數(shù)據(jù)庫重要的操作，近年來，學術界對多核CPU 平臺上的連接優(yōu)化技術做了深入的研究。文獻［4］首先提出了應用現(xiàn)代CPU 的多線程、自動預取等技術使簡單的無分區(qū)哈希連接（No Partition jOin，NPO）算法可以優(yōu)于面向cache 優(yōu)化的Radix 分區(qū)哈希連接（Partition Radix Hash jOin，PRO）算法，從而簡化算法設計復雜度。隨后，文獻［2］證明PRO 算法在面向硬件參數(shù)優(yōu)化后性能優(yōu)于NPO 算法，哈希連接算法需要根據(jù)硬件特征而定制優(yōu)化。文獻［5］進一步研究了面向多核CPU 優(yōu)化的排序歸并連接算法與PRO 算法的性能差異，證明PRO 算法的性能較高。這些研究開啟了一系列的深度優(yōu)化研究工作，文獻［6］從7 個優(yōu)化維度探索了連接優(yōu)化技術，文獻［7］綜合比較了13 個學術界與產業(yè)界的代表性連接算法，在新一代的至強融核處理器（Intel Xeon Phi，Phi）上也得到了驗證［8］。隨著GPU 逐漸應用于數(shù)據(jù)處理領域，基于GPU 的連接優(yōu)化技術［9］成為一個重要的研究領域。GPU 技術的快速迭代及硬件參數(shù)的變化使GPU 上的連接優(yōu)化更具挑戰(zhàn)性［10］，如基于CPU-GPU 融合架構的連接優(yōu)化技術［11］探索了不同哈希連接算法的性能特征，GPU上的存儲優(yōu)化技術［12］、以操作符為中心的處理模型和基于負載特征的GPU 熱數(shù)據(jù)存儲策略［13］等。由于GPU 與CPU 在硬件架構上顯著的差異，傳統(tǒng)CPU 平臺上的連接算法需要面向GPU 硬件特征而優(yōu)化實現(xiàn)，利用GPU 強大的并行計算性能優(yōu)化數(shù)據(jù)庫的連接性能［14］。CPU 平臺上代表性的NPO 與PRO 算法在GPU 平臺上通過面向GPU 硬件特性的優(yōu)化獲得較好的性能，并優(yōu)化PCIe傳輸性能［15］。值得注意的是，隨著GPU硬件的持續(xù)升級，GPU連接算法需要面向GPU 硬件的新特性而持續(xù)優(yōu)化，GPU 硬件新特性能夠顯著提升傳統(tǒng)的連接算法性能［16］。除傳統(tǒng)的哈希連接優(yōu)化技術之外，面向OLAP 模式特征而定制的數(shù)組索引連接（Array Index Join，AIJ）算法［1］和Array Join 連接算法［7］通過數(shù)組地址映射技術進一步提高了連接效率。AIJ 連接算法通過預分組將維表映射為維向量，通過代理鍵索引機制實現(xiàn)事實表外鍵與維向量之間基于地址映射的連接方法，在星形連接操作中，迭代處理事實表外鍵列與各維向量之間的映射連接，并將連接中間結果以共享向量索引方式迭代更新，消除了傳統(tǒng)關系數(shù)據(jù)庫中較難優(yōu)化的哈希連接算法，同時通過較小的向量索引縮減了連接中間結果的存儲空間消耗。

OLAP 查詢以多表連接為基礎，相對于兩表連接優(yōu)化技術，多表連接需要考慮更多的性能影響因素［17］，如兩階段優(yōu)化策略、數(shù)據(jù)傳輸和連接優(yōu)化。除連接算法本身的性能之外，文獻［3］指出雖然PRO 算法在兩表連接時性能更好，但其物化策略和較大的物化代價不適合多表連接的流水處理模式。在多表連接過程中，不同查詢處理模型產生不同的中間連接結果物化和處理代價對多表星形連接的性能產生較大的影響。圖1 顯示了數(shù)據(jù)庫代表性的行式、列式和向量化查詢處理模型的示例，圖中A、B、C代表3個數(shù)據(jù)列，Avec、BVec、CVec分別代表A、B、C 列對應的向量，tmpVec代表中間結果向量，resVec代表結果向量。行式處理模型是一種列間數(shù)據(jù)訪問的流水處理方式，不產生中間結果，當不同列上的操作有較低的選擇率時，受分支預測性能的影響可能會產生無效的數(shù)據(jù)訪問代價。列式處理每次處理一個或兩個列，數(shù)據(jù)訪問的cache 效率高，需要通過臨時列緩存中間計算結果，較大的中間結果列增加了內存物化代價，但在選擇和連接等具有過濾性的操作中，中間結果列可以提高后續(xù)列的訪問效率。向量化查詢處理模型［18］將列劃分為適合L1 cache 大小的向量，實現(xiàn)基于向量的流水處理，cache中的中間結果既保持了列式處理數(shù)據(jù)訪問效率高、過濾性好的優(yōu)點，也通過cache 內的中間結果緩存降低了內存物化代價，也與傳統(tǒng)數(shù)據(jù)庫的流水迭代處理模型保持兼容。實時編譯（Just In Time，JIT）技術進一步提高的查詢處理的代碼執(zhí)行效率，將傳統(tǒng)查詢處理的“拉”模式優(yōu)化為代碼執(zhí)行效率更高的“推”模式，通過與向量化查詢處理等技術的結合進一步提高查詢處理性能［19］。

早期GPU 上主要采用一次操作符查詢處理模型，與CPU平臺存在相同的global memory 上的物化存儲訪問代價，同時較大的中間結果物化開銷降低了GPU 內存利用率。隨著GPU 硬件技術的發(fā)展，多kernel 機制支持了流水處理模式，降低了物化代價。Tile-based execution model［3］是一種基于GPU線程塊粒度的向量化查詢處理方法，針對GPU 特殊的流處理多核（Streaming Multiprocessor，SM）內多CUDA 核心、多線程共享Shared memory 的硬件結構而設計的線程塊共享向量化查詢處理方法，將CPU 平臺代表性的向量化查詢處理方法在GPU平臺進行了適應化優(yōu)化設計。

總體而言，OLAP 的連接優(yōu)化是連接算法優(yōu)化、查詢處理模型優(yōu)化、存儲訪問優(yōu)化的綜合應用，尤其需要面向多核CPU和GPU 不同的硬件架構做針對性的優(yōu)化設計才能更好地適應多核CPU和GPU平臺。

圖1 行式、列式和向量化查詢處理模型Fig.1 Row-wise，column-wise and vectorized query processing models

2 星形連接優(yōu)化技術

本文在向量連接算法［1］基礎上研究面向OLAP 負載的多表星形連接算法優(yōu)化技術，通過維表代理鍵索引和維向量地址映射技術將連接優(yōu)化為數(shù)組地址映射操作，簡化連接算法實現(xiàn)，從而可以更好地分析多表星形連接算法的性能影響因素。

2.1 星形連接實現(xiàn)技術

典型的OLAP查詢語句示例如下：

select sum（…），c_nation，s_nation，d_month from lineorder inner join customer on lo_custkey=c_custkey inner join supplier on lo_suppkey=s_suppkey inner join date on lo_orderdate=d_datekey where…group by c_nation，s_nation，d_month；

基于向量連接的OLAP 查詢處理方法分為3 個處理階段［20］：1）維映射。將結構化查詢語言（Structured Query Language，SQL）命令分解到查詢相關的各個維表上，根據(jù)where 和group by 子句生成維向量。2）星形連接。在事實表相應的外鍵列與維向量之間執(zhí)行基于向量連接的多表連接操作，將連接的結果迭代存儲為向量索引。3）在事實表度量列上執(zhí)行基于向量索引的聚集計算。如圖2 示例所示，Dim Vector Index1～3對應查詢命令中相關的3 個點維表生成的維向量，F(xiàn)K1～3對應3個維表的外鍵列，其外鍵值可以直接映射為維向量中的偏移地址，Vector Index為向量索引，被3個連接階段共享訪問，并在連接執(zhí)行時根據(jù)連接結果迭代更新其記錄的group by 多維數(shù)組地址，CVector Index 為壓縮的向量索引結構。

圖2 星形連接技術Fig.2 Star-join technique

向量連接算法首先在各維表上按相應的where 子句過濾不滿足條件的元組，投影出當前維表上的group by 屬性或屬性組，并對其進行動態(tài)字典表壓縮，3 個維表group by 屬性字典表的集勢將group by 語句中的分組屬性映射多維數(shù)組，每個維表上的分組屬性投影到基于維表代理鍵的向量上并進行數(shù)組字典表壓縮。如圖2（a）中group by 語句中的分組屬性分別投影到3 個維表按代理鍵生成的維向量中，分組屬性按數(shù)組字典表壓縮，3個維表分組屬性數(shù)組字典表的集勢I、J、K分別為2、3、2，表示group by 語句對應的2×3×2=12 個多維數(shù)組單元。事實表外鍵值映射為維向量數(shù)組下標，多表星形連接操作是一個迭代計算對應維向量非空事實表記錄的group by屬性多維數(shù)組地址的過程。

多表星形連接操作是OLAP 查詢的核心操作，在實現(xiàn)中可以分為行式處理（tuple-at-a-time）、列式處理（column-at-atime）和向量化處理（vector-at-a-time）三種模式。

1）行式處理：每次讀取事實表全部外鍵值，分別映射到相應維向量，若均非空則計算group by 屬性多維數(shù)組地址，直接生成最終連接結果。

2）列式處理：每次處理一個外鍵列連接操作，使用向量索引（Vector Index）記錄當前事實表記錄與相應維表連接產生的部分group by 屬性多維數(shù)組地址，生成的向量索引同時用作下一外鍵列的位圖索引過濾下一外鍵列，多表連接過程迭代更新向量索引和相應的group by 屬性多維數(shù)組地址，最后一列完成連接后生成最終向量索引，非空位置記錄連接記錄的group by屬性多維數(shù)組地址。

3）向量化處理：事實表外鍵列以向量大小劃分為若干行組，每個行組內采用列式處理，作為中間結果的向量索引上的訪問和更新操作主要在L1 cache 中進行，降低多表連接過程中向量索引的內存訪問代價。

向量索引可以使用定長與壓縮兩種存儲結構，定長向量索引大小不受選擇率影響，但低選擇率時稀疏的非空值掃描操作對外鍵列的過濾效率較低；壓縮向量索引使用OID/GROUPIDX 二元結構，大小由選擇率決定，低選擇率時對外鍵列的過濾效果較好，但需要動態(tài)分配存儲空間。圖2 演示了基于定長向量索引與壓縮向量索引的星形連接執(zhí)行過程。

2.2 壓縮向量星形連接實現(xiàn)技術

如圖2（b），壓縮向量維護兩個列和一個值NUM，兩個列分別是OID 列和GROUPIDX 列，OID 列用來存儲記錄地址，GROUPIDX 列存儲多維數(shù)組地址值（i*J*K+j*K+k），其中i、j、k是維向量單元值，I、J、K為維向量字典表長度，I*J*K代表了group by分組屬性對應的多維數(shù)組的大小，用于預分配聚集計算階段的分組向量大小。NUM用來存儲CVectorIndex 滿足連接條件及記錄數(shù)。采用壓縮結構存儲中間VectorIndex 方式，一方面減小向量索引遍歷次數(shù)和物化代價，另一方面通過向量化處理的方式可以讓壓縮結構被緩存在cache內，降低主存讀寫次數(shù)。

算法1 壓縮向量星形連接。

輸入：維度表向量索引集合VectorInx，外鍵列集合FKCol，維表向量索引字典表元組數(shù)量集合DicCard；

輸出：壓縮向量索引CVectorIndex。

偽代碼：

2.3 面向多核CPU和GPU的優(yōu)化技術

多表星形連接算法在多核CPU 和GPU 平臺需要面向多級cache和GPU的shared memory結構進行特定的優(yōu)化設計。

2.3.1 多核CPU平臺下的優(yōu)化技術

多核CPU 的每一個核心有獨立的L1-L2-L3 cache（L3 cache slice）且容量較大，在向量化處理時各向量在一個線程內獨占私有cache，向量索引壓縮是一個串行處理過程，可以無鎖化處理（latch-free）。列式處理的定長向量索引和向量化處理的壓縮向量索引均可以在L1 cache 中高性能訪問和更新，從而優(yōu)化向量索引的物化和訪問代價。

2.3.2 GPU平臺下的優(yōu)化技術

GPU由多個SM組成，每個SM由多個CUDA核心構成，SM線程塊共享一個L1 cache和shared memory。在GPU平臺上的向量化查詢處理在shared memory 層執(zhí)行向量索引訪問，降低了查詢處理過程中的global memory訪問延遲。不同之處在于，一個SM內所有線程共享同一個相對CPU私有cache容量小得多的shared memory，線程私有向量方法因線程配額shared memory容量過小而效率降低，SM線程共享向量時應用壓縮向量需要通過并發(fā)控制機制而增加了處理代價。本文采用SM共享shared memory內線程間共享定長向量索引方法簡化GPU上的向量化查詢處理實現(xiàn)方法，通過提高數(shù)據(jù)處理并行度，降低串行負載的方法提高了多表星形連接算法執(zhí)行效率。

3 實驗測試與分析

實驗平臺硬軟件配置如表1 所示，實測服務器的內存讀取帶寬上限約為79 GB/s。

表1 實驗硬軟件配置Tab.1 Hardware and software configuration for experiments

3.1 測試數(shù)據(jù)集與連接基準

實驗測試集為星形模型基準（Star Schema Benchmark，SSB），數(shù)據(jù)規(guī)模SF=100。針對本文研究內容修改了基準測試查詢，去掉Q1 組事實表上的選擇操作，使測試查詢能夠更好地體現(xiàn)多表星形連接的執(zhí)行過程，修改后的基準稱為星形連接基準（Star Schema Join Benchmark，SSJB）。各連接基準測試查詢選擇率如表2所示。

表2 SSJB連接選擇率Tab.2 Join selectivities rate of SSJB

3.2 多表星形連接算法

實驗測試了CPU 端和GPU 端不同的多表星形連接算法，算法描述如表3所示。

為對比多表星形連接算法的性能，SSJB 基準在當前主流的內存數(shù)據(jù)庫Hyper、Vector、MonetDB 與GPU 數(shù)據(jù)庫OmniSci（CPU和GPU模式）、PG-Strom+Arrow 進行了性能測試，測試多表星形連接算法與當前代表性數(shù)據(jù)庫的性能對比，SSJB 基準測試SQL示例如下：

表3 星形連接算法Tab.3 Star-join algorithms

3.3 多表星形連接性能對比

表4 中首先測試了事實表與不同數(shù)量維表連接性能。GPU 端連接性能普遍優(yōu)于CPU 端實現(xiàn)性能，顯示了GPU 在加速連接操作方面的顯著收益。消除內存物化代價的GRSJ 算法性能優(yōu)于需要內存物化的GCSJ 和GVSJ 算法，對于中間結果多的查詢GRSJ 表現(xiàn)更好，中間結果少時GCSJ 性能更好。在數(shù)據(jù)庫端，OmniSci GPU 顯著優(yōu)于OmniSci CPU 和其他數(shù)據(jù)庫。在CPU 端，由于連接選擇率為100%，壓縮向量星形連接算法PCSJ和PVSJ性能低于行式處理算法RSJ，也低于非壓縮的VSJ向量處理算法。

表4 星形連接性能 單位：msTab.4 Performance of Star-joins unit：ms

表4 最后一行顯示了不同數(shù)據(jù)庫及算法在SSB 連接測試中的平均查詢執(zhí)行時間。SSJB 測試結果顯示，GPU 端算法性能顯著優(yōu)于CPU 端算法性能，OmniSci GPU 星形連接性能也顯著優(yōu)于其他數(shù)據(jù)庫。CPU 端算法中基于壓縮向量的算法PCSJ 性能較好，低選擇率帶來較高的壓縮處理性能收益。GPU 端算法中SJ 執(zhí)行時間略長于行式處理算法GRSJ 和向量處理算法GVSJ，優(yōu)化連接中間結果在GPU端同樣獲得性能收益，但GPU 端算法之間的性能差異較CPU 端小。數(shù)據(jù)庫方面，基于實時編譯技術的Hyper 性能優(yōu)于基于CPU 端數(shù)據(jù)庫，基于向量處理技術的OmniSci CPU 和Vector 也優(yōu)于基于列處理技術的MonetDB。

3.4 向量大小對性能的影響因素

向量化查詢處理的基本思想是通過優(yōu)化的向量大小參數(shù)設置使查詢處理過程中的中間結果列能夠緩存于高速的L1 cache 或GPU 的shared memory，本文測試了不同向量大小對向量化算法性能的影響。CPU 算法上按照cache 緩存大小設計不同的向量長度，測試了VSJ算法的性能表現(xiàn)；在GPU上根據(jù)共享內存的大小（96 KB）和L2 大?。? MB）設計測試GVSJ算法向量大小方案。

如圖3 測試結果所示，基于cache 緩存優(yōu)化的VSJ 算法在向量大小小于L1 時會擁有比較好的性能，當向量長度為1 024，即向量大小為4 KB 時擁有最好的性能，向量大小超過L1 之后性能逐漸降低，再超過L2 和L3 之后性能趨于穩(wěn)定。如圖4所示，在GPU 上：當向量大小在共享內存范圍之內且向量長度在1 024 左右時，擁有最好的性能；超過GPU 的共享內存大小和L1 大小后，性能有輕微的降低；向量大小超過L2 之后，GVSJ 算法性能趨于穩(wěn)定。圖3 和圖4 橫坐標對應向量的長度，每個向量對應的字寬度是4 B，故32 KB 大小L1 cache對應的向量長度位32/4=8 K，其余類似。

圖3 向量大小對性能影響（CPU）Fig.3 Effect of vector size on performance（CPU）

圖4 向量大小對性能影響（GPU）Fig.4 Effect of vector size on performance（GPU）

從以上結果分析可以看到，相對于CPU，GPU連接算法性能對于向量大小的敏感度要更低一些，主要原因是GPU 強大的并行計算能力彌補了內存訪問延遲。在CPU 平臺設計向量化算法時，選擇合適的向量大小能很大程度上優(yōu)化連接算法性能，需要考慮cache的大小和實際的算法特點進行向量大小優(yōu)化設計；GPU上連接算法的性能表現(xiàn)很好，算法設計相對簡單并盡可能減少邏輯判斷會有更好的性能。

4 結語

本文系統(tǒng)地研究了面向OLAP 負載中多表星形連接操作實現(xiàn)技術，提出了基于壓縮向量的向量化連接優(yōu)化技術，并在多核CPU 和GPU 平臺上實現(xiàn)算法并進行全面的性能測試。基于SSJB 連接基準測試了不同的算法實現(xiàn)與當前最具有代表性的內存數(shù)據(jù)庫與GPU 數(shù)據(jù)庫的多表星表連接性能，通過性能對比得出以下結論：1）GPU 對多表星形連接操作的加速效果顯著，無論在算法還是在數(shù)據(jù)庫系統(tǒng)層面均表現(xiàn)出顯著的性能提升；2）基于編譯的行式處理在多表星形連接操作中性能優(yōu)于列式處理，與向量化處理性能相近，在低選擇率時，壓縮向量處理模式性能較好；3）GPU平臺有較高的內存帶寬，行式、列式與向量化處理性能差異不大，可以簡化GPU 端算法設計復雜度，合適設置向量化處理的向量大小可以提高連接性能；4）GPU 數(shù)據(jù)庫相對于CPU 數(shù)據(jù)庫在連接優(yōu)化方面具有顯著的性能優(yōu)勢，是高性能數(shù)據(jù)庫未來的發(fā)展趨勢。

致謝：本研究工作得到中國人民大學校級公共計算云平臺支持。