• 写在前面：为什么要搞懂连接算法
• 三分钟版结论
• 实验准备：数据集是怎么设计的
• 第一站：Nested Loop Join——最朴素，也最容易背锅
  • 原理：它就是一个双层 for 循环
  • 实验：小表 join 大表，索引却没用上
  • 拆解计划：三个问题
  • 本站小结
• 第二站：Hash Join——删掉一个索引，计划就换了算法
  • 原理：先建一本"通讯录"，再逐个来查
  • 实验：同一个查询，索引删除前后
  • 为什么会迁移？优化器的决策链
  • build side 的选择与风险
  • Hash Join 的适用边界
  • 本站小结
• 第三站：Merge Join——有序是最大的资本
  • 原理：两条排好队的队列，双指针点名
  • 关键问题：凭什么"跳过"是安全的？
  • 实验：hint 强制 Merge Join，顺便看看分布式计划的代价
  • 本站小结
• 三种算法怎么选：一份选型指南
• 需要干预优化器时：Hint 与 Outline
• 附录 A：EXPLAIN EXTENDED 输出速查
  • 算子表
  • Outputs & filters 常见字段
  • Optimization Info 常见字段
  • 其他段落
• 附录 B：实验数据集脚本

一句话导读：本文用 3 组可复现的实验（10 万行级数据），逐行拆解 OceanBase 执行计划中 NESTED-LOOP JOIN、HASH JOIN、MERGE JOIN 三种连接算子的行为，回答三个问题——优化器为什么这么选？索引如何改变连接算法？拿到一份计划如何快速定位瓶颈？

写在前面：为什么要搞懂连接算法

做过慢 SQL 排查的同学大概率都有这样的经历：跑了一个 EXPLAIN，输出里赫然写着 HASH JOIN 或 NESTED-LOOP JOIN CARTESIAN，然后……然后就去搜"hash join 慢怎么办"了。

连接算子是执行计划里最常见的算子家族之一，两表关联的 SQL 最终都会落到这三种算法之一。看不懂它，等于看不懂执行计划的一半；看懂了它，很多"为什么这条 SQL 慢"的问题就有了分析框架：

• 为什么明明有索引，优化器却不用？
• 为什么删掉一个索引，连接算法就从 Merge Join 变成了 Hash Join？
• NESTED-LOOP JOIN CARTESIAN 是不是意味着 SQL 写砸了？

这些问题在本文的三个实验里都有真实答案。文中的每一个结论都来自实际执行的 EXPLAIN EXTENDED 输出，建表和造数脚本在附录，你可以完整复现。

三分钟版结论

优化器选型口诀（按优先级）：

1. 连接条件是非等值 → 只能 NLJ（Hash 不可用，Merge 退化为类 NLJ）；
2. 等值 + 驱动侧结果集小 + 被驱动侧有高选择度索引 → NLJ；
3. 等值 + 两侧天然有序（主键扫描 / 前导列为连接键的索引扫描）→ Merge Join；
4. 等值 + 双大表 + 无索引 → Hash Join；

实验准备：数据集是怎么设计的

为了让三种算法各自"本色出演"，实验构造了一组小数据集（完整脚本见附录 B）：

两组典型场景，刻意制造"大小悬殊"和"势均力敌"的对比：

• 20 行小表 join 10 万行大表（加一个过滤条件）：检验 NLJ 的行为，以及"有索引但优化器不用"的现象；
• 10 万行 join 10 万行（无任何过滤）：检验等值连接下 Merge 与 Hash 之间的迁移——只需要删掉一个索引。

环境说明：实验在两个 OceanBase 测试环境完成（4.3.5.3 单机 LOCAL 计划 / 4.5.0.0 分布式 DISTRIBUTED 计划，统计信息版本也不同）。文中会标注每组计划来自哪个环境；不同环境的估算代价（EST.TIME）不可直接横向比较，但算法行为和决策逻辑是通用的。

第一站：Nested Loop Join——最朴素，也最容易背锅

原理：它就是一个双层 for 循环

嵌套循环连接是最容易直觉理解的算法：外层循环逐行读取驱动表（outer table），对驱动表的每一行，去被驱动表（inner table）里找满足连接条件的行，找到就输出。

用伪代码表达就是：

for (row_r in 左表) {
    for (row_s in 右表) {
        if (row_r.key == row_s.key) output(row_r, row_s);
    }
}

它的核心特性决定了它的命运：被驱动侧的访问次数 = 驱动侧的输出行数。驱动表每返回一行，被驱动侧就被访问一次——驱动表返回 100 行，内侧查找就重复执行 100 次。

