12 张表以内找全局最优：ClickHouse 新连接优化器 26.11 起默认开启
TL;DR 先摆出来
ClickHouse 新的基于代价的连接优化器（CBO）建立在 DPsub 的高效实现上——这是一种穷举式动态规划算法，12 张表以内的查询能找到现有代价模型下最便宜的计划，并将从 26.11 版本起默认开启。
更关键的变化在半句里：以前只有 inner join 之间可以重排，其他所有连接类型都是优化屏障；新优化器把 LEFT、RIGHT、FULL 外连接，以及 SEMI 和 ANTI 连接全部纳入重排。让它安全的是一个冲突检测器：只放行不改变查询结果的重排（正确性），且能找到搜索空间里所有合法计划（完备性）。两个性质都有证明，并且在超过 9 万棵连接树、280 万个候选计划的测试中没有出现任何非法计划或漏掉的计划。
图：优化器的位置——把声明式 SQL 变成算子执行树（图源：ClickHouse 官方博客）
为什么连接顺序是优化器最值钱的决定
SQL 是声明式的：说想要什么结果，不说怎么算。中间的优化器需要三样东西——搜索空间（与原查询等价的所有计划）、代价模型（每个计划多贵）、搜索策略（不逐个试也能找到便宜的）。
没有哪个决定比连接顺序更影响成本：不同顺序产生的中间结果大小天差地别——先连两张大表可能物化几十亿行，先用小的选择性表过滤可能把结果缩到几千行。搜索空间同时也是最大的：n 张表左深连接就有 n! 种顺序，允许 bushy 计划后是 n!·Catalan(n−1)，即 (2n−2)!/(n−1)!。10 张表：3,628,800 种左深顺序、超过 176 亿棵连接树；12 张表约 28 万亿。
图：同一条 TPC-H 查询，”选择性表先连”的中间结果小约 100 倍（图源：ClickHouse 官方博客）
经典两条路：贪心——反复挑当前最便宜的两位选手结合，快、经常够用，但早早下注永不反悔，ClickHouse 此前默认就是它。动态规划——”一个集合的最优计划由两个更小不相交子集的最优计划拼出来”，每个子问题只解一次，能精确找到最便宜顺序。
DPsub：把子集变成整数
DPsub 是”子集驱动”的 DP 变体：每个表子集就是一个位掩码，子集就是 1 到 2ⁿ−1 之间的整数，枚举子集就是往上数数。拆分子集用”减一再加掩码”的技巧不重不漏地走完全部子子集，另一半一个 XOR 就出来。
吸引力在于枚举本身便宜到可以忽略：加一、减一、AND、XOR、popcount 都是单指令、约一个时钟周期完成的 CPU 基本操作，子集整个装在一个寄存器里，没有指针、没有哈希。每个子集的最优计划存在按掩码索引的数组里——12 张表只有 4,096 个条目，稳稳放进 CPU 缓存。搜索空间仍然大（拆分数量约按 3ⁿ 增长，12 张表约五十万个），但每个拆分开销只有几个时钟周期，所以优化器可以穷举每个子集每个拆分而不是激进剪枝。
代价是指数增长有上限：DPsub 在 ClickHouse 里最多枚举 12 张表的子集（默认口径 10 张，query_plan_optimize_join_order_limit 调高到 12），更大的连接树交给贪心兜底。
图：DPsub 的位掩码枚举——穷举每个子集与每个拆分（图源：ClickHouse 官方博客）
非 inner join：从”优化屏障”到冲突检测器
inner join 交换律结合律都成立，随便重排。麻烦的是那些行为取决于”对面无匹配行”的连接类型：
| 连接类型 | 返回什么 |
|---|---|
| Left outer | 左表全部行；右表无匹配时右列补 NULL（join_use_nulls = 1） |
| Full outer | 两边全部行；无匹配的行缺侧补 NULL |
| Semi | 左表中能匹配的行各一次，不带右表列、不带重复——就是 EXISTS/IN |
| Anti | 只要左表中在右边无匹配的行——就是 NOT EXISTS |
left outer、semi、anti 不满足交换律（A LEFT JOIN B 保 A 全部行，反过来保的是 B），而且常常不满足结合律。所以优化器必须对每个候选重排回答一个问题：这个重排合法吗？ 回答它的组件就是冲突检测器，实现基于 SIGMOD 2013 论文《On the Correct and Complete Enumeration of the Core Search Space》——论文证明了早期方法会漏合法计划或放进非法计划，并给出了可证明又对又全的检测器。
检测器查四条性质（后三条按算子类型对存成矩阵）：comm（可交换？）、assoc（可结合？）、l-asscom、r-asscom。规则同时取决于连接类型和谓词是否拒绝 NULL：assoc(⟕, ⋈) 为假；assoc(⋈, ⟕) 为真；两个都是左连接时，只有当条件能拒绝 NULL 补出来的行，assoc(⟕, ⟕) 才成立。检测器把规则存成静态数据，枚举时逐条核对，而不是假设所有重组都安全。
此前 ClickHouse 把 semi/anti 连接留在 inner-join 图之外单独处理：semi/anti 子节点从不被拍平进图、顶部的 semi/anti 把图封顶在两张表——每个 semi/anti 连接都是一道屏障。检测器把空间两头打开：比”全自由重排”小（非法的不用再探索），比”全当屏障”大（屏障挡住的合法重排全部放行）。
装进 DPsub：三个工程细节
- 整个连接树作为一张图进 DPsub：外连接、semi、anti、FULL 的两边全部入图；
- 笛卡尔积：CROSS JOIN 没有谓词边，显式按选择率 1 连一条边保持图连通，DPsub 可以把它挪到最便宜的位置，执行和展示仍是 CROSS JOIN；
- build side：代价模型对同一连接的两种输入方向收费相同，搜索结束后把较小输入放哈希连接的 build 侧（外连接 LEFT↔RIGHT 镜像互换），但 ANY/SEMI/ANTI 永不镜像——它们的语义依赖左右。
验证：280 万计划，0 反例
检测器错一次就会返回错结果，所以按论文的方式验证：对小规模 n 生成每一棵初始连接树（全形状 × 算子分配 × 二元等值谓词），穷举整个核心搜索空间，每个候选计划三向核对——本实现、独立参考实现、带 NULL 的随机数据库上真实执行。大规模算子集（inner、left/full outer、semi、anti）下，检测器生成了全部 280 万个核心计划，没有一个非法，没有一个执行失败。
差分模糊测试：随机生成混合 INNER/LEFT/RIGHT/FULL/SEMI/ANTI 的多路连接查询（含只引用单侧的 ON 子句），数据带 NULL、重复键、无匹配键，与引擎内计算的顺序无关 NULL-safe 校验和比对——1,200 条最多 7 表的查询，0 处不一致。
检测器打开的搜索空间（1,200 条 3–7 表抽样查询，DPsub 实际探索的合法计划数）：
| 表数 | 无检测器 | 有检测器 | 增益 |
|---|---|---|---|
| 3 | 757 | 757 | 1.00× |
| 4 | 1,283 | 1,583 | 1.23× |
| 5 | 1,633 | 2,883 | 1.77× |
| 6 | 3,228 | 8,868 | 2.75× |
| 7 | — | — | 11.51× |
实测收益：496 倍与 3.8 倍
原文给的 semi join 例子（big INNER JOIN mid ... LEFT SEMI JOIN tiny ...）：没有检测器时最大中间结果 (big ⋈ mid) ⋉ tiny = 503,768,186 行；有检测器后 mid ⋈ (big ⋉ tiny) 只有 1,015,092 行——中间结果小约 496 倍，两次跑的是同一个连接枚举器，唯一区别是 semi join 参不参与搜索，结果完全一致。
big/mid 各 300 万行、tiny 100 个键时的运行时间：
| 场景 | 贪心 | DPsub + 检测器 | 加速 |
|---|---|---|---|
| runtime join filters 关闭 | 0.133 s | 0.035 s | 3.8× |
| runtime join filters 开启（默认） | 0.044 s | 0.037 s | 1.2× |
图：让 semi join 参与搜索后，先过滤 big，最大中间结果从 5 亿行缩到 100 万行（图源：ClickHouse 官方博客）
TPC-DS（SF1）/TPC-H（SF1/SF10）性能测试对比贪心默认：TPC-H Q2 143ms → 65ms（−55%）、TPC-DS Q73 260ms → 143ms（−45%）、TPC-H Q5 574ms → 320ms（−44%）、TPC-DS Q86 93ms → 57ms（−39%）、TPC-DS Q65 302ms → 227ms（−25%）。
怎么用
26.11 起默认（贪心作为大连接树的兜底）：
SET query_plan_optimize_join_order_algorithm = 'dpsub,greedy';
SET query_plan_optimize_join_order_conflict_detector = 'c';
想对照旧行为就把检测器置空、算法回 greedy。看每个连接的顺序、类型和 strictness 用 EXPLAIN actions = 1。
小夏点评
- 这篇的工程含金量在”检测器”而不是”DP”：DPsub 是 1979 年就有的教科书算法，真正难的是让非 inner join 安全进搜索空间——SIGMOD 2013 的检测器加上”280 万计划三向核对、1,200 条模糊测试 0 反例”的验证规模，才让厂商敢把穷举 DP 设成默认。
- 收益结构值得注意：7 表以上搜索空间增益 11.5 倍、默认配置下加速只有 1.2 倍——ClickHouse 自家的 runtime join filters 已经吃掉了部分红利。优化器升级的价值在复杂多表查询和过滤器关掉的场景，上线后先盯自己报表里连接最多的那几条 SQL。
- 对中国 IT 运维/开发者：26.11 默认开启意味着升级即生效，老查询计划可能换连接顺序。建议升级前对核心报表 SQL 跑一遍
EXPLAIN actions = 1留底，灰度对比新旧算法（两条 SET 就能按查询切换）；数仓里 7 表以上的大连接、带 EXISTS/NOT EXISTS 的查询是最先看到收益的地方。
参考
- 原文（ClickHouse Blog，2026-10-28，Fisnik Kastrati）：https://clickhouse.com/blog/the-new-cost-based-join-optimizer-with-reordering-support-for-non-inner-joins
- SIGMOD 2013 论文：On the Correct and Complete Enumeration of the Core Search Space
