第 6 章：分布式查询优化——比单机复杂 10 倍的执行计划

结论先行：分布式查询优化比单机难在三个地方——搜索空间指数增长（数据可能在任何节点上）、统计信息不完整（全局统计总是滞后的）、网络传输成本巨大（跨节点传数据比本地读慢百万倍）。不同项目用了截然不同的策略来应对这些挑战。

一个旅行规划的故事

假设你要从北京出发，途经上海、杭州、深圳，最终到达广州。你需要规划路线：坐飞机还是高铁？先去上海还是先去杭州？在哪里住一晚？

如果只有 4 个城市，可能的路线组合还能人工比较。但如果是 20 个城市呢？可能的路线数量是 20 的阶乘（约 2.4×10^18），即使用计算机也不可能穷举所有组合。

旅行规划员的策略通常是：先用一些规则快速排除明显不合理的路线（比如从北京去广州不会绕道哈尔滨），然后在剩下的候选方案中用成本估算选最优的。

查询优化器做的就是同样的事——给一条 SQL 找到最快的执行方案。在分布式环境下，这个问题的复杂度比单机高出一个量级。

单机查询优化 vs 分布式查询优化

先回忆一下单机查询优化的基本流程：

SELECT u.name, o.total
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.city = '北京'
ORDER BY o.total DESC
LIMIT 10;

单机优化器需要决定：

先扫描 users 还是先扫描 orders？
用什么方式扫描？全表扫描、索引扫描、还是只读索引？
用什么方式做 JOIN？嵌套循环、Hash JOIN、还是 Sort-Merge JOIN？
在哪一步做排序？

分布式优化器除了上面这些，还需要决定：

users 表分布在 3 台机器上，WHERE city = ‘北京’ 需要查哪些分片？
orders 表分布在 3 台机器上，JOIN 怎么做？
- 把 users 的结果发给 orders 所在的节点（数据移动）？
- 还是把所有数据拉到协调节点做 JOIN（可能传输大量数据）？
排序和 LIMIT 在哪里做？每个分片先排序取 Top10 再合并，还是把所有数据拉过来一起排序？

单机优化器的决策空间：
  扫描方式 × JOIN方式 × 排序位置 = ~百种组合

分布式优化器的决策空间：
  扫描方式 × JOIN方式 × 排序位置 × 数据位置 × 网络传输策略
  = ~万种组合甚至更多

分布式 JOIN 的四种策略

JOIN 是分布式查询中最有挑战的操作。当两张表分布在不同节点上时，有四种基本策略：

策略一：协同分片 JOIN（最快）

如果两张表按同一个键分片（Co-located），JOIN 可以在每个分片内本地完成，不需要网络传输。

users 和 orders 都按 user_id Hash 分片：

  分片1: users(id=1..100) + orders(user_id=1..100)
  分片2: users(id=101..200) + orders(user_id=101..200)
  
  JOIN 在每个分片内本地执行，然后合并结果
  网络传输：只有最终结果

策略二：广播 JOIN（适合小表）

把小表的全部数据广播到每个分片，在每个分片上做本地 JOIN。

users: 1万行（小表）
orders: 1亿行（大表，分布在10个分片）

策略：把 users 的1万行数据发送到所有10个分片

  每个分片: 本地的 orders + 广播过来的 users → 本地 JOIN

  网络传输：1万行 × 10个分片 = 10万行
  （比移动1亿行的 orders 少多了）

策略三：重分布 JOIN（通用但昂贵）

按 JOIN 键重新分布其中一张（或两张）表的数据，让需要 JOIN 的行出现在同一个节点上。

users 按 user_id Hash 分片
orders 按 order_id Hash 分片（注意：不是 user_id！）

要做 JOIN ON users.id = orders.user_id：
  orders 需要按 user_id 重新分布
  
  分片1上的 orders → 根据 user_id 重新 hash → 发到对应分片
  分片2上的 orders → 根据 user_id 重新 hash → 发到对应分片
  
  重新分布完成后，每个分片做本地 JOIN
  
  网络传输：可能需要移动整个 orders 表

策略四：拉回协调节点 JOIN（最后的手段）

把所有数据拉到协调节点（Coordinator），在协调节点上做单机 JOIN。

  分片1 ──所有数据──► Coordinator
  分片2 ──所有数据──►     ↓       → JOIN → 返回结果
  分片3 ──所有数据──►  (内存可能不够)
  
  网络传输：所有涉及的数据
  内存压力：协调节点可能 OOM

