面向多核CPU和GPU平台的数据库星形连接优化

，3*

（1.数据工程与知识工程教育部重点实验室（中国人民大学），北京 100872；2.中国人民大学信息学院，北京 100872；3.中国人民大学中国调查与数据中心，北京 100872；4.中国气象局国家卫星气象中心，北京 100081）

0 引言

连接操作是关系数据库中最重要的操作之一，也是执行代价最大的操作之一，一直是数据库查询优化的核心问题。在典型联机分析处理（On-Line Analytical Processing，OLAP）负载中，事实表与维表之间的星形连接操作执行时间占到全部查询处理时间的80%左右［1］，提高星形连接操作性能是提高OLAP 查询处理性能的决定因素。当前研究热点主要集中在连接操作性能优化方面，对多表星形连接优化技术研究相对较少，而两表连接与多表连接在优化算法选择策略上有较大的差异［2］。分区Radix join 连接算法性能优于无分区的哈希连接算法，但在多表连接操作中Radix join 算法由于需要多次物化无法流水处理而失去性能优势［3］。另一方面，多表连接时需要通过不同的策略优化中间连接结果，需要结合细粒度记录级流水处理、粗粒度列级处理和向量化处理策略进行优化设计，同时面向中央处理器（Central Processing Unit，CPU）cache 或图形处理器（Graphics Processing Unit，GPU）shared memory 优化多表连接中间结果的物化和访问策略，提高多表连接整体性能。

本文通过面向多核CPU 平台上L1 cache级的连接中间结果缓存和压缩技术，以及面向GPU 多cuda 核心共享Shared memory 的向量化处理技术使多表星形连接的中间结果物化和访问发生在访问性能较好的L1 cache 和Shared memory，减少延迟较高的内存物化和访问代价，从而提高整体连接性能。本文的贡献主要体现在以下三个方面：

1）提出了基于压缩向量的星形连接算法，优化连接中间结果的存储效率和连接列的扫描效率；

2）设计了面向多核CPU 平台和GPU 平台的向量化星形连接算法，优化了连接中间结果在CPU 的L1 cache 和GPU 的shared memory上的物化和访问效率；

3）综合对比了不同的星形连接算法性能，以及当前主流的内存数据库和GPU 数据库多表连接性能，验证了本文提出的星形连接算法性能的优化程度。

本文所使用的算法名称及简称规则，行式关键字是R（Row），列式关键字C（Col），压缩关键字P（comPress），向量化处理关键字V（Vector），GPU 关键字G（GPU），星形连接关键字SJ（StarJoin）；例如RSJ 代表CPU 行式处理星形连接算法，GVSJ代表GPU下的向量星形连接算法。

1 相关工作

连接操作是关系数据库重要的操作，近年来，学术界对多核CPU 平台上的连接优化技术做了深入的研究。文献［4］首先提出了应用现代CPU 的多线程、自动预取等技术使简单的无分区哈希连接（No Partition jOin，NPO）算法可以优于面向cache 优化的Radix 分区哈希连接（Partition Radix Hash jOin，PRO）算法，从而简化算法设计复杂度。随后，文献［2］证明PRO 算法在面向硬件参数优化后性能优于NPO 算法，哈希连接算法需要根据硬件特征而定制优化。文献［5］进一步研究了面向多核CPU 优化的排序归并连接算法与PRO 算法的性能差异，证明PRO 算法的性能较高。这些研究开启了一系列的深度优化研究工作，文献［6］从7 个优化维度探索了连接优化技术，文献［7］综合比较了13 个学术界与产业界的代表性连接算法，在新一代的至强融核处理器（Intel Xeon Phi，Phi）上也得到了验证［8］。随着GPU 逐渐应用于数据处理领域，基于GPU 的连接优化技术［9］成为一个重要的研究领域。GPU 技术的快速迭代及硬件参数的变化使GPU 上的连接优化更具挑战性［10］，如基于CPU-GPU 融合架构的连接优化技术［11］探索了不同哈希连接算法的性能特征，GPU上的存储优化技术［12］、以操作符为中心的处理模型和基于负载特征的GPU 热数据存储策略［13］等。由于GPU 与CPU 在硬件架构上显著的差异，传统CPU 平台上的连接算法需要面向GPU 硬件特征而优化实现，利用GPU 强大的并行计算性能优化数据库的连接性能［14］。CPU 平台上代表性的NPO 与PRO 算法在GPU 平台上通过面向GPU 硬件特性的优化获得较好的性能，并优化PCIe传输性能［15］。值得注意的是，随着GPU硬件的持续升级，GPU连接算法需要面向GPU 硬件的新特性而持续优化，GPU 硬件新特性能够显著提升传统的连接算法性能［16］。除传统的哈希连接优化技术之外，面向OLAP 模式特征而定制的数组索引连接（Array Index Join，AIJ）算法［1］和Array Join 连接算法［7］通过数组地址映射技术进一步提高了连接效率。AIJ 连接算法通过预分组将维表映射为维向量，通过代理键索引机制实现事实表外键与维向量之间基于地址映射的连接方法，在星形连接操作中，迭代处理事实表外键列与各维向量之间的映射连接，并将连接中间结果以共享向量索引方式迭代更新，消除了传统关系数据库中较难优化的哈希连接算法，同时通过较小的向量索引缩减了连接中间结果的存储空间消耗。

