数据库查询优化器<2>物理筹划搜索和代价估计

统计信息维护

数据库为了让优化器做基数估计和代价估计，通常会维护一批统计信息。它们形貌的是：

表有多大、列值怎么分布、索引是否有用、数据是否倾斜、差别列之间是否相干。

这些统计信息不肯定每次查询都及时盘算，而是由数据库周期性或按需网络。
一、数据库通常维护哪些统计信息

1. 表级统计信息

表级统计信息形貌一张表的团体规模。
统计信息寄义用途表行数表中约莫有多少行估算扫描代价、JOIN 输入规模数据页数表占用多少磁盘页 / 块估算全表扫描 I/O 本钱均匀行宽每行均匀占多少字节估算内存、网络、排序、Hash 代价表巨细表的总存储巨细判断扫描本钱空闲空间 / 膨胀信息表中是否有大量空洞或逾期版本影响扫描服从和维护战略比方：

1. orders 表：
2. - 行数：10,000,000
3. - 数据页数：500,000
4. - 平均行宽：120 bytes

复制代码

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

1. 全表扫描 orders 的代价很高。

复制代码

2. 列级统计信息

列级统计信息是优化器估算 WHERE 条件选择率的焦点依据。
统计信息寄义用途NDVNumber of Distinct Values，差别值个数估算等值查询选择率NULL 比例该列中 NULL 所占比例估算 IS NULL、IS NOT NULL最大值 / 最小值列值范围估算范围查询均匀列宽该列均匀占多少字节估算行宽、排序和网络传输高频值 MCVMost Common Values，最常见值处理处罚数据倾斜直方图 Histogram列值分布情况估算范围查询和非匀称分布相干系数 / 聚簇度列值和物理存储序次的相干程度判断索引范围扫描是否高效比方列 status 的统计信息大概是：

1. status:
2. - NDV = 5
3. - NULL 比例 = 0
4. - 高频值：
5.   - 'paid'：60%
6.   - 'cancelled'：5%
7.   - 'pending'：20%

复制代码

假如没有高频值统计，优化器大概简单以为：

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

复制代码

但真原形况是：

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

复制代码

这就是为什么高频值统计很告急。
3. 直方图统计信息

直方图用来形貌列值的分布，尤其得当范围查询。
比方：

1. WHERE amount BETWEEN 100 AND 500

复制代码

假如优化器只知道：

1. amount 最小值 = 0
2. amount 最大值 = 10000

复制代码

它大概假设数据匀称分布，从而估计选择率为：

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

复制代码

但假如大多数订单金额都会集在 100 到 500 之间，这个估计就会严肃偏低。
直方图可以资助优化器知道：

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

复制代码

常见直方图范例包罗：
范例分析等宽直方图每个桶的值域宽度类似等高直方图每个桶中的行数大抵类似高频值直方图单独记载特别常见的值混淆直方图同时形貌高频值和区间分布4. 索引统计信息

索引统计信息形貌索引自己是否得当访问数据。
统计信息寄义用途索引页数索引占多少页估算索引扫描 I/O 本钱索引高度B+ 树有几层估算索引查找本钱索引列 NDV索引键差别值个数估算索引选择性聚簇因子 / 聚簇度索引序次和表数据物理序次是否靠近判断索引回表本钱唯一性是否唯一索引判断最多返回多少行叶子页数目索引叶子层规模估算范围扫描本钱比方：

1. WHERE customer_id = 10086

复制代码

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

1. 最多匹配 1 行。

复制代码

假如 customer_id 上是平常索引，而且 NDV 很高，优化器也大概以为索引扫描很划算。
但是，假如某个索引选择性很差，比方：

1. gender 只有 2 个不同值

复制代码

那么：

1. WHERE gender = 'F'

复制代码

大概返回大量行，优化器就不肯定会选择索引扫描。
5. 多列统计信息

单列统计信息无法精确形貌列之间的相干性，因此一些数据库会维护多列统计信息。
统计信息寄义用途多列 NDV多列组合有多少差别值估算组合条件选择率函数依赖一列是否决定另一列修正独立性假设多列高频值常见列组合处理处罚组合条件数据倾斜相干性统计多个列之间是否相干改善 AND 条件估计比方：

1. WHERE city = 'Tokyo'
2.   AND postal_code LIKE '100-%'

复制代码

假如优化器把 city 和 postal_code 当作独立条件，大概估算错误。
由于：

