【SQLite 内核】查询计划器与统计：没有 ANALYZE 时的启发式与代价估计边界

前十篇拆完了一次 SELECT 如何被编译成字节码（第 5、6 篇）、页面如何在 B-Tree 里被访问（第 4 篇）、日志与锁如何保证写路径正确（第 7–10 篇）。但还没回答一个更早发生的问题：同一条 SQL，sqlite3_prepare_v2 凭什么决定走哪条访问路径——用哪个索引、要不要建临时索引、连接顺序先跑哪张表。这一层是查询计划器（query planner），官方专门有 Query Planning 与 EXPLAIN QUERY PLAN 两份文档描述它的行为。

常见误区是把 SQLite 的计划器直接类比 PostgreSQL 式的代价优化器（CBO），以为背后是同一套统计驱动的穷举搜索。SQLite 官方文档自己把计划器称作”an AI that tries to pick the fastest algorithm”——这句话与其说是自谦，不如说是精确：嵌入式场景下，sqlite3_prepare_v2 必须在毫秒级完成决策，代价模型天生要向”够用、够快”妥协，而不是向”理论最优”妥协。本文钉三件事：

1. EXPLAIN QUERY PLAN 输出 SEARCH/SCAN/USING (COVERING) INDEX 的判定规则，用本机 3.53.2 实测两条真实路径核对。
2. ANALYZE 具体往 sqlite_stat1（及 SQLITE_ENABLE_STAT4 下的 sqlite_stat4）写了什么，以及没跑过 ANALYZE 时计划器用的是哪些写在文档里的具体猜测数字。
3. 连接顺序选择用的 N3 启发式算法与其复杂度边界，对照官方文档自己承认的”star-query”计划质量问题，说明”嵌入式不追求 PG 式穷举优化器”这句话背后的具体证据。

本文是「SQLite 内核」系列第 11 篇（共 17 篇）。→ 系列目录

篇目	核心内容
第 10 篇 · 事务与隔离	DEFERRED/IMMEDIATE/EXCLUSIVE、隔离叙事
第 11 篇 · 查询计划器与统计	SEARCH/SCAN 判定、sqlite_stat1、无统计启发式、N3 join 排序
第 12 篇 · 索引与 covering scan	覆盖索引、自动索引边界

版本锚定：官方 Query Planning（sqlite.org/queryplanner.html）、EXPLAIN QUERY PLAN（sqlite.org/eqp.html）、The SQLite Query Optimizer Overview（sqlite.org/optoverview.html）、The Next Generation Query Planner（sqlite.org/queryplanner-ng.html）、ANALYZE（sqlite.org/lang_analyze.html）。本文实测锚定本机 SQLite 3.53.2，编译时带 SQLITE_ENABLE_STAT4。EQP 输出格式官方明确标注”intended for interactive debugging only”，版本间可能变化，本文引用的输出只对 3.53.2 负责。

一、SEARCH 与 SCAN：EQP 的两种基本判定

EXPLAIN QUERY PLAN 文档给出的判定规则很短：每一条被扫描的表在输出里对应一行，detail 字段以 SCAN 或 SEARCH 开头——SCAN 表示全表扫描（包括按索引顺序走遍全表的情况），SEARCH 表示只访问表中一个子集。

用本机建的测试表验证（复现脚本：reproduce/11-query-plans.sh）：

CREATE TABLE orders(id INTEGER PRIMARY KEY, user_id INTEGER, amount REAL, note TEXT);
CREATE INDEX idx_orders_user ON orders(user_id);
-- 20000 行，user_id 均匀分布在 [0, 500) 之间

以下输出经本机 sqlite3 3.53.2 实际执行：

$ sqlite3 sk-planner.db "EXPLAIN QUERY PLAN SELECT amount FROM orders WHERE user_id=10;"
QUERY PLAN
`--SEARCH orders USING INDEX idx_orders_user (user_id=?)

$ sqlite3 sk-planner.db "EXPLAIN QUERY PLAN SELECT * FROM orders WHERE amount>5;"
QUERY PLAN
`--SCAN orders

user_id=10 有索引可用，计划器选 SEARCH；amount 上没有索引，只能 SCAN。这不是”计划器选错了”——amount 上没有 B-Tree 结构可供二分查找（第 4 篇的 index b-tree 只对建过索引的列存在），全表扫描是唯一正确的执行方式。