OLAP 查询以多表连接为基础，相对于两表连接优化技术，多表连接需要考虑更多的性能影响因素［17］，如两阶段优化策略、数据传输和连接优化。除连接算法本身的性能之外，文献［3］指出虽然PRO 算法在两表连接时性能更好，但其物化策略和较大的物化代价不适合多表连接的流水处理模式。在多表连接过程中，不同查询处理模型产生不同的中间连接结果物化和处理代价对多表星形连接的性能产生较大的影响。图1 显示了数据库代表性的行式、列式和向量化查询处理模型的示例，图中A、B、C代表3个数据列，Avec、BVec、CVec分别代表A、B、C 列对应的向量，tmpVec代表中间结果向量，resVec代表结果向量。行式处理模型是一种列间数据访问的流水处理方式，不产生中间结果，当不同列上的操作有较低的选择率时，受分支预测性能的影响可能会产生无效的数据访问代价。列式处理每次处理一个或两个列，数据访问的cache 效率高，需要通过临时列缓存中间计算结果，较大的中间结果列增加了内存物化代价，但在选择和连接等具有过滤性的操作中，中间结果列可以提高后续列的访问效率。向量化查询处理模型［18］将列划分为适合L1 cache 大小的向量，实现基于向量的流水处理，cache中的中间结果既保持了列式处理数据访问效率高、过滤性好的优点，也通过cache 内的中间结果缓存降低了内存物化代价，也与传统数据库的流水迭代处理模型保持兼容。实时编译（Just In Time，JIT）技术进一步提高的查询处理的代码执行效率，将传统查询处理的“拉”模式优化为代码执行效率更高的“推”模式，通过与向量化查询处理等技术的结合进一步提高查询处理性能［19］。

早期GPU 上主要采用一次操作符查询处理模型，与CPU平台存在相同的global memory 上的物化存储访问代价，同时较大的中间结果物化开销降低了GPU 内存利用率。随着GPU 硬件技术的发展，多kernel 机制支持了流水处理模式，降低了物化代价。Tile-based execution model［3］是一种基于GPU线程块粒度的向量化查询处理方法，针对GPU 特殊的流处理多核（Streaming Multiprocessor，SM）内多CUDA 核心、多线程共享Shared memory 的硬件结构而设计的线程块共享向量化查询处理方法，将CPU 平台代表性的向量化查询处理方法在GPU平台进行了适应化优化设计。

总体而言，OLAP 的连接优化是连接算法优化、查询处理模型优化、存储访问优化的综合应用，尤其需要面向多核CPU和GPU 不同的硬件架构做针对性的优化设计才能更好地适应多核CPU和GPU平台。

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

2 星形连接优化技术

本文在向量连接算法［1］基础上研究面向OLAP 负载的多表星形连接算法优化技术，通过维表代理键索引和维向量地址映射技术将连接优化为数组地址映射操作，简化连接算法实现，从而可以更好地分析多表星形连接算法的性能影响因素。

2.1 星形连接实现技术

典型的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）命令分解到查询相关的各个维表上，根据where 和group by 子句生成维向量。2）星形连接。在事实表相应的外键列与维向量之间执行基于向量连接的多表连接操作，将连接的结果迭代存储为向量索引。3）在事实表度量列上执行基于向量索引的聚集计算。如图2 示例所示，Dim Vector Index1～3对应查询命令中相关的3 个点维表生成的维向量，FK1～3对应3个维表的外键列，其外键值可以直接映射为维向量中的偏移地址，Vector Index为向量索引，被3个连接阶段共享访问，并在连接执行时根据连接结果迭代更新其记录的group by 多维数组地址，CVector Index 为压缩的向量索引结构。

图2 星形连接技术Fig.2 Star-join technique

