TiDB三类JOIN算法原理与实战选型指南

1. 为什么“join方式选错”会让TiDB查询慢得像在等泡面？

我第一次在某电商后台系统里看到一个报表SQL跑出17秒响应时，第一反应是查执行计划——结果发现EXPLAIN ANALYZE输出里赫然写着HashJoin，但右表扫描行数高达2300万，而左表才不到5000行。更诡异的是，这个SQL在MySQL上跑得飞快，换到TiDB集群后却成了性能瓶颈。当时团队里有位老同事直接说：“别调参数了，先看看join是不是选错了。”这句话让我记了三年。

这就是TiDB SQL优化里最隐蔽、也最容易被忽视的深水区：join方式不是数据库自动“猜对”的，而是你用SQL写法、索引设计、统计信息质量、甚至数据分布特征共同“投票”决定的。TiDB支持三种物理join算法：HashJoin、IndexJoin和MergeJoin，它们不是并列选项，而是存在明确的适用边界和成本博弈关系。一旦选错，轻则多扫几百万行，重则触发大量网络Shuffle、OOM Killer介入、甚至拖垮整个TiKV节点。

很多人误以为“加了索引就万事大吉”，但我在某金融风控系统的压测中亲眼见过：给右表加了覆盖索引，IndexJoin确实被选中了，可因为左表驱动列的值分布极度倾斜（95%的请求都查同一个用户ID），导致单个TiKV Region被反复高频访问，QPS没上去，P99延迟反而翻了4倍。这说明——join方式的选择，本质是数据访问模式、计算资源分配、网络IO开销三者之间的动态权衡。

你不需要背熟所有算法源码，但必须建立一套可验证的判断链路：

• 第一步，看执行计划里实际用了哪种join；
• 第二步，确认它是否符合该算法的理想前提（比如HashJoin要求小表能全量载入内存）；
• 第三步，反向验证：如果强制换一种join，代价是否真会更高？

这不是玄学，而是可以通过EXPLAIN FORMAT = 'VERBOSE'、SHOW STATS_HISTOGRAMS、甚至手动SELECT COUNT(*) GROUP BY探查数据分布来实证的。接下来，我们就从这三类join的底层行为讲起，不讲理论，只讲你在TiDB控制台上敲命令时，真正需要盯住的那几个数字。

2. HashJoin：不是“小表驱动大表”，而是“内存够不够塞下小表”

很多资料把HashJoin简单总结为“小表驱动大表”，这是对TiDB实现机制的重大误解。TiDB的HashJoin是Build-Side必须完全加载进内存构建哈希表，Probe-Side逐行探测。关键不在“小”，而在“能否一次性装下”。

2.1 内存阈值与实际占用的差距

TiDB默认tidb_mem_quota_query = 32GB，但HashJoin实际可用内存受两个硬约束：

1. 单个TiDB实例的全局内存池限制：由tidb_server_memory_limit控制（默认无限制，但生产环境建议设为物理内存的70%）；
2. 单个HashJoin算子的局部内存上限：由tidb_hash_join_concurrency×tidb_mem_quota_query共同决定，但更关键的是tidb_hash_join_concurrency默认值仅为5——这意味着即使你有32GB内存配额，TiDB最多只允许5个并发HashJoin任务，每个任务分到的内存远低于理论值。

我在某物流调度系统中遇到过真实案例：右表（运单明细）约800万行，单行平均120字节，理论哈希表大小≈800万×120B≈960MB。看起来远低于32GB，但执行时频繁OOM。排查发现：

• EXPLAIN FORMAT = 'VERBOSE'显示HashJoin的build_side_concurrency: 5，即5个goroutine并行构建哈希表；
• 每个goroutine需独立维护哈希桶、溢出链表、内存管理元数据，实测单goroutine内存开销达理论值的2.3倍；
• 当5个goroutine同时运行，峰值内存达960MB×2.3×5≈11GB，叠加其他算子，瞬间突破TiDB实例内存上限。