flowchart TD
  q["WHERE column = ?"] --> hasidx{"usable index<br/>on this column?"}
  hasidx -->|"yes"| search["SEARCH table<br/>USING INDEX idx (col=?)"]
  hasidx -->|"no"| scan["SCAN table<br/>(full table scan)"]
  search --> cov{"all referenced columns<br/>inside the index?"}
  cov -->|"yes"| covidx["USING COVERING INDEX<br/>(see article 12)"]
  cov -->|"no"| plainidx["USING INDEX<br/>(rowid lookup still needed)"]

amount>5 这条路径值得多说一句：官方文档明确写道 SCAN 也包含”按索引顺序遍历全表”的情形——如果计划器为了避免额外排序而选择沿着某个索引顺序整表扫，输出仍然是 SCAN，只是会附带 USING INDEX idx。SCAN/SEARCH 的区分标准是”访问的是全表还是子集”，不是”用不用索引”。

二、ANALYZE 写入了什么：sqlite_stat1 的具体语义

在没有运行 ANALYZE 之前，orders 库里根本不存在 sqlite_stat1 表——统计信息不是默认存在的元数据，是显式命令的产物：

$ sqlite3 sk-planner.db "SELECT name FROM sqlite_master WHERE name LIKE 'sqlite_stat%';"
（空，尚未 ANALYZE 时无输出）

$ sqlite3 sk-planner.db "ANALYZE;"
$ sqlite3 sk-planner.db "SELECT * FROM sqlite_stat1;"
orders|idx_orders_user|20000 40

sqlite_stat1 每行是 (tbl, idx, stat)：stat 字段的第一个数字是该索引扫过的总行数估计，后续数字依次是”索引最左 1 列、最左 2 列、……相同取值平均对应多少行”。本例 user_id 均匀分布在 500 个不同值上（abs(random()) % 500），20000 行除以 500 恰好是 40——"20000 40" 精确对应这个可验证的构造：总行数 20000，user_id 每个取值平均对应 40 行。这也是官方 Query Planning 文档举的例子（fruit/state 两个候选索引）里”哪个索引更有选择性”判断的直接依据：ANALYZE 之后，计划器知道走哪个索引平均能把结果收窄到更少的行。

ANALYZE 之后，同样两条查询的 EQP 输出没有变化——user_id=10 本来就只有一个可用索引，amount>5 本来就没有索引可选，统计信息在”只有一条路可走”时不改变结论，它真正发挥作用的场景是多个索引都可用、需要挑一个更好的（第三节 join 顺序、第 8.1 节范围查询都属于这类场景）。

ANALYZE 命令本身只在被显式调用（或通过 PRAGMA optimize 间接触发）时运行，官方文档明确说明”the use of ANALYZE is never required”，以及”statistics gathered by ANALYZE are not updated as the content of the database changes”——统计信息是运行时刻的快照，不会随数据增删自动刷新。SQLite 3.18.0 引入的 PRAGMA optimize 是官方现在推荐的用法：应用在关闭连接前调用一次，SQLite 自己判断哪些表值得重新 ANALYZE，而不是应用手工决定时机。

2.1 sqlite_stat4：直方图，但只在全量扫描时可用

本机编译带 SQLITE_ENABLE_STAT4，ANALYZE 之后同时生成了 sqlite_stat4，为每个索引存了一组采样记录（编码后的样本 key + 各列的近似匹配行数），供范围查询（BETWEEN/>/<）时估算选择性——sqlite_stat1 只能回答”等值查询平均命中几行”，sqlite_stat4 能回答”这个范围大概命中几行”。官方 ANALYZE 文档给出一条容易被忽略的边界：PRAGMA analysis_limit 设置的近似扫描不能用来生成 sqlite_stat4——“if a non-zero analysis limit is specified, the sqlite_stat4 table is not computed”，即直方图统计没有”近似版”，要么做完整扫描，要么完全没有。这是”统计精度换扫描代价”这条权衡在 SQLite 里最直接的体现:等值选择性可以用近似扫描凑合，范围选择性的直方图不能。

三、没有统计时，计划器怎么”猜”

