数据库Grace Hash Join

Hash Join（哈希连接） 是关系型数据库（如 MySQL、PostgreSQL、Oracle 等）在处理表连接操作时非常经典且高效的一种算法。它特别适用于大表之间的等值连接（Equi-join），尤其是在参与连接的列上没有合适的索引时。
简单来说，Hash Join 的核心思想是：利用较小的那张表在内存中构建一个哈希表，然后遍历较大的那张表，通过哈希运算去内存中的哈希表里“探测”匹配项。
以下是 Hash Join 全过程的详细拆解：
第一阶段：构建阶段 (Build Phase)

在这个阶段，数据库引擎会选择参与连接的两张表中较小的一张（通常称为 Build Table 或驱动表）。选择小表是为了尽可能让生成的哈希表能够完整地存放在内存中。

• 全表扫描：数据库开始顺序扫描这张较小的 Build Table。
  
• 计算哈希值：对于扫描到的每一行数据，提取出用于连接的列（Join Key），将其输入到一个特定的哈希函数 (Hash Function) 中，计算出一个哈希值。
  
• 存入哈希表：根据计算出的哈希值，将这一行数据（或所需的列数据）放入内存中哈希表对应的“桶（Bucket）”里。
  
  
  
  • 注意：如果不同的连接键计算出了相同的哈希值（哈希冲突 / Hash Collision），它们会被放入同一个桶中，通常以链表的形式连接起来。
    
  
  

第二阶段：探测阶段 (Probe Phase)

构建阶段完成后，内存中就准备好了一个供快速查找的哈希表。接下来处理较大的一张表（通常称为 Probe Table 或被驱动表）。

• 全表扫描：数据库开始顺序扫描这张较大的 Probe Table。
  
• 计算哈希值：对于扫描到的每一行，提取出连接列（Join Key），使用与第一阶段完全相同的哈希函数来计算哈希值。
  
• 探测哈希表：拿着计算出的哈希值，去第一阶段在内存中构建好的哈希表中寻找对应的“桶（Bucket）”。
  
• 精确匹配与输出：
  
  
  
  • 如果桶是空的，说明没有匹配项，直接丢弃该行。
    
  • 如果桶里有数据，数据库会遍历该桶中的链表，将其与当前 Probe Table 的连接键进行精确比较（这一步是为了排除哈希冲突导致的误判）。
    
  • 如果确认为等值匹配，则将这两行数据组合在一起，作为连接结果输出。
    
  
  

如果内存放不下怎么办？(Grace Hash Join)

经典的 In-Memory Hash Join 要求小表必须能全部塞进可用内存（即 Work Memory）。但如果两张表都非常巨大，导致最小的表也远远超出了内存限制，数据库就会采用它的变种：Grace Hash Join（由于数据需要落盘，性能会有所下降）。
整个过程会多出一个分区（Partitioning）的步骤：

• 切分两张表：使用一个哈希函数处理两张表的连接键，将 Build Table 和 Probe Table 拆分成多个较小的、一一对应的“分区文件（Partitions）”并写入磁盘。
  
• 分批处理：因为使用的是同一个哈希函数，所有潜在匹配的数据一定会被分发到编号相同的分区中。
  
• 按区连接：此时，数据库只需要将 Build Table 的第 1 个分区读入内存构建哈希表，然后用 Probe Table 的第 1 个分区去探测。完成后清空内存，接着处理第 2 个分区……以此类推，直到所有分区处理完毕。
  

Hash Join 的优缺点总结

优点：

• 极高的吞吐量：在处理缺乏索引的大批量数据等值连接时，性能通常碾压 Nested Loop Join（嵌套循环连接）。
  
• 扫描次数少：只需要对两张表各进行一次全表扫描（在内存充足的情况下）。
  

缺点：
<ul>仅限等值连接：只能用于基于 = 的连接操作（例如 ON a.id = b.id）。对于大于、小于（>、