企业官网建设流程全解析

从链式哈希表到并发构建与向量化探针：TiDB Hash Join V2 重构设计全解

【免费下载链接】tidbTiDB is built for agentic workloads that grow unpredictably, with ACID guarantees and native support for transactions, analytics, and vector search. No data silos. No noisy neighbors. No infrastructure ceiling.项目地址: https://gitcode.com/GitHub_Trending/ti/tidb

Hash Join 是数据库最基础的连接算法，TiDB 自 1.0 起便支持 Hash Join，但随着构建侧变大、连接类型变复杂，旧实现（V1）在并发构建、探针接口抽象与代码可维护性上逐渐暴露出瓶颈。本文以 TiDB 设计文档 2024-05-11-hash-join-v2.md 为主体，系统拆解 Hash Join V2 的完整重构思路：Build 阶段如何从列存转换为精心设计的行存布局并支持多线程并发建表，Probe 阶段如何通过统一探针接口与向量化中间块评估实现各类连接的通用处理，并对照当前仓库中 pkg/executor/join 的 V2 实际实现给出源码级佐证。读完本文，你将掌握这套行式存储布局、链式哈希表、两阶段并行构建与可插拔探针接口的设计全貌，并能据此快速定位并阅读 TiDB 中对应的实现代码。

背景与动机：为何需要对 Hash Join 做一次彻底重构

Hash Join 的基本思想是把连接拆成两个阶段：Build（构建）阶段按连接键建立哈希表；Probe（探测）阶段用探测侧的连接键在哈希表中查找，再依据查找结果与连接类型生成连接结果。这个思路本身没有变，变的是实现质量。设计文档明确指出旧实现存在三方面短板：

• Build 阶段不支持并发构建：当构建侧（build side）数据量很大时，串行建表会成为明显瓶颈；
• Probe 阶段接口设计不佳：在部分场景下会引起冗余计算，对应问题可见仓库跟踪记录（原 issue 编号 47424）；
• 概念体系过度复杂：在常见的 left/right side、build/probe side 之外，旧实现还引入了 inner/outer side，以及useOuterToBuild、outerIsRight、tryToMatchInners、tryToMatchOuters等额外概念来处理由此产生的组合复杂度，导致代码难以理解，修 bug 时也更容易出错。

上述问题分别指向两个阶段的设计难点：Build 阶段的核心问题是哈希表设计、构建侧数据组织与哈希表并发构建；Probe 阶段的核心问题则是探测过程中的内存控制（尤其是连接键大量重复时）、各种连接类型对查找结果的处理，以及最终连接结果的生成。基于这些考量，TiDB 决定对 Hash Join 做一次完整重构，即 Hash Join V2。

在仓库中，旧实现与新实现确实以文件为单位共存于 pkg/executor/join：V1 实现在 hash_join_v1.go（约 1500+ 行），V2 实现在 hash_join_v2.go（同样约 1500+ 行），二者共享 hash_join_base.go 中的公共上下文结构（hashJoinCtxBase、hashjoinWorkerResult、probeSideTupleFetcherBase等），这印证了"完整重构、而非在旧代码上打补丁"的设计取向。

Build 阶段：从列存 Chunk 到精心编排的行存

Build 阶段最直观的问题来自数据组织方式的转换。TiDB 中 Build 侧的输入数据是列式存储的chunk.Chunk，而在 Build 阶段需要把列存转换成行存，以便把整行作为一个地址单元挂进哈希表、并在后续探针阶段只做一次指针跳转就能取到该行的全部所需列。

行式存储的内存布局

设计文档给出的行式存储内存布局如下：

|---------------------|-----------------|----------------------|-------------------------------| | | | | V V V V next_row_ptr null_map serialized_key/key_length row_data

从左到右四个区域的职责分别是：