官方文档没有含糊地说”没有 ANALYZE 就是随便猜”，而是写出了具体的默认猜测数字：

第二行是一个非常具体、可直接验证的因果链：官方文档写道”skip-scan only becomes profitable… when the number of duplicates is about 18 or more”，而”没有 ANALYZE 时默认猜测重复度是 10”——10 小于 18，所以结论是确定的、不是运气：“a skip-scan is never used on a database that has not been analyzed”。这是本文能给出的最精确的一条”无统计启发式”证据：它不是模糊的”计划器会尽力猜”，而是两个写在文档里的具体数字相减，直接决定了一个优化路径的开关状态。

第三行同样精确：官方 Automatic Query-Time Indexes（第 12 篇会展开自动索引本身）一节写道，判断是否值得为某张无索引的表构建临时索引时，“in the absence of ANALYZE information, SQLite guesses that N is one million”——这个”一百万行”不是比喻，是计划器代价公式里真实代入的常数。对一张只有几百行的小表，这个猜测明显偏保守（真实成本远低于按百万行估算的成本），但保守估计不改变”建索引比不建索引便宜”这个方向性结论，只影响两者代价差的具体数值。

这条设计透露出计划器的取舍原则：没有实测数据时，宁可用一个偏大、偏安全的默认值，也不做无根据的乐观假设——把猜测写死在文档而不是藏在源码注释里，本身也是”嵌入式够用就好”这条边界的具体体现：PG 式 CBO 依赖持续更新的 pg_statistic，SQLite 在完全没有统计时也要给出一个确定性的默认行为，而不是拒绝规划或退化到不可预测的顺序。

四、Join 顺序：N3 启发式与”不做 PG 式穷举”的复杂度边界

多表 JOIN 的核心决策是”哪张表在外层循环、哪张在内层”。官方 The Next Generation Query Planner 文档完整交代了这段历史，是本篇学术边界最扎实的部分：

• 3.8.0（2013）之前：用”最近邻”（Nearest Neighbor，NN）启发式——每一步只贪心选当前代价最低的下一张表。NN 快，能在微秒级规划 60 路 JOIN，但文档自己承认对 TPC-H Q8（8 表 JOIN）算出的计划比穷举搜索找到的最优解慢将近 750 倍（代价按对数计算，27.38 对 36.92 看起来差距不大，指数还原后是这个倍数）。
• 穷举搜索：能找到最优解，但时间复杂度是 (O(K!))（(K) 是 JOIN 的表数），超过 10 路 JOIN 之后 sqlite3_prepare_v2 的耗时会变得不可接受。
• N3（“N Nearest Neighbors”）：3.8.0 引入的折中算法，每一步保留 (N) 条候选路径而不是 1 条，存储 (O(N))、计算 (O(K N))。官方给出的当前默认值：简单查询 (N=1)，两表 JOIN (N=5)，三表及以上 (N=12)（对 star-schema 结构再放宽到 18）。

flowchart LR
  nn["NN heuristic<br/>(pre-3.8.0)<br/>O(K), greedy,<br/>can miss optimal by ~750x"] -.replaced by.-> n3
  n3["N3 heuristic<br/>(3.8.0+)<br/>O(K*N), keeps N best<br/>partial plans per step"] -.bounded by.-> exhaustive
  exhaustive["Exhaustive search<br/>O(K!)<br/>optimal but infeasible<br/>beyond ~10-way join"]

这组数字直接支撑本文开头的判断：“不追求与 PG 优化器同复杂度”不是含糊的定性描述，而是有具体算法名字和复杂度公式的工程选择：N3 用有界的 (O(K N)) 换取”几乎总是够好”的计划，主动放弃穷举搜索保证的全局最优。

官方文档也没有回避 N3 的已知短板——star-query（一个大事实表 + 多个小维度表）场景下，N3 是贪心算法，当维度表数量增多、且索引存在双向可用性时，N 个候选槽位可能被”先扫小维度表”的局部最优路径占满，挤掉”先钻大事实表再逐个查维度表”的全局更优解；要让 N3 找到该场景下的最优解，需要的 (N) 值会随维度表数量指数增长。文档承认”more recent versions of SQLite (circa 2024 or 2025 and later) implement a heuristic to work around this”——这是官方文档自己写的、仍在演进中的计划器组件，不是本文替官方下的猜测。