1. postal_code 和 city 高度相关。

复制代码

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

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

复制代码

6. 分区统计信息

对于分区表，数据库通常会维护：
统计信息寄义全局统计信息整张分区表的总体统计分区级统计信息每个分区自己的统计分区行数每个分区约莫有多少行分区最大值 / 最小值分区列或平常列的范围分区 NDV每个分区内的差别值数目比方：

1. orders_2024：5 亿行
2. orders_2025：8 亿行
3. orders_2026：2 亿行

复制代码

对于查询：

1. WHERE order_date >= '2026-01-01'

复制代码

优化器可以通太过区统计和分区裁剪，只访问 2026 年相干分区。
7. 运行时统计信息

除了静态统计信息，有些数据库还会记载或使用运行时信息。
信息寄义用途实际返回行数某次实验中每个算子实际产生多少行用于反馈优化实际实验时间算子耗时判断代价模子是否精确缓存掷中率数据是否在 buffer cache 中影响 I/O 本钱临时文件巨细排序或 Hash 是否溢写磁盘调解后续筹划实验筹划汗青已往某类 SQL 的体现自顺应优化、筹划管理这类信息不肯定全部数据库都用于平常优化，但今世数据库越来越器重运行时反馈。
二、统计信息什么时间会更新

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

数据库通常提供显式下令，让用户或 DBA 自动网络统计信息。
常见下令情势包罗：

1. ANALYZE table_name;

复制代码

或：

1. UPDATE STATISTICS table_name;

复制代码

或：

1. DBMS_STATS.GATHER_TABLE_STATS(...);

复制代码

差别数据库下令差别，但目的类似：

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

复制代码

得当在这些场景手动更新：
场景缘故原由大量导入数据后原有统计信息已经禁绝确大量删除数据后表行数、分布都变了大量更新列值后列分布发生变革新建索引后优化器须要知道索引统计查询筹划忽然变差大概统计信息逾期分区装载 / 互换后新分区统计信息缺失或禁绝2. 自动更新

很多数据库会在表发生富足多的数据变革后，自动触发统计信息更新。
范例触发条件是：

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

复制代码

比方：

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

复制代码

自动更新的战略通常基于：
判断依据分析修改行数自前次统计以来修改了多少行修改比例修改行数占表总行数的比例表巨细大表和小表阈值大概差别统计信息年岁隔断前次网络已经多久查询需求某些数据库在优化时发现缺统计信息会触发网络3. 定期更新

生产体系中，常常会安排定时使命更新统计信息。
比方：

1. 每天凌晨
2. 每周末
3. 每次 ETL 之后
4. 每次批量装载之后

复制代码

如许做的缘故原由是：

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

复制代码

定期更新得当：
体系范例更新战略OLTP 体系自动更新 + 低峰期定期维护数据堆栈每次批处理处罚 / ETL 后更新分区表新分区加载后更新新分区统计报表体系数据革新后更新统计4. 采样更新

统计信息不肯定通过全表扫描得到。对于大表，数据库常常使用采样。
比方：

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

复制代码

采样的优点是：

1. 速度快，开销低。

复制代码

缺点是：

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

复制代码

对于特别告急的表或列，可以进步采样比例，乃至做全量统计。
5. 增量更新

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

1. orders 表按月份分区
2. 新装载 orders_2026_06 分区

复制代码

不必重新统计全部汗青分区，只须要：

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

复制代码

增量统计得当：

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

复制代码

6. 创建对象时更新

某些操纵会天生或革新统计信息，比方：
操纵大概产生的统计信息创建索引网络索引键分布、索引页数、高度等重修索引更新索引统计信息创建表初始统计信息为空或很少批量导入数据大概触发统计信息网络分区互换大概须要同步分区统计表重组 / VACUUM / OPTIMIZE大概影响页数、膨胀、物理布局统计三、统计信息不更新会有什么题目

假如统计信息逾期，优化器大概会做堕落误判断。
比方，原来表中只有：

1. orders：10 万行

复制代码

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

1. orders：1 亿行

复制代码

但统计信息仍然体现：

1. orders：10 万行

复制代码

优化器大概会错误地以为表很小，从而选择：

1. Nested Loop Join

复制代码

而不是更得当大表的：

1. Hash Join

复制代码

效果大概导致查询性能急剧降落。
四、一个范例例子

假设有表：

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

复制代码

