数据库查询优化器＜2＞物理计划搜索和代价估计

一、数据库通常维护哪些统计信息

1. 表级统计信息

表级统计信息描述一张表的整体规模。

例如：

orders 表： - 行数：10,000,000 - 数据页数：500,000 - 平均行宽：120 bytes

优化器看到这些信息后，就能粗略判断：

全表扫描 orders 的代价很高。

2. 列级统计信息

列级统计信息是优化器估算WHERE条件选择率的核心依据。

例如列status的统计信息可能是：

status: - NDV = 5 - NULL 比例 = 0 - 高频值： - 'paid'：60% - 'cancelled'：5% - 'pending'：20%

如果没有高频值统计，优化器可能简单认为：

status = 'paid' 的选择率 ≈ 1 / 5 = 20%

但真实情况是：

status = 'paid' 的选择率 = 60%

这就是为什么高频值统计很重要。

3. 直方图统计信息

直方图用来描述列值的分布，尤其适合范围查询。

例如：

WHERE amount BETWEEN 100 AND 500

如果优化器只知道：

amount 最小值 = 0 amount 最大值 = 10000

它可能假设数据均匀分布，从而估计选择率为：

(500 - 100) / (10000 - 0) = 4%

但如果大多数订单金额都集中在 100 到 500 之间，这个估计就会严重偏低。

直方图可以帮助优化器知道：

amount 的值主要集中在哪些区间。

常见直方图类型包括：

4. 索引统计信息

索引统计信息描述索引本身是否适合访问数据。

例如：

WHERE customer_id = 10086

如果customer_id上有唯一索引，优化器可以知道：

最多匹配 1 行。

如果customer_id上是普通索引，并且 NDV 很高，优化器也可能认为索引扫描很划算。

但是，如果某个索引选择性很差，例如：

gender 只有 2 个不同值

那么：

WHERE gender = 'F'

可能返回大量行，优化器就不一定会选择索引扫描。

5. 多列统计信息

单列统计信息无法准确描述列之间的相关性，因此一些数据库会维护多列统计信息。

例如：

WHERE city = 'Tokyo' AND postal_code LIKE '100-%'

如果优化器把city和postal_code当作独立条件，可能估算错误。

因为：

postal_code 和 city 高度相关。

多列统计信息可以帮助优化器知道：

city = 'Tokyo' 时，postal_code 不是随机分布的。

6. 分区统计信息

对于分区表，数据库通常会维护：

例如：

orders_2024：5 亿行 orders_2025：8 亿行 orders_2026：2 亿行

对于查询：

WHERE order_date >= '2026-01-01'

优化器可以通过分区统计和分区裁剪，只访问 2026 年相关分区。

7. 运行时统计信息

除了静态统计信息，有些数据库还会记录或利用运行时信息。

这类信息不一定所有数据库都用于普通优化，但现代数据库越来越重视运行时反馈。

二、统计信息什么时候会更新

统计信息的更新方式通常有以下几类。

1. 手动更新

数据库通常提供显式命令，让用户或 DBA 主动收集统计信息。

常见命令形式包括：

ANALYZE table_name;

或：

UPDATE STATISTICS table_name;

或：

DBMS_STATS.GATHER_TABLE_STATS(...);

不同数据库命令不同，但目的相同：

重新扫描或采样数据，生成新的统计信息。

适合在这些场景手动更新：

2. 自动更新

很多数据库会在表发生足够多的数据变化后，自动触发统计信息更新。

典型触发条件是：

表中插入、更新、删除的数据量超过某个阈值。

例如：

表有 100 万行 如果修改了其中较大比例的数据 数据库可能认为统计信息过期 然后自动重新收集统计信息

自动更新的策略通常基于：

3. 定期更新

生产系统中，经常会安排定时任务更新统计信息。

例如：

每天凌晨 每周末 每次 ETL 之后 每次批量装载之后

这样做的原因是：

白天业务繁忙时收集统计信息可能影响性能； 夜间低峰期收集更安全。

定期更新适合：

4. 采样更新