提示：不要依赖EXPLAIN里“Estimated Memory Usage”字段，那是基于统计信息的粗略估算。真实内存压力必须通过SHOW PROCESSLIST观察Mem列，或在Prometheus中监控tidb_server_memory_usage_bytes指标。

2.2 小表≠驱动表：当“小”只是假象

另一个常见陷阱是误判“小表”。TiDB的“小”指Build-Side在Apply Filter后剩余的行数足够小，而非原始表大小。

例如这条SQL：

SELECT /*+ HASH_JOIN(t1, t2) */ * FROM orders t1 JOIN order_items t2 ON t1.order_id = t2.order_id WHERE t1.status = 'shipped' AND t2.created_at > '2024-01-01';

表面看orders表（千万级）比order_items（亿级）小，但WHERE t1.status = 'shipped'可能只过滤出5%订单（50万行），而t2.created_at > '2024-01-01'可能过滤出30%明细（3000万行）。此时若强制HASH_JOIN(t1, t2)，Build-Side是50万行的orders，内存可控；但若TiDB因统计信息陈旧误判t1.status = 'shipped'命中率高达80%，就会错误选择t2为Build-Side，导致3000万行进内存——灾难就此开始。

验证方法很简单：

-- 查看t1在过滤条件下的实际行数 EXPLAIN SELECT * FROM orders WHERE status = 'shipped'; -- 查看t2在过滤条件下的实际行数 EXPLAIN SELECT * FROM order_items WHERE created_at > '2024-01-01';

对比rows列数值，谁小谁该做Build-Side。如果两者接近（比如都在100万~500万行），优先考虑IndexJoin或MergeJoin，避免内存风险。

2.3 HashJoin的隐藏杀手：数据倾斜

即使Build-Side总行数达标，若JOIN KEY存在严重倾斜，HashJoin性能仍会断崖下跌。TiDB的哈希函数无法规避热点Key，所有匹配该Key的Probe行都会打到同一个哈希桶，形成单goroutine瓶颈。

典型场景：

• 用user_id关联用户表和行为日志表，但user_id = 0（匿名用户）占日志表70%；
• 用tenant_id关联租户配置表和业务表，但tenant_id = 1（系统租户）数据量是其他租户总和的10倍。

检测方法：

-- 找出top 10热点join key SELECT order_id, COUNT(*) c FROM order_items GROUP BY order_id ORDER BY c DESC LIMIT 10;

如果第一行计数超过第二行10倍以上，且该Key在Build-Side也存在，HashJoin大概率会卡顿。此时必须改用IndexJoin（利用索引B+树的有序性分散访问）或添加/*+ USE_INDEX(t2, idx_order_id) */提示强制走索引。

3. IndexJoin：不是“有索引就能用”，而是“索引能否支撑嵌套循环”

IndexJoin常被称作“嵌套循环连接”，但TiDB的实现远比传统数据库精细。它的核心价值在于将Probe-Side的每行，转化为对Build-Side索引的点查或范围查，从而规避全表扫描，但前提是索引设计必须精准匹配访问模式。

3.1 索引覆盖度：为什么“联合索引顺序”决定生死

假设我们有如下SQL：

SELECT t1.name, t2.amount FROM users t1 JOIN payments t2 ON t1.user_id = t2.user_id WHERE t1.city = 'beijing' AND t2.status = 'success';

要让IndexJoin生效，Build-Side（payments表）的索引必须满足：

• 第一列必须是JOIN KEY（user_id）：这是嵌套循环的驱动基础，TiDB需要根据t1.user_id值快速定位t2中对应记录；
• 后续列应覆盖WHERE条件（status）和SELECT字段（amount）：避免回表。

因此，最优索引是：

ALTER TABLE payments ADD INDEX idx_user_status_amount (user_id, status, amount);

注意：user_id必须在最左，status次之（用于过滤），amount最后（用于覆盖查询）。如果建成了idx_status_user_amount (status, user_id, amount)，TiDB将完全无法使用该索引进行IndexJoin，因为status无法作为Probe的输入值。