数据库大概维护如下统计信息：
对象统计信息orders 表行数、页数、均匀行宽、表巨细order_id 列NDV、唯一性、最小值、最大值customer_id 列NDV、高频客户、NULL 比例status 列NDV、高频值，比方 paid、cancelledamount 列最小值、最大值、直方图order_date 列最小值、最大值、直方图、分区范围customer_id 索引索引高度、叶子页数、聚簇因子分区 orders_2026_06分区行数、分区页数、局部分布假如实验：

1. SELECT *
2. FROM orders
3. WHERE status = 'paid'
4.   AND amount > 100
5.   AND order_date >= '2026-01-01';

复制代码

优化器会使用：

1. status 的高频值统计
2. amount 的直方图
3. order_date 的分区统计
4. 表行数和页数
5. 相关索引统计

复制代码

来估算：

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

复制代码

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

更新方式触发时机特点手动更新DBA 或用户实验 ANALYZE / UPDATE STATISTICS 等下令可控，得当批量变动后自动更新表数据变革凌驾阈值方便，但大概有延伸定期更新每天、每周、低峰期使命稳固，得当生产体系采样更新大表统计时抽样网络开销低，但大概不敷精确全量更新扫描完备数据精确，但开销高增量更新分区表新增或修改部分分区得当大表和数据堆栈创建 / 重修索引建索引或重修索引时革新索引相干统计批量导入后大量 INSERT / LOAD 后防止优化器低估数据量大量删除后大批量 DELETE 后防止优化器高估数据量大量更新后UPDATE 改变列分布后防止选择率估计错误六、总结

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

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

复制代码

这些统计信息通常在：

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

复制代码

举行更新。
它们的作用可以概括为一句话：

统计信息是优化器估算行数和代价的依据；统计信息越精确，优化器越大概选择精确的实验筹划。

下面用教科书风格分析：逻辑优化之后，数据库怎样举行物理筹划搜索与代价估计。
一、逻辑优化之后得到了什么

逻辑优化之后，数据库得到的是一个颠末等价重写的逻辑查询筹划。
比方 SQL：

1. SELECT c.name, o.amount
2. FROM customers c
3. JOIN orders o
4.   ON c.customer_id = o.customer_id
5. WHERE c.region = 'Asia'
6.   AND o.amount > 100;

复制代码

逻辑优化后大概得到：

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

复制代码

这个筹划分析：

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

复制代码

但它还没有分析：

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

复制代码

这些题目属于物理筹划搜索与代价估计阶段。
二、物理筹划搜索与代价估计的焦点使命

逻辑筹划答复：

查询在逻辑上要做什么？

物理筹划搜索答复：

这些逻辑操纵具体用什么物理算法实验？

代价估计答复：

每种实验方式大概要花多少本钱？

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

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

复制代码

更精确地说，物理筹划搜索和代价估计是交织举行的，不是完全分开的两个阶段。
三、从逻辑算子到物理算子

逻辑算子只有语义，不规定实现方式。物理筹划天生的第一步，就是把逻辑算子映射为具体物理算子。
1. 表访问算子

逻辑上：

1. Scan(customers)

复制代码

物理上大概有多种实现：
物理访问方式寄义实用场景Seq Scan序次扫描整张表返回大量数据Index Scan使用索引扫描谓词选择率较高Index Lookup通过索引查少量行主键、唯一键查询Bitmap Scan先归并索引效果再访问表多个低选择性条件Covering Index Scan只读索引，不回表查询列都在索引中Partition Scan只扫描相干分区分区表查询比方：

1. WHERE c.region = 'Asia'

复制代码

假如 customers.region 上有索引，可以天生：

1. Index Scan[customers_region_idx]

复制代码

假如没有符合索引，则天生：

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

复制代码

2. 毗连算子

逻辑上：

1. customers ⋈ orders

复制代码

物理上大概实现为：
物理毗连算法特点实用场景Nested Loop Join双层循环匹配外表很小Index Nested Loop Join外表每行通过索引查内表内表毗连列有索引Hash Join一边建 Hash 表，一边探测大表等值毗连Sort-Merge Join双方排序后归并输入已有序或须要保序Broadcast Join分布式中广播小表小表毗连大表Shuffle Join分布式中按 key 重分布大表毗连大表同一个逻辑毗连：

1. R ⋈_R.a=S.b S

复制代码

大概天生：