查询优化器的核心任务就是：在这四种策略（以及它们的组合）中选出成本最低的方案。

TiDB 的 Cascades 框架

TiDB 实现了经典的 Cascades 查询优化框架——这是学术界公认的最先进的优化器架构，被 SQL Server、CockroachDB 等商业/开源数据库采用。

Cascades 的核心思想

Cascades 的核心是 Memo 结构——一种紧凑表示所有等价执行计划的数据结构。

想象你在做旅行规划。你不会列出所有可能的完整路线，而是把问题分解成子问题：

“北京到上海”有哪些方式？飞机（2小时）、高铁（4.5小时）
“上海到杭州”有哪些方式？高铁（1小时）、大巴（3小时）
“杭州到广州”有哪些方式？飞机（2.5小时）、高铁（8小时）

每个子问题的所有选项构成一个”等价类”（Equivalence Class），最终从每个等价类中选出最优方案组合成完整路线。

Memo 结构示意：

Group 1 (获取 users):
  ├── TableScan(users)           成本: 1000
  └── IndexScan(users, city_idx) 成本: 50  ← 如果有 city='北京' 条件

Group 2 (获取 orders):
  ├── TableScan(orders)          成本: 5000
  └── IndexScan(orders, uid_idx) 成本: 200

Group 3 (JOIN users × orders):
  ├── HashJoin(Group1, Group2)   成本: 1200
  ├── NLJoin(Group1, Group2)     成本: 50000
  └── MergeJoin(Group1, Group2)  成本: 800  ← 最优

最终选择: IndexScan(users) + MergeJoin + TableScan(orders)

TiDB 的 Cascades 实现在 pkg/planner/cascades/：

pkg/planner/cascades/
  cascades.go       ← 优化器入口，包含 Memo + Scheduler
  memo.go           ← Memo 数据结构
  rule/             ← 转换规则目录
    join_reorder.go     ← JOIN 重排序
    predicate_pushdown.go ← 谓词下推
    aggregation_elimination.go ← 聚合消除

谓词下推：分布式优化中最重要的规则

在分布式数据库中，最有价值的优化规则是谓词下推（Predicate Pushdown）——把 WHERE 条件尽可能推到数据所在的节点执行，减少网络传输的数据量。

-- 原始查询
SELECT * FROM users JOIN orders ON users.id = orders.user_id
WHERE users.city = '北京';

-- 没有谓词下推：
   所有节点: 发送全部 users 数据到协调节点
   所有节点: 发送全部 orders 数据到协调节点
   协调节点: 做 JOIN，然后过滤 city = '北京'
   网络传输: 可能 GB 级

-- 有谓词下推：
   所有节点: 先在本地过滤 city = '北京'，只发送匹配的行
   协调节点: 做 JOIN
   网络传输: 可能只有 MB 级（减少 1000 倍！）

TiDB 的优化器可以透明地决定把操作下推到 TiKV（行存，适合点查）还是 TiFlash（列存，适合扫描聚合），用户完全不需要关心数据在哪里。

Citus 的五层渐进式规划器

Citus 的查询规划器是开源世界最好的分布式查询规划文档之一。它的 planner/README.md 详细描述了五层逐级回退的规划策略。

五层策略详解

核心思想：大多数 OLTP 查询其实很简单——只涉及一个分片或几个协同分片。只有少数复杂查询才需要完整的分布式规划。所以 Citus 的策略是”先试简单的，不行再升级”。

SQL 进来
    |
    v
第1层: Fast-path Router
    "这条查询只涉及一个分片吗？"
    ├── 是 → 直接路由到那个分片，结束！（最快路径）
    └── 否 → 降级到第2层
    |
    v
第2层: Router Planner  
    "查询涉及的所有表都是协同分片的吗？"
    ├── 是 → 路由到对应分片组，每个分片本地执行
    └── 否 → 降级到第3层
    |
    v
第3层: Modification Planning
    "这是一条 INSERT/UPDATE/DELETE 吗？"
    ├── 是 → 使用专门的 DML 规划逻辑
    └── 否 → 降级到第4层
    |
    v