成本公式：

C(NLJ) ≈ C_scan(outer) + N_outer × C_access(inner)

• 内侧有高选择度索引（点查、少量回表）→ 单次访问代价极低，NLJ 是 OLTP 场景的最优解；
• 内侧没有索引 → 每次访问都是一次全表扫描，代价随驱动侧行数线性倍增。两表各 10 万行、无过滤、无索引时，行级比较次数是 10^5 × 10^5 = 10^10 量级——这就是第二站优化器拒绝 NLJ 的原因。

实验：小表 join 大表，索引却没用上

EXPLAIN EXTENDED
SELECT d.dept_id, e.emp_id, e.salary
FROM dept d
JOIN emp e ON d.dept_id = e.dept_id
WHERE d.dept_id = 10;

执行计划（环境：4.3.5.3，LOCAL）：

|ID|OPERATOR                  |NAME|EST.ROWS|EST.TIME(us)|
|0 |NESTED-LOOP JOIN CARTESIAN|    |5000    |4466        |
|1 |├─TABLE GET               |d   |1       |7           |
|2 |└─TABLE FULL SCAN         |e   |5000    |4334        |

关键明细（已去掉指针地址等噪音）：

0 - output([d.dept_id], [e.emp_id], [e.salary]), filter(nil), rowset=256
    conds(nil), nl_params_(nil), use_batch=false
1 - access([d.dept_id]), range_key([d.dept_id]), range[10 ; 10],
    range_cond([d.dept_id = 10])
2 - output([e.emp_id], [e.salary]), filter([e.dept_id = 10]),
    access([e.emp_id], [e.dept_id], [e.salary]),
    range_key([e.emp_id]), range(MIN ; MAX)always true

拆解计划：三个问题

问题 1：谁是驱动表？

看计划树的结构：连接算子（ID 0）的左孩子是驱动表，右孩子是被驱动表。本例中 d（TABLE GET，主键点查取 1 行）驱动，e（全表扫描）被驱动。执行顺序则是自底向上：1 号、2 号算子先产出数据，0 号连接算子最后汇合输出。

问题 2：为什么写着 CARTESIAN？是不是 SQL 写砸了？

不是。注意 join 算子上的三个信号：conds(nil)、nl_params_(nil)、use_batch=false——这不是经典的"索引参数化嵌套循环"（那种形态下连接条件会变成 nl_params_ 下推到内侧索引）。

真实原因藏在计划的 Outline Data 里，有一个 PRED_DEDUCE（谓词推导） 标记：优化器由 d.dept_id = 10 和连接条件 d.dept_id = e.dept_id 推导出了常量条件 e.dept_id = 10，并直接下推成 e 表全扫上的 filter([e.dept_id = 10])。

连接条件被消解成单表过滤之后，d 只剩 1 行，join 层面用笛卡尔拼接两侧就能得到正确结果（1 × 5000 = 5000，与 EST.ROWS 吻合）。所以这个 CARTESIAN 不是"写砸了"，恰恰是优化器做了一次聪明的改写。

问题 3：emp 上明明有 idx_emp_dept 索引，为什么全表扫描？

这是本实验最有价值的发现。Optimization Info 里写着：

e: avaiable_index_name:[idx_emp_dept, emp]

avaiable_index_name 列出了优化器评估过的路径——索引被评估过，然后被放弃了。原因算一笔账就明白：

• dept_id = 10 在 10 万行里命中约 5000 行，选择度 1/20 = 5%；
• 走索引就要回表取 emp_id、salary 两列，5000 次随机回表的代价，高于一次顺序全表扫描（估算 4334us）。

结论：有索引不等于必用索引。 等值条件命中行数太多（选择度差）且需要回表时，全表扫描反而更便宜。优化器从不"看索引下菜"，它只认估算代价。

顺带一提：总代价 4466us 里，e 的全表扫描占 4334us（约 97%）。拿到任何执行计划，按 EST.TIME 排序找最大者，就是定位瓶颈最直接的方法。

本站小结

1. 计划树里 join 的左孩子 = 驱动表，右孩子 = 被驱动表；数据流自底向上。
2. NLJ 的命门：内侧访问次数 = 驱动侧行数，无索引时代价按倍数爆炸。
3. NLJ 的最佳拍档：小结果集驱动 + 内侧高选择度索引（点查）。
4. conds(nil) + nl_params_(nil) + CARTESIAN 组合出现时，先别慌——很可能是谓词推导把连接条件消解成了单表过滤。
5. 索引用不用，看选择度和回表代价，不看"有没有"。