1. HashJoin(R, S)
2. NestedLoopJoin(R, S)
3. IndexNestedLoopJoin(R, S)
4. MergeJoin(R, S)

复制代码

每种毗连算法的代价公式差别，以是必须分别估计。
3. 聚合算子

逻辑上：

1. γ_customer_id, COUNT(*)(orders)

复制代码

物理上大概实现为：
物理聚合方式特点Hash Aggregate用 Hash 表维护分组状态Sort Aggregate先排序，再按组聚合Streaming Aggregate输入已有序时边读边聚合Partial Aggregate并行或分布式情况中先局部聚合假如输入已经按 customer_id 有序，Streaming Aggregate 大概比 Hash Aggregate 更自制。
4. 排序算子

逻辑需求：

1. ORDER BY amount DESC

复制代码

物理上大概有：
实现方式分析Sort对全部输入排序Top-N Sort只维护前 N 个效果Index Order Scan使用索引自然序次Merge Sort分布式或并行归并比方：

1. ORDER BY amount DESC LIMIT 10

复制代码

假如有 amount 索引，优化器大概选择：

1. Index Scan[amount_idx DESC] + Limit[10]

复制代码

而不是：

1. Seq Scan + Sort + Limit

复制代码

四、代价估计估什么

代价估计通常分成两个条理：

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

复制代码

1. 基数估计

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

1. σ_region='Asia'(customers)

复制代码

假如：

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

复制代码

则估计输出：

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

复制代码

对于毗连：

1. R ⋈_R.a=S.b S

复制代码

常见估计公式是：

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

复制代码

此中 NDV 体现某列差别值的数目。
2. 本钱估计

本钱估计估算物理实验须要斲丧多少资源。
常见本钱包罗：
本钱范例寄义I/O 本钱读写磁盘页、随机 I/O、序次 I/OCPU 本钱比力、过滤、表达式盘算、Hash 盘算内存本钱Hash 表、排序缓冲区、聚合状态网络本钱分布式数据库中的数据传输并行本钱线程调理、数据互换、同步开销比方 Hash Join 的大抵本钱可以体现为：

1. Cost(HashJoin(R, S))
2. ≈ Cost(R) + Cost(S)
3. + BuildHashCost(R)
4. + ProbeHashCost(S)

复制代码

Index Nested Loop Join 的大抵本钱可以体现为：

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

复制代码

假如外表 R 很小，索引嵌套循环大概很自制；假如 R 很大，它大概非常昂贵。
五、访问路径搜索

对于每张表，优化器起首会天生候选访问路径。
比方：

1. SELECT *
2. FROM orders
3. WHERE order_date >= '2026-01-01'
4.   AND status = 'paid';

复制代码

假设有这些索引：

1. orders(order_date)
2. orders(status)
3. orders(status, order_date)

复制代码

优化器大概天生：

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

复制代码

然后分别估算：

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

复制代码

选择多少较优访问路径进入后续筹划搜索。
六、毗连序次搜索

多表毗连是物理筹划搜索中最复杂的部分。
比方：

1. SELECT *
2. FROM A
3. JOIN B ON A.x = B.x
4. JOIN C ON B.y = C.y
5. JOIN D ON C.z = D.z;

复制代码

逻辑上是：

1. A ⋈ B ⋈ C ⋈ D

复制代码

但实验序次可以有很多种：

1. ((A ⋈ B) ⋈ C) ⋈ D
3. ((B ⋈ C) ⋈ D) ⋈ A
5. (A ⋈ (B ⋈ C)) ⋈ D
7. (A ⋈ B) ⋈ (C ⋈ D)

复制代码

差别序次的中心效果大概差异巨大。
比方：

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

复制代码

那么通常应优先思量：

1. B ⋈ C

复制代码

由于它能先产生较小的中心效果。
七、动态规划式筹划搜索

经典优化器常用动态规划搜索毗连序次。
根本头脑是：

先找单表最优筹划，再找两表最优筹划，再找三表最优筹划，渐渐构造更大的筹划。

以三张表 A, B, C 为例。
1. 单表阶段

1. BestPlan(A)
2. BestPlan(B)
3. BestPlan(C)

复制代码

每个单表筹划大概包罗：

1. Seq Scan
2. Index Scan
3. Bitmap Scan

复制代码

优化器估算它们的代价，生存较优者。
2. 两表阶段

罗列两表毗连：

1. BestPlan(A, B)
2. BestPlan(A, C)
3. BestPlan(B, C)

