Resources

• https://cloud.tencent.com/developer/article/1694495
• https://www.youtube.com/watch?v=J0nbgXIarhc&ab_channel=CMUDatabaseGroup
• https://zhuanlan.zhihu.com/p/144926830
• https://zhuanlan.zhihu.com/p/35622907
• https://zhuanlan.zhihu.com/p/54484592
• https://zhuanlan.zhihu.com/p/100933389
• https://www.bilibili.com/video/BV1Bt411v7ST
• https://www.the-paper-trail.org/post/2013-01-30-columnar-storage/

compression

vectorized query processing

late materialization

Hash join*

对于多线程下的join，我们的评估标准如下：

• 尽量减少执行阻塞（锁等待）
• 尽量保证提高cpu缓存命中率或者数据为工作线程局部持有

Hash join vs. index join

Hash join由于build的哈希表在probe之后立即丢弃，因此只有在大join（TiDB中大于1万行才会采用），相对的index join的索引会持久化，硬币的另一端就选择 index join

Partition hash join vs. non-partition hash join

Hash Join workload

Overview

partition主要将某些特性（比如日期，区分度）来将大数据划分为相对小数据，从而减轻计算压力，增加cpu使用率

Partition phase

由于hashing是基于 join key和扫描数据基于行，因此

NSM（行存）：每一行都得扫描才能包含join key

DSM（列存）：相当于扫描基于列，因此只要特定的列（如果想找同行的其余元素就加上offset）即可完成hashing

Non-blocking parittioning遇到的问题主要在于lock-free的工程复杂

Blocking partitioning的问题主要是性能的相对弱势

两种方法，根据partition的写入是否全局/局部进行区分，但是全局共享不可避免带来读写竞争和锁的管理，这种方法的分区只起到了缓解的作用

radix sort我们都接触过，是基数排序，简单讲就是按每位来迭代排序。

而radix partitioning相比于non-blocking的一次性，使用迭代来操作，其中使用prefix sum来确定每次写入的offset，同时先申请大小再实际写入，减少了后续竞争

Build phase

我们知道哈希碰撞的解决办法有开放地址和拉链两种解决办法，因此哈希函数需要做碰撞率和性能的取舍：少碰撞就占空间，多碰撞换读取速度

不同应用场景下我们有不同的加减法，给出一些我的调研：

• MySQL8
• PostgreSQL
• Oceanbase
• TiDB

Probe phase