查询优化器:SQL 到底是怎么跑起来的

#TL;DR

关系模型最被低估的一个性质,就是 SQL 只描述你要什么,而不是怎么拿。在 SELECT 和结果之间,有一块软件——查询优化器——它会解析你的查询、重写它、对几十到几千种可能的执行策略估算开销,然后挑一种。现代基于代价的优化器可以追溯到 1970 年代末 IBM 的 System R 项目,特别是 Pat Selinger 1979 年的论文。四十七年后,查询优化仍然是生产数据库里”这查询为什么慢”瞬间最大的单一来源——理解优化器怎么思考,是”会写 SQL”和”会调 SQL”之间最主要的技能鸿沟。

#它的工作

给这样一条查询:

SELECT c.name, SUM(o.amount)
FROM customers c
JOIN orders o ON o.cust_id = c.id
WHERE c.city = 'London'
GROUP BY c.name
HAVING SUM(o.amount) > 1000;

数据库得决定:

• 先读哪张表。 读 customers、过滤到伦敦、再查 orders?还是先读 orders、再连到 customers?
• JOIN 用哪种算法。 嵌套循环?哈希?排序归并?
• 用哪些索引。 customers.city 上有索引吗?orders.cust_id 上呢?
• GROUP BY 怎么排序或哈希。 已经按 c.name 排好了吗?还是要在内存里建一张哈希表?
• 什么时候应用 HAVING 和过滤。 能不能尽量早地把过滤挪下去(predicate pushdown)?

这些决定每个都彼此独立,组合起来爆炸得很快。10 张表的 join 有 10! = 360 万种顺序,每种又带多种算法,每种又带索引选择。优化器不可能全试一遍,它必须聪明地决定哪些方案值得考虑。

#四阶段流水线

一条 SQL 查询从被发出到被执行,大致经过四个阶段。

┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│   解析    │──►│   改写    │──►│   规划    │──►│   执行   │
└──────────┘   └──────────┘   └──────────┘   └──────────┘

解析 — 把 SQL 字符串变成解析树。语法错误在这里冒出来。输出:一棵抽象语法树,大致忠实于用户敲进来的内容。

改写(逻辑规划) — 应用不改变语义、但简化树的变换。例子:展开视图(把对视图的引用替换成它的定义)、常量折叠(WHERE 1 = 1 被剔除)、展平子查询、predicate pushdown(把过滤挪到离表更近的地方)、简化外连接。

规划(物理规划,也叫优化) — 决定实际执行策略。这里挑 join 顺序、join 算法、索引选择、聚合策略。输出是一棵执行计划——一棵物理操作符树。

执行 — 真正跑计划。读页、应用过滤、做 join、流式输出。等执行开始时,所有有意思的决定都已经做完了。

#逻辑计划 vs. 物理计划

看一眼计划真正长什么样是值得的。Postgres 的 EXPLAIN 对上面那条查询可能输出:

 GroupAggregate  (cost=0.71..24.86 rows=10 width=40)
   Group Key: c.name
   Filter: (sum(o.amount) > 1000)
   ->  Nested Loop  (cost=0.71..24.76 rows=25 width=14)
         ->  Index Scan using customers_city_idx on customers c
               (cost=0.29..8.30 rows=5 width=10)
               Index Cond: (city = 'London')
         ->  Index Scan using orders_cust_id_idx on orders o
               (cost=0.43..3.27 rows=5 width=8)
               Index Cond: (cust_id = c.id)

从下往上读:

1. 用 customers_city_idx 找 city = ‘London’ 的行。估算 5 行。
2. 对每行,用 orders_cust_id_idx 找匹配的订单。估算每个客户 5 条。
3. 把连接后的配对送进 GroupAggregate,按 name 累加金额。
4. 应用 HAVING 过滤。

优化器选了嵌套循环连接,因为它预期外侧(伦敦客户)很小。如果客户更多,它可能会选哈希连接。

cost=0.71..24.86 是优化器以内部单位估的开销,rows=10 是它对这一步输出行数的猜测。两者都是估计值,它们是计划选择的关键输入。

#基于代价的优化

现代优化器是基于代价的。它们估算每个候选计划的代价,然后挑最便宜的。相对的——基于规则的优化——按固定规则来,不考虑数据特征,在 1990 年代基本已经死掉,因为它在非平凡的工作负载上产出的计划糟糕。

代价估算依赖两样东西:

数据的统计信息。每个现代数据库都为每列维护统计:总行数、唯一值数、值的分布(常用直方图)、null 比例、平均行宽。Postgres 通过 ANALYZE 收集它们,别的数据库有类似机制。

代价模型,把计划操作换算成代价单位。对 N 行做顺序扫描,代价正比于读的页数;对 N × M 行做嵌套循环,代价正比于 N × M;一次索引查找,代价大约正比于 log M。其中每一项都靠 seq_page_cost(读一页顺序页的代价)、cpu_tuple_cost(在内存里处理一条元组的代价)这样的常数来调。

把统计和代价模型合起来,就能给任何候选计划一个估算代价。优化器在一组启发式引导下,去探索计划空间,挑最便宜的那一条。

#基数估算:会出错的那一块

代价估算最关键的输入是基数——某个操作会产生多少行。

对一个简单谓词,比如 WHERE city = 'London',优化器查 city 列的直方图。如果 ‘London’ 在样本里占 5%,而表有 10,000 行,估计就是 500 行。

对一个 JOIN,优化器先估两边各自输出多少行,再估多少行会匹配上。两张 1,000 和 10,000 行的表,在一个外键上连接,如果外键完全填充,优化器可能估出 10,000 行。

基数估算是现实优化器里最常出错的地方。它的失败产出了那种经典的”小数据跑得好、大数据惨爆”的计划:

• 列之间相关。 优化器假设列独立。若 city = 'London' 与 country = 'UK' 高度相关,对”两者同时满足”的估计往往偏低。
• 数据倾斜。 100 桶的直方图捕不到”60% 的行某状态列值是 'pending'”这种现实,尤其当桶边界不对齐时。
• 谓词叠加。 多个过滤常被假设按乘法组合。若每个过滤留下 10% 的行,四个过滤就被估成留下 0.01%——通常太激进。
• 统计过期。 如果 ANALYZE 最近没跑,优化器看到的分布与当前数据不符。

基数估算一错,优化器就是在按错的数据量去挑计划。这个计划被期望处理 100 行,实际却处理了 1000 万行——外层的嵌套循环对 100 很美妙,对 1000 万就是灾难。这是生产数据库里最常见的性能问题。

EXPLAIN ANALYZE 正是为诊断这种情况而存在——它会给出每一步估算行数和实际行数的对比。

->  Nested Loop  (cost=... rows=100 width=...)
              (actual rows=10432892 loops=1)

估计与实际差了五个数量级,就说明计划是错的,而原因是基数估算。修法通常是更好的统计信息、查询改写来帮助优化器,或显式提示。

#索引的选择

优化器会考虑相关列上的每一个索引,并估算每条潜在访问路径的代价:

• 顺序扫描。 读整张表的每一行。代价正比于表大小。
• 索引扫描。 沿着索引(B 树或哈希)走一遍,读出匹配的行。代价正比于结果大小,而不是表大小——但每行多一次随机 I/O。
• 仅索引扫描。 如果所需的所有列都在索引里,就完全跳过表。快得多。
• 位图索引扫描。 先把匹配的行 ID 构造成位图,然后按物理顺序读那些行。适合中等大小的结果集。

选哪种,取决于过滤预期返回多少行。对一张大表的 1% 来说,索引扫描快得多;对一张表的 50% 来说,顺序扫描其实更好——索引扫描的随机 I/O 超过了它带来的收益。

这就是为什么加一个索引不总能让查询变快。如果过滤选择性不高、优化器本来就选了顺序扫描,加索引会被忽略;如果优化器选了新索引、而过滤实际上不如它看起来那么选择性(基数估算错了),性能反而可能变差。

#连接顺序

对一个连接 N 张表的查询,优化器要选一种顺序。理论上,所有 N! 种顺序都是候选。实际上,优化器只用动态规划考察左深或**茂密(bushy)**的计划,直到某个阈值(通常 8-12 张表),再之上就切到启发式。

动态规划(Selinger 式)。 从小 join 构建大 join。对 2 张表,试两种顺序、所有算法,挑最好;对 3 张表,取每个 2 表子计划再加第三张表,以各种方式并起来;对 N 张表,重复。这样大致产出 O(2^N) 个候选计划,在 8-12 张表内可控。

大型连接用贪心/启发式。 超过 DP 阈值,优化器退到启发式:“先连小的”、“偏好带选择性过滤的连接”、“避免笛卡尔积”。它们产出计划很快,但不保证最优。Postgres 有 geqo(遗传查询优化),针对 12 张以上表连接,在候选计划上跑遗传算法。