统计信息不一定通过全表扫描获得。对于大表，数据库经常使用采样。

例如：

从 10 亿行中抽取 1% 的样本 根据样本估算整体分布

采样的优点是：

速度快，开销低。

缺点是：

对数据倾斜、高频值、极端值的估计可能不够准确。

对于特别重要的表或列，可以提高采样比例，甚至做全量统计。

5. 增量更新

对于分区表或超大表，重新统计整张表代价很高，因此数据库可能支持增量统计。

例如：

orders 表按月份分区 新装载 orders_2026_06 分区

不必重新统计所有历史分区，只需要：

统计新分区 再合并生成全局统计信息

增量统计适合：

大规模分区表 数据仓库 按时间追加数据的表

6. 创建对象时更新

某些操作会生成或刷新统计信息，例如：

三、统计信息不更新会有什么问题

如果统计信息过期，优化器可能会做出错误判断。

例如，原来表中只有：

orders：10 万行

后来导入大量数据，变成：

orders：1 亿行

但统计信息仍然显示：

orders：10 万行

优化器可能会错误地认为表很小，从而选择：

Nested Loop Join

而不是更适合大表的：

Hash Join

结果可能导致查询性能急剧下降。

四、一个典型例子

假设有表：

orders(order_id, customer_id, status, amount, order_date)

数据库可能维护如下统计信息：

如果执行：

SELECT * FROM orders WHERE status = 'paid' AND amount > 100 AND order_date >= '2026-01-01';

优化器会使用：

status 的高频值统计 amount 的直方图 order_date 的分区统计 表行数和页数 相关索引统计

来估算：

过滤后大约剩多少行？ 是否可以裁剪分区？ 是否使用 status 索引？ 是否使用 order_date 索引？ 是索引扫描还是全表扫描？

五、统计信息更新时机总结表

六、总结

数据库通常维护的统计信息包括：

表行数、页数、平均行宽； 列的 NDV、NULL 比例、最大最小值、高频值、直方图； 索引高度、索引页数、聚簇度、唯一性； 多列相关性、分区级统计、运行时反馈信息。

这些统计信息通常在：

手动 ANALYZE、 自动阈值触发、 定期维护任务、 批量导入 / 删除 / 更新后、 创建或重建索引后、 分区数据变化后

进行更新。

它们的作用可以概括为一句话：

统计信息是优化器估算行数和代价的依据；统计信息越准确，优化器越可能选择正确的执行计划。

下面用教科书风格说明：逻辑优化之后，数据库如何进行物理计划搜索与代价估计。

回到顶部

一、逻辑优化之后得到了什么

逻辑优化之后，数据库得到的是一个经过等价重写的逻辑查询计划。

例如 SQL：

SELECT c.name, o.amount FROM customers c JOIN orders o ON c.customer_id = o.customer_id WHERE c.region = 'Asia' AND o.amount > 100;

逻辑优化后可能得到：

π_c.name,o.amount( σ_c.region='Asia'(customers) ⋈_c.customer_id=o.customer_id σ_o.amount>100(orders) )

这个计划说明：

1. 先过滤 customers.region = 'Asia' 2. 先过滤 orders.amount > 100 3. 再按 customer_id 连接 4. 最后输出 c.name 和 o.amount

但它还没有说明：

customers 怎么扫描？ orders 怎么扫描？ JOIN 用 Hash Join 还是 Nested Loop Join？ JOIN 谁作为外表，谁作为内表？ 是否使用索引？ 是否并行？

这些问题属于物理计划搜索与代价估计阶段。

回到顶部

二、物理计划搜索与代价估计的核心任务

逻辑计划回答：

查询在逻辑上要做什么？

物理计划搜索回答：

这些逻辑操作具体用什么物理算法执行？

代价估计回答：

每种执行方式大概要花多少成本？

因此，逻辑优化之后的工作可以概括为：

逻辑计划 → 生成候选物理计划 → 对候选计划估算代价 → 比较并剪枝 → 继续搜索 → 选择估计代价最低的最终物理计划

更准确地说，物理计划搜索和代价估计是交织进行的，不是完全分开的两个阶段。