第二站：Hash Join——删掉一个索引，计划就换了算法

原理：先建一本"通讯录"，再逐个来查

Hash Join 只能处理等值连接条件（执行计划中的 equal_conds），分两个阶段：

• build 阶段：扫描 build 侧，对每一行的连接键算哈希值，在内存里建一张哈希表——相当于先把一侧数据做成一本按哈希值组织的"通讯录"；
• probe 阶段：扫描 probe 侧，逐行对连接键算哈希值，去"通讯录"里找到同一个桶，桶内做精确等值比较，匹配则输出。

两侧各扫一遍，复杂度 O(N + M)——前提是哈希表装得进内存、哈希分布均匀。

在执行计划里：左孩子 = build side（建哈希表的一侧），右孩子 = probe side（探测的一侧）。

实验：同一个查询，索引删除前后

SELECT o.order_id, i.item_id
FROM orders o
JOIN order_items i ON o.order_id = i.order_id;

两条 10 万行的表做等值连接，没有任何过滤条件。先看索引存在时的默认计划（环境：4.3.5.3，LOCAL）：

|ID|OPERATOR         |NAME                    |EST.ROWS|EST.TIME(us)|
|0 |MERGE JOIN       |                        |100001  |15350       |
|1 |├─TABLE FULL SCAN|o                       |100000  |2581        |
|2 |└─TABLE FULL SCAN|i(idx_order_items_order)|100000  |4896        |

优化器默认选了 Merge Join。原因：两侧在连接列 order_id 上天然有序——o 按主键扫描（OceanBase 表是索引组织表，按主键扫描天然有序）；i 走 idx_order_items_order 索引（连接键是前导列）。两边都有序，Merge Join 零排序成本。

然后，删掉这个索引：

DROP INDEX idx_order_items_order ON order_items;

再看计划：

|ID|OPERATOR         |NAME|EST.ROWS|EST.TIME(us)|
|0 |HASH JOIN        |    |100001  |36393       |
|1 |├─TABLE FULL SCAN|o   |100000  |2581        |
|2 |└─TABLE FULL SCAN|i   |100000  |4896        |

0 - equal_conds([o.order_id = i.order_id]), other_conds(nil)

连接算法从 Merge Join 迁移到了 Hash Join。没有改一个字的 SQL，只删了一个索引。

为什么会迁移？优化器的决策链

把这个决策链完整展开，是理解三种算法边界的最佳练习：

1. 为什么不再选 Merge Join？ i 失去了有序访问路径（索引没了），维持 Merge Join 就必须引入 SORT 算子先排序，代价反超；
2. 为什么不选 NLJ？ 无过滤条件，驱动侧全量 10 万行；内侧无索引，每访问一次都是全表扫描——比较量级 10^10，不可接受；
3. 于是 Hash Join 成为唯一合理选择：两侧各扫一遍，O(N + M)，估算 36393us。

计划里还能读出 build / probe 的分工：

• build side = 左孩子 = o（全扫 2581us，用来建哈希表）；
• probe side = 右孩子 = i（全扫 4896us，逐行探测）；
• join key 就是 equal_conds([o.order_id = i.order_id])。

build side 的选择与风险

优化器会尽量选较小的一侧做 build：哈希表要驻留内存，小表构建得快、占内存少（本例两侧同量级，优化器选了 o）。

如果 build side 太大会怎样？三个后果，按严重程度排列：

Hash Join 的适用边界

✅适合：等值连接 + 双大表 + 连接列无可用索引（或建索引不划算）——典型 OLAP 场景。

❌不适合：

• 非等值连接：哈希只支持等值匹配，直接不可用；
• 输出需要按连接键有序：Merge Join 可以"顺便"保序，Hash Join 输出无序；
• 小表驱动大表且内侧有高选择度索引：此时 NLJ + 索引更优。

本站小结

1. Hash Join 仅支持等值连接，join key 体现在 equal_conds；左孩子 build（建哈希表），右孩子 probe（探测）。
2. build side 尽量小；核心风险是 Spill to Disk——落盘即失去优势。
3. "双大表 + 无过滤 + 无索引"时 NLJ 代价是 N×M 量级，这就是优化器此时弃用 NLJ 的原因。
4. 索引的存在会改变算法选型：有序索引路径把优化器推向 Merge Join，索引一删，同一个查询落入 Hash Join。

第三站：Merge Join——有序是最大的资本

原理：两条排好队的队列，双指针点名

Merge Join 要求两侧输入按连接键有序且方向一致（计划中表现为 merge_directions([ASC])），然后用双指针同步扫描：

