数据库查询优化器代价模型深度实战：从基数估计到计划选择的工程真相

3 阅读 0 评论 0 点赞

数据库查询优化器代价模型深度实战：从基数估计到计划选择的工程真相

为什么两张百万级表的 JOIN 查询，一个错误的选择可以让执行时间从 200 毫秒变成 47 分钟？答案藏在查询优化器的代价模型里——那个从 1979 年 Selinger 论文一脉相承、至今仍在"猜"的神秘模块。本文将从底层统计学原理出发，结合 PostgreSQL 16 的优化器实现，剖析基数估计与代价模型的核心机制，并分享工程实践中的调优策略。

一、优化器的本质：一场概率论与工程妥协的博弈

数据库查询优化器的任务很简单：给定一条 SQL，在所有等价执行计划中，选择"最快"的那个。但"最快"是个不可观测的量——你只有执行之后才能知道真实耗时。因此优化器必须预测。

Predict 的输入是： 1. 基数估计（Cardinality Estimation）：每个算子将产生多少行输出； 2. 代价模型（Cost Model）：执行这些操作需要多少 CPU、I/O、内存时间。

两者相乘，得到每个候选计划的总代价，代价最低者获胜。这个框架自 1988 年 IBM System R / Selinger 论文以来几乎没有变过，变的是估计的准确性和代价参数的校准。

SQL → Parser → Logical Plan → Optimizer → Physical Plan → Executor
                            ↑
                    Cardinality × Cost Model

听起来优雅，实践处处是坑。先看一个真实案例：

-- 订单表 1200 万行，用户表 80 万行
-- 查询：北京地区 VIP 用户的最近一个月订单

SELECT o.order_id, o.amount, u.name
FROM orders o
JOIN users u ON o.user_id = u.id
WHERE o.create_time > '2026-09-01'
  AND u.city = '北京'
  AND u.level = 'VIP';

如果优化器估算出 orders 筛选后剩 15 万行、users 筛选后剩 800 行，它会倾向于 Nested Loop + users 驱动表，用 users 的 800 行去 probe orders 的时间索引——总代价大约 800 × log(150000) ≈ 13,600 次 IO。

但如果 orders 实际剩 110 万行（因为 9 月有促销活动），而 users 实际只有 200 行，那 Nested Loop 变成 200 次 probe 一个 110 万行的索引——性能雪崩。而 Hash Join 本来只需要 3 秒。

这就是基数估计错误的代价。

二、基数估计：直方图、MCV 与独立性假设陷阱

2.1 PostgreSQL 的统计信息基础

PostgreSQL 通过 ANALYZE 命令收集统计信息，存在 pg_statistic 系统表中。pg_stats 视图提供了友好的查询接口：

SELECT 
    attname,
    n_distinct,
    most_common_vals AS mcv,
    most_common_freqs AS mcf,
    histogram_bounds,
    correlation
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'create_time';

典型的输出结构：

字段	含义
`n_distinct`	不同值数量（负数表示比例，-1 表示全唯一）
`mcv`	最常见值列表（Most Common Values）
`mcf`	对应 MCV 的频率
`histogram_bounds`	直方图桶边界（等深分桶）
`correlation`	物理顺序与逻辑顺序的相关系数（-1 到 1）

默认情况下，PostgreSQL 对每列最多收集 default_statistics_target（默认 100）个 MCV 和 100 个直方图桶。这意味着：

出现频率在前 100 的值之外的谓词，优化器通过直方图估算；
直方图精度有限，无法区分排序相邻的值。

2.2 等深直方图 vs 等高直方图

PostgreSQL 使用的是等深直方图（Equi-depth / Height-balanced）：每个桶包含近似相等数量的行。这与等宽直方图不同——等宽直方图每个桶覆盖相等范围的值，对倾斜数据表现差。

等深直方图的估计过程（以 WHERE age = 30 为例）：

1. 检查 MCV：如果 30 在 MCV 中，直接返回 MCF 对应频率
2. 否则查找直方图：定位 age=30 落在第 k 桶（桶宽 w = (max-min)/N_buckets）
3. 均匀分布假设：selectivity = 1/N_buckets = 1/100 = 0.01
4. 等值条件修正：selectivity /= n_distinct（Heuristic）

注意第 4 步：PostgreSQL selfunc.c 中 var_eq_const 做了一个有争议的假设——如果值不在 MCV 中，认为其频率不超过 1/n_distinct。这在热点数据不在 MCV 时会显著低估。

2.3 Multi-Column 依赖：独立假设的致命伤

最根本的问题是：PostgreSQL 默认假设列间独立。对于条件 WHERE city = '北京' AND level = 'VIP'：