第4层: Recursive Planning
    "查询中有子查询吗？"
    ├── 是 → 递归地规划每个子查询
    └── 否 → 降级到第5层
    |
    v
第5层: Logical Planner
    "完整的分布式规划"
    构建多关系代数树，分析JOIN顺序和数据移动

第一层：Fast-path Router（95% 的 OLTP 查询走这里）

-- 这条查询只涉及一个分片
SELECT * FROM users WHERE user_id = 42;

-- Fast-path Router 的判断逻辑（简化）：
-- 1. 只涉及一张分布式表 ✓
-- 2. WHERE 条件包含分片键的等值条件 ✓
-- 3. 没有子查询、UNION 等复杂结构 ✓
-- → 直接路由到 hash(42) 对应的分片！

这一层几乎没有规划开销——不需要做 JOIN 分析、不需要考虑数据移动。对于典型的 OLTP 负载（根据主键查单行），这就是全部需要的优化。

第二层：Router Planner

-- 两张协同分片表的 JOIN
SELECT u.name, o.total
FROM users u JOIN orders o ON u.user_id = o.user_id
WHERE u.user_id = 42;

-- Router Planner 的判断：
-- 1. users 和 orders 都按 user_id 分片 ✓
-- 2. JOIN 条件是分片键 ✓
-- 3. WHERE 条件限定到一个分片 ✓
-- → 整个查询路由到一个分片，在分片内做本地 JOIN

第五层：Logical Planner（最复杂的查询走这里）

当查询涉及非协同分片表的 JOIN、全局聚合等复杂操作时，才会走到第五层。这一层会分析 JOIN 图，决定数据移动策略：

-- 复杂查询：涉及不同分片键的 JOIN
SELECT c.name, SUM(o.total)
FROM customers c 
JOIN orders o ON c.id = o.customer_id
JOIN products p ON o.product_id = p.id
GROUP BY c.name;

-- Logical Planner 需要决定：
-- 1. customers 按 c.id 分片，orders 按 o.order_id 分片
--    → 需要重分布 orders 按 customer_id 对齐
-- 2. products 是小表 → 广播到所有分片
-- 3. SUM 可以先在分片内做部分聚合，再合并

为什么这个设计很精彩

五层逐级回退的设计精彩在于：绝大多数查询都在前两层就被处理了，不需要付出完整分布式规划的代价。只有真正复杂的查询才会走到后面的层次。

这就像一个分诊台——感冒发烧直接开药，不需要做全身检查。只有疑难杂症才需要调动各科专家会诊。

CockroachDB 的代价模型

CockroachDB 使用基于代价的优化器（Cost-Based Optimizer, CBO）。它的核心思想是：给每种执行方案估算一个”成本”数字，选成本最低的方案。

成本的组成

总成本 = CPU 成本 + IO 成本 + 网络成本

CPU 成本：处理每行数据的 CPU 开销
  - 简单过滤: 低
  - Hash 计算: 中
  - 排序: 高

IO 成本：从磁盘读取数据的开销
  - 索引扫描: 低（只读索引）
  - 全表扫描: 高（读整张表）

网络成本：跨节点传输数据的开销
  - 本地读: 0
  - 跨节点传输 1MB: 高
  - 跨数据中心传输 1MB: 非常高

在分布式环境下，网络成本往往是决定性因素。一个需要跨节点传输 100MB 数据的方案，即使 CPU 成本很低，总成本也可能远高于一个本地执行但 CPU 成本较高的方案。

统计信息：优化器的”地图”

代价估算依赖于统计信息——每张表有多少行？每列有多少不同的值？数据的分布是均匀的还是倾斜的？

-- CockroachDB 的统计信息收集
CREATE STATISTICS stats ON user_id FROM users;

-- 统计信息示例：
-- users 表: 1000万行
-- user_id 列: 1000万个不同值（高基数）
-- city 列: 100个不同值（低基数）
-- city = '北京' 的行数: 约50万行（5%）

-- 有了统计信息，优化器可以估算：
-- SELECT * FROM users WHERE city = '北京'
-- 预计结果行数: 1000万 × 5% = 50万行

分布式环境下，统计信息的维护更具挑战——每个分片的统计信息是局部的，全局统计需要汇总，而汇总过程本身就有延迟和误差。

OpenTenBase 的 pgxcship

