从链式哈希表到并发构建与向量化探针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/tidbHash 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/joinV1 实现在 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 侧的列可以被划分为三类连接键列若连接键被内联它最先被访问因为 Probe 时需要用其做连接键比较非等值条件使用的列在连接键比较之后才会用到其余所有列最后才被用来构造连接结果。由此row_data 中各列的实际顺序如下表所示有非等值条件无非等值条件连接键内联inlined连接键列 非等值条件列 其余列连接键列 其余列连接键未内联非等值条件列 其余列所有列保持原始顺序设计意图很清晰把探针阶段最可能提前短路判断的列放在最前面。连接键内联时若连接键不匹配可直接淘汰存在非等值条件时非等值条件列紧随连接键之后能在构造完整结果前先做条件过滤而构造最终连接结果所需的其余列总是放在最后。这样顺序访问 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 }MetatableMetatableMeta记录 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 去评估该条件。DatarowTableSegmentrowTableSegment用于保存行存数据本身设计原型为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.goheapObjectsCanMove检查保证对象在堆上时 GC 不会移动其地址行地址只指向rowTableSegment.rawData中的有效位置而rawData是被多 goroutine 共享、可能运行时扩容的切片这类切片永远分配在堆上。taggedPtr在保存行地址的同时还能把哈希值的一部分打进 tag 位配合 tagged_ptr.go 中的 tag 工具做快速预过滤——探针查表时若 tag 不匹配则可直接判定键必然不匹配跳过昂贵的键比较。链表则由每行头部的next_row_ptr字段串联插入时头插法把旧槽位值写进新行的 next 指针与行内存布局一节中的第一个区域完全对应。专门的数据结构单测 hash_table_v2_test.go 覆盖了容量计算、查找与并发插入等行为。哈希表构建预构建分区 并发构建的两阶段流水线设计文档把哈希表构建拆成两个阶段Pre-build 阶段接收数据对数据做物理分区并把数据从列存转换为行存。分区数设定为partition_num max(concurrency, 16)其隐含目的是让每个分区都能分到一块相对独立的子数据为后续并行建表提供粒度Build 阶段全部数据完成 pre-build 后把 rowTable 数据分派给各个 build 线程每个线程独立构建自己负责的目标哈希表子表。若 build 线程数多于分区数同一子表可能被多线程写入冲突通过CASCompare-And-Swap处理若 build 线程数不超过分区数则一个子表同一时刻只被一个线程写入天然无写冲突。在仓库实现中这一流程被清晰落地到 hash_join_v2.goSetupPartitionInfo/genHashJoinPartitionNumber/getPartitionMaskOffset负责把并发度换算成始终为 2 的幂的分区数并用哈希值的高位MSB做分区掩码偏移这样分区时同样可以用位运算快速完成见 hash_join_v2.go 分区相关函数initHashTableContext按并发数 × 分区数的网格初始化 rowTables并创建一个由partitionNumber个子表组成的hashTableV2pre-build 阶段每个 worker 持有自己的rowTableBuilder把从 BuildSideExec 拉到的 Chunk 按哈希值高位分派进对应分区并同时完成列转行见fetchAndBuildHashTableImpl中createRowTableBuilder的调用之后由mergeRowTablesToHashTable把各 worker 的分散 segment 汇聚成分区级 rowTable再通过buildTask通道把 segment 范围分派给 build 线程buildHashTable每个 build 线程循环消费任务并调用子表构建。关键的无锁/加锁策略在subTable上体现得尤为直接见 hash_table_v2.goupdateHashValue无锁版本直接读写槽位并用头插法setNextRowAddress串链表适用于该子表只属于当前构建线程的场景atomicUpdateHashValueCAS 版本通过atomic.LoadUintptratomic.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.goOneInt64连接键只含单个 Int64采用整数直接比较FixedSerializedKey连接键定长采用定长序列化键比较VariableSerializedKey连接键变长采用变长序列化键比较。对应地在 join_table_meta.go 中构建行布局元信息时会依据连接键类型自动判定 keyMode单 int64 → OneInt64键总长固定 → FixedSerializedKey否则 → VariableSerializedKeyisKeyMatchedbase_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() }这个接口的语义非常明确地覆盖了探针期两类完全不同的行为按块探测SetChunkForProbe对单个探测 Chunk 做探测前的预处理Probe完成实际探测并把结果写进result.chk并保证result.chk.NumRows() result.chk.RequiredRows()即受控的行数产出方便上层按批消费IsCurrentChunkProbeDone判断当前块是否已全部探完行表扫描部分连接类型如以左表为构建侧的 left outer join在把全部探测块处理完后还必须回扫构建侧行表把从未被匹配过的行作为结果补出。NeedScanRowTable声明是否需要、InitForScanRowTable做扫描前准备、ScanRowTable执行回扫、IsScanRowTableDone汇报完成状态。在仓库中探针实现按连接类型拆成了多个文件构成完整的探针族谱公共基类在 base_join_probe.go内含行匹配缓存、matchedRowsHeaders/serializedKeys等按逻辑行号索引的工作数组以及前面提到的 keyMode 与isKeyMatched逻辑其余各文件分别实现inner_join_probe.goinner join 探针outer_join_probe.goouter join含 left/right outer探针负责输出未匹配行的 null 扩展semi_join_probe.gosemi join 探针left_outer_semi_join_probe.goleft outer semi join 探针anti_semi_join_probe.goanti 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 目录中的文件整体执行器hash_join_v2.go —— 定义HashJoinV2Exec、ProbeSideTupleFetcherV2、ProbeWorkerV2、BuildWorkerV2以及分区设置SetupPartitionInfo、哈希表上下文初始化initHashTableContext、数据拉取与构建主流程fetchAndBuildHashTableImpl、mergeRowTablesToHashTable、buildHashTable与资源清理Close、initMaxSpillRound数据组织join_row_table.go、join_table_meta.go、row_table_builder.go —— 行存 segment、行布局元数据与接收→分区→列转行的 pre-build哈希表hash_table_v2.go、tagged_ptr.go —— 子表、容量预分配、无锁/CAS 插入、tag 快速过滤探针族base_join_probe.go 各类*_join_probe.go—— 按连接类型实现Probe接口内存与落盘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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考