// selfunc.c: bool_and 处理
s1 = s1 * s2;  // 直接相乘

若 P(city=北京) = 0.05，P(level=VIP) = 0.1，估计选择性为 0.05 × 0.1 = 0.005。实际上，北京用户中 VIP 占比可能是 0.15（远高于全局的 0.1），真实选择性应为 0.05 × 0.15 = 0.0075，被低估了 50%。

解决方案：从 PostgreSQL 10 开始引入的扩展统计信息（Extended Statistics）：

-- 创建多列依赖统计
CREATE STATISTICS s_city_level (dependencies) ON city, level FROM users;
ANALYZE users;

-- 创建多列 Ndistinct 统计（解决 GROUP BY 去重估计）
CREATE STATISTICS s_ndistinct (ndistinct) ON city, level, status FROM users;
ANALYZE users;

创建后，pg_stats_ext 中会存储列间的函数依赖强度（0~1）。优化器在估算组合条件选择性时，会将独立概率乘积乘以依赖系数进行修正。

2.4 连接基数估计：从笛卡尔积到最小选择性

对于 t1 JOIN t2 ON t1.x = t2.y，连接基数估计的核心公式：

// costsize.c: estimate_joinrel_size
joinrel->rows = min(
    CLAUSE_AGGN(t1.rows * t2.rows * selectivity),
    t1.rows * (t2.rows / max_n_distinct(t2.y))
);

其中 selectivity 取决于等值连接条件的选择性。PostgreSQL 使用最大不同值假设（MVA）：

join_selectivity = 1 / max(ndistinct(t1.x), ndistinct(t2.y))

假设 t1.x 有 100 个不同值，t2.y 有 80 个不同值，则 selectivity = 1/100 = 0.01。

这个假设在两种典型情况下失效：

场景 A：外键连接导致的低估

SELECT * FROM orders JOIN users ON orders.user_id = users.id;

orders.user_id 有 80000 个不同值（80% 是有效用户），users.id 有 80000 个不同值。MVA 给出 selectivity = 1/80000，但实际上这是外键引用——几乎每个 order 都能找到对应 user，真实 selectivity = rows(orders) / max_ndistinct = 1,200,000 / 80,000 = 15。

PostgreSQL 通过外键约束能部分缓解，但跨表相关性的高估/低估仍常见。

三、代价模型：把 CPU 和 IO 映射到统一的"代价单位"

3.1 PostgreSQL 的代价公式

PostgreSQL 代价由 5 个核心参数决定（全在 postgresql.conf 中）：

参数	默认值	含义
`seq_page_cost`	1.0	顺序读取一个 8KB 页面的代价
`random_page_cost`	4.0	随机读取一个页面的代价
`cpu_tuple_cost`	0.01	处理一行的 CPU 代价
`cpu_index_tuple_cost`	0.005	处理一个索引行的 CPU 代价
`cpu_operator_cost`	0.0025	执行一个运算符的 CPU 代价

典型算子的代价计算公式：

// cost_seqscan: 全表扫描代价
cost = pages * seq_page_cost 
     + rows * cpu_tuple_cost;

// cost_index: 索引扫描代价
cost = pages * random_page_cost   -- 索引页随机 IO
     + index_tuples * cpu_index_tuple_cost   -- 处理索引元组
     + heap_pages * random_page_cost   -- 回表随机 IO
     + returned_rows * (cpu_tuple_cost + cpu_operator_cost);  -- 过滤+返回

3.2 代价模型校准：从默认值到生产匹配

默认参数诞生于 2005 年的 SATA SSD 之前。在 NVMe SSD 时代，random_page_cost = 4.0 已经严重失真——NVMe 随机读取与顺序读取的差距远小于 4 倍。

推荐校准步骤：

-- 1. 在测试环境执行 EXPLAIN (ANALYZE, BUFFERS) 获取实际执行时间
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT * FROM orders WHERE create_time > '2026-09-01' AND status = 'pending';

-- 2. 根据实际 SELECT 的耗时调整参数
-- 假设 NVMe SSD：随机/顺序 IO 比约 1.2:1
ALTER SYSTEM SET random_page_cost = 1.1;

-- 3. 对于全内存工作负载（shared_buffers 足够大）
ALTER SYSTEM SET seq_page_cost = 0.005;
ALTER SYSTEM SET random_page_cost = 0.006;

-- 4. 重新加载配置
SELECT pg_reload_conf();

校准验证方法：对比 EXPLAIN 估算代价与实际执行时间的相关系数。在健康的系统上，Spearman 相关系数应 > 0.85。如果持续偏低，说明代价参数不匹配或基数估计偏差大。

3.3 Join 算法代价对比：什么时候 Nested Loop 会赢