我在某SaaS平台优化时踩过这个坑：原索引是(status, user_id)，EXPLAIN显示IndexJoin未被选用，执行计划退化为HashJoin。重建索引为(user_id, status)后，IndexJoin立即生效，查询耗时从8.2秒降至0.35秒——提升23倍。根本原因在于：IndexJoin的Probe过程是“对t1的每一行，用t1.user_id去t2索引中查找”，索引最左列不匹配，查找就无从谈起。

3.2 驱动表选择：为什么左表不一定是驱动表

TiDB的IndexJoin默认以左表为Probe-Side（驱动表），但可通过STRAIGHT_JOIN或/*+ TIDB_INLJ(t2) */提示强制指定Build-Side。这在驱动表数据量大但过滤性强时至关重要。

例如：

SELECT /*+ TIDB_INLJ(t2) */ t1.*, t2.log_time FROM big_log_table t1 JOIN small_config_table t2 ON t1.config_id = t2.id WHERE t1.event_type = 'login' AND t1.created_at > '2024-05-01';

big_log_table虽是左表，但WHERE条件过滤后仅剩2000行；small_config_table虽小，但无有效过滤条件。若按默认逻辑，TiDB会尝试用2000行big_log_table去驱动small_config_table，看似合理。但问题在于：small_config_table的id索引是主键，B+树高度为2，每次点查IO成本极低；而big_log_table的event_type和created_at组合索引，若未包含config_id，则2000次Probe需2000次回表，总IO飙升。

此时强制TIDB_INLJ(t2)，让small_config_table成为Build-Side，TiDB会：

• 先全量扫描small_config_table（假设1000行），构建内存中的“配置ID→配置内容”映射；
• 再对big_log_table过滤后的2000行，直接查内存映射，零IO完成关联。

实测耗时从1.8秒降至0.09秒。关键洞察：当Build-Side极小（<1万行）且Probe-Side过滤后仍较大时，内存映射比索引点查更高效。

3.3 IndexJoin的临界点：何时该放弃？

IndexJoin并非万能。当Probe-Side过滤后行数超过一定阈值，其“N次点查”的累积开销会超过HashJoin的一次哈希构建。这个阈值没有固定值，取决于：

• Build-Side索引的B+树高度（高度越低越好）；
• Probe-Side行数与Build-Side总行数的比例；
• 网络延迟（跨TiKV节点时，每次点查都有RTT开销）。

经验法则：

• 若Probe-Side行数 < 1000，且Build-Side有合适索引，IndexJoin几乎总是最优；
• 若Probe-Side行数在1000~10000，需实测对比；
• 若Probe-Side行数 > 10000，且Build-Side行数 > 10万，IndexJoin大概率不如HashJoin或MergeJoin。

验证方法：

-- 强制使用IndexJoin并计时 SELECT /*+ TIDB_INLJ(t2) */ ... FROM t1 JOIN t2 ON ...; -- 强制使用HashJoin并计时 SELECT /*+ HASH_JOIN(t1, t2) */ ... FROM t1 JOIN t2 ON ...; -- 对比执行时间与`EXPLAIN ANALYZE`中的`execution info`

重点关注execution info里的probe time（Probe总耗时）和build time（Build总耗时），而非单纯看total time。

4. MergeJoin：不是“排序就行”，而是“双流有序性的精密对齐”

MergeJoin是TiDB中最易被低估的算法。它要求Probe-Side和Build-Side都按JOIN KEY严格升序排列，然后像归并排序一样双指针扫描。优势是零内存占用、零随机IO、线性时间复杂度；劣势是对数据序有强依赖，且一旦序乱，代价极高。

4.1 排序来源：索引 vs Sort算子，成本天壤之别

MergeJoin的排序可以来自两种途径：

• 天然有序：表按JOIN KEY聚簇（如PRIMARY KEY(user_id)），或存在INDEX(user_id)且查询能利用该索引扫描；
• 显式排序：TiDB执行Sort算子对数据重排。