这条边界与嵌入式分析负载的讨论直接相关：Gaffney et al.（PVLDB 2022，SQLite: Past, Present, and Future）讨论过 SQLite 在分析型工作负载上的定位与瓶颈——本文不复述该文的具体实验数字，只把它作为”复杂 join 计划质量在分析场景下是否够用”这个问题的讨论锚点：star-schema 正是分析型查询的典型结构，N3 在高维度场景下的已知短板与”SQLite 该不该被推到分析负载”的讨论天然相关，但两者是不同粒度的问题，不能互相替代论证。

五、与第 5、6 篇的分工

第 6 篇钉住的是”一条 SQL 怎么被编译”——词法、语法、语义分析、代码生成的四段管线；第 5 篇钉住的是”编译出的字节码怎么被 VDBE 逐条执行”。本篇钉的是介于两者之间但概念上更早发生的一步：代码生成阶段要先决定生成什么样的字节码，即用哪个索引、按什么顺序访问哪些表。计划器的输出是一份”访问计划”，VDBE 字节码是这份计划的具体翻译；EXPLAIN QUERY PLAN 给出计划本身，EXPLAIN 给出翻译后的字节码——第 5 篇已经用 EXPLAIN 展示过字节码格式，本篇不重复。

六、常见误解

1. 「SQLite 的查询计划器和 PostgreSQL 的 CBO 是同一类系统，只是实现细节不同。」 两者共享”用统计估算代价、挑成本最低的计划”这一大方向，但复杂度目标完全不同：PG 允许更长的规划时间来换取更精细的代价模型（含并行计划、物化视图选择等）；SQLite 的 N3 算法是有界近似算法，官方文档直接给出了它会在 star-query 场景下”贪心到丢失最优解”的已知反例。用”CBO”这个笼统标签抹平两者复杂度边界的差异，会误判 SQLite 在复杂分析查询上的能力上限。

2. 「没有 ANALYZE，计划器就是纯随机或纯启发式拍脑袋。」 见第三节：没有统计时的行为是确定性的、写死在文档里的默认猜测（表大小猜一百万行、索引重复度猜 10），不是随机决策。这组默认值的设计目标是”保守但确定”，不是”退化成不可预测”。

3. 「EXPLAIN QUERY PLAN 的输出格式稳定，可以在应用代码里解析它做自动化判断。」 官方文档用醒目的 Warning 明确否定：“The data returned by the EXPLAIN QUERY PLAN command is intended for interactive debugging only. The output format may change between SQLite releases.” 文档还记录了 3.24.0（2018）和 3.36.0（2021）两次实质性格式变化。把 EQP 输出接入 CI 或运行时逻辑做字符串匹配，是升级 SQLite 版本后最容易静默失效的地方之一。

4. 「运行过一次 ANALYZE，统计信息就会跟着数据变化自动更新。」 ANALYZE 文档原话：“Statistics gathered by ANALYZE are not updated as the content of the database changes.” 统计是那一刻的快照；数据发生显著变化后必须重新触发（手动 ANALYZE 或依赖 PRAGMA optimize 的周期调用），否则计划器会一直依据过期分布做决策——这正是研究台账里”统计漂移”这个开放问题在应用层最直接的表现。

七、学术谱系、工程间隙与开放问题

谱系：用统计信息驱动代价估算、在访问路径之间做选择的范式，最早在 System R 项目的 Selinger, P. G. 等人 Access Path Selection in a Relational Database Management System（SIGMOD 1979）里被系统化定义——该文首次把”用统计估算基数、按代价选连接顺序和访问路径”变成可实现的算法框架，此后几乎所有关系数据库的优化器都在这个范式内做变种。SQLite 的 ANALYZE + sqlite_stat1/4 + N3 是这个范式在单机嵌入、规划时间必须是毫秒级约束下的一个具体分叉：它保留了”统计驱动代价估算”的核心思想，但主动放弃了 System R 论文暗含的”规划时间可以适度更长以换取更优计划”的假设——嵌入式场景里，sqlite3_prepare_v2 的调用者通常在等待结果，不会容忍秒级规划开销。

