土法炼钢兴趣小组的算法知识备份

【数据库研究前沿】学习型查询优化器：Neo、Bao、Balsa 到 LLM-CBO

2026-04-24 · database · #query-optimizer #learned-qo #neo #bao #balsa #postgresql #pg_hint_plan

文章导航

分类入口
database
标签入口
#query-optimizer#learned-qo#neo#bao#balsa#postgresql#pg_hint_plan

目录

查询优化器（Query Optimizer, QO）是关系数据库最精巧、也最脆弱的子系统。四十多年来，基于代价的优化器（Cost-Based Optimizer, CBO）以一套启发式规则 + 统计信息 + 动态规划（Dynamic Programming, DP）作为骨架，把一条 SQL 翻译成一棵执行计划树。它大部分时候工作得不错，但在 join 条件相关、数据倾斜、或者查询模板变化剧烈的工作负载下，代价估计的偏差会被选择性乘积放大到几个数量级，最终让执行器跑在一个完全不合理的计划上。

从 2018 年起，学术界开始大规模尝试用机器学习替换或者辅助 CBO 的若干环节。Neo、Bao、Balsa 是这条路线上最有代表性的三个里程碑，它们分别回答了”能不能从零学一个 QO”“该不该完全放弃传统 CBO”“如何在没有专家执行计划作为监督信号时 bootstrap 学习”这三个问题。2023 年以后，随着大语言模型（Large Language Model, LLM）能力的提升，又出现了一批把 LLM 当作”外部查询顾问”的工作，给 CBO 注入 hints。

本文上半梳理这条研究线的核心想法，重点关注它们的训练数据、反馈回路和冷启动问题；下半结合 PostgreSQL 讨论怎样把一个 learned 组件以 hint 的形式接入真实系统，以及什么场景下反而不应该用它。

一、CBO 基础：为什么 learned QO 有机会

1.0 执行计划到底是什么

把话题拉回最基本的地方。一条 SQL 在 PostgreSQL 里，从字节流变成结果集的途中经过五个阶段：

parse tree ──▶ query tree ──▶ logical plan ──▶ physical plan ──▶ executor
  语法检查        语义改写       关系代数         具体算子选择        迭代执行

CBO 只活在”logical → physical”这一步。它的职责就是：给定一棵逻辑关系代数树，决定每个 join 用什么算法（hash / merge / nested loop）、每个扫描用什么方式（seq / index / bitmap）、以及多表 join 的顺序。

这听起来狭窄，但这一步的代价分布极不均匀——两个计划可能差几万倍。整个数据库领域过去四十年花在 CBO 上的研究论文可能比文件系统还多，就是因为这一步做好了，其它所有事才值得做。

1.1 System R 的遗产

关系数据库的优化器骨架来自 1979 年的 System R 论文（Selinger et al., SIGMOD 1979）。它确立了三个沿用至今的约定：

这三条在今天几乎所有主流优化器（PostgreSQL、MySQL、Oracle、SQL Server、DB2）里都能找到直接对应。问题在于：cost function 是一组写死的系数，selectivity 依赖直方图（histogram）和独立性假设（attribute value independence assumption）。两者都会在实际工作负载上失效。

1.2 代价估计为什么会偏差几个数量级

Leis 等人在 VLDB 2015 的 “How Good Are Query Optimizers, Really?” 里对 PostgreSQL、DB2 和几款商业系统做了系统评测。他们构造了 JOB（Join Order Benchmark），并发现：

误差按 join 层级指数放大，是独立性假设的直接后果。一旦基数估错，cost function 的比较就没有意义，DP 选出来的”最优”计划只是一个”对错得最离谱的估计而言最便宜”的计划。

这给 learned QO 留下了空间：只要能用模型学到更准的基数估计，或者直接学到”计划好坏的排序”，CBO 的结构性缺陷就有机会被绕开。

二、Neo：端到端学一个优化器

Neo（Marcus et al., VLDB 2019, “Neo: A Learned Query Optimizer”）是第一个认真尝试端到端替换传统 QO 的系统。它的核心想法直白：把”选计划”看成一个强化学习问题，状态是 partial plan，动作是下一步 join 哪两张表、用什么算法，奖励是执行时间。

2.1 架构

Neo 由三部分组成：

训练时 Neo 先用 PostgreSQL 的计划 + 真实执行时间做 expert bootstrapping，然后在线用自己选出来的计划执行、回填延迟、继续训练。

2.2 真正的贡献与局限

Neo 的贡献是证明了”端到端可行”：在 JOB 上它的总延迟能做到和 PostgreSQL 商业级优化器同档。但它有几个硬伤：

这些问题直接催生了 Bao。

三、Bao：不替换 CBO，只挑 hint

