# Utils ## JoinHashMap - 映射 - Key: hash value （根据 join on 表达式计算） - Value：row index（第几行） - 例如： `1 -> [3,6,8]` ，表示第 3，6，8 行的 hash 值为 1 - Hash 值一样不意味着匹配，会进一步检查(equal_rows_arr) - 结构： - map: `RowTable<(u64, u64)>`，存储 （hash_value, row_index) - 相同hash值的话，存储最后插入的 row index - next: `Vec<u64>`, 冲突链，大小跟总共有多少行一样。 - row index 以 1 为起始，0 表示空。 - 写入冲突解决： - 当前 map 中 存储了 (h, i)，新插入第 j 行的 hash 值也是 h 的话 - `next[j] = i`, map 更新写入 (h, j) - 读取 h 的所有 row indices - 初始：读取 map 拿到 j, 然后读取 `next[j]` 得到 i - 循环：读取 `next[j]`得到下一个 row index，依次类推。直到读到 0 结束。 - 冲突链的下一个 row index 就在是`next[cur]` ## JoinHashMapType trait - **get_matched_indices** - iter：item是 (usize, u64) 即 (row_index，hash_value) - 返回值 - input_indices：针对每个 hash 匹配的 rows，返回对应的 input row index（自身） - match_indices：hash 匹配到的 row indices - 两个 indices 大小一样。 - 只是 hash 匹配，需要进一步检查是否 value 真正相等。 - **get_matched_indices_with_limit_offset** - 多了 limit 和 offset - 可以从 offset 作为起点，只匹配 limit 个 --------- # HashJoinExec ## Rust doc - 多 partition 并行 equi join - **Join 表达式**：根据 join.on 条件，如 `col1 = col2` - **Filter 表达式**：join 后可以应用 filters（可选地），无法下推到 inputs 的 Non-equality 谓词 - Build side & Probe side - 小的 input 应该放到 build side，来减小 hash table 的大小。 - 当前固定左边是 build side， 右边是 probe side - 执行步骤： 1. **build 阶段**：从 build side input 创建 hashtable，并将所有 record batches 拼成一个大的 batch - hash table 是一个 **LIFO** 的结构，让 row index 小的在上面，probe 时可以维持 build-side input 的顺序。row index 小最后插入到 hashtable 中。 2. **probe 阶段**：流式执行，检查 hashtable 是否存在匹配。 ---------