向量连接算法首先在各维表上按相应的where 子句过滤不满足条件的元组，投影出当前维表上的group by 属性或属性组，并对其进行动态字典表压缩，3 个维表group by 属性字典表的集势将group by 语句中的分组属性映射多维数组，每个维表上的分组属性投影到基于维表代理键的向量上并进行数组字典表压缩。如图2（a）中group by 语句中的分组属性分别投影到3 个维表按代理键生成的维向量中，分组属性按数组字典表压缩，3个维表分组属性数组字典表的集势I、J、K分别为2、3、2，表示group by 语句对应的2×3×2=12 个多维数组单元。事实表外键值映射为维向量数组下标，多表星形连接操作是一个迭代计算对应维向量非空事实表记录的group by属性多维数组地址的过程。

多表星形连接操作是OLAP 查询的核心操作，在实现中可以分为行式处理（tuple-at-a-time）、列式处理（column-at-atime）和向量化处理（vector-at-a-time）三种模式。

1）行式处理：每次读取事实表全部外键值，分别映射到相应维向量，若均非空则计算group by 属性多维数组地址，直接生成最终连接结果。

2）列式处理：每次处理一个外键列连接操作，使用向量索引（Vector Index）记录当前事实表记录与相应维表连接产生的部分group by 属性多维数组地址，生成的向量索引同时用作下一外键列的位图索引过滤下一外键列，多表连接过程迭代更新向量索引和相应的group by 属性多维数组地址，最后一列完成连接后生成最终向量索引，非空位置记录连接记录的group by属性多维数组地址。

3）向量化处理：事实表外键列以向量大小划分为若干行组，每个行组内采用列式处理，作为中间结果的向量索引上的访问和更新操作主要在L1 cache 中进行，降低多表连接过程中向量索引的内存访问代价。

向量索引可以使用定长与压缩两种存储结构，定长向量索引大小不受选择率影响，但低选择率时稀疏的非空值扫描操作对外键列的过滤效率较低；压缩向量索引使用OID/GROUPIDX 二元结构，大小由选择率决定，低选择率时对外键列的过滤效果较好，但需要动态分配存储空间。图2 演示了基于定长向量索引与压缩向量索引的星形连接执行过程。

2.2 压缩向量星形连接实现技术

如图2（b），压缩向量维护两个列和一个值NUM，两个列分别是OID 列和GROUPIDX 列，OID 列用来存储记录地址，GROUPIDX 列存储多维数组地址值（i*J*K+j*K+k），其中i、j、k是维向量单元值，I、J、K为维向量字典表长度，I*J*K代表了group by分组属性对应的多维数组的大小，用于预分配聚集计算阶段的分组向量大小。NUM用来存储CVectorIndex 满足连接条件及记录数。采用压缩结构存储中间VectorIndex 方式，一方面减小向量索引遍历次数和物化代价，另一方面通过向量化处理的方式可以让压缩结构被缓存在cache内，降低主存读写次数。

算法1 压缩向量星形连接。

输入：维度表向量索引集合VectorInx，外键列集合FKCol，维表向量索引字典表元组数量集合DicCard；

输出：压缩向量索引CVectorIndex。

伪代码：

2.3 面向多核CPU和GPU的优化技术

多表星形连接算法在多核CPU 和GPU 平台需要面向多级cache和GPU的shared memory结构进行特定的优化设计。

2.3.1 多核CPU平台下的优化技术

多核CPU 的每一个核心有独立的L1-L2-L3 cache（L3 cache slice）且容量较大，在向量化处理时各向量在一个线程内独占私有cache，向量索引压缩是一个串行处理过程，可以无锁化处理（latch-free）。列式处理的定长向量索引和向量化处理的压缩向量索引均可以在L1 cache 中高性能访问和更新，从而优化向量索引的物化和访问代价。

2.3.2 GPU平台下的优化技术

GPU由多个SM组成，每个SM由多个CUDA核心构成，SM线程块共享一个L1 cache和shared memory。在GPU平台上的向量化查询处理在shared memory 层执行向量索引访问，降低了查询处理过程中的global memory访问延迟。不同之处在于，一个SM内所有线程共享同一个相对CPU私有cache容量小得多的shared memory，线程私有向量方法因线程配额shared memory容量过小而效率降低，SM线程共享向量时应用压缩向量需要通过并发控制机制而增加了处理代价。本文采用SM共享shared memory内线程间共享定长向量索引方法简化GPU上的向量化查询处理实现方法，通过提高数据处理并行度，降低串行负载的方法提高了多表星形连接算法执行效率。

3 实验测试与分析

实验平台硬软件配置如表1 所示，实测服务器的内存读取带宽上限约为79 GB/s。

表1 实验硬软件配置Tab.1 Hardware and software configuration for experiments

3.1 测试数据集与连接基准

