11 -【cmu15-721】【高级数据库系统】【卡内基梅隆大学】【中英字幕】

1. 今天我们要讨论并行哈希连接。

2. 并行哈希连接是高性能连接的首选方法。

3. 项目2和项目3的信息已经发布，需要尽快完成。

4. 哈希连接和排序连接是连接的两种基本方法。

5. 过去几十年中，哈希连接一直是主流方法，但最新的研究表明无分区方法可能更好。

6. 下一个目标是最小化我们访问内存的成本。假设我们在单个节点上运行，假设我们要进行连接的数据已经被加载到内存中。现在当我们访问数据时，我们希望确保最大化数据的局部性，即希望工作线程访问的数据在同一个CPU缓存中，或者至少在同一个NUMA区域中。我们还希望在将数据加载到CPU缓存时，尽可能地重用数据，以避免频繁地从内存中读取数据，从而浪费时间。为了实现这个目标，在算法实现中，我们需要注意CPU缓存和TLB硬件中的数据。我们还需要注意数据的顺序访问，以最大化数据的局部性。对于随机访问，我们可以将数据分割成每个操作或步骤都在同一个缓存行中的块。在进行数据分割时，我们需要权衡计算连接所需的指令数量和内存使用量。有时，不进行数据分割可能更好。哈希连接是数据系统中最重要的操作之一。我们需要尽可能快地执行哈希连接，并利用我们获得的额外核心。哈希连接的基本步骤包括分区、构建哈希表和探测。分区阶段将数据分割成不相交的子集，构建阶段创建哈希表，探测阶段将内部表的数据

7. 哈希函数是将任意值映射到较小域的函数，我们希望它既快速又具有较低的碰撞率。

8. 最快的哈希函数是xxhash，它在速度和碰撞率之间有一个很好的平衡。

9. 线性探测哈希表是最快的实现方式，它使用线性探测来处理碰撞。

10. cuckoo哈希和hopscotch哈希是其他的哈希表实现方式，但它们的性能不如线性探测哈希表。

11. 哈希表是哈希连接的关键数据结构，用于处理碰撞和查找操作。

12. City Hash、XX Hash和Highway Hash是目前被认为是最先进的哈希函数算法。

13. XX Hash 3是最新的版本，性能非常出色。

14. City Hash和Farm Hash不使用SIMD指令集，XX Hash可能也不使用SIMD指令集，因为使用SIMD会降低可移植性。

15. 线性探测哈希和链式哈希是最常见的哈希表实现方式，其他方法可能不太适合一般情况下使用。

16. Hopscotch Hashing是Robinhood Hashing的一种现代变体，通过限制“邻域”的大小来控制哈希表的扩展，以提高性能。

17. 一种哈希表的实现方法是Robinhood hashing，可以在邻近位置进行键的移动。

18. 另一种哈希表的实现方法是Cuckoo hashing，可以使用多个哈希函数和多个哈希表来解决冲突。

19. 在哈希表的构建过程中，可以使用布隆过滤器来优化查找性能。

20. 在实际系统中，大多数数据系统供应商会选择一种哈希表实现方法，并不会尝试过多的优化。

21. 在哈希连接中，哈希表的性能优化并不是最重要的，查询优化器的性能更为关键。