1
第九章 查询处理
?9.1 查询处理的过程
?9.2 关系代数表达式的转换（重点）
?9.3 查询代价的度量
?9.4 实现关系运算的算法代价
?9.5 表达式的求值方法
?9.6 查询优化（重点）
2
9.1 查询处理的过程
查询处理进程的三个步骤 （见教材 P159）：
(1)语法分析与翻译； (2)查询优化（ 重点 ）； (3)查询执
行。
据
关系代数表达式查询语句 语法分析与翻译器
执行计划
优化器
执行引擎查询输出
数据字典
数据字典
数
图 9.1 查询处理过程
3
?优化器可以从数据字典中获取许多统计信息，例如
关系中的元组数、关系中每个属性值的分布情况等。
优化器可以根据这些信息选择有效的执行计划，而用
户程序则难以获得这些信息。
?如果数据库的物理统计信息改变了，系统可以自动
对查询进行重新优化以选择相适应的执行计划。在非
关系系统中必须重写程序，而重写程序在实际应用中
往往是不太可能的。
?优化器可以考虑数百种不同的执行计划，而程序员
一般只能考虑有限的几种可能性。优化器中包括了很
多复杂的优化技术，这些优化技术往往只有最好的程
序员才能掌握。系统的自动优化相当于使得所有人都
拥有这些优化技术。
4
?查询优化器
查询优化是影响 RDBMS性能的关键因素。主要解决下面 3个
问题：
问题 1,每个查询语句可以翻译成多个等价的关系代数表达
式，应该选择哪一个表达式？
例如有 SQL语句：
Select student_number from student
where student_number<“s000003”
等价表达式为：
?σ student_number<“s000003” (∏ student_number(student))
?∏student_number(σ student_number<“s000003” ((student))
5
问题 2,每个关系表达式中的关系运算可以用不同的算法
来实现，且可以采用不同的索引，应该选择何种算法或
索引？
问题 3,对于表达式的求值何种采用计算方法？
以上三个问题的解决的方法形成执行计划。
6
9.2关系代数表达式的转换
引例：, 请给出计算机系的教师所讲课程的课程名称和
教师姓名, 。用如下两个等价的关系代数表达式表达：
?∏course_name,teacher_name （ σ department_name=,计算机
系” (teacher∞teaching)),其关系表达式树如下：
∏course_name,teacher_name
teacher teaching
∞
σ department_name=,计算机系”
7
? ∏ course_name,teacher_name （（ σ department_name=,计算机
系” (teacher） ∞ teaching)，其关系表达式树如下：
∏ course_name,teacher_name
∞
σ department_name=,计算机系,teaching
teacher
8
9.2.1 等价规则
约定：用 θ 表示谓词，用 L表示属性列表，用 E表示关系代数表达式。
（ 1） σ 的级联,σ θ 1∧ θ 2(E)= σ θ 1(σ θ 2(E))
（ 2）选择运算满足交换律,σ θ 1(σ θ 2(E))=σ θ 2(σ θ 1(E))
（ 3） ∏ 的级联：
∏ L1（ ∏ L2（ ? （ ∏ Ln（ E）） ? ）） = ∏ L1(E)
（ 4）选择可与笛卡儿积以及 theta连接相结合：
? σ θ (E1× E2)= E1 ∞ θ E2
? σ θ 1(E1 ∞ θ 2 E2)= E1 ∞ θ 1∧ θ 2E2
（ 5） theta连接（包括自然连接）运算满足交换律：
E1 ∞ θ E2 = E2 ∞ θ E1
9
（ 6）自然连接运算满足结合律：
(E1 ∞ E2) ∞ E3 = E1 ∞（ E2 ∞ E3）
（ 7）选择运算在选定条件下对 θ 运算的分配律
（ 8）投影运算对 θ 运算具有分配律
（ 9）集合运算并与交运算满足交换律
（ 10）集合运算并与交运算满足结合律
（ 11）集合运算对并、交、差运算具有分配律
（ 12）投影运算对并运算具有分配律
10
9.2.2 表达式转换举例
若有关系模式：
学生（学号，学生姓名，所在系）
选课（学号，课程名），有关系表达式：
例 1,∏ 学生姓名 （ σ 所在系 =,计算机系” (学生 ∞ 选课 )）
此关系代数表达式的含义？
下面对此关系作等价变换：
利用规则 7（ 1）可得如下等价表达式：
∏ 学生姓名 （（ σ 所在系 =,计算机系” (学生）） ∞ 选课）
11
例 2,∏ 学生姓名 （（ σ 所在系 =,计算机系” ∧ 课程名 like,数据库 %,(学生 ∞
选课 )）
此关系代数表达式的含义？
下面对此关系作等价变换：
利用规则 7（ 2）可得如下等价表达式：
∏ 学生姓名 （ （ σ 所在系 =,计算机系” （学生） ） ∞ （ σ 课程名
like,数据库 %,（选课） )）
12
关系表达式树分别如下：
∞
学生 选课
∏学生姓名
σ 所在系 =,计算机系” ∧ 课程名 like,数据库 %“
学生
∏学生姓名
∞
σ 所在系 =,计算机系” σ 所在系 =,计算机系”
选课
例 2关系代数表达式 例 1关系代数表达式
13
9.3 查询代价的度量
9.3.1 查询处理的代价
查询计划也称查询执行方案，是由一系列内部操作组成
的。这些内部操作按一定的次序构成查询的一个执行方
案。通常这样的执行方案有多个，需要对每个执行计划
计算代价，从中选择代价最小的一个。
?在集中式数据库中，查询的执行开销主要包括：
总代价 = I/O代价 + CPU代价
?在多用户环境下：
总代价 = I/O代价 + CPU代价 + 内存 代价
14
9.3.2 处理模型
?I/O代价用从磁盘向主存传送的 物理块数 来度量。
?假定所有块传送的代价相同。
?忽略了最终查询结果写回磁盘的代价。
?实现算法的代价考虑最坏情况下的代价。
15
9.4 实现关系运算 (选择、连接 )的算法代价
算法代价主要是计算磁盘存取代价，即在磁盘向主存传
送的物理块数来。
9.4.1 选择运算
（ 1）不用索引的搜索算法 -文件扫描：
?线性搜索算法 A1（？）
代价为,EA1=br
?二分搜索算法 A2（？）
代价为,EA2=「 log2(br) + 「 SC(A,r)/fr -1
找到符合查找条件的第一块
数据的代价 符合查找条件的数据块数目。 其中 SC(A,r）表示满足
选择条件的记录数。
有一块已被检索到
16
（ 2）使用索引的搜索算法 -索引扫描：
?在建立主索引的 码属性 上的等值比较算法：
代价为,EA3=HTi+1
?在建立主索引的非码属性上的等值比较算法,
代价为,EA4=HTi+ 「 SC(A,r)/fr
17
9.4.2 连接运算
有嵌套循环连接算法、索引嵌套循环连接算法、归并连
接算法等 。
1、嵌套循环连接算法
例,r∞θs的嵌套循环连接算法表示如下：
for 对于 r是的每一个元组 tr,do
begin
for 对于 s是的每一个元组 ts,do
begin
检查元组对（）满足连接条件吗？
若满足则把 tr.ts加到结果集中
end
end
18
嵌套循环连接算法代价分析：
?最坏情况下，缓冲区只能装一个数据块，则：
EJ=nr*bs+br，其中 nr为关系 r中的记录条数，
bs为 s中记录的块数,br为 r中记录的块数。
?最好情况下，两个关系都能放入缓冲区中，则：
EJ=bs+br
2、索引嵌套循环连接算法
将嵌套循环连接算法中嵌套于内层的文件扫描改为
索引扫描。则
EJ=br+nr*c，其中 c为使用连接条件并利用索引对关系 s
进行单个选择运算的代价。
19
9.5 表达式的求值方法
（ 1）实体化计算方法
（ 2）流水线计算方法
（ 3）上述两种方法的相互结合
20
9.5.1 实体化计算方法
?实体化计算方法是以适当的顺序每次执行表达式中的
一个运算，计算结果保存到一个临时关系（实体化）中
备用。如查询：
? ∏课程名 (（ σ 学号 <“s000003” (学生 )) ∞选课 ） 的实体化计
算方法执行过程为：
∏课程名
∞
σ 学号 <“s000003” 选课
学生
R1
R2
R3
21
9.5.2 流水线计算方法
?流水线计算方法是将表达式中多个关系运算组合成一
个操作流水线来实现，即将一个运算的结果作为下一个
运算的输入，每条记录依次执行到底。如查询：
? ∏课程名 (（ σ 学号 <“s000003” (学生 )) ∞选课 ） 的实体化计
算方法执行过程为：
∏课程名
∞
σ 学号 <“s000003” 选课
学生
T1
T2
T3
22
9.6 查询优化
? 查询优化器的工作目的：产生一个代价最小的查询执
行计划。
? 查询优化方法包括：
① 基于代价的优化；
② 启发式优化。
23
9.6.1 基于代价的优化方法
基于代价的优化方法，其思想是将各种可能的查询执行
计划全部产生出来，然后从中选择最小的一个。这样的
做法花费非常多的估计时间，因此很难实现。
24
9.6.2 启发式优化方法
启发式优化方法的基本规则是：
?合取（ ∧ ）选择 运算分解为单个选择运算序列；
?尽可能早地执行选择运算；
?为确保产生较小的关系，可重新组织表达式中多个连
接的顺序。
?把带有选择运算的笛卡儿积运算替换成 theta连接运算。
?将投影属性分解并发送可能早地执行投影运算；
?尽可能采用流水线计算方法。
第九章 查询处理
?9.1 查询处理的过程
?9.2 关系代数表达式的转换（重点）
?9.3 查询代价的度量
?9.4 实现关系运算的算法代价
?9.5 表达式的求值方法
?9.6 查询优化（重点）
2
9.1 查询处理的过程
查询处理进程的三个步骤 （见教材 P159）：
(1)语法分析与翻译； (2)查询优化（ 重点 ）； (3)查询执
行。
据
关系代数表达式查询语句 语法分析与翻译器
执行计划
优化器
执行引擎查询输出
数据字典
数据字典
数
图 9.1 查询处理过程
3
?优化器可以从数据字典中获取许多统计信息，例如
关系中的元组数、关系中每个属性值的分布情况等。
优化器可以根据这些信息选择有效的执行计划，而用
户程序则难以获得这些信息。
?如果数据库的物理统计信息改变了，系统可以自动
对查询进行重新优化以选择相适应的执行计划。在非
关系系统中必须重写程序，而重写程序在实际应用中
往往是不太可能的。
?优化器可以考虑数百种不同的执行计划，而程序员
一般只能考虑有限的几种可能性。优化器中包括了很
多复杂的优化技术，这些优化技术往往只有最好的程
序员才能掌握。系统的自动优化相当于使得所有人都
拥有这些优化技术。
4
?查询优化器
查询优化是影响 RDBMS性能的关键因素。主要解决下面 3个
问题：
问题 1,每个查询语句可以翻译成多个等价的关系代数表达
式，应该选择哪一个表达式？
例如有 SQL语句：
Select student_number from student
where student_number<“s000003”
等价表达式为：
?σ student_number<“s000003” (∏ student_number(student))
?∏student_number(σ student_number<“s000003” ((student))
5
问题 2,每个关系表达式中的关系运算可以用不同的算法
来实现，且可以采用不同的索引，应该选择何种算法或
索引？
问题 3,对于表达式的求值何种采用计算方法？
以上三个问题的解决的方法形成执行计划。
6
9.2关系代数表达式的转换
引例：, 请给出计算机系的教师所讲课程的课程名称和
教师姓名, 。用如下两个等价的关系代数表达式表达：
?∏course_name,teacher_name （ σ department_name=,计算机
系” (teacher∞teaching)),其关系表达式树如下：
∏course_name,teacher_name
teacher teaching
∞
σ department_name=,计算机系”
7
? ∏ course_name,teacher_name （（ σ department_name=,计算机
系” (teacher） ∞ teaching)，其关系表达式树如下：
∏ course_name,teacher_name
∞
σ department_name=,计算机系,teaching
teacher
8
9.2.1 等价规则
约定：用 θ 表示谓词，用 L表示属性列表，用 E表示关系代数表达式。
（ 1） σ 的级联,σ θ 1∧ θ 2(E)= σ θ 1(σ θ 2(E))
（ 2）选择运算满足交换律,σ θ 1(σ θ 2(E))=σ θ 2(σ θ 1(E))
（ 3） ∏ 的级联：
∏ L1（ ∏ L2（ ? （ ∏ Ln（ E）） ? ）） = ∏ L1(E)
（ 4）选择可与笛卡儿积以及 theta连接相结合：
? σ θ (E1× E2)= E1 ∞ θ E2
? σ θ 1(E1 ∞ θ 2 E2)= E1 ∞ θ 1∧ θ 2E2
（ 5） theta连接（包括自然连接）运算满足交换律：
E1 ∞ θ E2 = E2 ∞ θ E1
9
（ 6）自然连接运算满足结合律：
(E1 ∞ E2) ∞ E3 = E1 ∞（ E2 ∞ E3）
（ 7）选择运算在选定条件下对 θ 运算的分配律
（ 8）投影运算对 θ 运算具有分配律
（ 9）集合运算并与交运算满足交换律
（ 10）集合运算并与交运算满足结合律
（ 11）集合运算对并、交、差运算具有分配律
（ 12）投影运算对并运算具有分配律
10
9.2.2 表达式转换举例
若有关系模式：
学生（学号，学生姓名，所在系）
选课（学号，课程名），有关系表达式：
例 1,∏ 学生姓名 （ σ 所在系 =,计算机系” (学生 ∞ 选课 )）
此关系代数表达式的含义？
下面对此关系作等价变换：
利用规则 7（ 1）可得如下等价表达式：
∏ 学生姓名 （（ σ 所在系 =,计算机系” (学生）） ∞ 选课）
11
例 2,∏ 学生姓名 （（ σ 所在系 =,计算机系” ∧ 课程名 like,数据库 %,(学生 ∞
选课 )）
此关系代数表达式的含义？
下面对此关系作等价变换：
利用规则 7（ 2）可得如下等价表达式：
∏ 学生姓名 （ （ σ 所在系 =,计算机系” （学生） ） ∞ （ σ 课程名
like,数据库 %,（选课） )）
12
关系表达式树分别如下：
∞
学生 选课
∏学生姓名
σ 所在系 =,计算机系” ∧ 课程名 like,数据库 %“
学生
∏学生姓名
∞
σ 所在系 =,计算机系” σ 所在系 =,计算机系”
选课
例 2关系代数表达式 例 1关系代数表达式
13
9.3 查询代价的度量
9.3.1 查询处理的代价
查询计划也称查询执行方案，是由一系列内部操作组成
的。这些内部操作按一定的次序构成查询的一个执行方
案。通常这样的执行方案有多个，需要对每个执行计划
计算代价，从中选择代价最小的一个。
?在集中式数据库中，查询的执行开销主要包括：
总代价 = I/O代价 + CPU代价
?在多用户环境下：
总代价 = I/O代价 + CPU代价 + 内存 代价
14
9.3.2 处理模型
?I/O代价用从磁盘向主存传送的 物理块数 来度量。
?假定所有块传送的代价相同。
?忽略了最终查询结果写回磁盘的代价。
?实现算法的代价考虑最坏情况下的代价。
15
9.4 实现关系运算 (选择、连接 )的算法代价
算法代价主要是计算磁盘存取代价，即在磁盘向主存传
送的物理块数来。
9.4.1 选择运算
（ 1）不用索引的搜索算法 -文件扫描：
?线性搜索算法 A1（？）
代价为,EA1=br
?二分搜索算法 A2（？）
代价为,EA2=「 log2(br) + 「 SC(A,r)/fr -1
找到符合查找条件的第一块
数据的代价 符合查找条件的数据块数目。 其中 SC(A,r）表示满足
选择条件的记录数。
有一块已被检索到
16
（ 2）使用索引的搜索算法 -索引扫描：
?在建立主索引的 码属性 上的等值比较算法：
代价为,EA3=HTi+1
?在建立主索引的非码属性上的等值比较算法,
代价为,EA4=HTi+ 「 SC(A,r)/fr
17
9.4.2 连接运算
有嵌套循环连接算法、索引嵌套循环连接算法、归并连
接算法等 。
1、嵌套循环连接算法
例,r∞θs的嵌套循环连接算法表示如下：
for 对于 r是的每一个元组 tr,do
begin
for 对于 s是的每一个元组 ts,do
begin
检查元组对（）满足连接条件吗？
若满足则把 tr.ts加到结果集中
end
end
18
嵌套循环连接算法代价分析：
?最坏情况下，缓冲区只能装一个数据块，则：
EJ=nr*bs+br，其中 nr为关系 r中的记录条数，
bs为 s中记录的块数,br为 r中记录的块数。
?最好情况下，两个关系都能放入缓冲区中，则：
EJ=bs+br
2、索引嵌套循环连接算法
将嵌套循环连接算法中嵌套于内层的文件扫描改为
索引扫描。则
EJ=br+nr*c，其中 c为使用连接条件并利用索引对关系 s
进行单个选择运算的代价。
19
9.5 表达式的求值方法
（ 1）实体化计算方法
（ 2）流水线计算方法
（ 3）上述两种方法的相互结合
20
9.5.1 实体化计算方法
?实体化计算方法是以适当的顺序每次执行表达式中的
一个运算，计算结果保存到一个临时关系（实体化）中
备用。如查询：
? ∏课程名 (（ σ 学号 <“s000003” (学生 )) ∞选课 ） 的实体化计
算方法执行过程为：
∏课程名
∞
σ 学号 <“s000003” 选课
学生
R1
R2
R3
21
9.5.2 流水线计算方法
?流水线计算方法是将表达式中多个关系运算组合成一
个操作流水线来实现，即将一个运算的结果作为下一个
运算的输入，每条记录依次执行到底。如查询：
? ∏课程名 (（ σ 学号 <“s000003” (学生 )) ∞选课 ） 的实体化计
算方法执行过程为：
∏课程名
∞
σ 学号 <“s000003” 选课
学生
T1
T2
T3
22
9.6 查询优化
? 查询优化器的工作目的：产生一个代价最小的查询执
行计划。
? 查询优化方法包括：
① 基于代价的优化；
② 启发式优化。
23
9.6.1 基于代价的优化方法
基于代价的优化方法，其思想是将各种可能的查询执行
计划全部产生出来，然后从中选择最小的一个。这样的
做法花费非常多的估计时间，因此很难实现。
24
9.6.2 启发式优化方法
启发式优化方法的基本规则是：
?合取（ ∧ ）选择 运算分解为单个选择运算序列；
?尽可能早地执行选择运算；
?为确保产生较小的关系，可重新组织表达式中多个连
接的顺序。
?把带有选择运算的笛卡儿积运算替换成 theta连接运算。
?将投影属性分解并发送可能早地执行投影运算；
?尽可能采用流水线计算方法。
