如何设计查询优化器
从 MiniDB 的“固定全表扫描太慢”开始，长出访问路径、统计信息、代价模型、Join 顺序、计划解释和回归保护
阅读定位: 这页只讲单机关系型数据库里查询优化器的最小主线：同一句 SQL 有多种执行方式时，数据库怎样选一个足够好的计划。它不展开所有 Join 算法、分布式优化、向量化执行、列存优化或完整 Cascades / Volcano 框架。
一句话原则: 查询优化器不是“让 SQL 自动变快”的魔法。它是在信息不完整、统计会过期、数据会倾斜的情况下，用估算成本选择执行计划，并且要能解释为什么选错。
MiniDB 已经能执行 SQL。最简单的执行器永远从表第一页扫到最后一页，再逐行过滤。
select * from entries
where user_id = 7
and occurred_on >= '2026-01-01'
and occurred_on < '2026-02-01'
Plan v1:
SeqScan(entries)
Filter(user_id = 7 and date range)
| 它能工作 | 为什么不够 | 下一步需要什么 |
|---|
| 任何查询都能跑出正确结果 | 小表还行，大表每次都扫全表 | 知道有哪些可选访问路径 |
| 实现简单 | 有索引也不用，白白浪费 B+Tree | 让 Planner 能选择 IndexScan |
| 结果稳定 | 不同 SQL 复杂度差异巨大，却用同一套计划 | 为不同查询生成不同计划 |
阶段验收: 你能说清：优化器不是为了让数据库“聪明”，而是为了避免正确但灾难性慢的执行路径。
第一反应是规则优化：只要 where 条件命中索引，就用 IndexScan。但如果命中的行很多，走索引再回表可能比顺序扫表更慢。
| 查询 | 规则优化器选择 | 为什么可能错 |
|---|
where id = 10086 | 主键 IndexScan | 很好，只返回一行 |
where status = 'PAID' | status 索引 | 如果 90% 都是 PAID，索引回表会产生大量随机读 |
where amount > 0 | amount 索引 | 几乎全表都满足，扫索引再回表不划算 |
where occurred_on between ... | 日期索引 | 要看时间范围覆盖多少数据 |
这一步的教训: “有索引就用”不是优化器，只是另一种固定规则。优化器必须估算选择性。
MiniDB 需要先知道表大概有多少行、字段有多少不同值、值分布是否均匀，才能判断过滤条件会留下多少行。
| 统计信息 | 回答什么问题 | 没有它会怎样 |
|---|
| row_count | 表有多大 | 不知道 SeqScan 成本 |
| page_count | 表占多少页 | 不知道 IO 成本 |
| distinct_count | 某列不同值多少 | 无法估算等值过滤留下多少行 |
| min / max | 范围条件覆盖多大区间 | 无法估算日期、金额范围 |
| histogram / top values | 数据是否倾斜 | 会把热门值和冷门值估成一样 |
entries stats:
row_count: 10,000,000
page_count: 120,000
distinct(user_id): 500,000
top_values(status): PAID=90%, FAILED=1%, PENDING=9%
阶段验收: 对同一个 status 索引，你能解释为什么 status='FAILED' 适合索引，而 status='PAID' 可能不适合。
有了统计信息，MiniDB 还要把不同计划的代价估到同一套单位里：读多少页、随机读多少、吐出多少行、CPU 过滤多少次。
| 候选计划 | 大概成本项 | 什么时候便宜 |
|---|
| SeqScan | 读全表页 + 每行过滤 CPU | 返回比例很高，或表很小 |
| IndexScan + 回表 | 读索引页 + 随机读 heap page + 可见性判断 | 返回行很少，索引选择性高 |
| Covering Index Scan | 只读索引页，不回表 | 查询字段都在索引里 |
| Sort | 内存排序或外部排序 IO | 没有可用顺序索引时 |
cost(IndexScan):
index_pages_touched
+ estimated_rows * random_heap_page_cost
+ estimated_rows * visibility_check_cost
cost(SeqScan):
table_pages
+ row_count * filter_cpu_cost
不要误读: 代价模型不是精确物理仿真。它只是尽量把“哪个计划更可能便宜”估得不离谱。
很多慢计划不是最后一步慢，而是中间结果太大。优化器要尽早过滤行、尽早只取需要的列。
| 优化动作 | 失败前是什么样 | 为什么有用 |
|---|
| Predicate Pushdown | 先读出很多行，再在上层过滤 | 越早过滤，后面处理的数据越少 |
| Projection Pushdown | 每行带着所有字段往上传 | 只读需要字段，减少内存和 IO |
| Limit Pushdown | 先算完整结果再取前 N 条 | 能提前停止扫描或排序 |
| Order-aware Scan | 扫描后再排序 | 如果索引天然有序，可以避免 sort |
阶段验收: 同一条 SQL，优化前后计划树里中间结果行数应该明显不同，而不是只换了节点名字。
单表查询只是开始。三张表 Join 时，先 Join 哪两张，可能决定中间结果是几千行还是几千万行。
select *
from users u
join entries e on e.user_id = u.id
join categories c on c.id = e.category_id
where u.region = 'CN'
and c.kind = 'tax'
| Join 顺序 | 可能的中间结果 | 问题 |
|---|
| users → entries → categories | 先筛 region，再找 entries | 如果 CN 用户很多，仍可能很大 |
| categories → entries → users | 先筛 tax 类目，再找 entries | 如果 tax 类目很少，可能更便宜 |
| entries → users → categories | 先扫最大事实表 | 通常危险，除非 entries 已被强条件过滤 |
关键变化: 优化器不只是选索引。它还要决定关系之间的连接顺序，否则中间结果会爆炸。
同样是 Join，执行方式也不止一种。MiniDB 第一版可以支持 Nested Loop、Index Nested Loop 和 Hash Join 三个候选。
| Join 算法 | 适合什么 | 失败场景 |
|---|
| Nested Loop Join | 外表很小，内表也小 | 两张大表会变成灾难 |
| Index Nested Loop Join | 外表较小，内表 Join key 有索引 | 外表太大时随机查内表太多 |
| Hash Join | 等值 Join，构建侧能放进内存或可分批 | 内存不足会 spill，非等值 Join 不适用 |
| Merge Join | 两边已有序或排序成本可接受 | 需要排序，第一版可先不实现 |
阶段验收: 同一组表，在“小外表 + 内表索引”和“两张大表等值 Join”下，MiniDB 应该选择不同 Join 算法。
优化器最大的尴尬是：它的判断建立在统计信息上，而统计信息可能早就过期了。数据刚导入、热门用户暴涨、状态分布变化，都会让计划变差。
| 失败场景 | 优化器误判 | 需要的设计 |
|---|
| 导入一千万新行，但 stats 还是旧的 | 以为表很小，选择错误 Join 顺序 | ANALYZE / auto analyze |
| 某个热门 user_id 占 30% 数据 | 按均匀分布估算，只以为返回几行 | top values / histogram |
| 多列强相关 | 把两个条件当独立，低估或高估结果数 | 多列统计或保守估算 |
| 参数化 SQL | 用一个参数的计划套到另一个参数 | plan cache 失效策略或参数敏感计划 |
现实边界: 优化器永远可能错。设计上必须让它能被解释、被观测、被刷新统计、被必要时 hint 或改写查询救回来。
如果 MiniDB 只能执行计划，却不能解释计划，使用者就不知道慢在哪里。EXPLAIN 要把估算和实际尽量暴露出来。
| EXPLAIN 字段 | 它回答什么 | 排障价值 |
|---|
| plan tree | 执行节点是什么顺序 | 看是否走了预期索引或 Join 顺序 |
| estimated rows | 优化器以为会返回多少行 | 和实际差很多说明统计或模型错 |
| estimated cost | 为什么选这个计划 | 比较候选计划代价 |
| actual rows / time | 真实执行表现 | 定位估算错误、执行器慢或 IO 慢 |
| chosen index / join type | 关键选择是什么 | 帮助判断是否需要新索引或刷新统计 |
EXPLAIN ANALYZE:
HashJoin estimated_rows=2,000 actual_rows=800,000
IndexScan categories_kind_idx estimated_rows=3 actual_rows=2
SeqScan entries estimated_rows=20,000 actual_rows=7,500,000
阶段验收: 一条慢 SQL 至少能回答：慢是因为没走索引、Join 顺序错、估算错，还是执行器本身慢。
| 阶段 | 遇到的问题 | 长出的设计 | 真正吸收点 |
|---|
| 固定 SeqScan | 正确但大表太慢 | 访问路径选择 | SQL 有多种执行方法 |
| 有索引就用 | 低选择性索引会更慢 | 选择性估算 | 索引不是永远便宜 |
| 不知道数据分布 | 估不出返回行数 | 统计信息 | 优化依赖对数据的认知 |
| 候选计划很多 | 无法比较谁更便宜 | 代价模型 | 用统一尺子比较计划 |
| Join 中间结果爆炸 | 顺序选错会灾难 | Join 枚举 | 优化器核心在控制中间结果 |
| 统计过期 | 优化器自信选错 | ANALYZE / EXPLAIN | 优化器必须可解释可纠偏 |
| 练习 | 故意制造什么失败 | 通过标准 |
|---|
| SeqScan vs IndexScan | 一张百万行表，按主键查一行 | 选择 IndexScan，明显少读页 |
| 低选择性索引 | status='PAID' 命中 90% 行 | 不盲目走 status 索引 |
| 数据倾斜 | 一个热门 user_id 占大量数据 | top values 统计能改变估算 |
| Join 顺序 | 三表 Join，过滤条件在小维表上 | 先从高选择性表开始 |
| Join 算法 | 小外表 + 内表索引、两张大表等值 Join | 分别选 Index Nested Loop 和 Hash Join |
| 统计过期 | 导入大量数据后不 ANALYZE | EXPLAIN 能看出估算行数和实际行数严重偏离 |
| 计划回归 | 更新统计后计划变差 | 有慢 SQL 样本和 EXPLAIN 对比 |
如何设计 MVCC
如果你还没理解为什么 IndexScan 后仍要做版本可见性判断，先回到
如何设计 MVCC。
如何设计分布式数据库
当单机 MiniDB 的存储、索引、事务、MVCC 和优化器都具备以后，下一步看
如何设计分布式数据库：复制、分片、分布式事务和跨节点查询计划。
总结: 查询优化器不是概念堆，而是被错计划逼出来的选择系统：固定 SeqScan 太慢，于是要选访问路径；有索引就用会翻车，于是要估算选择性；估算离不开统计信息；候选计划要用代价模型比较；Join 顺序会放大中间结果；统计过期会让优化器自信地错；所以 EXPLAIN、ANALYZE 和计划回归保护也是优化器设计的一部分。