• next_row_ptr：指向下一行的指针。用于哈希表构建——它让所有哈希值相同的行串成一个链表，这正是下文"链式哈希表"的载体；
• null_map：实际包含两部分——当前行每一列的 null 标志位（null_flag），以及用于right semi / outer join 的 used_flag。若需要 used_flag，它总是占据 null_map 的第一位；
• serialized_key / key_length（可选）：当连接键被内联（inlined）到 row_data 中、且键是变长类型时，该字段记录当前行的键长度；当连接键未内联时，该字段保存的是连接键的序列化表示，用于在 Probe 阶段做快速的连接键比较。该字段是可选的——对于可以内联进 row_data 且定长的连接键（例如单整数连接键），完全不需要它；
• row_data：当前行所有列的数据，整体为变长结构。定长元素（如 int64）直接保存，变长元素（如字符串相关类型）则先保存 size 再保存原始数据。

由于 row_data 变长，列数据只适合顺序访问，而不是随机下标访问。为此 row_data 内的列顺序必须精心设计，而不是沿用输入的原始顺序。

列的三分类与重排策略

Build 侧的列可以被划分为三类：

1. 连接键列：若连接键被内联，它最先被访问，因为 Probe 时需要用其做连接键比较；
2. 非等值条件使用的列：在连接键比较之后才会用到；
3. 其余所有列：最后才被用来构造连接结果。

由此，row_data 中各列的实际顺序如下表所示：

设计意图很清晰：把探针阶段最可能提前短路判断的列放在最前面。连接键内联时，若连接键不匹配可直接淘汰；存在非等值条件时，非等值条件列紧随连接键之后，能在构造完整结果前先做条件过滤；而构造最终连接结果所需的"其余列"总是放在最后。这样顺序访问 row_data 时，就能尽可能避免"取了一整行却只用上前几列"的浪费。

在仓库实现中，这套行布局元数据落在 join_table_meta.go，其维护的信息与设计文档一一对应：每列大小（-1 表示变长）、行内列顺序数组rowColumnsOrder、null_map 长度、行数据偏移量、used_flag 掩码，以及决定行内键编码方式与比较方式的keyMode；实际保存行数据的rowTableSegment定义在 join_row_table.go。

RowTable：行存数据的容器

RowTable 用来存放已完成列转行的数据，需要保存 meta 与 data 两部分信息。设计文档给出的结构原型为：

type rowTable struct { meta *tableMeta segments []*rowTableSegment }

Meta：tableMeta

tableMeta记录 Build 阶段所需的元信息，至少包括：