// cost_nestloop
run_cost = outer_rows * (inner_scan_cost + cpu_operator_cost)
         + inner_rows * cpu_tuple_cost;  // 每次 probe 的 CPU

// cost_hashjoin
startup_cost = outer_rows * cpu_operator_cost   -- 构建哈希表
             + hash_table_cost;
run_cost = outer_rows * cpu_tuple_cost  -- 探测
         + (qual_selectivity * inner_rows) * cpu_operator_cost;

// cost_mergejoin
startup_cost = sort_cost(outer) + sort_cost(inner);  -- 排序代价
run_cost = (outer_rows + inner_rows) * cpu_operator_cost;

决策边界示意（假设代价参数合理）：

Nested Loop 胜出:  outer_rows < 50 AND inner 有高效索引
Hash Join 胜出:    medium-medium 规模，内存充足（work_mem 足够）
Merge Join 胜出:    两表已有序 OR 结果需要排序供后续算子使用

PostgreSQL 通过 enable_nestloop / enable_hashjoin / enable_mergejoin 可以临时禁用某类 Join 算法进行调优测试——但生产环境不建议关闭，因为代价模型应该自动选择正确方案。如果经常需要手动关闭某算法，根源在基数估计不准或代价参数偏差。

四、现代优化器的演进：从静态模型到自适应执行

4.1 运行时重新优化：Adaptive Query Execution

Spark 3.0 引入的 AQE（Adaptive Query Execution） 和 Oracle 的 Adaptive Query Optimization 代表了最新方向：如果运行时发现某算子实际行数与预估偏差超过阈值，动态切换 Join 策略。

PostgreSQL 目前没有原生 AQE，但有部分缓解机制：

Materialize + Gather：在 CTE 中先物化，后续节点使用实际行数重新优化（但优化器不一定每次都重新选择计划）；
pg_stat_statements + auto_explain：事后诊断，手动创建更精准的统计信息。

4.2 基于机器学习的优化器

Microsoft 的 Cardinality Estimation (CE) Model（SQL Server 2014+）引入了神经网络替代直方图。MariaDB 的 ANALYZE FORMAT=JSON 输出更丰富的统计信息用于训练。但这在工程上仍面临挑战：训练数据的覆盖率和执行时延约束。

一个轻量级折中：直方图 + MCV 扩展 + 列组统计信息——这就是 PostgreSQL 当前的方向。若你的工作负载有稳定的查询模式（如 HTAP、TPC-DS），可以盲目增加 default_statistics_target 来 300+ 并配合扩展统计信息，代价是 ANALYZE 耗时和内存开销线性增加。

五、工程实践：如何驯服你的查询优化器

5.1 监控与诊断三件套

-- 1. 识别估计偏差大的查询（每日运行，持续记录）
SELECT 
    queryid,
    LEFT(query, 100) AS query_prefix,
    mean_exec_time,
    rows  -- 顶层算子实际返回行数
FROM pg_stat_statements
ORDER BY mean_exec_time DESC
LIMIT 20;

-- 2. 查看 EXPLAIN (ANALYZE) 估算 vs 实际对比
EXPLAIN (ANALYZE, BUFFERS, FORMAT JSON)
SELECT ...;  -- 比较 planned rows vs actual rows

-- 3. 检查过期统计信息
SELECT 
    schemaname, tablename,
    last_analyze, last_autoanalyze,
    n_tup_ins + n_tup_upd + n_tup_del AS total_changes
FROM pg_stat_user_tables
WHERE last_autoanalyze < NOW() - INTERVAL '1 day'
  AND n_tup_ins > 100000
ORDER BY total_changes DESC;

5.2 手动优化三张牌

牌一：创建扩展统计

-- 对高频多列组合条件创建依赖统计
CREATE STATISTICS s_orders_status_time (dependencies)
ON status, create_time FROM orders;

ANALYZE orders;

牌二：定制直方图精度

-- 对关键列增加统计目标（默认 100 → 500）
ALTER TABLE orders ALTER COLUMN create_time SET STATISTICS 500;
ALTER TABLE orders ALTER COLUMN status SET STATISTICS 500;
ANALYZE orders;

注意：每增加 100 的 statistic target 约增加 ANALYZE 时间 20~40%。在表持续高 DML 场景（TPS > 5k），需要在精度与 ANALYZE 窗口之间找平衡。

牌三：暂存计划指南（当优化器顽固不化）

-- 安装扩展
CREATE EXTENSION IF NOT EXISTS pg_plan_advsr;  -- 或 pg_hint_plan

-- pg_hint_plan 示例：强制指定 Join 方式
SELECT /*+
    HashJoin(o u)
    Leading((o u))
*/
    o.order_id, o.amount, u.name