Bao（Marcus et al., SIGMOD 2021, “Bao: Making Learned Query Optimization Practical”）的立场是：CBO 大部分时候是对的，learned 组件只需要在它犯错的时候修正它。

3.1 hint set 作为动作空间

Bao 不再试图自己构造计划树，而是预先定义一组 hint set，每个 hint set 关掉 PostgreSQL 的一部分能力，例如：

典型 Bao 配置下有 48 个 hint set。对每条查询，Bao 让 CBO 分别产生 48 个计划，用一个 Tree CNN 对 48 个候选的延迟做 Thompson Sampling，挑出最值得执行的那个。执行完把延迟回填进训练集。

3.2 工程上的三个关键优势

3.3 Bao 的理论视角：contextual bandit

把 Bao 翻译成强化学习术语，它其实是一个 contextual bandit：每条查询是一个 context（query 特征 + DB 统计），48 个 hint set 是 arms，arm 的 reward 是负延迟。Thompson Sampling 在这个规模下非常适合，因为：

这是为什么 Bao 比 Neo 更适合生产：它继承了 bandit 理论四十年的稳定性成果，不像 full RL 那样易发散。

四、Balsa：没有专家数据时如何冷启动

Balsa（Yang et al., SIGMOD 2022, “Balsa: Learning a Query Optimizer Without Expert Demonstrations”）关注的是 Neo 的一个隐藏假设——它需要一个成熟 CBO 作为监督信号来源。对没有 CBO 的场景（新硬件、新存储、或者干脆是新 DSL），这个假设不成立。

Balsa 的思路分两阶段：

Balsa 在 JOB 上做到了不依赖 PostgreSQL 监督数据就超过 PostgreSQL 优化器。它真正的价值在于提供了一条”纯从零学 QO”的路径，对 FoundationDB、DuckDB 这类还在快速演化 cost model 的系统有借鉴意义。

五、LLM-assisted QO：把大模型当作外部顾问

2023 年后出现一类新工作，代表作包括：

这一条线尚未成熟，但有几个稳定结论：

把这些工作放在一起看，2024–2026 的 learned QO 研究重心正在从”替换”向”协作”迁移：CBO 做骨架，learned model 做基数修正或者 plan rerank，LLM 做规则改写和 hint 生成。

5.1 基数估计：learned model 真正的甜点

一条经常被忽视但最务实的路线，是只用模型做 基数估计（cardinality estimation），其它一切不动。代表工作包括：

这条路线漂亮的地方是 接口极干净：模型只替换 估 #rows of predicate P 这一个函数，DP、cost function、plan search 都不动。在工程上这意味着回退代价几乎为零——模型挂了就用老的直方图估计，不影响正确性、只影响效率。

5.2 几条反直觉的经验

几条来自不同团队 postmortem 的经验，对做工程选型有帮助：

六、工程落地：PostgreSQL + pg_hint_plan 的最小方案

下半换视角，从一个 DBA 或 SRE 的角度看怎样把上面任何一个 learned 组件接入真实库。

6.1 pg_hint_plan：最小侵入的 hint 通道

pg_hint_plan 是一个 PostgreSQL 扩展，允许在 SQL 前面用注释语法给出 hint，优化器会忠实执行：

/*+ HashJoin(t1 t2) Leading((t1 (t2 t3))) IndexScan(t1 idx_t1_x) */
SELECT *
FROM t1 JOIN t2 ON t1.id = t2.id
        JOIN t3 ON t2.k = t3.k
WHERE t1.x = 42;

它覆盖了 Bao 用到的所有 hint 动作：join 方法、join 顺序、扫描方法、是否并行。把它作为”动作空间”，等价于实现了 Bao 的执行端。

6.2 采集训练数据：pg_stat_statements + auto_explain

没有数据，learned QO 是空中楼阁。PostgreSQL 原生的两个扩展就足够采集起点数据：

CREATE EXTENSION pg_stat_statements;
LOAD 'auto_explain';
SET auto_explain.log_min_duration = 100;   -- ms
SET auto_explain.log_analyze = on;
SET auto_explain.log_format = 'json';

每条超过 100ms 的查询会被记录 JSON 计划和真实行数/耗时。把 queryid + plan_json + total_time 作为三元组，就可以训练任意 plan embedding 模型。pg_stat_statements 提供 queryid 作为模板标识，天然支持 per-template 学习，避免参数化导致的分布漂移。

6.3 注入学习结果：两种架构

                   ┌────────────────────┐
  查询文本 ───▶   │  模板识别 + 特征化  │───┐
                   └────────────────────┘   │
                                            ▼
                   ┌────────────────────┐  learned scorer
                   │  候选 hint 集合    │◀─(Bao-style)
                   └────────────────────┘
                            │
                            ▼
                   /*+ ... */ 注入原 SQL
                            │
                            ▼
                   PostgreSQL + pg_hint_plan

两种常见架构：