二者成本差异巨大。以users表（主键id）和orders表（索引idx_user_id(user_id)）为例：

• 若SQL为SELECT * FROM users u JOIN orders o ON u.id = o.user_id，users按id升序扫描天然有序，orders可走idx_user_id升序扫描，MergeJoin零额外成本；
• 若SQL为SELECT * FROM users u JOIN orders o ON u.id = o.user_id ORDER BY u.name，TiDB必须对users按name排序，破坏了id的天然序，MergeJoin失效，退化为HashJoin。

我在某教育平台优化课表查询时发现：原SQL带ORDER BY class_name，EXPLAIN显示MergeJoin未被选用。去掉ORDER BY后，MergeJoin立即生效，耗时从3.1秒降至0.42秒。根本原因：ORDER BY触发了Sort算子，使Probe-Side失去有序性。

注意：MergeJoin对ORDER BY极其敏感。即使ORDER BY字段与JOIN KEY无关，只要它导致TiDB无法保证JOIN KEY的扫描序，MergeJoin就会被排除。

4.2 数据分布陷阱：为什么“部分有序”比“完全无序”更危险

最危险的情况是数据在物理上部分有序，但统计信息未反映此特征。TiDB的统计信息（ANALYZE TABLE）默认采样率100%，但对超大表会降为10%或更低。若采样恰好错过有序段，TiDB会误判数据“无序”，拒绝MergeJoin。

例如：orders表按order_id递增写入，理论上idx_user_id是近似有序的（新订单集中在少数用户）。但ANALYZE TABLE orders采样时只扫了老数据，统计信息显示user_id分布均匀，TiDB便认为idx_user_id扫描无法保证升序，弃用MergeJoin。

解决方案：

• 对写入模式已知的表，手动指定高采样率：ANALYZE TABLE orders WITH 20000000 ROWS；
• 或强制提示：SELECT /*+ MERGE_JOIN(t1, t2) */ ...，但需确保EXPLAIN中sort算子消失，否则提示无效。

验证MergeJoin是否真正生效，不能只看EXPLAIN类型，更要检查：

• EXPLAIN FORMAT = 'VERBOSE'中merge_join的left_sort_key和right_sort_key是否非空；
• EXPLAIN ANALYZE中execution info是否有sort time字段（有则说明走了Sort，非真·MergeJoin）。

4.3 MergeJoin的杀手锏：处理超大数据集

当Probe-Side和Build-Side都超千万行时，MergeJoin往往是唯一可行方案。HashJoin内存爆炸，IndexJoinN次点查IO雪崩，而MergeJoin只需常量内存，且能充分利用TiKV的Range Scan能力。

典型案例：某广告系统需关联10亿级曝光日志与5000万级用户画像。

• HashJoin：Build-Side 5000万行，内存需求超100GB，TiDB直接OOM；
• IndexJoin：Probe-Side 10亿行，即使10%命中率也有1亿次点查，网络IO彻底打满；
• MergeJoin：两表均按user_id排序，TiDB启动双流Scan，内存占用<500MB，耗时稳定在22秒。

实现关键：

• exposure_log表必须有INDEX(user_id)，且写入时按user_id分片（TiDB默认按PK分片，需确认PK是否为user_id或含user_id）；
• user_profile表主键为user_id，天然聚簇有序；
• SQL中避免任何破坏user_id序的操作（如GROUP BY、DISTINCT、非user_id的ORDER BY）。

5. 实战决策树：从执行计划到最终优化的完整闭环

纸上谈兵终觉浅。我把过去三年在数十个TiDB生产环境积累的join优化流程，浓缩成一张可直接执行的决策树。它不依赖“感觉”，每一步都有命令验证，每一个分支都有明确退出条件。

5.1 第一步：捕获真实执行计划（不是EXPLAIN，是EXPLAIN ANALYZE）

永远不要用EXPLAIN代替EXPLAIN ANALYZE。前者是预估，后者是实测。尤其在join场景，预估行数误差常达10倍以上。