FROM orders o
JOIN users u ON o.user_id = u.id
WHERE o.create_time > '2026-09-01'
  AND u.city = '北京'
  AND u.level = 'VIP';

5.3 代价模型微调守则

场景	推荐调整	原理
NVMe SSD	`random_page_cost = 1.1~1.5`	消除随机/顺序 IO 的过度惩罚
全内存工作负载	`seq_page_cost = 0.005, random_page_cost = 0.006`	强调 IO 主导的是 CPU
高并发 OLTP	`cpu_tuple_cost = 0.02`（略上调）	反映元组处理在锁竞争下的真实代价
列存/压缩表	手动计算 `seq_page_cost` 乘以压缩比后的有效值	反映单次 IO 可读取更多行

六、总结：优化器不是黑盒，但需要理解它的语言

回顾全文的关键脉络：

基数估计准确 → 正确估算每种计划的输出规模
      ↓
代价模型准确 → 正确预测每种算子的执行时间
      ↓
选择最优计划 → 最低代价的物理执行路径

优化器的每一层都有假设，假设失效时就会出错。作为工程师，我们有三重武器抵御这些问题：

丰富统计信息：扩展统计、定制直方图目标、定期 ANALYZE；
校准代价参数：根据实际存储介质和负载类型调整 PostgreSQL 的代价参数；
监控与反馈环：pg_stat_statements 是巡检的神经末梢，持续追踪估算偏差。

下次当你发现一个查询从 200 毫秒变成 47 分钟时，先别急着改 SQL——打开 EXPLAIN (ANALYZE)，看看那张计划树的 rows 估算。80% 的情况，修复一个统计信息问题就能让一切回归正轨。

点赞(0) 打赏

本文分类：AI应用开发
本文标签：PostgreSQL 数据库内核查询优化代价模型基数估计
浏览次数：3 次浏览
发布日期：2026-10-01 11:32:12
本文链接：https://www.ybb.press/ai-applications/10559.html

数据库查询优化器代价模型深度实战：从基数估计到计划选择的工程真相

数据库查询优化器代价模型深度实战：从基数估计到计划选择的工程真相

一、优化器的本质：一场概率论与工程妥协的博弈

二、基数估计：直方图、MCV 与独立性假设陷阱

2.1 PostgreSQL 的统计信息基础

2.2 等深直方图 vs 等高直方图

2.3 Multi-Column 依赖：独立假设的致命伤

2.4 连接基数估计：从笛卡尔积到最小选择性

三、代价模型：把 CPU 和 IO 映射到统一的"代价单位"

3.1 PostgreSQL 的代价公式

3.2 代价模型校准：从默认值到生产匹配

3.3 Join 算法代价对比：什么时候 Nested Loop 会赢

四、现代优化器的演进：从静态模型到自适应执行

4.1 运行时重新优化：Adaptive Query Execution

4.2 基于机器学习的优化器

五、工程实践：如何驯服你的查询优化器

5.1 监控与诊断三件套

5.2 手动优化三张牌

5.3 代价模型微调守则

六、总结：优化器不是黑盒，但需要理解它的语言

评论列表共有 0 条评论

发表评论取消回复

数据库查询优化器代价模型深度实战：从基数估计到计划选择的工程真相

数据库查询优化器代价模型深度实战：从基数估计到计划选择的工程真相

一、优化器的本质：一场概率论与工程妥协的博弈

二、基数估计：直方图、MCV 与独立性假设陷阱

2.1 PostgreSQL 的统计信息基础

2.2 等深直方图 vs 等高直方图

2.3 Multi-Column 依赖：独立假设的致命伤

2.4 连接基数估计：从笛卡尔积到最小选择性

三、代价模型：把 CPU 和 IO 映射到统一的"代价单位"

3.1 PostgreSQL 的代价公式

3.2 代价模型校准：从默认值到生产匹配

3.3 Join 算法代价对比：什么时候 Nested Loop 会赢

四、现代优化器的演进：从静态模型到自适应执行

4.1 运行时重新优化：Adaptive Query Execution

4.2 基于机器学习的优化器

五、工程实践：如何驯服你的查询优化器

5.1 监控与诊断三件套

5.2 手动优化三张牌

5.3 代价模型微调守则

六、总结：优化器不是黑盒，但需要理解它的语言

数据库查询优化器代价模型深度实战：从基数估计到计划选择的工程真相

Bw-Tree 无锁 B+树深度实战：从 Mapping Table 增量更新到学习索引 RMI / PGM-index / ALEX 的工程全解

PostgreSQL 查询优化深度实战：从执行计划分析到索引策略与并行查询的最佳实践

pgvector：PostgreSQL向量搜索扩展深度工程实践

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复