数据库查询优化中的并行哈希连接（Parallel Hash Join）原理解析

一、并行哈希连接的基本概念
并行哈希连接是传统哈希连接算法在并行计算环境下的扩展，旨在通过多线程/多进程协作提升大表连接性能。其核心思想是将连接任务分解为多个子任务，利用并行计算资源同时处理。

二、传统哈希连接的局限性

1. 单线程瓶颈：传统哈希连接在单线程中执行建哈希表和探测两个阶段，无法利用多核CPU资源。
2. 内存限制：大表的哈希表可能超出单机内存，需借助磁盘交换，性能急剧下降。
3. 数据倾斜敏感：若连接键分布不均，单个线程可能处理大量数据，造成负载不平衡。

三、并行哈希连接的执行步骤

1. 数据分区阶段：

   • 每个并行工作线程读取输入表（如左表T1和右表T2）的一部分数据。
   • 对所有数据行根据连接键计算哈希值，并按哈希值范围分配到不同的分区（称为"桶"）。
   • 关键要求：相同连接键的数据必须分配到同一分区，确保连接正确性。

2. 并行建哈希表阶段：

   • 每个线程独立处理一个或多个分区，将较小的表（如T1）的分区数据构建为内存哈希表。
   • 例如：若线程P1负责分区1，则仅对T1中属于分区1的数据建哈希表。

3. 并行探测阶段：

   • 每个线程读取另一张表（如T2）的对应分区，并探测本线程持有的哈希表。
   • 例如：线程P1用T2的分区1数据探测T1分区1的哈希表，输出匹配结果。

4. 结果合并阶段：

   • 各线程生成的连接结果直接合并为最终结果集（无需排序或去重）。

四、并行优化的关键技术

1. 动态负载均衡：

   • 若某些分区数据量过大，调度器可将该分区的处理任务拆分给多个线程。
   • 例如：通过二次哈希将大分区细分为子分区，由多个线程协作处理。

2. 避免数据倾斜：

   • 采用混合哈希策略：对频繁出现的连接键（热点键）单独处理，防止单个线程过载。
   • 例如：将热点键分散到多个分区，或使用多级分区策略。

3. 内存管理：

   • 监控每个分区的内存使用，若哈希表过大则触发溢出到磁盘的机制。
   • 并行处理溢出文件，减少I/O阻塞。

五、示例说明
假设表T1（销售记录）和T2（产品信息）通过产品ID连接，使用4线程并行处理：

1. 线程1-4分别读取T1和T2的1/4数据，按产品ID的哈希值模4分配分区。
2. 线程1构建T1分区1的哈希表，同时线程2构建T1分区2的哈希表，以此类推。
3. 线程1用T2分区1的数据探测T1分区1的哈希表，其他线程同步处理对应分区。
4. 最终合并4个线程的结果输出。

六、适用场景与限制

• 适用：大表等值连接、分布式数据库、MPP架构。
• 限制：
  • 非等值连接（如范围连接）无法直接使用。
  • 需要额外开销管理并行任务协调和数据分发。
  • 数据倾斜严重时可能退化为单线程性能。