第15讲数据库查询处理与优化

第15讲关系查询与优化1实例应用实例假设学生-课程数据库中有1000个学生，10000个选课记录，其中选修“c02”课程的记录为50个。一个磁盘块能存储10个S元组，或100个SC元组。用SQL语句表达查询：选修了“c02”课程的学生姓名。用多种等价的关系代数表达式来完成这一查询。分析该查询在不同存储结构和索引结构的磁盘I/O次数。2实例【例】查询选修了“c02”课程的学生姓名

Q1:SELECTSN

FROMS，SC WHERES.Sno=SC.Sno ANDSC.Cno='c02';Q2:SELECTSNFROMS WHERESnoIN（SELECTSno

FROMSCWHERECno=‘c02’）；3实例【例】查询选修了“c02”课程的学生姓名

π

Sn

(бS.Sno=SC.Sno∧SC.Cno='2'(S×SC))

πSn

(бSC.Cno='2'(S⋈SC))πSn

(S⋈бSC.Cno='2'(SC))

4关系查询与优化查询处理步骤查询优化技术代数优化物理优化5查询语句查询解析器查询分析

查询预处理器关系代数查询树查询优化器查询计划的执行代码执行引擎执行结果查询预处理

查询优化查询执行数据字典数据库系统的查询处理步骤

SELECTSnFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';语法分析树关系代数优化查询树查询代码生成器生成执行代码查询处理器的组成和查询处理的典型步骤6查询分析与预处理

查询分析接受类似SQL这样的高级查询语言表示的查询，并进行词法分析和语法分析。7【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。查询分析与预处理

Q1:SELECTSN FROMS，SC WHERES.Sno=SC.SnoANDSC.Cno='c02';

Q2:SELECTSN

FROMSWHERESnoIN（SELECTSno

FROMSCWHERECno=‘c02’）8【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。查询分析与预处理用查询语句Q1实现两个关系的连接查询的语法分析树9【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。查询分析与预处理用查询语句Q2实现两个关系的嵌套查询的语法分析树10查询分析与预处理查询有效性检查根据数据字典对合法的查询语句进行语义检查。检查语句中的数据库对象在所查询的特定数据库模式中是否为有效且有语义含义的名字。检查所有属性的类型是否与其使用相对应，以及根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。11查询分析与预处理生成关系代数初始查询树查询预处理器采用一些相应的规则，用一个或多个关系代数运算符替换语法树上的结点与结构，生成一个对应于SQL查询的关系代数初始查询树。关系代数查询树是一个树数据结构，在查询树中，查询的输入关系表示为叶结点，关系代数操作表示为内部结点，一元关系操作符只有一个子结点，二元关系操作符有两个子结点。

12查询分析与预处理每个内部节点用关系操作符来标记，每个叶子结点用关系名来标记。一元关系操作符只有一个孩子，二元操作符有两个孩子。

Q1查询的关系代数查询树【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))13查询分析与预处理

Q2查询的关系代数查询树【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。Q2：πSN(S⋈πSno(бSC.Cno='c02'(SC)))14查询语句查询解析器

查询预处理器关系代数查询树查询优化器查询计划的执行代码执行引擎执行结果数据字典查询分析与预处理SELECTSnFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';语法分析树关系代数优化查询树查询代码生成器πSn(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))

15由查询优化器将查询预处理器所生成的关系代数初始查询树转换成一个预期所需执行时间较小的等价的关系代数查询树，得到一个可被转换成最有效的物理查询计划的一个“优化”的逻辑查询计划。代数优化16代数优化的必要性

代数优化

【例】分析实现“查询选修了课程号为‘c02’课程的学生姓名”的两种关系代数查询树的执行效率。Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))Q2：πSN(S⋈πSno(бSC.Cno='c02'(SC)))17代数优化的必要性

