同一条 SQL，换个连接顺序可能慢 476 倍——这不是修辞，是本文模拟器的实测输出。查询优化器是数据库里最接近『人工智能』的部件：它看不懂业务语义，全靠统计信息和代价模型在千万个候选执行计划中赌博。本文实现一个迷你的基于代价优化器（CBO），完整复现选择率估计、连接顺序枚举、两种连接算法的代价对照，以及统计信息过期如何让优化器在错误的地图上导航。

一、优化器面对的问题规模

一条三表连接查询有 6 种连接顺序；十表连接有超过 362 万种。再乘上每张表的访问路径（全表扫描/索引扫描）和每步连接算法（嵌套循环/哈希/归并），计划空间爆炸到不可能全枚举。优化器的本质是在多项式时间内找一个足够好的计划，而非最优计划——System R 在 1979 年定下的这条务实原则至今未变。

二、CBO 的三块基石

三、完整可运行实现（Python 3，约 120 行）

#!/usr/bin/env python3
"""CBO 模拟：NLJ 与哈希连接对照、连接顺序枚举、
   笛卡尔积陷阱、统计过期误判"""
from itertools import permutations

class Stats:
    def __init__(self, rows, ndv):
        self.rows = rows
        self.ndv = ndv

STATS = {
    'users':  Stats(10000,  {'id': 10000}),
    'orders': Stats(100000, {'uid': 10000, 'item_id': 500}),
    'items':  Stats(500,    {'id': 500}),
}
SEL = {'users': 0.6, 'orders': 0.25, 'items': 1.0}

# 连接谓词的 NDV；users 与 items 间无连接谓词 -> None 表示笛卡尔积
JOIN_NDV = {frozenset(['users', 'orders']): 10000,
            frozenset(['orders', 'items']): 500,
            frozenset(['users', 'items']): None}

def join_card(l, r, pair):
    ndv = JOIN_NDV[frozenset(pair)]
    if ndv is None:
        return l * r            # 无连接谓词：笛卡尔积爆炸
    return l * r / ndv

def nlj_cost(l, r):
    return l + l * r            # 嵌套循环：左侧每行扫一遍右侧

def hj_cost(l, r):
    return l + r                # 哈希连接：各扫一遍

def evaluate(order, use_nlj):
    total = sum(STATS[t].rows for t in order)   # 三表扫描
    left_rows = STATS[order[0]].rows * SEL[order[0]]
    joined = [order[0]]
    for nxt in order[1:]:
        right_rows = STATS[nxt].rows * SEL[nxt]
        pair = (joined[-1] if len(joined) == 1 else 'orders', nxt)
        if len(joined) > 1:
            pair = ('orders', nxt) if 'orders' in joined \
                   else (joined[0], nxt)
        total += (nlj_cost if use_nlj else hj_cost)(left_rows,
                                                    right_rows)
        left_rows = join_card(left_rows, right_rows, pair)
        joined.append(nxt)
    return total, left_rows

print('=== 基于代价的优化器模拟 ===')
print('查询: users ⋈ orders ⋈ items WHERE age>30 AND status=paid')
print('过滤后基数: users=6000, orders=25000, items=500')
print('注意: users 与 items 之间没有连接谓词（先连它俩 = 笛卡尔积）')

for label, use_nlj in [('嵌套循环连接(NLJ)', True),
                       ('哈希连接(HJ)', False)]:
    print()
    print('--- 连接算法 = %s ---' % label)
    results = []
    for perm in permutations(['users', 'orders', 'items']):
        cost, card = evaluate(perm, use_nlj)
        results.append((cost, perm, card))
        print('  %-22s 代价 %14.0f  中间结果峰值 %.0f 行'
              % (' ⋈ '.join(perm), cost, card))
    results.sort()
    print('  最优: %s (%.0f)  最差: %s (%.0f)  差距 %.0f 倍'
          % (' ⋈ '.join(results[0][1]), results[0][0],
             ' ⋈ '.join(results[-1][1]), results[-1][0],
             results[-1][0] / results[0][0]))

print()
print('--- 统计信息过期：优化器的阿喀琉斯之踵 ---')
print('orders 实际 100000 行，统计却停留在 1000 行（过期）')
backup = STATS['orders'].rows
STATS['orders'].rows = 1000
stale = []
for perm in permutations(['users', 'orders', 'items']):
    cost, _ = evaluate(perm, False)
    stale.append((cost, perm))
stale.sort()
print('优化器按过期统计选出: %s，估计代价仅 %.0f'
      % (' ⋈ '.join(stale[0][1]), stale[0][0]))
STATS['orders'].rows = backup
real_cost, _ = evaluate(stale[0][1], False)
best_cost, _ = min(((evaluate(p, False)[0], p)
        for p in permutations(['users', 'orders', 'items'])))