• left_val right_val → 推进右指针；
• 相等 → 输出匹配行，两侧同时推进（连接键有重复值时，同值区间内做局部展开）；
• 任一侧越界，结束。

每侧行只扫一次、指针只前进不回退，复杂度 O(N + M)。

用一个 8 步的小例子感受一下双指针的节奏（左 [1,2,3,5]，右 [2,3,4,6]）：

关键问题：凭什么"跳过"是安全的？

这是 Merge Join 最精髓的一点。以 left.order_id = right.order_id 为连接条件时：

• 若 left_val right_val，同理可以安全跳过右指针。

有序性保证了"跳过不丢解"。 而非等值连接（比如范围条件 a.id < b.id）没有这个性质——跳过的行可能还有解，无法安全剪枝，Merge Join 实际退化为类似 NLJ 的逐行比较模式。这就是"Merge Join 在非等值场景受限"的根本原因。

再回答一个常见疑问：既然两侧有序时 Merge Join 这么高效，无序时差在哪？ 差在排序本身：输入无序就得先引入 SORT，O(N log N) 的 CPU 开销，还可能落盘——这时候 Merge Join 未必比 Hash Join 便宜，第二站的实验正是优化器做了这个权衡后放弃了 Merge。

实验：hint 强制 Merge Join，顺便看看分布式计划的代价

环境换到 4.5.0.0（分布式），这个环境默认生成的是 HASH JOIN 计划，所以用 hint 明确指定：

EXPLAIN EXTENDED
SELECT /*+ LEADING(o i) USE_MERGE(o i) */
  o.order_id, i.item_id
FROM orders o
JOIN order_items i ON o.order_id = i.order_id;

|ID|OPERATOR              |NAME                    |EST.ROWS|EST.TIME(us)|
|0 |MERGE JOIN            |                        |100002  |138841      |
|1 |├─TABLE FULL SCAN     |o                       |100001  |2581        |
|2 |└─PX COORDINATOR      |                        |100000  |128386      |
|3 |  └─EXCHANGE OUT DISTR|:EX10000                |100000  |90306       |
|4 |    └─TABLE FULL SCAN |i(idx_order_items_order)|100000  |4896        |

0 - equal_conds([o.order_id = i.order_id]), other_conds(nil)
   merge_directions([ASC])

这份计划里藏着三个值得展开的细节：

细节 1：Merge Join 的前提是如何满足的。 o 按主键 order_id 全扫（range_key([o.order_id])，天然有序）；i 走 idx_order_items_order 索引（range_key([i.order_id], [i.item_id])，连接键是前导列）；merge_directions([ASC]) 确认两侧同为升序。三个条件凑齐，Merge Join 才可行——这也是为什么删掉索引后（第二站）Merge 直接出局。

细节 2：覆盖索引，免回表。 i 侧 is_index_back=false：OceanBase 的索引条目会隐含主键列，所以 idx_order_items_order(order_id) 实际包含 (order_id, item_id)，恰好覆盖了查询需要的所有列，一次索引扫描全搞定。计划 Optimization Info 里的 pruned_index_name:[order_items] 表示优化器代价比较后裁掉了主表扫描路径。顺带澄清一个容易混淆的点：访问路径（走索引还是全表）和连接算法（Hash 还是 Merge）是两个独立决策——这个环境里默认的 HASH JOIN 计划同样让 i 走了这个索引。

细节 3：EXCHANGE 的代价可能比扫描大一个数量级。 这是一份 Plan Type: DISTRIBUTED 计划：i 表数据不在计算节点本地，需要经过 EXCHANGE OUT DISTR → PX COORDINATOR 跨节点拉取。看估算代价：EXCHANGE 要 90306us，是本地索引扫描（4896us）的 18 倍；整个计划 138841us 里约 95% 花在 i 侧的数据传输链路上。对比单机环境的同款 Merge Join（总代价 15350us），结论很直接：数据本地性对连接性能的影响，可以远超扫描方式和连接算法本身（两套环境统计信息不同，数字仅作量级参考）。

本站小结

1. Merge Join 双前提：两侧按连接键有序 + 等值条件；有序性证据是 merge_directions([ASC])，有序来源通常是主键扫描或前导列为连接键的索引扫描。
2. 匹配规则：`` 推右、= 输出并双侧推进；跳跃的安全性完全依赖等值条件 + 有序性。
3. 非等值连接下跳跃不安全，Merge Join 退化为类 NLJ——这是它非等值受限的根本原因。
4. 有序输入的优势是省掉 SORT 的 O(N log N) 开销；无序时优化器会在"排序 + Merge"与 Hash Join 之间做总代价权衡。
5. 分布式计划里，EXCHANGE（跨节点数据传输）的代价可能远超扫描本身——调优时别忘了数据本地性这个变量。