OpenTenBase 的查询优化有一个独特的机制：pgxcship（src/backend/optimizer/util/pgxcship.c）——它判断一条查询是否可以”完整地下推到单个 Datanode 执行”。

可下推查询 vs 不可下推查询

-- 可下推：查询只涉及一个 Datanode 的数据
SELECT * FROM users WHERE user_id = 42;
-- pgxcship 判断: user_id 是分片键，hash(42) 定位到 dn1
-- → 整条 SQL 直接发给 dn1 执行

-- 不可下推：查询涉及多个 Datanode
SELECT * FROM users WHERE city = '北京';
-- pgxcship 判断: city 不是分片键，无法定位
-- → 需要发给所有 Datanode，收集结果后在 Coordinator 合并

pgxcship 的判断逻辑

// pgxcship.c 的简化判断流程
bool pgxc_is_query_shippable(Query *query) {
    // 1. 检查是否只涉及一个分布式表
    if (涉及多个不同分片键的表)
        return false;  // 不可下推
    
    // 2. 检查 WHERE 条件是否包含分片键等值条件
    if (WHERE 中有 分片键 = 常量)
        return true;   // 可以下推到单个节点
    
    // 3. 检查是否有不支持的操作（聚合、窗口函数等）
    if (有 不能在远程执行的操作)
        return false;  // 不可下推
    
    // 4. 协同分片检查
    if (所有涉及的表按相同键分片 && JOIN键是分片键)
        return true;   // 可以下推
    
    return false;
}

pgxcship 的局限性

pgxcship 是一个相对简单的二元判断——要么完全下推，要么不下推。它不像 Citus 的五层规划器那样有渐进式的回退策略，也不像 TiDB 的 Cascades 那样做成本对比。

这意味着一些可以部分下推的查询，在 OpenTenBase 中可能完全不下推，导致协调节点承受了不必要的负载。这是 OpenTenBase 查询优化器可以改进的方向之一——也是犀牛鸟 2026 参与者可以贡献的方向。

Citus 的渐进策略:
  完全下推 → 部分下推 → 广播JOIN → 拉回协调

TiDB 的 Cascades:
  对每种方案估算成本 → 选最优

OpenTenBase 的 pgxcship:
  可以完全下推 → 下推
  不能完全下推 → 全部拉回协调  ← 这里有优化空间

查询优化器对比

维度	TiDB (Cascades)	Citus (五层)	CockroachDB (CBO)	OpenTenBase (pgxcship)
框架	Cascades 搜索	逐级回退	代价优化	二元下推判断
搜索空间	大（枚举等价方案）	小（命中即停）	大（代价对比）	最小（是/否）
规划速度	中	快（OLTP快路径）	中	快
计划质量	高	中-高	高	中
复杂度	高	中	高	低
统计信息	丰富	利用 PG 统计	丰富	利用 PG 统计
适合场景	复杂查询 + HTAP	OLTP 为主	复杂查询	OLTP 为主

常见误区

误区一：”查询优化只是选择索引” → 正确理解：在分布式环境下，索引选择只是优化的一小部分。更重要的是数据移动策略（广播、重分布、下推）和 JOIN 顺序。错误的 JOIN 顺序可能导致传输数 GB 的中间结果。

误区二：”优化器总能找到最优方案” → 正确理解：优化器依赖统计信息来估算成本。如果统计信息过时或不准确，优化器可能选出一个很差的方案。这在分布式环境下更常见——全局统计信息的收集和更新本身就是一个挑战。

误区三：”Cascades 一定比简单方案好” → 正确理解：Cascades 框架虽然理论上更强大，但实现复杂、规划时间更长。对于 OLTP 负载（简单查询为主），Citus 的快路径 Router 可能比 Cascades 更高效——因为它几乎不花规划时间。

读完本章你能做什么

用”旅行规划”的类比解释查询优化器在做什么
说出分布式 JOIN 的四种策略及各自的适用场景
解释 TiDB Cascades 框架的 Memo 结构和规则驱动优化
描述 Citus 五层渐进式规划器的每一层做什么
理解 OpenTenBase pgxcship 的工作原理和局限性
理解谓词下推为什么是分布式查询优化中最重要的规则

导读目录：README.md 上一章：第 5 章 · 数据分片与再均衡——把大象切成小块下一章：第 7 章 · Citus 与 Vitess——不动内核的智慧