操作步骤：

1. 在业务低峰期，对慢SQL执行：

   EXPLAIN ANALYZE FORMAT = 'VERBOSE' SELECT /* your sql here */;

2. 重点提取三组数据：
   • join_type:HashJoin/IndexJoin/MergeJoin/LeftHashJoin等；
   • rows_read: Probe-Side和Build-Side各自扫描的行数；
   • execution info:build time,probe time,sort time,mem_max等。

提示：若EXPLAIN ANALYZE耗时过长（>30秒），先用EXPLAIN快速看join_type和rows，再针对性加/*+ ... */提示测试。

5.2 第二步：诊断当前join方式是否合理（三问法）

对execution info中的join_type，连续问三个问题：

Q1：Build-Side行数是否在安全阈值内？

• HashJoin: Build-Siderows_read< 500万行（内存保守估计）；
• IndexJoin: Probe-Siderows_read< 1万行（避免点查风暴）；
• MergeJoin: 双方rows_read无绝对上限，但需确认sort time为0。

Q2：索引是否被正确利用？

• IndexJoin: Build-Side的index列是否显示实际使用的索引名？若为PRIMARY或NULL，说明索引未命中；
• MergeJoin:left_sort_key/right_sort_key是否为user_id等JOIN KEY？若为<unknown>，说明序丢失。

Q3：是否存在数据倾斜？
执行：

-- 对JOIN KEY做频次分析 SELECT /*+ AGG_TO_COP() */ join_key, COUNT(*) c FROM build_side_table GROUP BY join_key ORDER BY c DESC LIMIT 5;

若c[0] / c[1] > 5，判定为倾斜，HashJoin需规避。

若任一问题答案为“否”，进入第三步。

5.3 第三步：强制切换join方式并量化对比

不要猜测，要实测。用Hint强制指定join，并记录精确耗时：

关键技巧：用SELECT SLEEP(0.001)注入微小延迟，隔离网络抖动影响

-- 测试HashJoin SELECT /*+ HASH_JOIN(t1,t2) */ COUNT(*) FROM t1 JOIN t2 ON ...; -- 立即执行（避免缓存干扰） SELECT SLEEP(0.001); -- 测试IndexJoin SELECT /*+ TIDB_INLJ(t2) */ COUNT(*) FROM t1 JOIN t2 ON ...;

记录每次执行的Query_time（来自Slow Log）或Duration（来自EXPLAIN ANALYZE），取5次平均值。差异>10%即具统计意义。

5.4 第四步：根治——索引与统计信息的协同优化

Hint是止痛药，索引和统计信息才是手术刀。根据第三步结论，执行根治操作：

• 若IndexJoin未被选用：

  1. 检查Build-Side索引是否以JOIN KEY为最左列；
  2. 若涉及多条件，用SHOW CREATE TABLE确认索引列顺序；
  3. 重建索引：DROP INDEX idx_old ON t2; CREATE INDEX idx_new ON t2(join_key, where_col, select_col);

• 若MergeJoin未被选用：

  1. 执行SHOW STATS_HISTOGRAMS WHERE table_name = 't2' AND column_name = 'join_key'，确认直方图是否平坦（平坦=分布均匀，TiDB认为无需Merge）；
  2. 若业务上实际倾斜，强制更新统计：ANALYZE TABLE t2 WITH 5000000 ROWS;
  3. 确认查询无ORDER BY、GROUP BY等破坏序的操作。

• 若HashJoin内存溢出：

  1. 降低tidb_hash_join_concurrency至3（减少goroutine争抢）；
  2. 增加tidb_mem_quota_query至64GB（需评估实例内存）；
  3. 终极方案：改写SQL，用WHERE提前过滤Build-Side，如JOIN (SELECT * FROM t2 WHERE status='valid') t2 ON ...。

最后，把优化后的SQL加入回归测试集，每周用pt-query-digest扫描Slow Log，确保无新SQL落入同一陷阱。TiDB的join优化不是一锤子买卖，而是持续的数据治理过程。