代数优化在衡量代价时，需要使用如下一些参数：操作符使用的内存大小M。假设内存被分成缓冲区，缓冲区的大小与磁盘块的大小相同。M表示一个特定的操作符执行时可以获得的内存缓冲区的数目。关系R所占磁盘块的大小B(R)通常假设R聚集存储在B个块或近似B个块中。关系R中元组的数目T(R)一个块中能容纳的R的元组数可表示为T/B。关系R的一个属性列上不同值的数目V(R,a)。18代数优化【例】分析实现“查询选修了课程号为‘c02’课程的学生姓名”的两种关系代数查询树的执行效率。（1）T(S)=1000，T(SC)=10000。选修“c02”课程的元组为50个。（2）假设数据记录均为定长记录，一个磁盘块能存储10个S元组记录，或100个SC元组记录。则B(S)=100，B(SC)=100。（3）对关系S和关系SC的连接采用嵌套循环方法，选择关系S作为外循环关系。内存的磁盘缓冲区M=7，可同时容纳5块关系S的磁盘块、1块关系SC的磁盘块，1块用于存放中间结果。（4）关系S和SC的运算结果装满一个缓冲区块后需及时地由缓冲区存储到磁盘上的中间文件中，一个缓冲区块能存储10个运算结果记录。（5）假设缓冲区管理器每秒读写20个磁盘块。代数优化的必要性

191.计算广义笛卡尔积S×SC

代数优化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))20…

10个S元组……100个SC元组……10个SC×S元组……10个S元组…

100个SC元组

…

10个SC×S元组…磁盘B(S)=100块B(SC)=100块T(S)*T(SC)/105块1块1块内存20次100次106次代数优化211.计算广义笛卡尔积S×SC

读取关系S和关系SC的总的磁盘块数=读取关系S的磁盘块数+读取关系SC的遍数×每遍读取的关系SC的磁盘块数=B(S)+(100/5)×B(SC)=100+20×100=2100（块）

读数据时间=2100/20=105秒运算中间结果元组数=1000*10000=107

运算中间结果需占用的磁盘块数=107/10=106（块）

运算中间结果写入磁盘时间=107/10/20=5×104秒

代数优化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))222.选择操作бS.Sno=SC.Sno∧SC.Cno='c02'

选择操作执行时间=中间结果文件读取时间=运算中间结果写入磁盘时间=5×104（s）

运算结果只有50条记录，可驻留内存。3.投影操作πSN

对内存的50条记录进行操作，忽略不计。

查询Q1所需总时间=105＋5×104

＋5×104

=100105（s）≈27.8（h）代数优化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))231.读SC作选择和投影πSno(бSC.Cno='c02'(SC))

读取关系SC的磁盘块数=B(SC)=100（块）读数据时间=100/20=5（s）在内存中，对读取的数据进行选择和投影操作，时间忽略不计。满足条件的中间结果元组数=50，驻留内存，不必用中间文件。2.读S作连接和投影πSN(S⋈πSno(бSC.Cno='c02'(SC)

))

读取关系S的磁盘块数=B(S)=100（块）读数据时间=100/20=5（s）在内存中，对读取的S元组与50个选课元组进行连接操作后投影，时间忽略不计。查询Q2所需总时间=5＋5=10（s）

代数优化≈Q2：πSN(S⋈πSno(бSC.Cno='c02'(SC)))24代数优化的必要性

对于实现同一查询的不同的关系代数表达式（查询树），其操作的次序不同，查询效率不同，查询时间相差很大。有必要对查询预处理器产生的关系代数初始查询树进行优化，得到较优的逻辑查询计划，而不管用户书写的SQL查询是什么形式。代数优化如何改变关系代数表达式的操作次序，提高其查询效率？25代数优化

关系代数表达式（查询树）的优化就是指按照一定的规则，改变关系代数表达式中操作的次序和组合，将其转换为一个可以更高效执行的关系代数表达式（查询树）。基于代数等价的启发式优化代数优化26基于代数等价的启发式优化通过利用一些启发式规则，将一个代数表达式转换为另一个不同的但等价的代数表达式，产生可被进一步优化的查询执行计划。关系代数表达式等价：指用相同的关系实例代替两个表达式中相应的关系所得到的结果是相同的。代数优化27基于代数等价的启发式优化常用的等价变换规则设E、E1、E2等是关系代数表达式，F、F1、F2是条件表达式1.连接、笛卡尔积交换律

E1×E2≡E2×E1 E1⋈E2≡E2⋈E1 E1⋈FE2≡E2⋈FE12.连接、笛卡尔积的结合律

(E1×E2)×E3≡E1×(E2×E3)(E1⋈E2)⋈E3≡E1⋈(E2⋈E3)(E1⋈F1E2)⋈F2E3≡E1⋈F1(E2⋈F2E3)代数优化28基于代数等价的启发式优化常用的等价变换规则3.投影的串接定律