实验测试集为星形模型基准（Star Schema Benchmark，SSB），数据规模SF=100。针对本文研究内容修改了基准测试查询，去掉Q1 组事实表上的选择操作，使测试查询能够更好地体现多表星形连接的执行过程，修改后的基准称为星形连接基准（Star Schema Join Benchmark，SSJB）。各连接基准测试查询选择率如表2所示。

表2 SSJB连接选择率Tab.2 Join selectivities rate of SSJB

3.2 多表星形连接算法

实验测试了CPU 端和GPU 端不同的多表星形连接算法，算法描述如表3所示。

为对比多表星形连接算法的性能，SSJB 基准在当前主流的内存数据库Hyper、Vector、MonetDB 与GPU 数据库OmniSci（CPU和GPU模式）、PG-Strom+Arrow 进行了性能测试，测试多表星形连接算法与当前代表性数据库的性能对比，SSJB 基准测试SQL示例如下：

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

3.3 多表星形连接性能对比

表4 中首先测试了事实表与不同数量维表连接性能。GPU 端连接性能普遍优于CPU 端实现性能，显示了GPU 在加速连接操作方面的显著收益。消除内存物化代价的GRSJ 算法性能优于需要内存物化的GCSJ 和GVSJ 算法，对于中间结果多的查询GRSJ 表现更好，中间结果少时GCSJ 性能更好。在数据库端，OmniSci GPU 显著优于OmniSci CPU 和其他数据库。在CPU 端，由于连接选择率为100%，压缩向量星形连接算法PCSJ和PVSJ性能低于行式处理算法RSJ，也低于非压缩的VSJ向量处理算法。

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

表4 最后一行显示了不同数据库及算法在SSB 连接测试中的平均查询执行时间。SSJB 测试结果显示，GPU 端算法性能显著优于CPU 端算法性能，OmniSci GPU 星形连接性能也显著优于其他数据库。CPU 端算法中基于压缩向量的算法PCSJ 性能较好，低选择率带来较高的压缩处理性能收益。GPU 端算法中SJ 执行时间略长于行式处理算法GRSJ 和向量处理算法GVSJ，优化连接中间结果在GPU端同样获得性能收益，但GPU 端算法之间的性能差异较CPU 端小。数据库方面，基于实时编译技术的Hyper 性能优于基于CPU 端数据库，基于向量处理技术的OmniSci CPU 和Vector 也优于基于列处理技术的MonetDB。

3.4 向量大小对性能的影响因素

向量化查询处理的基本思想是通过优化的向量大小参数设置使查询处理过程中的中间结果列能够缓存于高速的L1 cache 或GPU 的shared memory，本文测试了不同向量大小对向量化算法性能的影响。CPU 算法上按照cache 缓存大小设计不同的向量长度，测试了VSJ算法的性能表现；在GPU上根据共享内存的大小（96 KB）和L2 大小（6 MB）设计测试GVSJ算法向量大小方案。

如图3 测试结果所示，基于cache 缓存优化的VSJ 算法在向量大小小于L1 时会拥有比较好的性能，当向量长度为1 024，即向量大小为4 KB 时拥有最好的性能，向量大小超过L1 之后性能逐渐降低，再超过L2 和L3 之后性能趋于稳定。如图4所示，在GPU 上：当向量大小在共享内存范围之内且向量长度在1 024 左右时，拥有最好的性能；超过GPU 的共享内存大小和L1 大小后，性能有轻微的降低；向量大小超过L2 之后，GVSJ 算法性能趋于稳定。图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 平台设计向量化算法时，选择合适的向量大小能很大程度上优化连接算法性能，需要考虑cache的大小和实际的算法特点进行向量大小优化设计；GPU上连接算法的性能表现很好，算法设计相对简单并尽可能减少逻辑判断会有更好的性能。

4 结语

本文系统地研究了面向OLAP 负载中多表星形连接操作实现技术，提出了基于压缩向量的向量化连接优化技术，并在多核CPU 和GPU 平台上实现算法并进行全面的性能测试。基于SSJB 连接基准测试了不同的算法实现与当前最具有代表性的内存数据库与GPU 数据库的多表星表连接性能，通过性能对比得出以下结论：1）GPU 对多表星形连接操作的加速效果显著，无论在算法还是在数据库系统层面均表现出显著的性能提升；2）基于编译的行式处理在多表星形连接操作中性能优于列式处理，与向量化处理性能相近，在低选择率时，压缩向量处理模式性能较好；3）GPU平台有较高的内存带宽，行式、列式与向量化处理性能差异不大，可以简化GPU 端算法设计复杂度，合适设置向量化处理的向量大小可以提高连接性能；4）GPU 数据库相对于CPU 数据库在连接优化方面具有显著的性能优势，是高性能数据库未来的发展趋势。

致谢：本研究工作得到中国人民大学校级公共计算云平台支持。