6. 超越语法：理解TiDB的分布式基因如何重塑join逻辑

所有关系型数据库的join优化都绕不开“数据本地性”这一终极命题。而TiDB的分布式架构，让这个问题变得既简单又复杂——简单在于数据天然分片，复杂在于跨分片join引入了不可忽视的网络开销。

6.1 Region与Join：为什么“同Region”是性能黄金标准

TiDB将数据按KEY切分为多个Region，每个Region由3副本组成，分布在不同TiKV节点。当JOIN的两表数据落在同一Region时，TiDB可将join计算下推到该Region的TiKV节点执行，全程无网络传输。

但现实很骨感：users表按id分片，orders表按order_id分片，user_id与order_id无数学关系，99%的join必然跨Region。此时TiDB必须：

• 将Probe-Side数据（如users的1000行）序列化，通过gRPC发送到Build-Side所在TiKV节点；
• 在目标节点执行join（HashJoin构建哈希表，IndexJoin做点查）；
• 将结果发回TiDB汇总。

这个过程引入了三次网络往返：

1. TiDB → TiKV（发送Probe数据）；
2. TiKV内部（Build + Probe）；
3. TiKV → TiDB（返回结果）。

我在某实时风控系统中做过测量：跨Region的HashJoin，网络耗时占总耗时的65%；而同Region的HashJoin，网络耗时<5%。这意味着——优化join的最高境界，不是选算法，而是让数据物理靠近。

6.2 解决方案：分区表与Shard Row ID

TiDB提供两种“让数据靠近”的手段：

方案1：分区表（Partitioned Table）
对orders表按user_id哈希分区：

CREATE TABLE orders ( order_id BIGINT, user_id BIGINT, ... ) PARTITION BY HASH (user_id) PARTITIONS 64;

这样，user_id相同的订单必然落在同一Partition，进而大概率在同一Region。当JOIN users ON users.id = orders.user_id时，TiDB能识别user_id的等值条件，将Probe（users）和Build（orders）都路由到同一TiKV节点。

方案2：Shard Row ID（推荐）
对orders表启用Shard Row ID：

ALTER TABLE orders SHARD_ROW_ID_BITS = 4 PRE_SPLIT_REGIONS = 4;

SHARD_ROW_ID_BITS = 4表示将_tidb_rowid的高4位作为Shard，生成2^4=16个Shard，数据按Shard分散。配合user_id作为主键前缀，可实现user_id相近的数据物理聚集。

注意：Shard Row ID需在建表时启用，已有表需重建。但它对应用透明，无需修改SQL，是长期演进的首选。

6.3 最后一道防线：物化Join结果

当上述所有优化仍无法满足SLA时，终极方案是用空间换时间，预计算join结果。

例如，某BI系统需频繁查询“用户最近3笔订单金额”，可创建物化视图：

CREATE TABLE user_recent_orders AS SELECT u.id as user_id, u.name, o1.amount as amount1, o2.amount as amount2, o3.amount as amount3 FROM users u LEFT JOIN orders o1 ON u.id = o1.user_id AND o1.rank = 1 LEFT JOIN orders o2 ON u.id = o2.user_id AND o2.rank = 2 LEFT JOIN orders o3 ON u.id = o3.user_id AND o3.rank = 3;

然后对user_recent_orders建PRIMARY KEY(user_id)。查询时直接SELECT * FROM user_recent_orders WHERE user_id = ?，毫秒级响应。

代价是存储空间和数据新鲜度（需定时刷新）。但在报表、监控等场景，这是最可靠的兜底方案。

TiDB的join优化，最终指向一个朴素真理：没有银弹，只有对数据、算法、硬件的深刻理解与持续权衡。每一次EXPLAIN ANALYZE的凝视，都是与TiDB内核的一次对话。当你能从execution info的数字里，读出内存的喘息、网络的脉搏、磁盘的叹息，你就真正掌握了这门手艺。