我在生产环境的经验是：OLAP（queryid 稳定、模板少、单条代价高）走 proxy；OLTP（模板多、单条代价低）只在极少数”慢查询黑名单”模板上走 ORM 注入，而不是全量接管。

6.4 反馈回路

完整回路需要三个后台任务：

[每 5 分钟]  从 pg_stat_statements 拉最近窗口的 (queryid, plan_hash, avg_time)
[每小时]    用 auto_explain 日志补全 plan JSON，落到特征仓库
[每天]      重训 scorer；灰度更新 hint 表

注意 Bao 原文采用的是在线 bandit，但在多副本、多地域生产环境里，立刻回写模型会带来审计困难。工程上更稳妥的是异步批训练 + hint 表版本化发布，每次发布附带一个可以一键回滚的 hint_version 字段。

6.5 什么时候不要用 learned QO

不是所有场景都适合。以下情况建议直接退回 CBO：

learned QO 真正赚钱的场景，是模板稳定、单条查询代价高、允许少量执行抖动的分析型工作负载。离开这个区间，CBO + 专家 hint 仍然是更稳妥的选择。

6.6 一条真实工程链路的时间线

把前面的片段组装成一条端到端链路，大致长这样：

[应用]        [proxy 拦截器]         [feature store]       [scorer service]      [PostgreSQL]
   │  SQL         │  解析 + queryid      │                      │                    │
   ├────────────▶ │                      │                      │                    │
   │              │  查缓存 hint 表       │                      │                    │
   │              │◀──────┐              │                      │                    │
   │              │       │ 无缓存 → 调 scorer                   │                    │
   │              │──────────── 特征 +候选 hints ──────────────▶ │                    │
   │              │                      │                      │ ← 读模型 + 返回排名  │
   │              │◀────── 最佳 hint ─────┼──────────────────────┘                    │
   │              │  拼注释 /*+...*/                                                  │
   │              ├────────────────────────────────────────────────────────────────▶ │
   │              │                                                                   │ 执行 + auto_explain
   │ 行集 ◀───────┤                                                                   │
   │              │  异步：查询完成后把真实耗时回填到 feature store                     │
   │              │──────────────────────▶ │                                          │

值得强调的是：scorer service 必须是同步低延迟的（<5ms p99），否则 learned QO 给一个每条查询加 20ms 的固定开销，OLTP 场景得不偿失。常见做法是把 scorer 做成 sidecar、用 ONNX Runtime 跑模型，避免跨网络调用。

6.7 监控与报警

上线后监控指标至少包括：

报警的姿态也要保守。learned QO 不是核心系统，任何报警都优先走 自动降级回 CBO，而不是页 SRE。页 SRE 的情况只留给”回退开关本身失效”这种二级故障。

6.8 与本仓库相关文章的互链

七、一个被低估的话题：hint 管理本身

讨论 learned QO 时，大家的注意力都在”模型是不是比 CBO 准”。工程落地之后会发现，hint 怎么管理往往比模型本身更麻烦。

7.1 hint 的生命周期

一条 hint 从诞生到下线，至少经历这些状态：

生成 → 灰度 → 全量 → 观察 → 过期/回滚
  │       │        │       │       │
  │       │        │       │       └─ 老统计信息变化后，旧 hint 可能反而变差
  │       │        │       └─ 需要一段时间的 A/B 才能相信
  │       │        └─ 放给全量查询
  │       └─ 1%–10% 流量
  └─ 模型或规则生成

对每条 hint 必须持久化这些字段：

CREATE TABLE hint_catalog (
    query_template_id  text PRIMARY KEY,
    hint_text          text NOT NULL,
    baseline_ms_p50    numeric NOT NULL,
    hint_ms_p50        numeric,
    baseline_ms_p99    numeric NOT NULL,
    hint_ms_p99        numeric,
    state              text NOT NULL,  -- shadow / canary / active / retired
    created_at         timestamptz NOT NULL DEFAULT now(),
    last_observed_at   timestamptz NOT NULL DEFAULT now(),
    model_version      text NOT NULL,
    rollback_reason    text
);

没有这张表，你会发现三个月后没人知道为什么某条 SQL 突然变慢——因为三个月前某次训练自动加了一条 hint。

7.2 为什么不直接 UPDATE pg_class

PostgreSQL 允许直接改 pg_class.reloptions、pg_statistic 欺骗优化器。这条路短期看起来省事，长期是灾难：

把 learned 组件的产出始终以 hint 而非 catalog tweak 的形式注入，是 Bao 论文没有明说、但工程上非常重要的一条。

7.3 与 stored procedure / prepared statement 的协作

很多业务场景查询是预编译的（PREPARE / EXECUTE）。这种场景下 hint 注入要特别注意：

这些细节决定了 learned QO 在真实 OLTP 栈里到底有没有机会。光看论文跑出来的 end-to-end 提升数字，很容易忽视这层隐患。