复制代码

比方：

1. BestPlan(A, B)
2. =
3. min {
4.   HashJoin(BestPlan(A), BestPlan(B)),
5.   NestedLoopJoin(BestPlan(A), BestPlan(B)),
6.   MergeJoin(BestPlan(A), BestPlan(B))
7. }

复制代码

优化器会估算每个候选毗连筹划的代价，然后生存较优者。
3. 三表阶段

构造三表毗连：

1. BestPlan(A, B, C)

复制代码

可以由以下方式产生：

1. BestPlan(A, B) ⋈ C
2. BestPlan(A, C) ⋈ B
3. BestPlan(B, C) ⋈ A

复制代码

每一种又可以选择差别毗连算法：

1. Hash Join
2. Nested Loop Join
3. Merge Join

复制代码

终极生存估计代价最低的计划。
八、左深树、右深树和灌木树

毗连筹划通常可以体现为树。
1. 左深树

1.         ⋈
2.        / \
3.       ⋈   D
4.      / \
5.     ⋈   C
6.    / \
7.   A   B

复制代码

对应：

1. (((A ⋈ B) ⋈ C) ⋈ D)

复制代码

特点：

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

复制代码

2. 右深树

1.     ⋈
2.    / \
3.   A   ⋈
4.      / \
5.     B   ⋈
6.        / \
7.       C   D

复制代码

对应：

1. A ⋈ (B ⋈ (C ⋈ D))

复制代码

特点：

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

复制代码

3. 灌木树

1.       ⋈
2.      / \
3.     ⋈   ⋈
4.    / \ / \
5.   A  B C  D

复制代码

对应：

1. (A ⋈ B) ⋈ (C ⋈ D)

复制代码

特点：

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

复制代码

九、物理属性与 interesting properties

优化器比力筹划时，不但看当前代价，还会看筹划输出的物理属性。
常见物理属性包罗：
物理属性寄义排序属性输出是否已经按某列有序分区属性数据是否按某个 key 分布并行属性是否并行输出唯一性输出是否已经唯一覆盖性是否不须要回表物化状态中心效果是否已物化比方：

1. SELECT *
2. FROM orders
3. JOIN customers ON orders.customer_id = customers.customer_id
4. ORDER BY orders.order_date;

复制代码

筹划 A：

1. Hash Join
2. 输出无序
3. 当前代价低
4. 后面还需要 Sort

复制代码

筹划 B：

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

复制代码

假如背面有 ORDER BY，筹划 B 大概团体更优。
这种“对后续算子有用的物理属性”称为：

1. interesting properties

复制代码

因此优化器偶尔不会只生存当前代价最低的筹划，还会生存一些具有有用属性的候选筹划。
十、剪枝：为什么不能罗列全部筹划

多表毗连的候选筹划数目增长非常快。表越多，大概的毗连序次和物理实现越多。
因此优化器必须举行剪枝。
常见剪枝战略包罗：
剪枝方式寄义代价剪枝假如一个筹划显着比另一个筹划贵且无额外属性，就扬弃物理属性剪枝生存差别排序、分区属性的少数筹划搜索空间限定只搜索左深树或限定 join reorder 范围启发式规则优先毗连小表、优先下推过滤超时克制优化时间到达阈值后克制搜索Top-K 生存每个子题目只生存多少较优筹划比方，对于同一个关系聚集 {A, B}：

1. Plan 1:
2. Cost = 100
3. Output order = none
5. Plan 2:
6. Cost = 300
7. Output order = none

复制代码

假如二者输出属性类似，Plan 2 可以被剪掉。
但假如：

1. Plan 1:
2. Cost = 100
3. Output order = none
5. Plan 2:
6. Cost = 130
7. Output order = A.x

复制代码

Plan 2 大概被生存，由于后续 ORDER BY A.x 或 Merge Join 大概用得上。
十一、Volcano / Cascades 风格优化器

今世数据库优化器常使用 Volcano 或 Cascades 风格的搜索框架。
它们的根本头脑是：

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

复制代码

比方逻辑规则：

1. R ⋈ S ≡ S ⋈ R

复制代码

实现规则：

1. LogicalJoin → HashJoin
2. LogicalJoin → NestedLoopJoin
3. LogicalJoin → MergeJoin

复制代码