工程间隙：官方文档承认统计信息”不会随数据变化自动更新”，这与生产环境里数据分布持续漂移（新增用户、热点变化、历史数据老化）之间存在直接落差——论文式代价模型假设统计是准确的，工程现实是统计随时可能过期，SQLite 把”何时重新统计”这个决策完全交给应用（或 PRAGMA optimize 的启发式判断），没有类似 PG autovacuum 那样的后台自动统计进程，这是单进程嵌入式模型必然要放弃的能力。

开放问题：官方文档自己承认 N3 在 star-query 场景下存在已知的计划质量短板，并且用”2024 or 2025 and later”这种时间限定词说明修复仍在演进——这是一个官方公开承认、仍在处理中的具体问题，不是本文推测。它与 Gaffney et al.（PVLDB 2022）讨论的”SQLite 在分析负载上的定位”是同一问题域的两个层面：一个是计划器算法本身在高维度 JOIN 上的局部最优陷阱，另一个是”该不该把分析型查询交给 SQLite”这个更高层的选型问题——本系列第 17 篇会收束选型讨论，本篇只钉住计划器这一层的具体证据，不越界下选型结论。

八、小结

1. EXPLAIN QUERY PLAN 用 SCAN/SEARCH 区分”访问全表”与”只访问子集”，USING (COVERING) INDEX 标注具体路径；本机 3.53.2 实测 user_id=10（有索引）走 SEARCH，amount>5（无索引）走 SCAN，两条路径都是唯一可行选择，不是计划器的取舍结果。
2. ANALYZE 把统计写进 sqlite_stat1（总行数 + 各级前缀列平均重复行数）与可选的 sqlite_stat4（直方图，仅完整扫描可得）；没有 ANALYZE 时，计划器使用文档写明的确定性默认猜测（表大小 100 万行、索引重复度 10），不是随机决策。
3. Join 顺序用 N3 有界近似算法（(O(K N))），主动放弃穷举搜索的 (O(K!)) 最优保证；官方文档承认该算法在 star-query 场景下有已知的贪心陷阱，且修复仍在演进——这是”嵌入式不追求 PG 式穷举优化器”这句话背后可核对的具体证据，不是模糊的定性判断。

参考资料

规范与官方文档（A 级）

1. SQLite Documentation, Query Planning（sqlite.org/queryplanner.html）——SEARCH/SCAN 基本语义、覆盖索引概念。
2. SQLite Documentation, EXPLAIN QUERY PLAN（sqlite.org/eqp.html）——输出格式、稳定性警告。
3. SQLite Documentation, The SQLite Query Optimizer Overview（sqlite.org/optoverview.html）——§6 skip-scan 阈值、§7 join 顺序历史、§14 自动索引猜测。
4. SQLite Documentation, The Next Generation Query Planner（sqlite.org/queryplanner-ng.html）——NN/N3 算法、TPC-H Q8 案例、star-query 已知短板。
5. SQLite Documentation, ANALYZE（sqlite.org/lang_analyze.html）——sqlite_stat1/sqlite_stat4 语义、PRAGMA optimize、PRAGMA analysis_limit 边界。

论文（A 级，谱系锚点）

6. Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A. & Price, T. G. Access Path Selection in a Relational Database Management System. SIGMOD 1979（代价驱动访问路径选择的奠基 work）。
7. Gaffney, K. P., Prammer, M., Brasfield, L., Hipp, D. R., Kennedy, D. & Patel, J. M. SQLite: Past, Present, and Future. PVLDB 15(12): 3535–3547, 2022. DOI: 10.14778/3554821.3554842（分析负载讨论锚点，不代入其实验数字）。

实验（A 级，本机实测）

8. 本机 sqlite3 3.53.2：20000 行 orders 表 + idx_orders_user 索引，ANALYZE 前后 EQP 对比、sqlite_stat1 内容核对；脚本 reproduce/11-query-plans.sh，输出见第一、二节。

站内

9. SQL 编译管线、VDBE 字节码执行——本篇与两篇的分工边界。
10. 嵌入式行存全景——Gaffney et al. 的系列首次引用与分析负载分工。
11. 本系列 index、PLAN.md。

上一篇：事务与隔离 下一篇：索引与 covering scan