DBPA · 10.2

查询优化与执行计划

在结果等价的前提下选择较低代价的执行计划

VER. 2608.2 Built with impress.js

学习目标

查询优化在结果等价的基础上比较逻辑改写、物理路径和执行方向

01解释非过程化 SQL 为何允许自动优化
02区分代数优化和物理优化
03应用选择与投影下推规则
04说明启发式与代价优化的差异
05依据选择率、块数、索引、内存和统计信息比较候选计划
06比较查询计划的需求驱动与主动生产在请求、缓冲和流水上的差异

2/15

LEARNING OBJECTIVES

查询优化连接内部表示与物理选路

高层表达让系统可以利用数据字典、统计信息和当前物理状态

用户／应用

用户和应用表达结果需求，不指定存取路径

优化器

优化器从合法内部表示出发改写逻辑表达式，再比较物理候选

物理状态

表块、索引、内存和数据分布变化后，系统可能重新优化

内部关系表示与操作算法→等价改写与物理选路

3/15

WHY OPTIMIZE

优化目标是用较小代价得到相同结果

集中式系统尤其关注块 I/O；分布式系统还要估计节点间通信

总成本　＝　I/O　＋　CPU　＋　内存　＋　通信

I/O

I/O 包括块的读取、写出和随机访问

CPU

CPU 处理比较、排序和哈希计算

内存

内存提供缓冲区以及排序、哈希工作区

通信

通信表示分布式节点之间传输数据

Takeaway

常见组合策略是先用启发式缩小候选，再估算代价并选择较优计划；实际优化器不一定固定按此顺序执行

4/15

COST MODEL

代数优化：改写逻辑，再选物理路径

结果不变，参与后续操作的中间关系变小

SQL→关系代数表达式→语法树→等价逻辑方案→物理计划

SELECT Student.Sname FROM Student, SC WHERE Student.Sno = SC.Sno AND SC.Cno = '81003'

Takeaway

在相同关系模式和语义下，Q1 ≡ Q2 ≡ Q3 表示结果相同；它们是等价关系代数表达式，不是已经确定的物理执行计划

5/15

ALGEBRAIC OPTIMIZATION

选择下推通常是最重要的启发式规则

先过滤元组，再连接和投影；在示例假设下，块读写估算可从约 2,002,100 降到约 200

示例假设：Student 有 1000 条记录，SC 有 10000 条记录，Cno='81003' 命中 50 条记录

计划	中间结果	示例假设下块读写估算
先笛卡儿积	约 10⁷ 个元组	约 2,002,100 块
先连接再选择	约 10⁴ 个连接结果	约 4,100 块
先选择 SC	只保留 50 条课程记录	约 200 块

Takeaway

差异来自中间结果规模和扫描次数；这些数字只属于本组示例假设，不是跨数据库常数

6/15

PUSH SELECTION

语法树优化把规则变成可检查步骤

重点是减少中间数据和重复扫描，同时保持关系代数等价

选择下推

把选择条件尽可能移向叶端

投影下推

把投影尽早下推，去掉无用列，但保留后续连接和选择所需属性

连接化

把笛卡儿积和连接条件合为连接

复用

结果较小且复用成本合算时，再共享公共子表达式

01Q1 先从笛卡儿积和合取条件开始
02拆分选择条件并把只涉及 SC 的条件下推
03保留 Sno 等后续连接属性，不把连接列投影掉
04再连接和投影得到 Q3，逐步检查结果等价

7/15

TREE RULES

物理优化在等价逻辑计划中选择存取算法

逻辑计划不变，扫描、索引、排序和哈希会改变执行代价

选择对象	候选	依据
单表选择	全表或索引扫描	表大小和选择率
等值连接	索引、排序—合并、哈希或嵌套循环	索引、排序、块数和内存
通用连接	嵌套循环等候选	块数量和可用缓冲
条件组合	组合索引或多个索引	条件结构与选择性

Takeaway

Student ⋈ SC 可使用嵌套循环、排序—合并、索引连接或哈希连接；物理优化依据条件筛选候选，不重新定义算法

8/15

PHYSICAL OPTIMIZATION

启发式规则先缩小候选计划

规则通常有效，但只是候选起点，不保证每种数据状态都最好

01主码等值查询：优先检查主码索引
02非主属性或范围查询：低选择率时考虑索引扫描，不把 10% 当作固定阈值
03AND 条件：比较组合索引、多个索引和全表扫描；OR 条件通常先考虑顺序扫描
04连接属性已有排序：考虑排序—合并连接
05内表连接属性有索引：考虑索引连接
06等值连接且构建输入适合内存：考虑哈希连接
07没有明显优势时再比较嵌套循环，并优先让块数较小的表作外表

9/15

HEURISTIC RULES

统计信息让物理选择可以被估算

优化器需要知道数据规模、分布和索引状态

信息	例子	用途
表级	元组数、块数、元组长度	扫描和连接成本
列级	不同值个数、分布	选择率估算
索引级	层数、叶数、选择基数	索引扫描成本
系统级	内存和通信条件	计划总体代价

均匀分布时 f ≈ 1/m　｜　全表扫描 cost ≈ B　｜　主码 B+树等值查找 `cost ≈ L+1`

Takeaway

不能保证。B、L、m 和 f 只形成代价估算；数据分布、缓存和统计信息变化都可能改变实际结果

10/15

COST ESTIMATION

查询计划描述算子如何产生结果

执行器按计划读取基本表或索引，并逐层产生输出

基本表／索引访问→选择／连接／投影算子→根节点结果

Takeaway

计划树同时描述访问路径和关系算子；叶节点表示基本表或索引访问

11/15

PLAN EXECUTION

执行计划可以需求驱动，也可以主动生产

两种方向对应不同的请求、缓冲和流水行为

方式	请求或元组关系	直观特点
自顶向下	根算子请求向下；元组逐层向上返回	需求驱动，按需拉取一条或一批
自底向上	叶算子生成元组写入缓冲，父算子取走	主动生产，可能受缓冲和阻塞影响
共同目标	按计划完成查询	结果语义不改变

Takeaway

不是。自顶向下时请求向下、结果向上；自底向上时叶算子主动生产元组

12/15

TOP DOWN OR BOTTOM UP

用等价、代价和执行方向理解查询优化

查询优化把语义等价的逻辑表达式连接到物理代价判断

等价

关系代数变换保持结果不变

逻辑

选择与投影尽早下推以减少中间结果

物理

启发式、统计信息和代价估算共同选择物理路径

执行

执行器按需求驱动或主动生产的方式推进算子

Takeaway

结果等价不代表代价相同；选择率、块数、内存和统计信息共同影响计划

13/15

RECAP

本节知识地图

14/15

KNOWLEDGE MAP

本节问题

01对 81003 查询说明 Q1 与 Q3 为何结果等价但代价不同？
02在 Q1 语法树上把 SC.Cno='81003' 下推，并列出必须保留的连接属性？
03给定等价表达式和索引，如何判断属于代数优化还是物理优化？
04给定 B、m、f、L、块数、排序、索引与内存，怎样选择扫描和 Student⋈SC 的连接算法？
05自顶向下的请求流、元组返回流与自底向上的缓冲生产分别是什么？

Takeaway

等价变换与代价估算需要结合选择率、块数和索引条件；执行器方向可用自顶向下与自底向上对照理解

15/15

CHECK YOUR UNDERSTANDING