八、研究与工程的距离：一张诚实地图

把这条线从 2018 年看到 2026 年，给工程师一张 “哪些已落地、哪些还在纸上” 的诚实地图：

主题 论文成熟度 工程落地度 常见误区
基数估计 高 中（云厂商内部） 以为模型精度直接等于端到端收益
Plan rerank（Bao 系） 高 中 以为一次 bandit 收敛就稳定，忽略分布漂移
端到端生成（Neo 系） 中 低 以为能在 OLTP 上线
LLM hint 生成 低 低 以为能替代 DBA
LLM 参数调优（DB-BERT） 低 试点 以为能替代 OtterTune

这张表每一格背后都有血泪教训，但它更值得读者记住的是趋势方向：从左到右、从上到下，成熟度在提升，但”落地”永远慢于”论文”两到三年。

8.1 下一步研究会去哪里

8.2 值得做的工程实验

如果你手里有一个 workload 想动手验证：

这是一个两天工作量的实验，能给团队一个清晰的 ROI 判断。没有它就开始部署 learned QO，很容易踩坑。

九、一个常被提起的误解：关于”LLM 自己写查询计划”

最后澄清一个在读论文时容易建立的误解：LLM 不会自己写执行计划。所有 LLM-assisted QO 的工作里，LLM 产出的都是 hint 或者 rewrite，真正的计划生成仍然由 CBO 完成。原因有三：

把 LLM 限制在”自然语言 → 结构化 hint”这一层，是 2024–2026 年工业界得出的稳定结论。未来是否会演化出”LLM 直接生成 plan tree”，属于开放问题，目前没有实证支持其可行性。

对工程师而言，看到任何声称 “LLM 取代优化器” 的讲法，都先回到这三条常识校验一下：输出是不是可执行的计划树、有没有接实时 statistics、出错怎么回退。三条都没回答清楚，就不是严肃工作。

十、本篇小结

这篇文章围绕”能不能用模型替换 CBO”做了一次历史梳理和工程翻译。几条可以带走的结论：

下一篇会讨论学习型索引，和本篇构成 “换掉规划 vs 换掉索引结构” 的对照阅读。要预留的思考题是：规划和索引是 CBO 流水线的上下游——如果我们同时学它们，会不会相互抵消，还是叠加收益？ 这个问题在目前的论文里还没有系统答案，值得读者带着自己的问题继续跟踪后续 SIGMOD / VLDB 工作。

参考文献

  1. P. G. Selinger et al., “Access Path Selection in a Relational Database Management System”, SIGMOD 1979, https://dl.acm.org/doi/10.1145/582095.582099. System R 优化器奠基论文。

  2. V. Leis et al., “How Good Are Query Optimizers, Really?”, VLDB 2015, http://www.vldb.org/pvldb/vol9/p204-leis.pdf. JOB benchmark 与基数估计误差实测。

  3. R. Marcus et al., “Neo: A Learned Query Optimizer”, VLDB 2019, https://www.vldb.org/pvldb/vol12/p1705-marcus.pdf.

  4. R. Marcus et al., “Bao: Making Learned Query Optimization Practical”, SIGMOD 2021, https://dl.acm.org/doi/10.1145/3448016.3452838.

  5. Z. Yang et al., “Balsa: Learning a Query Optimizer Without Expert Demonstrations”, SIGMOD 2022, https://arxiv.org/abs/2201.01441.

  6. I. Trummer, “DB-BERT: A Database Tuning Tool that ‘Reads the Manual’”, SIGMOD 2022, https://dl.acm.org/doi/10.1145/3514221.3517843.

  7. P. Akioyamen et al., “The Unreasonable Effectiveness of LLMs for Query Optimization”, arXiv:2404.02213, 2024, https://arxiv.org/abs/2404.02213.

  8. ossc-db/pg_hint_plan, GitHub, https://github.com/ossc-db/pg_hint_plan. PostgreSQL hint 扩展。

  9. PostgreSQL pg_stat_statements, https://www.postgresql.org/docs/current/pgstatstatements.html.

  10. PostgreSQL auto_explain, https://www.postgresql.org/docs/current/auto-explain.html.

上一篇: 如何读数据库顶会论文：SIGMOD/VLDB/CIDR 阅读路线 下一篇: 学习型索引再审视：RMI、ALEX、PGM

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2026-09-25 · database

数据库 MVCC：快照隔离到底隔离了什么

从 PostgreSQL 源码级别拆解 MVCC 的实现机制：堆表版本链、事务快照、可见性判断规则、VACUUM、隔离级别的真实行为，以及 Snapshot Isolation 抓不住的 Write Skew 和 SSI 如何解决它。附 MySQL InnoDB vs PostgreSQL MVCC 对比。

By .