π

A1,A2,

…,An(πB1,B2,…,Bm(E))≡πA1,A2,…,An(E){A1,A2,…,An}构成{B1，B2，…，Bm}的子集

4.选择的串接定律

бF1(бF2(E))≡бF1∧F2(E)代数优化29基于代数等价的启发式优化常用的等价变换规则5.选择与投影的交换律

бF

(πA1,A2,…,An(E))≡πA1,A2,…,An(бF(E))

F只涉及属性A1，…，An

πA1,A2,…,An

(

бF(E))≡πA1,A2,…,An(бF

(πA1,A2,…,An,B1,B2,…,Bm(E)))

F中有不属于A1,…,An的属性B1,…,Bm代数优化30基于代数等价的启发式优化常用的等价变换规则6.选择与笛卡尔积的交换律

бF(E1×E2)≡бF(E1)×E2

F中涉及的属性都是E1中的属性

бF(E1×E2)≡бF1(E1)×бF2(E2)

F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性

бF(E1×E2)≡бF2(бF1(E1)×E2)F=F1∧F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性代数优化31基于代数等价的启发式优化常用的等价变换规则7.选择对自然连接的分配律

бF(E1⋈E2)≡бF(E1)⋈бF(E2)

F是只涉及E1和E2的公共属性8.选择对并的分配律

бF(E1∪E2)≡бF(E1)∪бF(E2)

E1与E2有相同的属性或属性有对应性

9.选择对差运算的分配律

бF(E1-E2)≡бF(E1)-бF(E2)

E1、E2有相同的属性或属性有对应性代数优化32基于代数等价的启发式优化常用的等价变换规则10.投影对笛卡尔积的分配律

πA1,A2,…,An,B1,B2,…,Bm(E1×E2)≡πA1,A2,…,An(E1)×πB1,B2,…,Bm(E2)A1，…，An是E1的属性，B1，…，Bm是E2的属性11.投影对并的分配律

πA1,A2,…,An(E1∪E2)≡πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)12.选择与连接运算的结合бF(E1×E2)≡E1⋈FE2

бF1(E1⋈F2E2)≡E1⋈F1∧F2E2代数优化33基于代数等价的启发式优化主要的启发式规则

选择运算应尽可能先做投影运算和选择运算同时进行将投影运算与其前面或后面的双目运算结合某些选择运算同在其前面执行的笛卡尔积结合成为一个连接运算提取公共子表达式

代数优化34基于代数等价的启发式优化启发式代数优化算法输入：一个关系代数查询树输出：计算关系代数表达式的一个优化序列步骤：（1）分解选择运算（2）交换选择运算，将其尽可能移到叶端（3）交换投影运算，将其尽可能移到叶端（4）合并串接的选择和投影运算（5）对内结点分组每个二元运算(×，⋈，∪，-)和它所有的直接祖先为一组。如果其后代直到叶子全是单目运算，则也将它们并入该组。（6）生成优化序列代数优化35代数优化基于代数等价的启发式优化【例】利用优化算法对执行效率较低的查询Q1的查询树进行优化。Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))

πSN(бS.Sno=SC.Sno(

б

SC.Cno=‘c02’(S×SC)))

πSN(бS.Sno=SC.Sno(

б

SC.Cno=‘c02’(SC×S)))

πSN(бS.Sno=SC.Sno(

б

SC.Cno=‘c02’(SC)×S))

πSN

(

б

SC.Cno=‘c02’(SC)⋈S))

36代数优化基于代数等价的启发式优化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))37代数优化基于代数等价的启发式优化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))

38代数优化基于代数等价的启发式优化【例7-5】供应商零件数据库中有供应商、零件、项目和供应四个基本关系：供应商关系S(Sno，Sname，Status，City)零件关系P(Pno，Pname，Color，Weight)工程项目关系J(Jno，Jname，City)供应情况关系SPJ(Sno，Pno，Jno，Qty)查询：检索使用上海供应商生产的红色零件的工程号。试写出该查询尽可能优化的关系代数表达式，并画出对应的关系代数查询树。

39