回到顶部

三、从逻辑算子到物理算子

逻辑算子只有语义，不规定实现方式。物理计划生成的第一步，就是把逻辑算子映射为具体物理算子。

1. 表访问算子

逻辑上：

Scan(customers)

物理上可能有多种实现：

例如：

WHERE c.region = 'Asia'

如果customers.region上有索引，可以生成：

Index Scan[customers_region_idx]

如果没有合适索引，则生成：

Seq Scan[customers] + Filter[region = 'Asia']

2. 连接算子

逻辑上：

customers ⋈ orders

物理上可能实现为：

同一个逻辑连接：

R ⋈_R.a=S.b S

可能生成：

HashJoin(R, S) NestedLoopJoin(R, S) IndexNestedLoopJoin(R, S) MergeJoin(R, S)

每种连接算法的代价公式不同，所以必须分别估计。

3. 聚合算子

逻辑上：

γ_customer_id, COUNT(*)(orders)

物理上可能实现为：

如果输入已经按customer_id有序，Streaming Aggregate可能比Hash Aggregate更便宜。

4. 排序算子

逻辑需求：

ORDER BY amount DESC

物理上可能有：

例如：

ORDER BY amount DESC LIMIT 10

如果有amount索引，优化器可能选择：

Index Scan[amount_idx DESC] + Limit[10]

而不是：

Seq Scan + Sort + Limit

回到顶部

四、代价估计估什么

代价估计通常分成两个层次：

1. 基数估计：每个算子输出多少行？ 2. 成本估计：执行这个物理算子要花多少资源？

1. 基数估计

基数估计估算每一步的输出规模。

例如：

σ_region='Asia'(customers)

如果：

customers 有 1,000,000 行 region = 'Asia' 的选择率约为 0.1

则估计输出：

1,000,000 × 0.1 = 100,000 行

对于连接：

R ⋈_R.a=S.b S

常见估计公式是：

|R ⋈ S| ≈ |R| × |S| / max(NDV(R.a), NDV(S.b))

其中NDV表示某列不同值的数量。

2. 成本估计

成本估计估算物理执行需要消耗多少资源。

常见成本包括：

例如 Hash Join 的粗略成本可以表示为：

Cost(HashJoin(R, S)) ≈ Cost(R) + Cost(S) + BuildHashCost(R) + ProbeHashCost(S)

Index Nested Loop Join 的粗略成本可以表示为：

Cost(IndexNestedLoop(R, S)) ≈ Cost(R) + |R| × Cost(IndexLookup(S))

如果外表R很小，索引嵌套循环可能很便宜；如果R很大，它可能非常昂贵。

回到顶部

五、访问路径搜索

对于每张表，优化器首先会生成候选访问路径。

例如：

SELECT * FROM orders WHERE order_date >= '2026-01-01' AND status = 'paid';

假设有这些索引：

orders(order_date) orders(status) orders(status, order_date)

优化器可能生成：

候选 1：Seq Scan orders 候选 2：Index Scan orders_order_date_idx 候选 3：Index Scan orders_status_idx 候选 4：Index Scan orders_status_order_date_idx 候选 5：BitmapAnd(status_idx, order_date_idx)

然后分别估算：

每种访问路径会读多少页？ 会返回多少行？ 是否需要回表？ 是否能利用索引顺序？ 是否能覆盖查询所需列？

选择若干较优访问路径进入后续计划搜索。

回到顶部

六、连接顺序搜索

多表连接是物理计划搜索中最复杂的部分。

例如：

SELECT * FROM A JOIN B ON A.x = B.x JOIN C ON B.y = C.y JOIN D ON C.z = D.z;

逻辑上是：

A ⋈ B ⋈ C ⋈ D

但执行顺序可以有很多种：

((A ⋈ B) ⋈ C) ⋈ D ((B ⋈ C) ⋈ D) ⋈ A (A ⋈ (B ⋈ C)) ⋈ D (A ⋈ B) ⋈ (C ⋈ D)

不同顺序的中间结果可能差别巨大。

例如：