print('该计划的真实代价: %.0f —— 估计偏差 %.1f 倍'
      % (real_cost, real_cost / stale[0][0]))
print('真实最优计划代价: %.0f' % best_cost)
print('结论: 过期统计让优化器在错误地图上导航 -> 必须定期 ANALYZE')

四、真实运行输出与解读

以上代码在 Python 3 下原样运行（仅依赖 itertools），输出如下：

=== 基于代价的优化器模拟 ===
查询: users ⋈ orders ⋈ items WHERE age>30 AND status=paid
过滤后基数: users=6000, orders=25000, items=500
注意: users 与 items 之间没有连接谓词（先连它俩 = 笛卡尔积）

--- 连接算法 = 嵌套循环连接(NLJ) ---
  users ⋈ orders ⋈ items 代价      157631500  中间结果峰值 15000 行
  users ⋈ items ⋈ orders 代价    75006116500  中间结果峰值 7500000 行
  orders ⋈ users ⋈ items 代价      157650500  中间结果峰值 15000 行
  orders ⋈ items ⋈ users 代价      162660500  中间结果峰值 15000 行
  items ⋈ users ⋈ orders 代价    75006111000  中间结果峰值 150000000 行
  items ⋈ orders ⋈ users 代价      162636000  中间结果峰值 15000 行
  最优: users ⋈ orders ⋈ items (157631500)
  最差: users ⋈ items ⋈ orders (75006116500)  差距 476 倍

--- 连接算法 = 哈希连接(HJ) ---
  users ⋈ orders ⋈ items 代价         157000  中间结果峰值 15000 行
  users ⋈ items ⋈ orders 代价        3142000  中间结果峰值 7500000 行
  orders ⋈ users ⋈ items 代价         157000  中间结果峰值 15000 行
  orders ⋈ items ⋈ users 代价         167000  中间结果峰值 15000 行
  items ⋈ users ⋈ orders 代价        3142000  中间结果峰值 150000000 行
  items ⋈ orders ⋈ users 代价         167000  中间结果峰值 15000 行
  最优: orders ⋈ users ⋈ items (157000)
  最差: users ⋈ items ⋈ orders (3142000)  差距 20 倍

--- 统计信息过期：优化器的阿喀琉斯之踵 ---
orders 实际 100000 行，统计却停留在 1000 行（过期）
优化器按过期统计选出: orders ⋈ users ⋈ items，估计代价仅 18400
该计划的真实代价: 157000 —— 估计偏差 8.5 倍
真实最优计划代价: 157000
结论: 过期统计让优化器在错误地图上导航 -> 必须定期 ANALYZE

五、理论分析

5.1 计划枚举：动态规划与左深树

System R 的经典做法是用动态规划自底向上构造计划：先算所有单表最优访问路径，再两两组合、三三组合……每步只保留同一结果集上代价最低的子计划（最优子结构），复杂度从阶乘级降到指数级 O(3^n)。再叠加『只考虑左深树』的剪枝（右侧永远是基表，便于流水执行与索引利用），十表连接也能在毫秒级完成枚举。PostgreSQL 在超过 geqo_threshold（默认 12 表）后切换到遗传算法 GEQO，用随机搜索换时间。

5.2 基数估计的误差传播

连接基数公式假设两表连接列独立且均匀分布——现实中数据倾斜与列间相关性无处不在（城市列与省份列强相关）。误差在多表连接中指数传播：n 表连接时估计误差可放大到 (误差因子)^n。这是优化器最深的阿喀琉斯之踵，也是直方图、多列统计（CREATE STATISTICS）、以及近年学习型基数估计（用 ML 模型替代公式）研究火热的原因。

5.3 代价模型的哲学

代价模型的目的不是预测真实执行时间，而是给候选计划正确排序——只要相对序不错，绝对值偏多少无所谓。理解这一点才能解释很多『怪异』现象：随机 I/O 与顺序 I/O 的固定权重比（PostgreSQL 的 random_page_cost=4 vs seq_page_cost=1）在 SSD 时代是失真的，但只要排序不错，计划依然正确。代价模型是罗盘不是秒表。

六、工程应用

七、常见误区

八、参考文献

  1. P. Selinger et al. (1979). Access Path Selection in a Relational Database Management System. ACM SIGMOD.（System R 优化器原始论文，CBO 的源头）
  2. G. Graefe (1995). The Cascades Framework for Query Optimization. IEEE Data Engineering Bulletin.（现代优化器架构）
  3. V. Leis et al. (2015). How Good Are Query Optimizers, Really? VLDB.（用 Join Order Benchmark 实测主流优化器的里程碑研究）
  4. PostgreSQL Documentation: Chapter 14 Performance Tips 与 Chapter 75 Planner Statistics。
  5. MySQL Documentation: Optimizing SQL Statements 与 hash join、optimizer switch 相关章节。
← 返回文章列表