物理优化物理优化从一个逻辑查询计划产生物理查询计划时，为逻辑查询计划的每一个操作符选择实现算法并选择这些操作符的执行顺序，还包括许多实现细节。被查询的关系是怎样被访问的，即获得所存储数据的方式以及一个关系何时或是否应当被排序等；必须估计每个可能选项的执行代价，使用代价估计来评价一个查询计划。40

物理优化操作符的实现算法

每一个操作符实现算法的选择是将逻辑查询计划转变为物理查询计划过程中的一个必不可少的部分。针对各种操作符，已提出了很多算法，大体上分为三类：基于排序的方法基于散列的方法基于索引的方法41

物理优化操作符的实现算法

对算法的描述仍使用磁盘I/O的次数作为衡量每个查询的代价的标准和使用如下参数：操作符使用的内存大小M。关系R所占磁盘块的大小B(R)关系R中元组的数目T(R)关系R的一个属性列上不同值的数目V(R,a)。42

物理优化操作符的实现算法

选择操作的实现算法

选择操作σc(R)是读取关系R中那些满足谓词条件C的元组，定位这些元组的基本方法有两种：简单的全表扫描方法索引扫描法43

物理优化操作符的实现算法

选择操作的实现算法简单的全表扫描方法如果R是聚集的，那么全表扫描的代价近似为B(R)。如果R不是聚集的，那么全表扫描所需的I/O代价为T(R)。44

物理优化操作符的实现算法

选择操作的实现算法索引扫描法假设条件C是a=v

的形式，a是一个存在着索引的属性，v是一个值。如果R.a上的索引是聚集的，具有某一a值的元组平均聚集分布在B(R)/V(R,a)个磁盘块中，读取σa=v(R)所需的磁盘I/O的次数将大约是B(R)/V(R,a)。如果a是R的一个关键字，那么V(R,a)=T(R)，至少需要一次磁盘I/O去读取具有关键字值为v的元组。如果R.a上的索引是非聚集的，大约访问T(R)/V(R,a)个元组。T(R)/V(R,a)是估计的磁盘I/O次数。45

物理优化【例7-6】假设B(R)=1000，T(R)=20000，即R有20000个元组可存放在1000个磁盘块中。假设a是R的一个属性，且在a上有一个索引，估计σa=0(R)的代价。①如果R是聚集的，不使用索引，则需进行全表扫描，那么代价是1000次磁盘I/O。②如果R不是聚集的，而且不使用索引，则需进行全表扫描，那么代价是20000次磁盘I/O。③如果V(R,a)=100并且索引是聚集的，那么相同a值的元组聚集存储在平均B(R)/V(R,a)块磁盘块中，因此基于索引的算法需要1000/100=10次磁盘I/O。④如果V(R,a)=100并且索引是非聚集的，那么相同a值的元组可能随机存储在T(R)/V(R,a)块磁盘块中，因此基于索引的算法需要20000/100=200次磁盘I/O。⑤如果V(R,a)=20000，即a是一个关键字，那么基于索引的算法，不管索引是聚集的或是非聚集的，都将需要1次磁盘I/O。46

物理优化操作符的实现算法

连接操作的实现算法在下面的连接算法中，将R(X,Y)与S(Y,Z)连接，Y表示R和S的所有公共属性，X是R的所有不在S模式中的属性，Z是S的所有不在R模式中的属性。假设S是较小的关系。

47

物理优化操作符的实现算法

连接操作的实现算法一趟连接运算假设较小的关系S，可存入内存的M-1块中。读取S的所有元组，并且构造一个以Y属性为查找关键字的内存查找结构。将R的每一磁盘块中的元组读到内存中剩下的那一个缓冲区中。对于R的每一个元组t，利用查找结构找到S中与t在Y的所有属性上相符合的元组。对于S中每一个匹配的元组，将它与t配对后形成一个元组，并且将结果元组移到输出文件中。读取操作对象需要B(S)+B(R)次磁盘I/O，仅从磁盘读取一次数据。48…S元组……R元组……R×S元组……S元组…R元组

…R×S元组…磁盘B(S)≤M-1

M-1块1块1块缓冲区一趟连接运算

物理优化1次1次B(R)49

物理优化操作符的实现算法