三种算法怎么选：一份选型指南

把三站实验的结果放在一起，优化器的选型逻辑就非常清晰了（以下均为环境 4.3.5.3 的实测）：

拿到一条 join SQL，按这个顺序判断：

1. 先看连接条件类型：非等值 → NLJ 是唯一选择；
2. 等值连接再看规模与索引：
   • 小结果集驱动 + 高选择度索引 → NLJ；
   • 双大表 + 两侧天然有序（或输出需有序）→ Merge Join；
   • 双大表 + 无索引 → Hash Join；
3. 带着风险意识看结果：NLJ 的风险在 N×M 倍增；Hash 的风险在 build 侧溢写落盘；Merge 的风险在被迫排序、以及分布式场景的 EXCHANGE 网络代价。

遇到慢连接 SQL 的排查清单：

1. EXPLAIN EXTENDED 拿到完整计划，先看 Plan Type（LOCAL / DISTRIBUTED）；
2. 按 EST.TIME 排序找最贵算子——瓶颈可能在扫描，也可能在 EXCHANGE；
3. 确认连接条件是等值还是非等值，决定了算法的可选空间；
4. 查看各表的 avaiable_index_name（评估过哪些路径）和 pruned_index_name（裁掉了哪些路径）——索引"在但没用"通常意味着选择度差或回表代价高；
5. 检查统计信息（stats info 的 is_expired、版本时间）——估算失真会导致选型错误；
6. 确认必要时再考虑 hint 干预（下一节）。

需要干预优化器时：Hint 与 Outline

当优化器的选择确实不合适（统计信息失真、数据分布特殊等），可以用 hint 明确干预。本文实验涉及的核心 hint：

另外一个非常实用的技巧：EXPLAIN EXTENDED 输出中的 Outline Data（BEGIN_OUTLINE_DATA ... END_OUTLINE_DATA）记录了生成当前计划的全部决策——连接顺序、算法、访问路径、改写动作。把它整体作为 hint 附加到原 SQL 上，即可固定执行计划，是计划回归防护的标准手段。

Outline 里还会出现 OUTER_TO_INNER（外连接改写为内连接）、PRED_DEDUCE（谓词推导）这类改写标记——比如第一站那个"CARTESIAN"计划，正是 PRED_DEDUCE 把连接条件推导成了单表常量过滤。

附录 A：EXPLAIN EXTENDED 输出速查

算子表

|ID|OPERATOR |NAME|EST.ROWS|EST.TIME(us)|

Outputs & filters 常见字段

Optimization Info 常见字段

其他段落

• Plan Type：LOCAL（单机）/ DISTRIBUTED（含 PX / EXCHANGE 算子）；
• Note：并行度说明（如 Degree of Parallelism is 1 because of table property）；
• Parameters：绑定参数实际取值。

附录 B：实验数据集脚本

-- 数字发生器：seq_10 经 5 次 CROSS JOIN 笛卡尔展开为 100,000 行
CREATE TABLE seq_100000 AS
SELECT (a.n*10000 + b.n*1000 + c.n*100 + d.n*10 + e.n + 1) AS id
FROM seq_10 a CROSS JOIN seq_10 b CROSS JOIN seq_10 c
CROSS JOIN seq_10 d CROSS JOIN seq_10 e;

-- dept：20 行小表（dept_id 主键）
-- emp：100,000 行，dept_id = MOD(id-1,20)+1 均匀分布；建 idx_emp_dept(dept_id)
-- orders：100,000 行，order_id 主键
-- order_items：100,000 行，order_id 与 orders 1:1 映射；建 idx_order_items_order(order_id)
-- （第二站实验中该索引被删除，用于观察计划迁移）

ANALYZE TABLE dept; ANALYZE TABLE emp;
ANALYZE TABLE orders; ANALYZE TABLE order_items;

数据量确认：

注：emp 表的完整建表语句为 (emp_id INT PRIMARY KEY, dept_id INT NOT NULL, salary DECIMAL(10,2) NOT NULL, pad VARCHAR(100))，灌数使用 MOD(id-1,20)+1 生成 dept_id、3000+MOD(id,7000) 生成 salary、REPEAT('A',50) 生成 pad；orders / order_items 同理由 seq_100000 派生。建库语句：DROP DATABASE IF EXISTS join_lab; CREATE DATABASE join_lab; USE join_lab;