数据库查询优化中的并行嵌套循环连接（Parallel Nested Loop Join）优化技术

1. 问题描述
嵌套循环连接（Nested Loop Join, NLJ）是数据库中最基础的连接算法之一，适用于小表（驱动表）与大表（被驱动表）的连接操作。其传统实现为双重循环：外层循环遍历驱动表的每一行，内层循环遍历被驱动表并匹配连接条件。但当表数据量极大时，串行NLJ的性能可能成为瓶颈。并行嵌套循环连接通过将驱动表或内层扫描任务分配到多个CPU核心并行执行，以提升连接效率。

2. 串行NLJ的局限性

• 执行模式：

  for each row r1 in driver_table:  
      for each row r2 in driven_table:  
          if join_condition(r1, r2) is true:  
              output r1 and r2  
  

• 问题：
  • 若驱动表有M行，被驱动表有N行，时间复杂度为O(M×N)。
  • 内层循环需反复扫描被驱动表（若无索引则全表扫描），I/O和CPU压力集中。

3. 并行化思路
并行NLJ的核心思想是将外层循环或内层循环的任务拆分到多个工作进程（Worker）中，主要分为两种策略：

策略1：并行扫描驱动表（Partitioned Driver Table）

• 步骤：
  1. 将驱动表划分为K个分区（K为并行度），每个Worker处理一个分区。
  2. 每个Worker独立扫描分配给自己的驱动表分区，并对每一行执行内层循环（扫描被驱动表并匹配）。
  3. 所有Worker的输出结果合并为最终连接结果。
• 优势：
  • 驱动表的分区扫描可并行（如并行顺序扫描）。
  • 适合驱动表较大但可分区，且被驱动表有索引的场景。

策略2：并行化内层循环（Parallel Inner Scan）

• 步骤：
  1. 外层循环串行遍历驱动表的每一行。
  2. 对每一行，启动多个Worker并行扫描被驱动表的不同分区，协作完成匹配。
  3. 通过共享驱动表当前行数据，避免重复传输。
• 适用场景：
  • 驱动表很小（如过滤后仅少量行），但被驱动表极大且无索引。
  • 需解决内层全表扫描的并行化问题。

4. 关键技术细节

• 数据分布方式：

  • 轮询分布（Round-Robin）：驱动表行均匀分配到Worker。
  • 范围分区（Range Partitioning）：按驱动表的连接键分区，可能提升缓存命中率。
  • 哈希分布（Hash Partitioning）：按连接键哈希值分区，适用于后续并行哈希连接混合优化。

• 被驱动表的访问优化：

  • 若被驱动表有索引，每个Worker可独立利用索引加速匹配（如Index NLJ）。
  • 若无索引，需并行顺序扫描被驱动表，并通过块范围分配（Block Range Sampling）避免Worker重复扫描相同数据。

• 负载均衡：

  • 若驱动表数据分布倾斜，可能造成部分Worker空闲。动态任务分配（如动态分块）可缓解此问题。

5. 示例与执行计划
假设查询：

SELECT * FROM small_table s JOIN large_table l ON s.id = l.foreign_key;  

并行NLJ的执行计划可能显示为：

Parallel Nested Loop Join  
  ->  Parallel Seq Scan on small_table s  [驱动表并行扫描]  
  ->  Index Scan using idx_foreign_key on large_table l  [内层索引扫描]  

每个Worker执行流程：

1. 从驱动表的分区获取一行(s.id, ...)。
2. 使用s.id值检索被驱动表的索引idx_foreign_key，快速定位匹配行。
3. 输出连接结果。

6. 适用场景与限制

• 适用场景：
  • 驱动表过滤后数据量适中，可均匀分区。
  • 被驱动表有索引或可并行顺序扫描。
  • 系统CPU资源充足，无其他瓶颈（如I/O带宽不足）。
• 限制：
  • 若被驱动表无索引且无法并行扫描，内层循环可能成为瓶颈。
  • 数据倾斜时并行效率下降。
  • 线程同步和结果合并可能引入额外开销。

7. 总结
并行NLJ通过将串行双重循环任务分解到多个CPU核心，利用现代多核架构加速连接操作。其效果取决于数据分布、索引设计及资源分配策略。在实际数据库中（如PostgreSQL的并行计划），优化器会基于代价模型选择是否启用并行NLJ，并动态调整并行度以平衡开销与收益。