连接操作的实现算法嵌套循环连接嵌套循环连接算法是对外层循环关系（如S）中的每条元组，检查内层循环关系（如R）中的每个元组是否满足连接条件，如果满足条件，则连接后作为结果输出，直到外层循环关系中的元组处理完为止。基于块的嵌套循环连接算法对作为操作对象的两个关系的访问均按块组织，假定B(S)≤B(R)，并且B(S)＞M。使用尽可能多的内存来存储属于较小关系S的元组，S是外层循环中的关系。

50

物理优化操作符的实现算法

连接操作的实现算法基于块的嵌套循环连接算法①读取关系S的M-1个磁盘块中的元组到内存缓冲区中。②为S在内存中的元组创建一个查找结构，它的查找关键字是R和S的公共属性。③浏览R的所有块，依次读取每一块到内存M块中的最后一块中。④在读入R的一个块后，将块中所有元组与S在内存中的所有块中的所有元组进行比较。对于那些能连接的元组，输出连接得到的元组。⑤重复执行前面的步骤，直到处理完S中所有磁盘块中的数据。读取数据的磁盘I/O次数是B(S)+(B(S)B(R))/(M-1)。

51…S元组…S元组…R元组……R×S元组……S元组…R元组

…R×S元组…磁盘B(S)＞M

B(R)M-1块1块缓冲区基于块的嵌套循环连接算法

物理优化1次B(S)/(M-1)次52

物理优化【例7-7】假定B(R)=1000，B(S)=500，M=101。使用100个内存块的缓冲区来对S进行缓冲。计算采用基于块的嵌套循环连接算法代价。算法中的外层循环需循环5次。在每次外循环中，用100次磁盘I/O读取S的数据块组。在内循环中用1000次磁盘I/O来读取R。因此，运算中读取数据需要5×(100+1000)=5500次磁盘I/O。如果交换内外循环中的关系，外循环需执行10次。每次外循环需进行100+500=600次磁盘I/O，总共6000次。所以，在外循环中使用较小的关系，算法使用的磁盘I/O要略少一些，略有优势。53

物理优化操作符的实现算法

连接操作的实现算法排序-归并连接关系R和S按照连接属性Y有序聚集存储。两个缓冲区，一个给R的当前块，另一个给S的当前块。①按照连接属性的顺序对关系R和S并发地进行物理顺序扫描，把关系R和S的首个磁盘块中的元组读入内存缓冲区。②在读入内存的当前R和S的元组中顺序查找连接属性Y的最小匹配值y。如果需要，从排序的R和/或S中继续读取下一个磁盘块，直到找到最小匹配值y。③连接内存中R和S的具有相同y值的所有元组。如果一个关系在内存中已没有未考虑的元组，就顺序读取该文件的下一个磁盘块，直到处理完两个关系中具有相同y值的所有元组。④在内存R和S的元组中顺序查找连接属性Y的下一个匹配值y，从步骤3开始重复执行。直到处理完某一关系的所有磁盘块中的元组。54…S元组……R元组……R×S元组……S元组R元组

…R×S元组…磁盘B(S)B(R)1块1块缓冲区排序-归并连接算法

物理优化1次1次读取操作对象需要B(S)+B(R)次磁盘I/O，仅从磁盘读取一次数据。55

物理优化【例7-8】假定B(R)=1000，B(S)=500，M=101。假设R和S均已按属性Y排序，计算采用排序归并连接算法代价。用1500次磁盘I/O来读取R和S的每一个块，仅需要101个内存块中的两个。如果需要可以使用所有101块来容纳具有公共Y值的R和S的元组。56

物理优化操作符的实现算法

连接操作的实现算法基于散列的连接算法的基本思想是如果数据量太大以至于不能存入内存缓冲区中，可使用一个合适的散列键散列一个或多个操作对象的所有元组。然后通过一次处理具有相同散列值的一对桶的方式执行操作。假设h是散列函数，用连接属性Y作散列键，来散列两个关系R和S的元组，将元组散列到适当的散列桶中。如果R与S的元组能连接，那么它们必然出现在具有某个i值的对应的桶Ri和Si中。57

物理优化操作符的实现算法

连接操作的实现算法基于散列的连接算法每一个桶对中有一个能全部装入M-1个缓冲区中。