在这种框架中，优化器不是只处理处罚一棵固定的筹划树，而是在一个由等价表达式构成的搜索空间中探求最低代价实现。
十二、一个完备例子

思量 SQL：

1. SELECT c.name, o.amount
2. FROM customers c
3. JOIN orders o
4.   ON c.customer_id = o.customer_id
5. WHERE c.region = 'Asia'
6.   AND o.amount > 100
7. ORDER BY o.amount DESC
8. LIMIT 10;

复制代码

1. 逻辑优化后的筹划

1. Limit[10]
2. └── Sort[o.amount DESC]
3.     └── Projection[c.name, o.amount]
4.         └── Join[c.customer_id = o.customer_id]
5.             ├── Selection[c.region = 'Asia']
6.             │   └── customers
7.             └── Selection[o.amount > 100]
8.                 └── orders

复制代码

2. 天生候选访问路径

对 customers：

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

复制代码

对 orders：

1. O1: Seq Scan orders + Filter amount > 100
2. O2: Index Scan orders_amount_idx
3. O3: Index Scan orders_customer_id_idx

复制代码

3. 估算单表访问代价

假设统计信息体现：

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

复制代码

则估计：

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

复制代码

然后比力：

1. C1 和 C2 哪个更便宜？
2. O1 和 O2 哪个更便宜？

复制代码

4. 天生候选毗连筹划

候选筹划大概包罗：

1. P1:
2. HashJoin(C2, O1)
4. P2:
5. HashJoin(O1, C2)
7. P3:
8. NestedLoop(C2, IndexLookup orders_customer_id_idx)
10. P4:
11. MergeJoin(Sort C2 by customer_id, Sort O1 by customer_id)

复制代码

5. 对毗连筹划估算代价

比方：

1. Cost(P1)
2. = Cost(C2)
3. + Cost(O1)
4. + BuildHashCost(C2)
5. + ProbeHashCost(O1)
6. Cost(P3)
7. = Cost(C2)
8. + rows(C2) × Cost(IndexLookup orders_customer_id_idx)

复制代码

假如 C2 输出 100,000 行，索引查找要实验 100,000 次，代价大概较高。
但假如 C2 只输出 100 行，P3 大概非常自制。
6. 思量 ORDER BY 和 LIMIT

查询有：

1. ORDER BY o.amount DESC
2. LIMIT 10

复制代码

因此优化器还会思量：

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

复制代码

一个特别筹划大概是：

1. P5:
2. Limit[10]
3. └── NestedLoop
4.     ├── Index Scan orders_amount_idx DESC, condition amount > 100
5.     └── Index Lookup customers_pk
6.         Filter region = 'Asia'

复制代码

这个筹划的头脑是：

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

复制代码

它不肯定得当返回全部效果，但对 ORDER BY + LIMIT 10 大概非常高效。
这分析物理筹划搜索必须思量整个查询的上下文，而不能只看局部算子。
十三、终极物理筹划选择

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

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

复制代码

然后选择估计代价最低的计划。
终极筹划大概是：

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

复制代码

也大概是：

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

复制代码

终极选择哪个，取决于统计信息和代价模子。
十四、为什么优化器大概选错

优化器选择的是：

1. 估计代价最低的计划

复制代码

但不肯定是真实运行最快的筹划。
缘故原由包罗：
缘故原由分析统计信息逾期表行数、列分布禁绝确数据倾斜某些值特别常见列相干性独立性假设不建立参数未知预编译 SQL 中参数值未知缓存状态变革实际 I/O 本钱差别UDF 本钱难估函数实验代价不确定分布式数据倾斜某些节点数据过多代价模子简化真实硬件活动更复杂因此，优化器的目的通常不是找到理论绝对最优筹划，而是：

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

十五、总结

逻辑优化之后，数据库会进入物理筹划搜索与代价估计阶段。
其根本过程是：

1. 1. 从逻辑计划出发；
2. 2. 为每个逻辑算子生成可能的物理实现；
3. 3. 为每张表枚举访问路径；
4. 4. 为多表查询搜索 JOIN 顺序；
5. 5. 对每个候选物理计划估算输出行数和执行成本；
6. 6. 根据代价进行比较、剪枝和保留；
7. 7. 最终选择估计代价最低的物理执行计划。

复制代码

一句话概括：

逻辑优化决定“等价地做什么”，物理筹划搜索决定“具体怎么做”，代价估计负责给每种做法打分，优化器根据分数选择终极实验筹划。