西华师范大学计算机学院
第四章 关系系统及其查询优化
第四章 关系系统及其查询优化
4.1 关系系统
4.2 关系系统的查询优化
4.3 小结
关系系统
? 能够 在一定程度上 支持关系模型的数据库管理
系统是关系系统 。
? 由于关系模型中并非每一部分都是 同等 重要的
? 并不苛求一个实际的关系系统必须 完全 支持关
系模型 。
关系模型
? 关系数据结构
– 域及域上定义的关系
? 关系操作
– 并、交、差、广义笛卡尔积、选择、投影、连接、
除等
? 关系完整性
– 实体完整性、参照完整性、用户自己定义的完整性
关系系统的定义
一个数据库管理系统可定义为关系系统, 当且仅
当它至少支持：
1,关系数据库 （ 即关系数据结构 ）
在用户眼里,数据库是由表,并且只有表构成的 。
2,支持选择、投影和（自然）连接运算
对这些运算不要求用户定义任何物理存取路径
对关系系统的 最低 要求
关系系统的定义
● 不支持关系数据结构的系统显然不能称为关系系统
● 仅支持关系数据结构, 但没有选择, 投影和连接运算
功能的系统仍不能算作关系系统 。
– 原因：选择、投影、连接运算是最有用的运算，有了这三种
运算功能就能解决绝大部分的实际问题，提高用户的生产率
? 支持选择、投影和连接运算，但要求定义物理存取路
径，这种系统也不能算作真正的关系系统
– 原因：降低或丧失了数据的物理独立性
– 因此,关系系统必须 能自动选择路径,必须 能查询优化,这是关
系系统的关键技术。
4.1.2 关系系统的分类
? 分类依据：支持关系模型的程度
? 分类
⒈ 表式系统：支持关系数据结构 (即表 )，它不是关系系统。
S M
I
S M
I
S M
I
( a ) ( b ) ( c )
(a) (最小 )关系系统； (b) 关系完备的系统； (c) 全关系系统
一个关系数据模型 （ 圆 ） 由三部分组成,结构 S,完整性 I和数据操纵 M。 每一部分
中阴影的大小,表示支持该内容的程度 。
4.1.2 关系系统的分类
⒉ (最小 )关系系统：支持关系数据结构及选择、投影、连接关
系操作，如 FoxBASE和 FoxPro。
⒊ 关系完备的系统：支持关系数据结构及所有的关系代数操作
⒋ 全关系系统：支持关系模型的所有特征，特别支持数据结构
中域的概念,支持实体完整性和参照完整性。 目前,很多关系
系统已接近了此目标。
关系系统的分类 （续）
数据结构 数据操作 完整性
表式系统 表 ? ?
(最小 )关系系统 表 选择, 投影,
连接
?
关系完备的系统 表 ? ?
全关系系统 ? ? ?
第四章 关系系统及其查询优化
4.1 关系系统
4.2 关系系统的查询优化
4.3 小结
4.2 关系系统的查询优化
4.2.1 查询优化概述
4.2.2 查询优化的必要性
4.2.3 查询优化的一般准则
4.2.4 关系代数等价变换规则
4.2.5 关系代数表达式的优化算法
4.2.6 优化的一般步骤
4.2.1 查询优化概述
? 查询优化的必要性
– 为了达到所需的性能要求, 数据库系统必须
使用查询优化技术 。
? 查询优化的可能性
–关系表达式具有高度语义层次，使
DBMS可以从关系表达式中分析查询 语
义 。
由 DBMS进行查询优化的好处
? 自动优化系统中用户不必考虑如何最好地表达查询以
获得较好的效率
? 优化器可以比用户程序的 优化 做得更好
(1) 优化器可以从数据字典中获取许多统计信息, 而用户程序则难
以获得这些信息, 例如：每个基表中元组的数目, 每个域中值的
个数等 。 因此优化器可以对给定查询的执行策略作出更为精确的
计算, 从而更有可能选择最高效的执行方案 。
由 DBMS进行查询优化的好处
(2)如果数据库的物理统计信息改变了, 优化器可以自动对查询
重新优化 （ 即重新处理一遍原来的查询请求 ） 以选择相适应
的执行计划 。 而在非关系系统中必须重写程序, 这在实际应
用中往往是不太可能的 。
(3)优化器可以考虑一个给定查询的成百上千种不同的执行计划,
而程序员一般只能考虑有限的几种可能性 。
(4)优化器可以认为是包含着最优秀程序员的技巧和服务的程序 。
也即,优化器可以根据变化了的当前信息,自动选择一个对当时
情况较有利的执行计划 。 但用户程序是不可能有此性能的,
用户程序的执行计划是不会随系统当时的实际情况而变化的 。
查询优化目标
? 查询优化的目标
选择有效策略,等价变换给定的关系表达式,使
结果表达式求解 （ 程序 ） 的代价较小
? 实际系统的查询优化步骤
1,将查询转换成某种内部表示, 通常是语法树
2,根据一定的等价变换规则把语法树转换成标准
（ 优化 ） 形式
实际系统的查询优化步骤
3,选择低层的操作算法, 根据存取路径, 数据的存储
分布情况等, 对于语法树中的每一个操作, 计算各种
执行算法的执行代价以选择代价小的执行算法
4,生成查询计划 (查询执行方案 )
由以上三条最后生成了一系列的内部操作 。 根据这些
内部操作要求的执行次序,确定一个执行方案 。
代价模型
? 集中式数据库
? 单用户系统
总代价 = I/O代价 + CPU代价
? 多用户系统
总代价 = I/O代价 + CPU代价 + 内存代价
? 分布式数据库
总代价 = I/O代价 + CPU代价 [+ 内存代价 ] + 通信代价
4.2.2 查询优化的必要性
关系代数和关系演算具有等价性, 同一个
问题用同一种方法有不同的解决途径, 这些方
法结果相同, 但执行效率有较大差别 。 下面
先看一个实例, 说明查询优化的一般问题 。
例：求选修了课程Ｃ 2的学生姓名
SELECT Student.Sname
FROM Student,SC
WHERE Student.Sno=SC.Sno
AND SC.Cno='2';
查询优化的必要性（续）
假设 1：外存：
Student:1000条,SC:10000条,选修 2号课程,50条
假设 2：一个内存块装元组,10个 Student,或 100个 SC,
内存中一次可以存放, 5块 Student元组,
1块 SC元组和若干块连接结果元组
假设 3：读写速度,20块 /秒
假设 4：连接方法,基于数据块 的嵌套循环法
执行策略 1
Ｑ 1＝ ПＳ name(бStudent.Sno=SC.Sno ∧ SC.Cno='2'(Student× SC))
① Student× SC
一般的做法是,在内存中尽可能多地装入某个表 （ 如 s表 ） 的若
干块元组, 留出一块存放另一个表 （ 如 sc表 ） 的元组, 然后把内存中
sc的每个元组和 s的每个元组连接, 连接后的元组装满一块后就写到中
间文件上, 再从 sc表中读入一块和内存中的 s元组连接, 直到 sc表处理
完 。 这时再一次读入若干块 s元组, 读入一块 sc元组, 重复上述处理
过程, 直到把 s表处理完 。
在笛卡尔积操作中, 表 s的每个元组只装入内存一次, 而 sc的每个
元组却要反复多次装入内存 。
读取总块数 = 读 Student表块数 + 读 SC表遍数
*每遍块数
=1000/10+(1000/(10× 5)) × (10000/100)
=100+20× 100=2100
读数据时间 =2100/20=105秒
不同的执行策略,考虑 I/O时间
中间结果大小 = 1000*10000 = 107 (1千万条元组 )
写中间结果时间 = 10000000/10/20 = 50000秒
② б
? 假定内存处理时间不计,这一步读取中间文件花
费的时间需 5× 104秒（同写中间文件一样）
③ П
总时间 =105＋ 50000＋ 50000秒 = 100105秒
= 27.8小时
查询优化的必要性（续）
2,Ｑ 2＝ ПＳ name(бSC.Cno=' 2' (Student SC))
①
读取总块数 = 2100块
读数据时间 =2100/20=105秒
中间结果大小 =10000 （ 减少 1000倍 ）
写中间结果时间 =10000/10/20=50秒
② б读取中间文件, 执行选择运算
读数据时间 =50秒
③ П
总时间 ＝ 105＋ 50＋ 50秒＝ 205秒 =3.4分
查询优化的必要性（续）
3,Ｑ 2＝ ПSname(Student бSC.Cno=' 2' (SC))
① б
读 SC表总块数 = 10000/100=100块
读数据时间 =100/20=5秒
中间结果大小 =50条 不必写入外存
②
读 Student表总块数 = 1000/10=100块
读数据时间 =100/20=5秒
③ П
总时间 ＝ 5＋ 5秒＝ 10秒
查询优化的必要性（续）
4,Ｑ 2＝ ПＳ name(Student бSC.Cno='2' (SC))
假设 SC表在 Cno上有索引, Student表在 Sno上有
索引
① б
读 SC表索引 =
读 SC表总块数 = 50/100<1块
读数据时间
中间结果大小 =50条 不必写入外存
查询优化的必要性（续）
②
读 Student表索引 =
读 Student表总块数 = 50/10=5块
读数据时间
③ П
总时间 <10秒
4.2.3 查询优化的一般准则
查询优化主要是合理安排操作的顺序, 使系统效率较高 。
优化是相对的, 变换后的表达式不一定是所有等价表达式中
执行时间最少的 。 因此, 优化没有一个特定的模式, 常根
据经验, 运用下列策略来完成 。
? 选择运算应尽可能先做
– 在查询优化中, 这是最重要, 最基本的一条 。 选择运算
使中间结果显著变小, 减少运算量和从外存读块的次数,
从而使执行时间成数量级地减少 。
? 在执行连接操作前对关系适当进行预处理
– 按连接属性排序或在连接属性上建立索引, 提高存取效
率 。
– 例如,对两个表进行自然连接操作,则可先对两表建立有关
索引,然后,只要对两表进行一遍扫描即可完成自然连接操
作 。 提高了连接的速度 。
4.2.3 查询优化的一般准则（续）
? 同一关系的投影运算和选择运算同时进
行。 这样做可避免重复扫描关系，从而
达到缩短时间的目的。
? 将投影运算与其前面或后面的双目运算
结合
– 目的：减少扫描关系的遍数
查询优化的一般准则 （续）
? 某些选择运算＋在其前面执行的笛卡尔积
===> 连接运算, 避免选择操作是在笛卡
尔积运算完的一个较大关系上进行, 减少时间
和空间的开销 。
例,бStudent.Sno=SC.Sno (Student× SC)
Student SC
? 找出公共子表达式,并把运算结果存于外存 。
需要时,再从外存读入, 以免重复计算 。
4.2.4 关系代数等价变换规则
? 关系代数是关系数据理论的基础, 关系演算, SQL语
言等都可以转化为关系代数去实现 。 所以关系代数表
达式的优化是查询优化的基本课题 。
? 关系代数表达式等价
– 指用相同的关系代替两个表达式中相应的关系所得
到的结果是相同的,两个关系代数表达式 E1和 E2等价,
一般表示为,E1≡E2,例如 R∩S≡R–(R-S) 。
– 上面的优化策略大部分都涉及到代数表达式的变换
常用的等价变换规则
设 E1,E2等是关系代数表达式,F是条件表达式
l,连接、笛卡尔积交换律
E1× E2≡ E2× E1
E1 E2≡E2 E1
E1 F E2≡E2 F E1
关系代数等价变换规则（续）
2,连接, 笛卡尔积的结合律
(E1× E2) × E3 ≡ E1 × (E2× E3)
(E1 E2) E3 ≡ E1 (E2 E3)
(E1 E2) E3 ≡ E1 (E2 E3)
F1 F2 F1 F2
关系代数等价变换规则（续）
3,投影的串接定律
π A1,A2,?,An(π B1,B2,?,Bm(E))≡ π A1,A2,?,An (E)
假设：
1) E是关系代数表达式
2) Ai(i=1,2,…,n),Bj(j=l,2,…, m)是属性名
3){A1,A2,…,An}构成 {Bl,B2,…, Bm}的子集
即：对同一关系连续的多个投影可以转换为仅含最
少属性的投影操作 。
关系代数等价变换规则（续）
4,选择的串接定律
бF1 （ б F2（ E）） ≡ бF1∧ F2(E)
– 选择的串接律说明 对同一关系连续的多个
选择可以转换为一个用 AND连接的选择操作 。
– 这样一次就可检查全部条件 。
关系代数等价变换规则（续）
5,选择与投影的交换律
(1)假设, 选择条件 F只涉及属性 A1,…,An
бF (πA1,A2,?,An(E))≡ πA1,A2,?,An(бF(E))
(2)假设, F中有不属于 A1,…,An的属性 B1,…,Bm
π A1,A2,?,An ( бF(E))≡
πA1,A2,?,An(бF (πA1,A2,?,An,B1,B2,?,Bm(E)))
关系代数等价变换规则（续）
6,选择与笛卡尔积的交换律
(1) 假设,F中涉及的属性都是 E1中的属性
бF (E1× E2)≡бF (E1)× E2
(2) 假设,F=F1∧ F2,并且 F1只涉及 E1中的属性,
F2只涉及 E2中的属性
则由上面的等价变换规则 1,4,6可推出：
бF(E1× E2) ≡б F1(E1)× бF2 (E2)
关系代数等价变换规则（续）
(3) 假设,F=F1∧ F2，
F1只涉及 E1中的属性,
F2涉及 E1和 E2两者的属性
бF(E1× E2)≡б F2(бF1(E1)× E2)
它使部分选择在笛卡尔积前先做
关系代数等价变换规则（续）
7,选择与并的交换
假设,E=E1∪ E2,E1,E2有相同的属性名
бF(E1∪ E2)≡ бF(E1)∪ бF(E2)
8,选择与差运算的交换
假设,E1与 E2有相同的属性名
бF(E1-E2)≡ бF(E1) - бF(E2)
关系代数等价变换规则（续）
9,投影与笛卡尔积的交换
假设,E1和 E2是两个关系表达式,
A1,…,An是 E1的属性,
B1,…,Bm是 E2的属性
π A1,A2,…,An,B1,B2,…,Bm （ E1× E2)≡
π A1,A2,…,An（ E1)× π B1,B2,…,Bm(E2)
关系代数等价变换规则（续）
l0,投影与并的交换
假设,E1和 E2 有相同的属性名
π A1,A2,…,An(E1∪ E2)≡
π A1,A2,…,An(E1)∪ π A1,A2,…,An(E2)
小结
1-2,连接, 笛卡尔积 的交换律, 结合律
3,合并或分解 投影 运算
4,合并或分解 选择 运算
5-8,选择运算与其他运算交换
5,9,10,投影运算与其他运算交换
4.2 关系系统的查询优化
4.2.1 查询优化概述
4.2.2 查询优化的必要性
4.2.3 查询优化的一般准则
4.2.4 关系代数等价变换规则
4.2.5 关系代数表达式的优化算法
4.2.6 优化的一般步骤
4.2.5 关系代数表达式的优化算法
算法：关系表达式的优化
输入：一个关系表达式的语法树 。
输出：计算该表达式的程序 。
方法：
（ 1） 分解选择运算
利用规则 4把形如 бF1 ∧ F2 ∧ … ∧ Fn (E)变换为
бF1 (бF2(… (бFn(E))… ))
关系代数表达式的优化算法 (续 )
（ 2） 通过交换选择运算, 将其尽可能移到叶端
对每一个选择, 利用规则 4～ 8尽可能把它移到
树的叶端 。
（ 3） 通过交换投影运算, 将其尽可能移到叶端
对每一个投影利用规则 3,9,l0,5中的一般形
式尽可能把它移向树的叶端 。
关系代数表达式的优化算法 (续 )
（ 4） 合并串接的选择和投影, 以便能同时执行
或在一次扫描中完成
– 利用规则 3～ 5把选择和投影的串接合并成单
个选择, 单个投影或一个选择后跟一个投影 。
– 使多个选择或投影能同时执行, 或在一次扫
描中全部完成
– 尽管这种变换似乎违背, 投影尽可能早做,
的原则, 但这样做效率更高 。
关系代数表达式的优化算法 (续 )
（ 5） 对内结点分组
– 把上述得到的语法树的内节点分组 。
– 每一双目运算 (×,, ∪, -)和它所有的直
接祖先为一组 (这些直接祖先是 б,π运算 )。
– 如果其后代直到叶子全是单目运算, 则也将
它们并入该组, 但当双目运算是笛卡尔积
(× ),而且其后的选择不能与它结合为等值
连接时除外 。 把这些单目运算单独分为一组 。
关系代数表达式的优化算法 (续 )
（ 6） 生成程序
– 生成一个程序, 每组结点的计算是程序中的
一步 。
– 各步的顺序是任意的, 只要保证任何一组的
计算不会在它的后代组之前计算 。
4.2 关系系统的查询优化
4.2.1 查询优化概述
4.2.2 查询优化的必要性
4.2.3 查询优化的一般准则
4.2.4 关系代数等价变换规则
4.2.5 关系代数表达式的优化算法
4.2.6 优化的一般步骤
4.2.6 优化的一般步骤
1,把查询转换成某种内部表示
2,代数优化：把语法树转换成标准 （ 优化 ）
形式
3,物理优化：选择低层的存取路径
4．生成查询计划，选择代价最小的
优化的一般步骤 (续 )
（ 1） 把查询转换成某种内部表示
例：求选修了课程Ｃ 2的学生姓名
SELECT Student.Sname
FROM Student,SC
WHERE Student.Sno=SC.Sno
AND SC.Cno='2';
（ 1）把查询转换成某种内部表示
语法树 结果
project(Sname)
select(SC.Cno=?2?)
join(Student.Sno=SC.Sno)
Student SC
关系代数语法树
πSname
?SC.Cno=’2’
?Student.Sno=SC.Sno
×
Student SC
（ 2）代数优化
利用优化算法把语法树转换成标准 （ 优化 ） 形式
πSname
?Student.Sno=SC.Sno
?SC.Cno=?2?
×
Student
SC
（ 3）物理优化：选择低层的存取路径
- 优化器查找数据字典获得当前数据库状态信息
? 选择字段上是否有索引
? 连接的两个表是否有序
? 连接字段上是否有索引
– 然后根据一定的优化规则选择存取路径
如本例中若 SC表上建有 Cno的索引, 则应该利
用这个索引, 而不必顺序扫描 SC表 。
（ 4）生成查询计划，选择代价最小的
– 在作连接运算时, 若两个表 (设为 R1,R2)均无序, 连
接属性上也没有索引, 则可以有下面几种查询计划,
? 对两个表作排序预处理
? 对 R1在连接属性上建索引
? 对 R2在连接属性上建索引
? 在 R1,R2的连接属性上均建索引
– 对不同的查询计划计算代价, 选择代价最小的一个 。
– 在计算代价时主要考虑磁盘读写的 I/O数, 内存 CPU处
理时间在粗略计算时可不考虑 。
【 例 】 有职工和部门构成的关系数据库：
EMP（编号 E＃，姓名 EN，性别 SEX，年龄 AGE，工资 SAL，部
门 D＃）,
DEPT（部门号 D＃，部门名 DN，管理者号 MGR，地址 ADD）
求出管理者号为 18所在部门的职工姓名,且他
们的工资不超过 500元。
解,依据题意可写出如下查询：
Q1,πEN（（ EMP σMGR=′18′（ DEPT））
－ （ σSAL>′500′（ EMP） σMGR=′18′（ DEPT）））
? 对应的查询树如下图 (a)所示 。 其优化过程从合并
树叶 EMP和 DEPT开始, 然后依据各种等价变换规
则, 进行一系列变换, 最后形成图 (f)。 这一查询
对有经验的读者可直接写出优化结果：
Q2,πEN（ πEN,D＃ （ σNOT SAL>′50０ ′（ EMP））
πD＃ （ σMGR=′18′（ DEPT）））
图 查询优化过程示意图
?
EN
?
m g r ＝ '1 8 '
—
E M P ?
s al ＞ '5 0 0 '
?
m g r ＝ '1 8 '
D E P T E M P D E P T
( a )
?
EN
—
?
m g r ＝ '1 8 '
?
s al ＞ '5 0 0 '
D E P T E M P
( b )
查询优化过程示意图
?
EN
?
n o t (s al ＞ '5 0 0 ')
?
m g r ＝ '1 8 '
E M P
D E P T
?
EN
—
?
m g r ＝ '1 8 '
E M P
D E P T
?
s al ＞ '5 0 0 '
?
EN
?
n o t (s al ＞ '5 0 0 ')
?
m g r ＝ '1 8 '
E M P D E P T
( d )
查询优化过程示意图
?
EN
?
EN, D#
?
n o t (s al ＞ '5 0 0 ')
?
mg r ＝ '1 8 '
E M P D E P T
( e )
?
EN
?
EN, D#
?
D#
?
n o t (s al ＞ '5 0 0 ')
?
mg r ＝ '1 8 '
E M P D E P T
( f )
第四章 关系系统及其查询优化
4.1 关系系统
4.2 关系系统的查询优化
4.3 小结
4.3 小结
? 关系系统
– 关系系统的定义
一个数据库管理系统可定义为关系系统, 当且仅当
它至少支持：
1,关系数据库 （ 即关系数据结构 ）
2,支持选择、投影和（自然）连接运算，
且不要求用户定义任何物理存取路径
小结 （续）
–关系系统的分类
? 表式系统
? (最小 )关系系统
? 关系完备系统
? 全关系系统
关系系统的分类 （续）
数据结构 数据操作 完整性
表式系统 表 ? ?
(最小 )关系系统 表 选择, 投影,
连接
?
关系完备的系统 表 ? ?
全关系系统 ? ? ?
小结 （续）
? 关系系统的查询优化
– 代数优化：关系代数表达式的优化
? 关系代数等价变换规则
? 关系代数表达式的优化算法
– 物理优化：存取路径和低层操作算法的选择
第四章 关系系统及其查询优化
第四章 关系系统及其查询优化
4.1 关系系统
4.2 关系系统的查询优化
4.3 小结
关系系统
? 能够 在一定程度上 支持关系模型的数据库管理
系统是关系系统 。
? 由于关系模型中并非每一部分都是 同等 重要的
? 并不苛求一个实际的关系系统必须 完全 支持关
系模型 。
关系模型
? 关系数据结构
– 域及域上定义的关系
? 关系操作
– 并、交、差、广义笛卡尔积、选择、投影、连接、
除等
? 关系完整性
– 实体完整性、参照完整性、用户自己定义的完整性
关系系统的定义
一个数据库管理系统可定义为关系系统, 当且仅
当它至少支持：
1,关系数据库 （ 即关系数据结构 ）
在用户眼里,数据库是由表,并且只有表构成的 。
2,支持选择、投影和（自然）连接运算
对这些运算不要求用户定义任何物理存取路径
对关系系统的 最低 要求
关系系统的定义
● 不支持关系数据结构的系统显然不能称为关系系统
● 仅支持关系数据结构, 但没有选择, 投影和连接运算
功能的系统仍不能算作关系系统 。
– 原因：选择、投影、连接运算是最有用的运算，有了这三种
运算功能就能解决绝大部分的实际问题，提高用户的生产率
? 支持选择、投影和连接运算，但要求定义物理存取路
径，这种系统也不能算作真正的关系系统
– 原因：降低或丧失了数据的物理独立性
– 因此,关系系统必须 能自动选择路径,必须 能查询优化,这是关
系系统的关键技术。
4.1.2 关系系统的分类
? 分类依据：支持关系模型的程度
? 分类
⒈ 表式系统：支持关系数据结构 (即表 )，它不是关系系统。
S M
I
S M
I
S M
I
( a ) ( b ) ( c )
(a) (最小 )关系系统； (b) 关系完备的系统； (c) 全关系系统
一个关系数据模型 （ 圆 ） 由三部分组成,结构 S,完整性 I和数据操纵 M。 每一部分
中阴影的大小,表示支持该内容的程度 。
4.1.2 关系系统的分类
⒉ (最小 )关系系统：支持关系数据结构及选择、投影、连接关
系操作，如 FoxBASE和 FoxPro。
⒊ 关系完备的系统：支持关系数据结构及所有的关系代数操作
⒋ 全关系系统：支持关系模型的所有特征，特别支持数据结构
中域的概念,支持实体完整性和参照完整性。 目前,很多关系
系统已接近了此目标。
关系系统的分类 （续）
数据结构 数据操作 完整性
表式系统 表 ? ?
(最小 )关系系统 表 选择, 投影,
连接
?
关系完备的系统 表 ? ?
全关系系统 ? ? ?
第四章 关系系统及其查询优化
4.1 关系系统
4.2 关系系统的查询优化
4.3 小结
4.2 关系系统的查询优化
4.2.1 查询优化概述
4.2.2 查询优化的必要性
4.2.3 查询优化的一般准则
4.2.4 关系代数等价变换规则
4.2.5 关系代数表达式的优化算法
4.2.6 优化的一般步骤
4.2.1 查询优化概述
? 查询优化的必要性
– 为了达到所需的性能要求, 数据库系统必须
使用查询优化技术 。
? 查询优化的可能性
–关系表达式具有高度语义层次，使
DBMS可以从关系表达式中分析查询 语
义 。
由 DBMS进行查询优化的好处
? 自动优化系统中用户不必考虑如何最好地表达查询以
获得较好的效率
? 优化器可以比用户程序的 优化 做得更好
(1) 优化器可以从数据字典中获取许多统计信息, 而用户程序则难
以获得这些信息, 例如：每个基表中元组的数目, 每个域中值的
个数等 。 因此优化器可以对给定查询的执行策略作出更为精确的
计算, 从而更有可能选择最高效的执行方案 。
由 DBMS进行查询优化的好处
(2)如果数据库的物理统计信息改变了, 优化器可以自动对查询
重新优化 （ 即重新处理一遍原来的查询请求 ） 以选择相适应
的执行计划 。 而在非关系系统中必须重写程序, 这在实际应
用中往往是不太可能的 。
(3)优化器可以考虑一个给定查询的成百上千种不同的执行计划,
而程序员一般只能考虑有限的几种可能性 。
(4)优化器可以认为是包含着最优秀程序员的技巧和服务的程序 。
也即,优化器可以根据变化了的当前信息,自动选择一个对当时
情况较有利的执行计划 。 但用户程序是不可能有此性能的,
用户程序的执行计划是不会随系统当时的实际情况而变化的 。
查询优化目标
? 查询优化的目标
选择有效策略,等价变换给定的关系表达式,使
结果表达式求解 （ 程序 ） 的代价较小
? 实际系统的查询优化步骤
1,将查询转换成某种内部表示, 通常是语法树
2,根据一定的等价变换规则把语法树转换成标准
（ 优化 ） 形式
实际系统的查询优化步骤
3,选择低层的操作算法, 根据存取路径, 数据的存储
分布情况等, 对于语法树中的每一个操作, 计算各种
执行算法的执行代价以选择代价小的执行算法
4,生成查询计划 (查询执行方案 )
由以上三条最后生成了一系列的内部操作 。 根据这些
内部操作要求的执行次序,确定一个执行方案 。
代价模型
? 集中式数据库
? 单用户系统
总代价 = I/O代价 + CPU代价
? 多用户系统
总代价 = I/O代价 + CPU代价 + 内存代价
? 分布式数据库
总代价 = I/O代价 + CPU代价 [+ 内存代价 ] + 通信代价
4.2.2 查询优化的必要性
关系代数和关系演算具有等价性, 同一个
问题用同一种方法有不同的解决途径, 这些方
法结果相同, 但执行效率有较大差别 。 下面
先看一个实例, 说明查询优化的一般问题 。
例：求选修了课程Ｃ 2的学生姓名
SELECT Student.Sname
FROM Student,SC
WHERE Student.Sno=SC.Sno
AND SC.Cno='2';
查询优化的必要性（续）
假设 1：外存：
Student:1000条,SC:10000条,选修 2号课程,50条
假设 2：一个内存块装元组,10个 Student,或 100个 SC,
内存中一次可以存放, 5块 Student元组,
1块 SC元组和若干块连接结果元组
假设 3：读写速度,20块 /秒
假设 4：连接方法,基于数据块 的嵌套循环法
执行策略 1
Ｑ 1＝ ПＳ name(бStudent.Sno=SC.Sno ∧ SC.Cno='2'(Student× SC))
① Student× SC
一般的做法是,在内存中尽可能多地装入某个表 （ 如 s表 ） 的若
干块元组, 留出一块存放另一个表 （ 如 sc表 ） 的元组, 然后把内存中
sc的每个元组和 s的每个元组连接, 连接后的元组装满一块后就写到中
间文件上, 再从 sc表中读入一块和内存中的 s元组连接, 直到 sc表处理
完 。 这时再一次读入若干块 s元组, 读入一块 sc元组, 重复上述处理
过程, 直到把 s表处理完 。
在笛卡尔积操作中, 表 s的每个元组只装入内存一次, 而 sc的每个
元组却要反复多次装入内存 。
读取总块数 = 读 Student表块数 + 读 SC表遍数
*每遍块数
=1000/10+(1000/(10× 5)) × (10000/100)
=100+20× 100=2100
读数据时间 =2100/20=105秒
不同的执行策略,考虑 I/O时间
中间结果大小 = 1000*10000 = 107 (1千万条元组 )
写中间结果时间 = 10000000/10/20 = 50000秒
② б
? 假定内存处理时间不计,这一步读取中间文件花
费的时间需 5× 104秒（同写中间文件一样）
③ П
总时间 =105＋ 50000＋ 50000秒 = 100105秒
= 27.8小时
查询优化的必要性（续）
2,Ｑ 2＝ ПＳ name(бSC.Cno=' 2' (Student SC))
①
读取总块数 = 2100块
读数据时间 =2100/20=105秒
中间结果大小 =10000 （ 减少 1000倍 ）
写中间结果时间 =10000/10/20=50秒
② б读取中间文件, 执行选择运算
读数据时间 =50秒
③ П
总时间 ＝ 105＋ 50＋ 50秒＝ 205秒 =3.4分
查询优化的必要性（续）
3,Ｑ 2＝ ПSname(Student бSC.Cno=' 2' (SC))
① б
读 SC表总块数 = 10000/100=100块
读数据时间 =100/20=5秒
中间结果大小 =50条 不必写入外存
②
读 Student表总块数 = 1000/10=100块
读数据时间 =100/20=5秒
③ П
总时间 ＝ 5＋ 5秒＝ 10秒
查询优化的必要性（续）
4,Ｑ 2＝ ПＳ name(Student бSC.Cno='2' (SC))
假设 SC表在 Cno上有索引, Student表在 Sno上有
索引
① б
读 SC表索引 =
读 SC表总块数 = 50/100<1块
读数据时间
中间结果大小 =50条 不必写入外存
查询优化的必要性（续）
②
读 Student表索引 =
读 Student表总块数 = 50/10=5块
读数据时间
③ П
总时间 <10秒
4.2.3 查询优化的一般准则
查询优化主要是合理安排操作的顺序, 使系统效率较高 。
优化是相对的, 变换后的表达式不一定是所有等价表达式中
执行时间最少的 。 因此, 优化没有一个特定的模式, 常根
据经验, 运用下列策略来完成 。
? 选择运算应尽可能先做
– 在查询优化中, 这是最重要, 最基本的一条 。 选择运算
使中间结果显著变小, 减少运算量和从外存读块的次数,
从而使执行时间成数量级地减少 。
? 在执行连接操作前对关系适当进行预处理
– 按连接属性排序或在连接属性上建立索引, 提高存取效
率 。
– 例如,对两个表进行自然连接操作,则可先对两表建立有关
索引,然后,只要对两表进行一遍扫描即可完成自然连接操
作 。 提高了连接的速度 。
4.2.3 查询优化的一般准则（续）
? 同一关系的投影运算和选择运算同时进
行。 这样做可避免重复扫描关系，从而
达到缩短时间的目的。
? 将投影运算与其前面或后面的双目运算
结合
– 目的：减少扫描关系的遍数
查询优化的一般准则 （续）
? 某些选择运算＋在其前面执行的笛卡尔积
===> 连接运算, 避免选择操作是在笛卡
尔积运算完的一个较大关系上进行, 减少时间
和空间的开销 。
例,бStudent.Sno=SC.Sno (Student× SC)
Student SC
? 找出公共子表达式,并把运算结果存于外存 。
需要时,再从外存读入, 以免重复计算 。
4.2.4 关系代数等价变换规则
? 关系代数是关系数据理论的基础, 关系演算, SQL语
言等都可以转化为关系代数去实现 。 所以关系代数表
达式的优化是查询优化的基本课题 。
? 关系代数表达式等价
– 指用相同的关系代替两个表达式中相应的关系所得
到的结果是相同的,两个关系代数表达式 E1和 E2等价,
一般表示为,E1≡E2,例如 R∩S≡R–(R-S) 。
– 上面的优化策略大部分都涉及到代数表达式的变换
常用的等价变换规则
设 E1,E2等是关系代数表达式,F是条件表达式
l,连接、笛卡尔积交换律
E1× E2≡ E2× E1
E1 E2≡E2 E1
E1 F E2≡E2 F E1
关系代数等价变换规则（续）
2,连接, 笛卡尔积的结合律
(E1× E2) × E3 ≡ E1 × (E2× E3)
(E1 E2) E3 ≡ E1 (E2 E3)
(E1 E2) E3 ≡ E1 (E2 E3)
F1 F2 F1 F2
关系代数等价变换规则（续）
3,投影的串接定律
π A1,A2,?,An(π B1,B2,?,Bm(E))≡ π A1,A2,?,An (E)
假设：
1) E是关系代数表达式
2) Ai(i=1,2,…,n),Bj(j=l,2,…, m)是属性名
3){A1,A2,…,An}构成 {Bl,B2,…, Bm}的子集
即：对同一关系连续的多个投影可以转换为仅含最
少属性的投影操作 。
关系代数等价变换规则（续）
4,选择的串接定律
бF1 （ б F2（ E）） ≡ бF1∧ F2(E)
– 选择的串接律说明 对同一关系连续的多个
选择可以转换为一个用 AND连接的选择操作 。
– 这样一次就可检查全部条件 。
关系代数等价变换规则（续）
5,选择与投影的交换律
(1)假设, 选择条件 F只涉及属性 A1,…,An
бF (πA1,A2,?,An(E))≡ πA1,A2,?,An(бF(E))
(2)假设, F中有不属于 A1,…,An的属性 B1,…,Bm
π A1,A2,?,An ( бF(E))≡
πA1,A2,?,An(бF (πA1,A2,?,An,B1,B2,?,Bm(E)))
关系代数等价变换规则（续）
6,选择与笛卡尔积的交换律
(1) 假设,F中涉及的属性都是 E1中的属性
бF (E1× E2)≡бF (E1)× E2
(2) 假设,F=F1∧ F2,并且 F1只涉及 E1中的属性,
F2只涉及 E2中的属性
则由上面的等价变换规则 1,4,6可推出：
бF(E1× E2) ≡б F1(E1)× бF2 (E2)
关系代数等价变换规则（续）
(3) 假设,F=F1∧ F2，
F1只涉及 E1中的属性,
F2涉及 E1和 E2两者的属性
бF(E1× E2)≡б F2(бF1(E1)× E2)
它使部分选择在笛卡尔积前先做
关系代数等价变换规则（续）
7,选择与并的交换
假设,E=E1∪ E2,E1,E2有相同的属性名
бF(E1∪ E2)≡ бF(E1)∪ бF(E2)
8,选择与差运算的交换
假设,E1与 E2有相同的属性名
бF(E1-E2)≡ бF(E1) - бF(E2)
关系代数等价变换规则（续）
9,投影与笛卡尔积的交换
假设,E1和 E2是两个关系表达式,
A1,…,An是 E1的属性,
B1,…,Bm是 E2的属性
π A1,A2,…,An,B1,B2,…,Bm （ E1× E2)≡
π A1,A2,…,An（ E1)× π B1,B2,…,Bm(E2)
关系代数等价变换规则（续）
l0,投影与并的交换
假设,E1和 E2 有相同的属性名
π A1,A2,…,An(E1∪ E2)≡
π A1,A2,…,An(E1)∪ π A1,A2,…,An(E2)
小结
1-2,连接, 笛卡尔积 的交换律, 结合律
3,合并或分解 投影 运算
4,合并或分解 选择 运算
5-8,选择运算与其他运算交换
5,9,10,投影运算与其他运算交换
4.2 关系系统的查询优化
4.2.1 查询优化概述
4.2.2 查询优化的必要性
4.2.3 查询优化的一般准则
4.2.4 关系代数等价变换规则
4.2.5 关系代数表达式的优化算法
4.2.6 优化的一般步骤
4.2.5 关系代数表达式的优化算法
算法：关系表达式的优化
输入：一个关系表达式的语法树 。
输出：计算该表达式的程序 。
方法：
（ 1） 分解选择运算
利用规则 4把形如 бF1 ∧ F2 ∧ … ∧ Fn (E)变换为
бF1 (бF2(… (бFn(E))… ))
关系代数表达式的优化算法 (续 )
（ 2） 通过交换选择运算, 将其尽可能移到叶端
对每一个选择, 利用规则 4～ 8尽可能把它移到
树的叶端 。
（ 3） 通过交换投影运算, 将其尽可能移到叶端
对每一个投影利用规则 3,9,l0,5中的一般形
式尽可能把它移向树的叶端 。
关系代数表达式的优化算法 (续 )
（ 4） 合并串接的选择和投影, 以便能同时执行
或在一次扫描中完成
– 利用规则 3～ 5把选择和投影的串接合并成单
个选择, 单个投影或一个选择后跟一个投影 。
– 使多个选择或投影能同时执行, 或在一次扫
描中全部完成
– 尽管这种变换似乎违背, 投影尽可能早做,
的原则, 但这样做效率更高 。
关系代数表达式的优化算法 (续 )
（ 5） 对内结点分组
– 把上述得到的语法树的内节点分组 。
– 每一双目运算 (×,, ∪, -)和它所有的直
接祖先为一组 (这些直接祖先是 б,π运算 )。
– 如果其后代直到叶子全是单目运算, 则也将
它们并入该组, 但当双目运算是笛卡尔积
(× ),而且其后的选择不能与它结合为等值
连接时除外 。 把这些单目运算单独分为一组 。
关系代数表达式的优化算法 (续 )
（ 6） 生成程序
– 生成一个程序, 每组结点的计算是程序中的
一步 。
– 各步的顺序是任意的, 只要保证任何一组的
计算不会在它的后代组之前计算 。
4.2 关系系统的查询优化
4.2.1 查询优化概述
4.2.2 查询优化的必要性
4.2.3 查询优化的一般准则
4.2.4 关系代数等价变换规则
4.2.5 关系代数表达式的优化算法
4.2.6 优化的一般步骤
4.2.6 优化的一般步骤
1,把查询转换成某种内部表示
2,代数优化：把语法树转换成标准 （ 优化 ）
形式
3,物理优化：选择低层的存取路径
4．生成查询计划，选择代价最小的
优化的一般步骤 (续 )
（ 1） 把查询转换成某种内部表示
例：求选修了课程Ｃ 2的学生姓名
SELECT Student.Sname
FROM Student,SC
WHERE Student.Sno=SC.Sno
AND SC.Cno='2';
（ 1）把查询转换成某种内部表示
语法树 结果
project(Sname)
select(SC.Cno=?2?)
join(Student.Sno=SC.Sno)
Student SC
关系代数语法树
πSname
?SC.Cno=’2’
?Student.Sno=SC.Sno
×
Student SC
（ 2）代数优化
利用优化算法把语法树转换成标准 （ 优化 ） 形式
πSname
?Student.Sno=SC.Sno
?SC.Cno=?2?
×
Student
SC
（ 3）物理优化：选择低层的存取路径
- 优化器查找数据字典获得当前数据库状态信息
? 选择字段上是否有索引
? 连接的两个表是否有序
? 连接字段上是否有索引
– 然后根据一定的优化规则选择存取路径
如本例中若 SC表上建有 Cno的索引, 则应该利
用这个索引, 而不必顺序扫描 SC表 。
（ 4）生成查询计划，选择代价最小的
– 在作连接运算时, 若两个表 (设为 R1,R2)均无序, 连
接属性上也没有索引, 则可以有下面几种查询计划,
? 对两个表作排序预处理
? 对 R1在连接属性上建索引
? 对 R2在连接属性上建索引
? 在 R1,R2的连接属性上均建索引
– 对不同的查询计划计算代价, 选择代价最小的一个 。
– 在计算代价时主要考虑磁盘读写的 I/O数, 内存 CPU处
理时间在粗略计算时可不考虑 。
【 例 】 有职工和部门构成的关系数据库：
EMP（编号 E＃，姓名 EN，性别 SEX，年龄 AGE，工资 SAL，部
门 D＃）,
DEPT（部门号 D＃，部门名 DN，管理者号 MGR，地址 ADD）
求出管理者号为 18所在部门的职工姓名,且他
们的工资不超过 500元。
解,依据题意可写出如下查询：
Q1,πEN（（ EMP σMGR=′18′（ DEPT））
－ （ σSAL>′500′（ EMP） σMGR=′18′（ DEPT）））
? 对应的查询树如下图 (a)所示 。 其优化过程从合并
树叶 EMP和 DEPT开始, 然后依据各种等价变换规
则, 进行一系列变换, 最后形成图 (f)。 这一查询
对有经验的读者可直接写出优化结果：
Q2,πEN（ πEN,D＃ （ σNOT SAL>′50０ ′（ EMP））
πD＃ （ σMGR=′18′（ DEPT）））
图 查询优化过程示意图
?
EN
?
m g r ＝ '1 8 '
—
E M P ?
s al ＞ '5 0 0 '
?
m g r ＝ '1 8 '
D E P T E M P D E P T
( a )
?
EN
—
?
m g r ＝ '1 8 '
?
s al ＞ '5 0 0 '
D E P T E M P
( b )
查询优化过程示意图
?
EN
?
n o t (s al ＞ '5 0 0 ')
?
m g r ＝ '1 8 '
E M P
D E P T
?
EN
—
?
m g r ＝ '1 8 '
E M P
D E P T
?
s al ＞ '5 0 0 '
?
EN
?
n o t (s al ＞ '5 0 0 ')
?
m g r ＝ '1 8 '
E M P D E P T
( d )
查询优化过程示意图
?
EN
?
EN, D#
?
n o t (s al ＞ '5 0 0 ')
?
mg r ＝ '1 8 '
E M P D E P T
( e )
?
EN
?
EN, D#
?
D#
?
n o t (s al ＞ '5 0 0 ')
?
mg r ＝ '1 8 '
E M P D E P T
( f )
第四章 关系系统及其查询优化
4.1 关系系统
4.2 关系系统的查询优化
4.3 小结
4.3 小结
? 关系系统
– 关系系统的定义
一个数据库管理系统可定义为关系系统, 当且仅当
它至少支持：
1,关系数据库 （ 即关系数据结构 ）
2,支持选择、投影和（自然）连接运算，
且不要求用户定义任何物理存取路径
小结 （续）
–关系系统的分类
? 表式系统
? (最小 )关系系统
? 关系完备系统
? 全关系系统
关系系统的分类 （续）
数据结构 数据操作 完整性
表式系统 表 ? ?
(最小 )关系系统 表 选择, 投影,
连接
?
关系完备的系统 表 ? ?
全关系系统 ? ? ?
小结 （续）
? 关系系统的查询优化
– 代数优化：关系代数表达式的优化
? 关系代数等价变换规则
? 关系代数表达式的优化算法
– 物理优化：存取路径和低层操作算法的选择
