主要观点：CedarDB 的高效连接处理至关重要，本文深入探讨其背后技术，包括简单高效稳健的连接处理哈希表。
关键信息：

• 哈希表是数据处理常用数据结构，CedarDB 依赖它执行查询执行引擎关键部分，实现关系连接为哈希连接。
• 常见哈希表实现不适合数据库系统连接处理，需满足并行数据处理、高效过滤非匹配行、抗重复倾斜等需求。
• 数据库系统并行化算法开销值得，哈希连接可将工作分为构建和探测阶段，采用链式哈希表实现并行插入，同步可通过原子比较交换循环实现。
• 连接处理探测阶段是热点路径，需高效过滤非匹配行，利用哈希值找到表槽和布隆过滤器进行包含性检查，仅需 10 条 x86 指令。
• 选择合适哈希函数，基于 CRC 的自定义哈希函数紧凑且抗碰撞，在小哈希表时能减少指令提高性能，大哈希表时能利用 CPU 乱序执行隐藏内存访问延迟。
• 处理倾斜时，结合链式哈希表指针数组和线性探测方案的密集存储布局，即“unchained”布局，可兼顾碰撞抵抗和低误报率。
• 评估哈希表实现效果，与简单链式和罗宾汉哈希方案比较，在不同基准测试中表现优异，在 TPC-H 等 workload 上平均快 6 倍。
  重要细节：
• 构建阶段仅插入连接较小边的元组，探测阶段仅检查较大边的元组是否匹配，分三个阶段进行并同步。
• 哈希表布局用哈希高位找表槽，低位做布隆过滤器检查，节省空间和指令，目录大小为数据集下一个 2 的幂次方。
• 预计算 4kB 布隆标签查找表，测试所有标签位匹配只需一条指令，布隆过滤器误报率<1%。
• 不同基准测试中，unchained 布局在图查询中可提速 16 倍，在 TPC-H 等关系型 workload 上比链式哈希表稍快且比开放寻址方案快得多，与 Hyper 和 DuckDB 比较也有优势。