DS7.1 Join operator

type

status

date

slug

summary

`SNLJIterator`

实现 Simple Nested Loop Join（SNLJ） 时的核心组件 —— SNLJIterator。它负责执行一个 朴素双层循环连接（Nested Loop Join），其中：

外层是左表（left）：每次从左表拿一条 leftRecord；

内层是右表（right）：右表每次都被从头遍历，尝试与当前左表记录匹配；

若匹配成功（compare(...) == 0），就 concat 连接成一个新记录返回。

核心设计理念（火山模型中的 Pull 模式）

在 Volcano Model 中，每次上层算子调用 .next()，SNLJIterator 就“懒惰地”去匹配下一个可连接的 Record。

方法逐步分析

1. 构造函数 SNLJIterator()

初始化左表和右表的迭代器；

右表使用 BacktrackingIterator，以便每次重新从头开始扫描；

rightSourceIterator.markNext() 设定了“开头重置点”。

2. fetchNextRecord()：连接逻辑的精华

这段逻辑其实就是：

在 fetchNextRecord() 中以“惰性”方式实现了双层嵌套循环。

3. hasNext() / next() 实现

典型的 Lazy Iterator 写法；

.next() 调用 .hasNext() 保证提前取好下一个值，且只取一次。

细节亮点

技术点	说明
`BacktrackingIterator.reset()`	用于让右表“回到开头”
`leftRecord` 维护状态	避免重复从左表读入
惰性加载	只有调用 `.next()` 才会去拉一条新的连接结果

示例运行逻辑（假设匹配条件为 `left.c == right.c`）

假设：

左表 left = [1, 2]

右表 right = [1, 2, 3]

运行过程：

总结：SNLJIterator 特点

特性	说明
简洁	遵循经典嵌套连接结构
惰性执行	符合 Volcano 模型
使用 reset()	避免重新创建迭代器，提升效率
易扩展	替换 `compare()` 可实现不同连接条件

`BNLJIterator`

Block Nested Loop Join 的执行逻辑

核心思想：

用 内存中 B-2 页 存左表 block（block of records）；

每次右表只读入一页；

对左块和右页做双层循环，进行连接；

若右表所有页都扫完，再读下一左块，重置右表。

1. `fetchNextLeftBlock()`

从 leftSourceIterator 中读出至多 B-2 页，设置成 leftBlockIterator，并初始化 leftRecord。

2. `fetchNextRightPage()`

从 rightSourceIterator 中抓取下一页的记录，设置为 rightPageIterator。

3. `fetchNextRecord()`

这是 核心三层循环 的模拟：

我们必须维护：leftBlockIterator, rightPageIterator, leftRecord

总结：BNLJIterator 中变量控制含义

变量	作用
`leftSourceIterator`	整个左表的 record 流（外部流）
`leftBlockIterator`	当前左表块中的 records
`rightSourceIterator`	整个右表（reset 后复用）
`rightPageIterator`	当前右表页中的 records
`leftRecord`	当前左表块中的某条记录
`nextRecord`	暂存返回值，供 `hasNext()` 使用

`SHJOperator`（Simple Hash Join Operator）

类作用概述：Simple Hash Join

SHJOperator 是数据库中一种高效的连接算法，适用于在内存足够的情况下将一侧数据加载到 hash table 中，然后用另一侧来 probe（探测）。

它的前提：左表某一分区的记录必须能放进 B-2 页内存，如果不能放入，就会 throw IllegalArgumentException

执行流程一览

1. `iterator()` → 执行 join：

2. `backtrackingIterator()`：

创建一个空的 Run joinedRecords

调用 run(left, right, pass = 1)

返回连接后的结果迭代器

关键阶段拆解

1. `partition(...)`：哈希分区（只对 leftRecords）

使用 HashFunc.hashDataBox(columnValue, pass) 计算哈希值

然后做 mod partitionNum 取分区编号

每个分区对应一个 Partition 对象（磁盘管理）

📌 注意：

这里只分 left 表！

right 是不分区的，在每个 build 阶段重复使用

2. `buildAndProbe(...)`：构建 hash 表并探测匹配记录

Build 阶段：

Probe 阶段：

注意：

所有中间结果都存入 joinedRecords；

left 被加载进 hash table，right 只需遍历一次；

有 B-2 页内存限制！

3. `createPartitions()`：

根据可用内存页数（B-1）创建多个 Partition 对象（B-1 分区），预备存储哈希桶。

`estimateIOCost()` 特别之处

意图明确：

告诉优化器 不要选择 SHJ，除非它是唯一选项；

因为 SHJ 可能会因分区过大直接 fail；

总结结构图（执行流程）

可能扩展点 / 提示

方向	建议
💥 容错策略	当前失败直接抛异常 → 可以考虑 fallback 到 recursive GHJ（多次分区）
📉 IO 估算优化	可以估算实际读写页数（left + right + join output）而非 Integer.MAX_VALUE
🧪 测试建议	多测 hash 冲突、负 hash 值、极端分布等情况
✏️ 更复杂的 GHJ	支持左右两表都分区 + 多轮递归 partition

SNLJIterator