①可按桶号i的大小将包含较少磁盘块的桶（Si中的桶）读入到内存的缓冲区中，构造内存中的一个散列查找结构。②读入另一关系R中的与Si对应的桶Ri，将读入的Ri中的元组与内存中Si中的记录进行连接，将连接的结果进行输出。③重复以上步骤，直到S中的所有桶处理完。连接操作读取操作对象需要B(S)+B(R)次磁盘I/O，仅从磁盘读取一次数据。

58…S元组……R元组……R×S元组……S(Ki)元组…R(Ki)元组

…R×S元组…磁盘B(S)B(R)M-1块1块缓冲区基于散列的连接算法

物理优化1次1次S(Ki)S(Ki)R(Ki)R(Ki)59

物理优化【例7-9】假定B(R)=1000，B(S)=500，M=101。假设R和S均已按属性Y排序，计算采用基于散列的连接算法代价。假设以连接属性Y作为散列键将R和S分别散列到100个桶中，则一个桶的平均大小对于R占10个磁盘块，对于S占5个磁盘块。远远小于101块可用的缓冲区数量。所以在每一个桶对上执行一趟连接即可完成运算。执行对应桶的一次连接需1500次磁盘I/O。60

物理优化操作符的实现算法

连接操作的实现算法基于索引的连接运算如果一个关系（如S）有一个属性Y上的索引。①读入R的一个磁盘块，考虑块中每一个元组t，令ty是元组t中y属性的值。②使用S上的索引，来找到S中所有在Y属性上具有相同ty的那些元组所在的磁盘块，将这些元组（所在的磁盘块）读入内存与R中的元组t连接起来，作为结果输出。③重复以上步骤，直到R中的所有元组处理完。61…S元组…S元组…R元组

…R×S元组……S(ty)元组…R(ty)元组

…R×S元组…磁盘B(S)B(R)1块1块缓冲区基于索引的连接算法

物理优化tyty

S的索引62

物理优化操作符的实现算法

连接操作的实现算法基于索引的连接运算如果R是聚集的，将需要读取B(R)个块来得到R的所有元组。如果R是非聚集的，那么可能会需要将近T(R)个磁盘I/O来读取R的所有元组。对于R的每一个元组，将平均读取S的T(S)/V(S,Y)个元组。如果S在Y上有一个非聚集的索引，那么读取S所需的磁盘I/O的次数是T(R)T(S)/V(S,Y)。如果S上的索引是聚集的，那么仅T(R)B(S)/V(S,Y)次磁盘I/O就够了。对于算法中的每一个Y值，可能需要增加几次磁盘I/O，用于读取相关索引文件。63

物理优化【例7-10】假定B(R)=1000，B(S)=500，M=101。假设一个块可以容纳每个关系的10个元组，即T(R)=10000，T(S)=5000，同时假设V(S,Y)=100。计算采用基于索引的连接算法代价。如果R是聚集的，需要1000次磁盘I/O用来读取R的所有元组。S在Y上有一个聚集索引，需要10000×500/100=50000次磁盘I/O读取S。如果R是非聚集的或S上的索引是非聚集的，代价会更高。64

物理优化操作符的实现算法

连接操作的实现算法基于索引的连接运算常见的连接查询的情况是与S相比，R是很小的，V(S,Y)是很大的。在这种情况下，S的大多数元组的Y值根本不出现在R中，这些元组将无需被算法检查，即不需要读入内存。但是，不论基于排序的还是基于散列的连接方法都需检查S的每一个元组至少一次。所以，在实际的应用中，索引选择算法仍是一种常用的方法。65【例】分析实现“查询选修了课程号为‘c02’课程的学生姓名”（1）T(S)=1000，T(SC)=10000。选修“c02”课程的元组为50个。（2）一个磁盘块能存储10个S元组记录，或100个SC元组记录。则B(S)=100，B(SC)=100。

Q1:SELECTSN FROMS，SC WHERES.Sno=SC.SnoANDSC.Cno='c02';

Q1：πSN((бSC.Cno='c02'(SC)⋈S))——————————R

物理优化66