type TableMeta struct { // if the row has fixed length isFixedLength bool // the row length if the row is fixed length rowLength int // if the join keys has fixed length isJoinKeysFixedLength bool // the join keys length if it is fixed length joinKeysLength int // is the join key inlined in the row data isJoinKeysInlined bool // the length of null map, the null map include null bit for each column in the row and the used flag for right semi/outer join nullMapLength int // the column order in row layout, as described above, the save column order maybe different from the column order in build schema // for example, the build schema maybe [col1, col2, col3], and the column order in row maybe [col2, col1, col3], then this array // is [1, 0, 2] rowColumnsOrder []int // the column size of each column, -1 mean variable column, the order is the same as rowColumnsOrder columnsSize []int // the serialize mode for each key serializeModes []codec.SerializeMode // the first n columns in row is used for other condition, if a join has other condition, we only need to extract // first n columns from the RowTable to evaluate other condition columnCountNeededForOtherCondition int // total column numbers for build side chunk, this is used to construct the chunk if there is join other condition totalColumnNumber int // column index offset in null map, will be 1 when if there is usedFlag and 0 if there is no usedFlag colOffsetInNullMap int // keyMode is the key mode, it can be OneInt/FixedSerializedKey/VariableSerializedKey keyMode keyMode // offset to rowData, -1 for variable length, non-inlined key rowDataOffset int // the mask of usedFlag in nullmap usedFlagMask uint32 }

这些字段相互配合地回答了三个关键问题：这行是否定长（isFixedLength/rowLength，定长行可以极快地随机定位）；连接键是否被内联（isJoinKeysInlined与rowDataOffset，决定行数据里要不要留出键区、以及比较键时去哪个偏移取数）；null 位图与 used_flag 怎么布局（nullMapLength、colOffsetInNullMap、usedFlagMask）。columnCountNeededForOtherCondition与前面"列重排"相呼应——存在其他条件时，只需从 RowTable 中取出前 n 列即可构造 Chunk 去评估该条件。

Data：rowTableSegment

rowTableSegment用于保存行存数据本身，设计原型为：

type rowTableSegment struct { rawData []byte // the chunk of memory to save the row data hashValues []uint64 // the hash value of each rows rowLocations []unsafe.Pointer // the start address of each row validJoinKeyPos []int // the pos of rows that need to be inserted into hash table, used in hash table build }

四个字段各司其职：

• rawData：一段连续内存，按前面的行布局存放各行数据；
• hashValues：每行（连接键）的哈希值，预先算好保存，构建哈希表时直接复用，避免重复计算；
• rowLocations：每行起始地址，指向 rawData 内部，哈希表槽位最终存的就是这些地址；
• validJoinKeyPos：真正需要插入哈希表的行的位置集合。这里隐含一个重要细节——并非所有行都会进入哈希表：连接键为 NULL 的行对 inner/equality 类连接没有匹配价值，会被validJoinKeyPos过滤掉，从而减少哈希表体积与探针期无效比较。

采用分段（segment）而不是单个超大数组的原因在于内存管理：以若干段为单位追加数据，可以按段分配/释放、按段并行构建，也为后续 spill（落盘）按分区粒度回收内存提供了基础。仓库中 row_table_builder.go 承担了"接收 Chunk → 分区 → 列转行 → 写入 segment"这一 pre-build 的核心工作，并配套了 row_table_builder_test.go 与 join_row_table_test.go 做单元验证。

哈希表设计：容量预分配、无需存哈希值的链式哈希表

上图展示了 V2 哈希表的核心结构。设计文档明确指出：哈希表采用链式哈希表（chain hash table），并且在构建前就一次性扩容到所需大小，整个 Build 过程不再扩容。这一点带来一个非常实际的收益——既然槽位数固定、每个槽在构建期只增不改容量，哈希表中就无需保存哈希值相关信息，每个槽位只需保存行地址。

当前实现的 hash_table_v2.go 完整落实了这一设计：每个subTable对应一个分区（partition），内部是hashTable []taggedPtr槽位数组加posMask。槽位长度按nextPowerOfTwo(validKeyCount)取 2 的幂次并保证至少minimalHashTableLen（即 32，见 hash_join_v2.go 中常量定义），然后pos = hashValue & posMask即可完成取模定位——这是"2 的幂容量 + 位与代替取模"的经典优化。

值得展开的是槽位中存储的taggedPtr。Go 语言中把unsafe.Pointer存成整型再转回通常是不安全的，但此处是合法且有充分注释保证的特例，源码注释说明了两个前提（见 hash_table_v2.go）：

1. heapObjectsCanMove检查保证对象在堆上时 GC 不会移动其地址；
2. 行地址只指向rowTableSegment.rawData中的有效位置，而rawData是被多 goroutine 共享、可能运行时扩容的切片，这类切片永远分配在堆上。

taggedPtr在保存行地址的同时还能把哈希值的一部分打进 tag 位，配合 tagged_ptr.go 中的 tag 工具做快速预过滤——探针查表时若 tag 不匹配则可直接判定"键必然不匹配"，跳过昂贵的键比较。链表则由每行头部的next_row_ptr字段串联（插入时头插法，把旧槽位值写进新行的 next 指针），与"行内存布局"一节中的第一个区域完全对应。专门的数据结构单测 hash_table_v2_test.go 覆盖了容量计算、查找与并发插入等行为。

哈希表构建：预构建分区 + 并发构建的两阶段流水线

设计文档把哈希表构建拆成两个阶段：

1. Pre-build 阶段：接收数据，对数据做物理分区，并把数据从列存转换为行存。分区数设定为partition_num = max(concurrency, 16)，其隐含目的是让每个分区都能分到一块相对独立的子数据，为后续并行建表提供粒度；
2. Build 阶段：全部数据完成 pre-build 后，把 rowTable 数据分派给各个 build 线程，每个线程独立构建自己负责的目标哈希表（子表）。若 build 线程数多于分区数，同一子表可能被多线程写入，冲突通过CAS（Compare-And-Swap）处理；若 build 线程数不超过分区数，则一个子表同一时刻只被一个线程写入，天然无写冲突。

在仓库实现中，这一流程被清晰落地到 hash_join_v2.go：

• SetupPartitionInfo/genHashJoinPartitionNumber/getPartitionMaskOffset负责把并发度换算成始终为 2 的幂的分区数，并用哈希值的高位（MSB）做分区掩码偏移，这样分区时同样可以用位运算快速完成（见 hash_join_v2.go 分区相关函数）；
• initHashTableContext按"并发数 × 分区数"的网格初始化 rowTables，并创建一个由partitionNumber个子表组成的hashTableV2；
• pre-build 阶段每个 worker 持有自己的rowTableBuilder，把从 BuildSideExec 拉到的 Chunk 按哈希值高位分派进对应分区，并同时完成列转行（见fetchAndBuildHashTableImpl中createRowTableBuilder的调用）；
• 之后由mergeRowTablesToHashTable把各 worker 的分散 segment 汇聚成分区级 rowTable，再通过buildTask通道把 segment 范围分派给 build 线程（buildHashTable），每个 build 线程循环消费任务并调用子表构建。

关键的无锁/加锁策略在subTable上体现得尤为直接（见 hash_table_v2.go）：

• updateHashValue：无锁版本，直接读写槽位并用头插法setNextRowAddress串链表，适用于"该子表只属于当前构建线程"的场景；
• atomicUpdateHashValue：CAS 版本，通过atomic.LoadUintptr+atomic.CompareAndSwapUintptr循环重试完成插入，适用于"多线程争抢同一子表"的场景；
• subTable.build(startSegmentIndex, endSegmentIndex)：当构建范围恰好覆盖子表的全部 segment 时走无锁路径，否则走 CAS 路径——正好对应文档中"线程数少于/多于分区数"的两种情形。

整体流程可用下面这张图概括：

从图中可以直观看到：输入数据流先被多个 pre-build 并行处理单元切分（"..."表示分区远多于图中示意数量），经sync && dispatch partitioned data同步汇聚后，再把各分区的构建任务分派给多个 build 处理单元并行建表。此外，仓库中还配套了内存与落盘管理：hashTableContext使用独立的memory.Tracker统计哈希表内存，partitionNumber > 1024时直接限制最大 spill 轮数为 1，相关逻辑位于 hash_join_v2.go 的initMaxSpillRound与 hash_join_spill.go。这说明 V2 的并行构建并不以牺牲内存可控性为代价，构建到一半发现内存超限时，可以按分区粒度暂停、落盘并继续。

Probe 阶段：查表、键比较与中间连接块的向量化

哈希表查找与连接键比较

哈希表查找：算出连接键的哈希值后，直接用hashValue & posMask定位目标子表槽位即可完成查找（见subTable.lookup）。由于容量预分配且无需扩容，lookup 路径上不存在重哈希、搬迁等额外开销，是一条非常"直"的快速路径；tag 预过滤还能在进入链表遍历前淘汰大部分不匹配情形。

连接键比较：链式哈希表查到的只是"候选行"，仍需做连接键比较。Build 侧的连接键已经内联在行里（或按行内序列化布局存放），Probe 侧则把连接键序列化到一个字节缓冲区。常规做法是内存比较（memory compare）；但对于简单情形可以优化为更专用的比较——例如连接键是单个整数时，直接用整数比较而非逐字节比较。

当前实现将键的形态收敛为三种keyMode（定义于 base_join_probe.go）：

• OneInt64：连接键只含单个 Int64，采用整数直接比较；
• FixedSerializedKey：连接键定长，采用定长序列化键比较；
• VariableSerializedKey：连接键变长，采用变长序列化键比较。

对应地在 join_table_meta.go 中，构建行布局元信息时会依据连接键类型自动判定 keyMode（单 int64 → OneInt64，键总长固定 → FixedSerializedKey，否则 → VariableSerializedKey），isKeyMatched（base_join_probe.go）再按 keyMode 分派比较逻辑。这一层抽象正是文档所说"简单情形用专用比较替代 memcmp"的实现载体。

Joined block 生成与非等值条件的向量化评估

连接键比较通过后，需要把探测侧列与构建侧列拼成一个"连接块（joined block）"。这里的精妙之处在于分两种情况：

• 没有其他非等值条件的连接：joined block 就是最终连接结果，直接输出；
• 存在非等值条件的连接：joined block 只是一个中间结果，先基于它评估非等值条件，再生成最终结果。通过先产生中间 joined block，非等值条件可以进入向量化（vector）模式求值——既更快，也更容易支持复杂的非等值条件。

为了避免白造中间列，构造 joined block 时遵循最少列原则：

• 对 Probe 侧：只构造非等值条件用到的列；
• 对 Build 侧：
  • 若连接键未内联：只构造非等值条件用到的列；
  • 若连接键已内联：构造连接键列 + 非等值条件用到的列（因为键列就近在行首，顺带取出几乎零成本，且可能被条件本身引用）。

这与此前"列三分类与重排"的策略一脉相承：在 row_data 层面靠列序让顺序访问最少浪费，在 joined block 层面靠最少列让向量化求值最少浪费。

统一的 Probe 接口

为了甩掉旧实现 inner/outer 与tryToMatchInners/tryToMatchOuters等冗余概念，V2 把各类连接（inner、outer、semi、anti-semi、left/right outer 等）在探针期的差异收敛到一个接口后面。设计文档给出的接口原型为：

type JoinProbe interface { // SetChunkForProbe will do some pre-work when start probing a chunk SetChunkForProbe(chunk *chunk.Chunk) error // Probe is to probe current chunk, the result chunk is set in result.chk, and Probe need to make sure result.chk.NumRows() <= result.chk.RequiredRows() Probe(joinResult *hashjoinWorkerResult, sqlKiller sqlkiller.SQLKiller) (ok bool, result *hashjoinWorkerResult) // IsCurrentChunkProbeDone returns true if current probe chunk is all probed IsCurrentChunkProbeDone() bool // ScanRowTable is called after all the probe chunks are probed. It is used in some special joins, like left outer join with left side to build, after all // the probe side chunks are handled, it needs to scan the row table to return the un-matched rows ScanRowTable(joinResult *hashjoinWorkerResult, sqlKiller sqlkiller.SQLKiller) (result *hashjoinWorkerResult) // IsScanRowTableDone returns true after scan row table is done IsScanRowTableDone() bool // NeedScanRowTable returns true if current join need to scan row table after all the probe side chunks are handled NeedScanRowTable() bool // InitForScanRowTable do some pre-work before ScanRowTable, it must be called before ScanRowTable InitForScanRowTable() }

这个接口的语义非常明确地覆盖了探针期两类完全不同的行为：

1. 按块探测：SetChunkForProbe对单个探测 Chunk 做探测前的预处理，Probe完成实际探测并把结果写进result.chk，并保证result.chk.NumRows() <= result.chk.RequiredRows()（即受控的行数产出，方便上层按批消费），IsCurrentChunkProbeDone判断当前块是否已全部探完；
2. 行表扫描：部分连接类型（如"以左表为构建侧的 left outer join"）在把全部探测块处理完后，还必须回扫构建侧行表，把从未被匹配过的行作为结果补出。NeedScanRowTable声明是否需要、InitForScanRowTable做扫描前准备、ScanRowTable执行回扫、IsScanRowTableDone汇报完成状态。

在仓库中，探针实现按连接类型拆成了多个文件，构成完整的探针族谱：公共基类在 base_join_probe.go（内含行匹配缓存、matchedRowsHeaders/serializedKeys等按逻辑行号索引的工作数组，以及前面提到的 keyMode 与isKeyMatched逻辑），其余各文件分别实现：

• inner_join_probe.go：inner join 探针；
• outer_join_probe.go：outer join（含 left/right outer）探针，负责输出未匹配行的 null 扩展；
• semi_join_probe.go：semi join 探针；
• left_outer_semi_join_probe.go：left outer semi join 探针；
• anti_semi_join_probe.go：anti semi join 探针。

每一类探针都配有对应的*_test.go单测文件（如 inner_join_probe_test.go、right_outer_join_probe_test.go、left_outer_semi_join_probe_test.go），覆盖了与 null、used_flag、结果行数控制相关的边界行为。

Probe 阶段的整体流程

如上图所示，Probe 是一个迭代式的块处理循环：读取一个探测块 → 判断输入是否结束（结束则进入"回扫行表输出结果"分支并收尾）→ 探测哈希表 → 比较连接键并生成 joined block → 判断是否存在其他条件（存在则向量化评估后生成最终结果，否则直接输出）→ 判断当前块是否处理完毕，未完毕则读取下一块继续。整个过程与JoinProbe接口的生命周期完全对应：块级方法负责循环体，ScanRowTable系列方法负责收尾分支。

整个探针期间还贯穿了内存与执行安全控制：探针上下文（HashJoinCtxV2等）通过memTracker/diskTracker跟踪资源，Probe/ScanRowTable接口签名中携带sqlKiller用于在 SQL 被 kill 或超时时及时中止，相关基础上下文定义在 hash_join_base.go 与 hash_join_stats.go（后者还记录 probe/build 各阶段的耗时统计，供诊断与调优）。

从提案到代码：如何在仓库中研读 Hash Join V2

设计文档本质是一份提案（proposal），而仓库代码是它演进后的最终形态。若你想结合源码深入研读，建议按以下顺序阅读 pkg/executor/join 目录中的文件：

1. 整体执行器：hash_join_v2.go —— 定义HashJoinV2Exec、ProbeSideTupleFetcherV2、ProbeWorkerV2、BuildWorkerV2，以及分区设置（SetupPartitionInfo）、哈希表上下文初始化（initHashTableContext）、数据拉取与构建主流程（fetchAndBuildHashTableImpl、mergeRowTablesToHashTable、buildHashTable）与资源清理（Close、initMaxSpillRound）；
2. 数据组织：join_row_table.go、join_table_meta.go、row_table_builder.go —— 行存 segment、行布局元数据与"接收→分区→列转行"的 pre-build；
3. 哈希表：hash_table_v2.go、tagged_ptr.go —— 子表、容量预分配、无锁/CAS 插入、tag 快速过滤；
4. 探针族：base_join_probe.go + 各类*_join_probe.go—— 按连接类型实现Probe接口；
5. 内存与落盘：hash_join_spill.go、hash_join_stats.go —— spill 触发、分区粒度内存回收与阶段耗时统计。

阅读时可以对照各文件配套的*_test.go（尤其是 hash_table_v2_test.go 与各探针测试），用单测中的构造输入来反推每一步的内存布局期望，往往比直接读代码更快建立直觉。

需要说明的是，提案中的若干表述在落地过程中会依据工程约束做微调：例如文档以partition_num = max(concurrency, 16)描述分区数量级，而当前实现通过genHashJoinPartitionNumber将分区数规整为不超过 16 的 2 的幂并配合posMask位运算；又如文档中keyMode的取值名是 OneInt/FixedSerializedKey/VariableSerializedKey，而实际代码定义为OneInt64/FixedSerializedKey/VariableSerializedKey（见 base_join_probe.go 的常量定义）。因此在以提案为纲的同时，应以 pkg/executor/join 当前代码为最终事实来源。

小结

Hash Join V2 的核心贡献可以浓缩为三句话：以精心编排的行式存储解决数据组织问题，以容量预分配的链式哈希表配合无锁/CAS 双路径解决并发构建问题，以统一探针接口 + 向量化中间连接块解决各类连接的通用处理问题。它一方面用"内联/非内联 + 列重排"消灭了探针期对行数据的随机访问与冗余取列，另一方面把 V1 中纠缠不清的 inner/outer 概念收敛为边界清晰的 build/probe 两阶段抽象，使新增连接类型只需实现一个探针接口即可接入。理解这份设计，不仅能帮你读懂 pkg/executor/join 中超过 7000 行的高性能连接实现，也能为你在其他数据库/计算引擎中设计 join 算子提供一份可直接借鉴的参考蓝本。

【免费下载链接】tidbTiDB is built for agentic workloads that grow unpredictably, with ACID guarantees and native support for transactions, analytics, and vector search. No data silos. No noisy neighbors. No infrastructure ceiling.项目地址: https://gitcode.com/GitHub_Trending/ti/tidb