1979 年的 Selinger 论文(“Access Path Selection in a Relational Database Management System”)引入了 DP 方法,大致仍是现代优化器的工作方式。现代的改进主要在更好的代价估算和对大型连接更聪明的启发式,核心算法没变。

#为什么同一条查询能又快又慢

开发者带点懊悔地问的问题:“为什么这查询昨天 50 ms,今天 5 分钟?”

几种原因:

• 统计更新导致计划变了。 ANALYZE 跑了一次,优化器看到的数据分布变了,它挑了不同的计划。对当前数据来说,新计划更差。
• 参数嗅探。 数据库为某个具体参数值缓存了一个计划。下一次用不同参数值调用时,复用缓存的计划,但这个计划对新值不合适。
• 数据增长跨过了一个阈值。 1,000 行的表上顺序扫描没问题;到了 100,000 行就慢。优化器可能还没意识到,因为统计跟不上。
• 索引膨胀或统计陈旧。 优化器估某个索引会很快,实际索引因为更新已经膨胀,比估算差得多。
• 其他查询在抢资源。 在空闲系统上很快的计划,在忙碌系统上就慢。
• 新加或新删了索引。 访问路径变了。

诊断”为什么慢”一般就是跑 EXPLAIN ANALYZE,盯两样东西:估计行数与实际行数之间的大落差(基数问题)、以及出乎意料地昂贵的步骤(访问路径错)。

#查询提示:覆盖优化器

一些数据库允许给优化器提示——强制某条访问路径或某种连接算法的指令。例如:

• Oracle: SELECT /*+ USE_NL(o, c) */ ...
• SQL Server: SELECT ... FROM o INNER LOOP JOIN c ...
• MySQL: SELECT ... FROM t1 FORCE INDEX (idx1) ...
• Postgres: 原生不支持提示,不过 pg_hint_plan 扩展加上了。

查询提示是钝器。它们用你的判断覆盖优化器的代价分析。它们有用的情形:

• 你知道优化器对这条具体查询一贯选错。
• 你已经试过其他办法(更好的统计、模式调整、查询改写)。
• 工作负载稳定,最优计划不会变。

危险在于:它们会顽固地留在那里,经过本该让情况自愈的变化依然生效。 今天强制走索引扫描的提示,等你把那个索引删了、升级了数据库、改了数据分布之后,它仍然会强制走那个索引扫描。Postgres 选择不原生支持提示,带着一种意识形态——立场是:如果优化器错了,应该修优化器,不应该绕开它。

#优化器为什么难

研究了五十年,查询优化仍然是活跃领域。根本困难:

• 计划空间巨大。 对 20 张表的 join,可能计划数比可观测宇宙里的原子还多,你只能探索极小一部分。
• 基数估算未解。 基于直方图、采样、机器学习(确有用 ML 做估算器的严肃研究)的估算器,在真实数据上都会按可预测的方式失败。
• 代价依赖于缓存。 冷缓存下的顺序扫描和热缓存下的完全两样。优化器对缓冲池内容的模型并不完美。
• 负载漂移。 为上个月工作负载优化过的计划,对这个月的负载可能很差。自适应查询处理(在执行中重新思考计划)是个持续中的研究方向。
• 相互影响。 并发跑的许多查询在资源上彼此竞争,一个”单独看一条查询”的优化器难以建模这种情况。

上述每一条都是活的研究话题。查询优化器至今仍是任何数据库里最难的软件之一,在每一个成熟数据库产品里,它都占掉相当大一份的性能工程精力。

#优化器真正解锁了什么

关系模型那篇文章说,SQL 描述取什么,数据库引擎决定怎么取。这句话之所以有意义,全靠优化器的存在。没有它,“声明式查询语言”就只是语法;有了它,SQL 才是真正意义上面向数据访问的抽象。

回报是同样的 SQL 能随数据库进步而继续工作。你的查询在升级之后可能快了 100 倍,因为优化器变聪明了——你一行代码都没改。可以加索引,优化器会用;数据分布变,优化器会适应。查询是稳定的契约,执行是自适应的。

这是关系模型默默兑现的承重承诺。Codd 1970 年的论文倡议数据独立性——程序不该知道数据怎么存。优化器正是把这份承诺在实践中落实的组件。它让 SQL 变成一门写起来高效的语言,也让 SQL 变成一门调起来让人头疼的语言。两件事同时成立,并且已经同时成立了近五十年。