A ⋈ B 产生 10,000,000 行 B ⋈ C 产生 1,000 行

那么通常应优先考虑：

B ⋈ C

因为它能先产生较小的中间结果。

回到顶部

七、动态规划式计划搜索

经典优化器常用动态规划搜索连接顺序。

基本思想是：

先找单表最优计划，再找两表最优计划，再找三表最优计划，逐步构造更大的计划。

以三张表A, B, C为例。

1. 单表阶段

BestPlan(A) BestPlan(B) BestPlan(C)

每个单表计划可能包括：

Seq Scan Index Scan Bitmap Scan

优化器估算它们的代价，保留较优者。

2. 两表阶段

枚举两表连接：

BestPlan(A, B) BestPlan(A, C) BestPlan(B, C)

例如：

BestPlan(A, B) = min { HashJoin(BestPlan(A), BestPlan(B)), NestedLoopJoin(BestPlan(A), BestPlan(B)), MergeJoin(BestPlan(A), BestPlan(B)) }

优化器会估算每个候选连接计划的代价，然后保留较优者。

3. 三表阶段

构造三表连接：

BestPlan(A, B, C)

可以由以下方式产生：

BestPlan(A, B) ⋈ C BestPlan(A, C) ⋈ B BestPlan(B, C) ⋈ A

每一种又可以选择不同连接算法：

Hash Join Nested Loop Join Merge Join

最终保留估计代价最低的计划。

回到顶部

八、左深树、右深树和灌木树

连接计划通常可以表示为树。

1. 左深树

⋈ / \ ⋈ D / \ ⋈ C / \ A B

对应：

(((A ⋈ B) ⋈ C) ⋈ D)

特点：

搜索空间较小 实现简单 传统优化器常优先搜索 适合嵌套循环连接

2. 右深树

⋈ / \ A ⋈ / \ B ⋈ / \ C D

对应：

A ⋈ (B ⋈ (C ⋈ D))

特点：

在某些 Hash Join 或流水线执行中有优势

3. 灌木树

⋈ / \ ⋈ ⋈ / \ / \ A B C D

对应：

(A ⋈ B) ⋈ (C ⋈ D)

特点：

搜索空间最大 可能找到更优计划 适合复杂查询和并行执行

回到顶部

九、物理属性与 interesting properties

优化器比较计划时，不只看当前代价，还会看计划输出的物理属性。

常见物理属性包括：

例如：

SELECT * FROM orders JOIN customers ON orders.customer_id = customers.customer_id ORDER BY orders.order_date;

计划 A：

Hash Join 输出无序 当前代价低 后面还需要 Sort

计划 B：

Merge Join 输出已有序 当前代价略高 后面可以省掉 Sort

如果后面有ORDER BY，计划 B 可能整体更优。

这种“对后续算子有用的物理属性”称为：

interesting properties

因此优化器有时不会只保留当前代价最低的计划，还会保留一些具有有用属性的候选计划。

回到顶部

十、剪枝：为什么不能枚举所有计划

多表连接的候选计划数量增长非常快。表越多，可能的连接顺序和物理实现越多。

因此优化器必须进行剪枝。

常见剪枝策略包括：

例如，对于同一个关系集合{A, B}：

Plan 1: Cost = 100 Output order = none Plan 2: Cost = 300 Output order = none

如果二者输出属性相同，Plan 2 可以被剪掉。

但如果：

Plan 1: Cost = 100 Output order = none Plan 2: Cost = 130 Output order = A.x

Plan 2 可能被保留，因为后续ORDER BY A.x或 Merge Join 可能用得上。

回到顶部

十一、Volcano / Cascades 风格优化器

现代数据库优化器常使用 Volcano 或 Cascades 风格的搜索框架。

它们的基本思想是：

1. 用等价规则生成逻辑等价表达式 2. 用实现规则生成物理表达式 3. 将等价表达式组织在 memo 结构中 4. 对候选计划估算代价 5. 剪枝并选择最低代价计划

例如逻辑规则：

R ⋈ S ≡ S ⋈ R

实现规则：

