海量智库第13期｜Vastbase G100性能优化技术介绍之【vsonichashjoin优化】

海量数据 2023-06-16

377

导语

哈希连接作为多表连接中最常用的算子之一，性能的影响至关重要，我们分析了现有的vsonichashjoin的实现，从硬件的角度出发，解决了哈希表在大数据量或高冲突率下的资源访问的性能瓶颈，提升了整体的性能。

vsonichashjoin目前存在的问题

Hash表仅存储位置信息

分析现有vsonichashjoin实现，可以看到hash表中只存位置，这也就意味着，进行条件匹配的时候无论能否匹配上，都必须要访问底层存储datumarray以获取数据，这会带来额外的内存访问，hash表只承担了访问跳转的功能，内存利用率不高，并且会基于join条件个数进一步放大内存访存带来的问题(Cache Miss、TLB Miss、内存带宽不足)。

解决Hash冲突的方式不友好

通过原始Hash冲突的解决方式，可以看到他必须要访问next数组来判断是否为0，才能知道后面是否还存在冲突，因此导致内存不断跳跃式访问的问题。

解决Hash冲突的方式不友好

基于链表式的hash表无法更好的利用内存局部的原理，CPU会根据内存地址一次取一个cacheline(一般64字节)大小的内存放入CPU缓存中，而一个位置信息可能只占8字节，跳跃式的内存访问无法充分利用CPU缓存。

Hash表过大，CPU缓存装不下

按照当前的计算机架构，CPU对内存的读写访问一般会根据内存地址以cacheline为单位放入CPU的多级缓存中，L1cache、L2cache一般是单核缓存，L3cache是多核共享缓存。对于访问一个内存很大的hash表来说，可能会面临两个问题：

hash表内存太大，无法放入L2cache，hash表会以cacheline为单位不断的在主存与缓存中间交换，交换的成本就是cachemiss所带来的CPU流水线的停顿。

由于join操作本身也需要一定的工作内存，并且join算子在Plan Tree上进行迭代，一旦投影到上层算子上的时候，整个内存布局就会发生改变，导致后续访问hash表时依然会cache miss。

Vastbase基于vsonichashjoin

的优化方案

优化方向1：在hash表中存储datavalue或者hashvalue来减少对底层datumarray的访问

实际上大多数hash表的实现都会在hash表中存储hashvalue，但hashvalue相同不意味原始数据也相同，所以有的时候会去掉hashvalue来减少hash表的大小，但存储hashvalue可以用来过滤，因为hash值相同，数据不同只是小概率事件。

一般我们会基于int类型的主键进行多表连接，所以存储datavalue实际上是一种特殊场景的优化，但这种特殊场景却又十分普遍。对于int类型的join条件，int类型的数据可以替代hashvalue的作用，直接校验数据是否相同，当然，对于这一列我们可以直接从hash表上进行投影。

因为hash表中只能存定长数据，所以很明显，如果join条件中没有int类型，或者全部是由复杂表达式构成的，那么只能存hashvalue。

如果其中有一个或全部都是int类型，那么还需要考虑条件个数的问题，如果有很多个条件，这时只存了一个int值，实际对筛选并没有起太大的作用，所以在超过阈值的条件个数时，存hashvalue更合适，经过测试目前这个值暂定为2比较合适。

这里会从左遍历连接条件，将第一个int类型条件的数据放入hash表(越靠前期待选择率越低)。

目前暂时没有将其与选择率挂钩。

优化方向2：在位置信息的高bit上加入提示信息，来指导下一次访问的方向，或者停止访问

不难看出，表示位置的整型数据，高bit实际上大部分都是不使用的，一个int32bit，表示几百万数据可能只用了20多个bit而已，我们可以利用高bit的数据作为hint，来对冲突进行指示。

这里实际上是只用了2bit，4种组合来指示冲突的位置，这个做法实际上对解决冲突的内存访问性能得到了的提升。因为基于原来的实现，必须要访问next数组，检查值是否为0，才能判断出后面是否还有冲突，现在只要访问当前元素的位置信息的高bit，就可以检查出这个元素后面是否还有冲突，避免了无效的内存访问。

我们还可以组合链表方式与线性探测的方式，先使用链表方式解决冲突，然后探测冲突的链表是否可以在右侧展平。

优化方向3：改用线性探测的方式，但一个hashbucket不只存储一个元素，而是一组元素，并添加位图

线性探测拥有比较好的数据局部性，所有的冲突元素大概率在第一次访问元素的右侧。

在hashbucket上添加了位图，位图由1bit的标记数据与7bit的hashvalue组成，7bit的hashvalue可以进行初步筛选，位图拥有更小的内存，可以使用更小的内存成本换取更多的有用信息。

每个hash bucket group的元素容量根据数据量决定，最后一个元素不会使用，用于标记这个组是否有元素溢出到下一个组，可以及时的停止线性探测。

优化方向4：从根本上解决hash冲突，对原始数据进行重新排列

不管是那种方式解决冲突，实际上都没有根本解决冲突，因为原始的数据的位置没有变化。如果将原始数据按照hashbucket的分布进行重排，让hashbucket冲突的所有元素，都处于连续的线性空间内，从根本上解决了hash冲突带来的内存跳跃式访问。

使用计数排序的方式，只要遍历一遍数据，就可以计算每个hashbucket中的数量，并计算每个hahsbuck中数量的前缀和，可以以O(n)的时间复杂度对原始数据按照hash分布进行重排。

优化方向5：将大的hash表根据缓存大小切分成多个分区，每个分区独自完成join

如果把一个大的hash表拆分成多个分区后，那么就可以把每次探测时所需的内存限制在一个较小的范围内，那么他可以装入L2cache，从而避免探测大内存的hash表时，CPU缓存与主存间交换数据所带来的访问延时。

优化方向6：基于分区的hashjoin，可以自由决定完成每个小分区的join方式

当拆分成多个小分区后，每组分区可以独立选择内外表，而没有必要按照优化器的判断，可以一定程度上减少优化器代价估计的错误。

并且，由于大量重复值一定会落在同一个分区内，即使构建了hashtable，那不过也是在冲突链或者数组上线性探测，那么构建hash表毫无意义，还会浪费内存，我们可以将这组分区采用nestloop方式完成join。

vsonichashjoin算子优化实现效果

环境信息：

CPU：96C服务器

内存：376GB

磁盘：1T机械磁盘

参数配置：

cstore_buffer = 150GB

work_mem = 10GB

以TPCH中join最丰富的Q9为例，6个表进行join，在单线程、IN-MEMORY的场景下，100g数据量，Q9的耗时减少了几乎一倍。

（优化前）

（优化后）

图文编辑｜程筱淇

内容审核｜市场营销部

关于海量数据

北京海量数据技术股份有限公司（股票代码：603138.SH）成立于2007年，是国内首家以数据库为主营业务的主板上市企业。公司十余年来秉承“专注做好数据库”的初心，始终致力于数据库产品的研发、销售和服务。核心产品海量数据库Vastbase系列、数据库一体机Vastcube系列，全栈国产化，应用满足度高，目前广泛应用于政务、制造、金融、通信、能源、交通等多个重点行业，已成为国产企业级数据库的首选之一。

hash 海量数据缓存性能优化优化

文章转载自海量数据，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

海量智库第13期｜Vastbase G100性能优化技术介绍之【vsonichashjoin优化】

vsonichashjoin目前存在的问题

评论