物理优化物理优化从一个逻辑查询计划产生物理查询计划时，为逻辑查询计划的每一个操作符选择实现算法并选择这些操作符的执行顺序，还包括许多实现细节。被查询的关系是怎样被访问的，即获得所存储数据的方式以及一个关系何时或是否应当被排序等；必须估计每个可能选项的执行代价，使用代价估计来评价一个查询计划。67基于代价的物理优化方法查询计划的代价因素一个查询的实际执行所需的代价包括:磁盘访问代价：读写记录所在磁盘数据块的代价。存储代价：存储由查询执行计划产生的中间结果文件的代价。计算代价：在查询执行过程中对数据缓冲区完成内存操作的代价。内存使用代价：与执行查询所需内存缓冲区数相关的代价。通信代价：将查询与查询结果从一个数据库站点传送到另一个站点（或发出查询的终端）的代价。

物理优化68基于代价的物理优化方法查询计划的代价因素代价用的磁盘I/O次数受以下因素影响：在选择逻辑查询计划时所选取的用于实现查询的逻辑查询运算符，例如进行乘积运算还是连接运算。中间关系的大小。用于实现逻辑查询运算符的物理查询运算符，例如连接运算算法的选择，对给定关系是否加以排序等其他运算。由一个物理运算符向下一个物理运算符传递参数的方式，例如，通过在磁盘上保存中间结果还是通过使用迭代算子每次传送一个参数的一个元组或一个主存缓冲区。

物理优化69基于代价的物理优化方法查询计划的代价因素在对由给定的逻辑查询计划导出可能的物理查询计划进行评价时，我们需要知道各个物理计划的代价是多少。在不执行查询计划的情况下，我们不能准确知道其代价。由于执行一个查询计划比查询编译器选择一个计划所做的工作要多得多，我们需要不执行查询计划而估计该计划的代价。要准确估计不同查询计划的代价，查询优化器需要从数据库中有效地获得某些重要的参数信息，即从数据字典中获取代价估计所需的各种信息。

物理优化70基于代价的物理优化方法代价估计基于的数据信息对每个关系表文件，该表的记录总数（T）、记录长度、占用的块数（B）、占用的溢出块数（BO）；对关系表文件的每个属性，该属性不同值的个数（V）、选择率（具有该值的记录数/T）、该属性最大值、最小值，该属性上是否已建索引，何种索引（B+树索引、散列索引、聚集索引）；对于索引，比如B+树索引，该索引的层数（L）、不同索引值的个数、索引的选择基数S（有S个元组有某个索引值）、索引的叶结点数（Y）等等。

物理优化优化器可以根据这些信息作出正确的估算，选择高效的执行计划。

71基于代价的物理优化方法物理查询计划的选择方法

由给定的逻辑查询计划可有多个可能的物理查询计划，要穷尽所有的查询计划进行代价估算往往是不可行的，会造成查询优化本身付出的代价大于获得的益处。常常先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量；然后分别计算这些候选方案的执行代价，较快地选出最终的优化方案。

物理优化72基于代价的物理优化方法物理查询计划的选择方法

启发式选择某些操作（如选择和连接操作）可以有多种执行这个操作的算法，可以根据一些启发式规则来选择代价较小的实现操作的算法。

物理优化73基于代价的物理优化方法物理查询计划的选择方法

常用的启发式规则（1）选择操作若关系R的元组数较小，比如T(R)<M，可采用简单的全表扫描方法，即使选择列上有索引。如果逻辑计划需要进行σa=v(R)操作，且关系R在属性a上有索引，则使用索引扫描法。对于更一般的选择操作，如选择涉及a=v那样的一个条件以及其他条件，可以先进行一次索引扫描，然后对选中的元组作进一步选择（也称过滤）。

物理优化74基于代价的物理优化方法物理查询计划的选择方法

常用的启发式规则（2）连接操作如果两个关系都已经按照连接属性排序，则选用排序-归并算法。如果一个关系在连接属性上有索引，则选用索引连接方法，其中该关系在算法内层循环中（即算法中的关系S，可通过连接运算的交换律来满足）。如果前两个规则不适用，而其中一个关系较小，则可以选用散列连接方法。最后可以选用嵌套循环方法，并选择其中较小的关系，即占用的磁盘块数较小的关系作为算法的外循环中的关系（即算法中的关系S）。

物理优化75基于代价的物理优化方法物理查询计划的选择方法

基于代价估算的选择查询优化器可通过估计每一个可能的物理查询计划的代价，比较并选择估计代价最小的查询计划。以选择操作为例说明在逻辑查询计划到物