LogicalJoin → HashJoin LogicalJoin → NestedLoopJoin LogicalJoin → MergeJoin

在这种框架中，优化器不是只处理一棵固定的计划树，而是在一个由等价表达式组成的搜索空间中寻找最低代价实现。

回到顶部

十二、一个完整例子

考虑 SQL：

SELECT c.name, o.amount FROM customers c JOIN orders o ON c.customer_id = o.customer_id WHERE c.region = 'Asia' AND o.amount > 100 ORDER BY o.amount DESC LIMIT 10;

1. 逻辑优化后的计划

Limit[10] └── Sort[o.amount DESC] └── Projection[c.name, o.amount] └── Join[c.customer_id = o.customer_id] ├── Selection[c.region = 'Asia'] │ └── customers └── Selection[o.amount > 100] └── orders

2. 生成候选访问路径

对customers：

C1: Seq Scan customers + Filter region = 'Asia' C2: Index Scan customers_region_idx

对orders：

O1: Seq Scan orders + Filter amount > 100 O2: Index Scan orders_amount_idx O3: Index Scan orders_customer_id_idx

3. 估算单表访问代价

假设统计信息显示：

customers 有 1,000,000 行 region = 'Asia' 选择率 10% orders 有 10,000,000 行 amount > 100 选择率 20%

则估计：

customers 过滤后约 100,000 行 orders 过滤后约 2,000,000 行

然后比较：

C1 和 C2 哪个更便宜？ O1 和 O2 哪个更便宜？

4. 生成候选连接计划

候选计划可能包括：

P1: HashJoin(C2, O1) P2: HashJoin(O1, C2) P3: NestedLoop(C2, IndexLookup orders_customer_id_idx) P4: MergeJoin(Sort C2 by customer_id, Sort O1 by customer_id)

5. 对连接计划估算代价

例如：

Cost(P1) = Cost(C2) + Cost(O1) + BuildHashCost(C2) + ProbeHashCost(O1) Cost(P3) = Cost(C2) + rows(C2) × Cost(IndexLookup orders_customer_id_idx)

如果C2输出 100,000 行，索引查找要执行 100,000 次，代价可能较高。

但如果C2只输出 100 行，P3可能非常便宜。

6. 考虑 ORDER BY 和 LIMIT

查询有：

ORDER BY o.amount DESC LIMIT 10

因此优化器还会考虑：

能不能利用 orders_amount_idx 的顺序？ 能不能避免全量排序？ 能不能使用 Top-N Sort？

一个特殊计划可能是：

P5: Limit[10] └── NestedLoop ├── Index Scan orders_amount_idx DESC, condition amount > 100 └── Index Lookup customers_pk Filter region = 'Asia'

这个计划的思想是：

按 amount 从大到小扫描 orders 每找到一个订单，就查对应 customer 如果 customer.region = 'Asia'，则输出 找到 10 条后停止

它不一定适合返回全部结果，但对ORDER BY + LIMIT 10可能非常高效。

这说明物理计划搜索必须考虑整个查询的上下文，而不能只看局部算子。

回到顶部

十三、最终物理计划选择

优化器会为候选计划估算总代价：

Total Cost = 子计划成本 + 当前物理算子成本

然后选择估计代价最低的计划。

最终计划可能是：

Limit[10] └── Top-N Sort[o.amount DESC] └── Hash Join[c.customer_id = o.customer_id] ├── Index Scan[customers_region_idx] └── Seq Scan[orders] Filter[o.amount > 100]

也可能是：

Limit[10] └── Nested Loop Join ├── Index Scan[orders_amount_idx DESC] │ Filter[o.amount > 100] └── Index Lookup[customers_pk] Filter[c.region = 'Asia']

最终选择哪个，取决于统计信息和代价模型。

回到顶部

十四、为什么优化器可能选错

优化器选择的是：

估计代价最低的计划

但不一定是真实运行最快的计划。

原因包括：

因此，优化器的目标通常不是找到理论绝对最优计划，而是：

在有限优化时间内，根据当前统计信息和代价模型，找到一个估计代价较低的计划。