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

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

2、储结构和索引结构的磁盘分析该查询在不同存储结构和索引结构的磁盘I/O次次数。数。第第15讲讲 关系查询与优化关系查询与优化实例【例】查询选修了“c02”课程的学生姓名 Q1: SELECT SN FROM S，SC WHERE S.Sno=SC.Sno AND SC.Cno= c02 ; Q2: SELECT SN FROM S WHERE Sno IN （SELECT Sno FROM SC WHERE Cno=c02）；第第15讲讲 关系查询与优化关系查询与优化实例【例】查询选修了“c02”课程的学生姓名 Sn (S.Sno=SC.Sno SC.Cno=2 (SSC) Sn (SC.Cno

3、= 2 (S SC) Sn (S SC.Cno= 2 (SC) 第第15讲讲 关系查询与优化关系查询与优化关系查询与优化关系查询与优化 查询处理步骤 查询优化技术 代数优化代数优化 物理优化物理优化第第15讲讲 关系查询与优化关系查询与优化查询语句查询语句查询解析器查询解析器查询分析查询分析 查询预处理器查询预处理器关系代数查询树关系代数查询树查询优化器查询优化器查询计划的执行代码查询计划的执行代码执行引擎执行引擎执行结果执行结果查询预处理查询预处理 查询优化查询优化查询执行查询执行数据字典数据字典数据库系统的查询处理步骤数据库系统的查询处理步骤 SELECT Sn FROM S，SC WHE

4、RE S.Sno=SC.Sno AND SC.Cno= c02 ;语法分析树语法分析树关系代数优化查询树关系代数优化查询树查询代码生成器查询代码生成器生成执行代码生成执行代码查询处理器的组成和查询处理的典型步骤 第第15讲讲 关系查询与优化关系查询与优化查询分析与预处理查询分析与预处理 查询分析 接受类似接受类似SQL这样的高级查询语言表示的这样的高级查询语言表示的查询，并进行词法分析和语法分析。查询，并进行词法分析和语法分析。第第15讲讲 关系查询与优化关系查询与优化【例例】在在“学生学生- -课程课程”数据库中查询选修了课程号为数据库中查询选修了课程号为“c02”c02”课程的学生姓名。课

5、程的学生姓名。查询分析与预处理查询分析与预处理 Q1: SELECT SN FROM S，SC WHERE S.Sno=SC.Sno AND SC.Cno= c02 ; Q2: SELECT SN FROM S WHERE Sno IN （SELECT Sno FROM SC WHERE Cno=c02）第第15讲讲 关系查询与优化关系查询与优化【例例】在在“学生学生- -课程课程”数据库中查询选修了课程号为数据库中查询选修了课程号为“c02”c02”课程的学生姓名。课程的学生姓名。查询分析与预处理查询分析与预处理用查询语句用查询语句Q1实现两个关系的连接查询的语法分析树实现两个关系的连接查询

6、的语法分析树第第15讲讲 关系查询与优化关系查询与优化【例例】在在“学生学生- -课程课程”数据库中查询选修了课程号为数据库中查询选修了课程号为“c02”c02”课程的学生姓名。课程的学生姓名。查询分析与预处理查询分析与预处理用查询语句用查询语句Q2实现两个关系的嵌套查询的语法分析树实现两个关系的嵌套查询的语法分析树第第15讲讲 关系查询与优化关系查询与优化查询分析与预处理查询分析与预处理 查询有效性检查 根据数据字典对合法的查询语句进行语义根据数据字典对合法的查询语句进行语义检查。检查。 检查语句中的数据库对象在所查询的特定数据检查语句中的数据库对象在所查询的特定数据库模式中是否为有效且有语

7、义含义的名字。库模式中是否为有效且有语义含义的名字。 检查所有属性的类型是否与其使用相对应，以检查所有属性的类型是否与其使用相对应，以及根据数据字典中的用户权限和完整性约束定及根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。义对用户的存取权限进行检查。第第15讲讲 关系查询与优化关系查询与优化查询分析与预处理查询分析与预处理 生成关系代数初始查询树 查询预处理器采用一些相应的规则，用一查询预处理器采用一些相应的规则，用一个或多个关系代数运算符替换语法树上的个或多个关系代数运算符替换语法树上的结点与结构，生成一个对应于结点与结构，生成一个对应于SQL查询的查询的关系代数初始查询

8、树。关系代数初始查询树。 关系代数查询树是一个树数据结构，在关系代数查询树是一个树数据结构，在查询树中，查询的输入关系表示为叶结查询树中，查询的输入关系表示为叶结点，关系代数操作表示为内部结点，一点，关系代数操作表示为内部结点，一元关系操作符只有一个子结点，二元关元关系操作符只有一个子结点，二元关系操作符有两个子结点。系操作符有两个子结点。 第第15讲讲 关系查询与优化关系查询与优化查询分析与预处理查询分析与预处理每个内部节点用关系操每个内部节点用关系操作符来标记，每个叶子作符来标记，每个叶子结点用关系名来标记。结点用关系名来标记。一元关系操作符只有一一元关系操作符只有一个孩子，二元操作符有个

9、孩子，二元操作符有两个孩子。两个孩子。 Q1查询的关系代数查询树【例例】在在“学生学生- -课程课程”数据库中查询选修了课程号为数据库中查询选修了课程号为“c02”c02”课程的学生姓名。课程的学生姓名。Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC)第第15讲讲 关系查询与优化关系查询与优化查询分析与预处理查询分析与预处理 Q2查询的关系代数查询树【例例】在在“学生学生- -课程课程”数据库中查询选修了课程号为数据库中查询选修了课程号为“c02”c02”课程的学生姓名。课程的学生姓名。Q2：SN (S Sno(SC.Cno= c02 (SC) ) 第第15讲讲 关系查

10、询与优化关系查询与优化查询语句查询语句查询解析器查询解析器 查询预处理器查询预处理器关系代数查询树关系代数查询树查询优化器查询优化器查询计划的执行代码查询计划的执行代码执行引擎执行引擎执行结果执行结果数据字典数据字典查询分析与预处理查询分析与预处理SELECT Sn FROM S，SC WHERE S.Sno=SC.Sno AND SC.Cno= c02 ;语法分析树语法分析树关系代数优化查询树关系代数优化查询树查询代码生成器查询代码生成器Sn (S.Sno=SC.Sno SC.Cno= c02 (SSC) 第第15讲讲 关系查询与优化关系查询与优化 由查询优化器将查询预处理器所生成的由查询优

11、化器将查询预处理器所生成的关关系代数初始查询树系代数初始查询树转换成一个预期所需执转换成一个预期所需执行时间较小的等价的行时间较小的等价的关系代数查询树关系代数查询树，得，得到一个可被转换成最有效的物理查询计划到一个可被转换成最有效的物理查询计划的一个的一个“优化优化”的逻辑查询计划的逻辑查询计划。代数优化第第15讲讲 关系查询与优化关系查询与优化 代数优化的必要性代数优化的必要性 代数优化 【例例】分析实现分析实现“查询选修了课程号为查询选修了课程号为c02课课程的学生姓名程的学生姓名”的两种关系代数查询树的执行效的两种关系代数查询树的执行效率。率。Q1：SN (S.Sno=SC.Sno S

12、C.Cno=c02 (SSC)Q2：SN (S Sno(SC.Cno= c02 (SC) ) 第第15讲讲 关系查询与优化关系查询与优化 代数优化的必要性 代数优化在衡量代价时，需要使用如下一些参数：在衡量代价时，需要使用如下一些参数： 操作符使用的内存大小操作符使用的内存大小M。 假设内存被分成缓冲区，缓冲区的大小与磁盘块的大小相同假设内存被分成缓冲区，缓冲区的大小与磁盘块的大小相同。M表示一个特定的操作符执行时可以获得的内存缓冲区的表示一个特定的操作符执行时可以获得的内存缓冲区的数目。数目。 关系关系R所占磁盘块的大小所占磁盘块的大小B(R) 通常假设通常假设R聚集存储聚集存储在在B个块或

13、近似个块或近似B个块中。个块中。 关系关系R中元组的数目中元组的数目T(R) 一个块中能容纳的一个块中能容纳的R 的元组数可表示为的元组数可表示为T/B。 关系关系R的一个属性列上不同值的数目的一个属性列上不同值的数目V(R,a)。第第15讲讲 关系查询与优化关系查询与优化代数优化【例例】分析实现分析实现“查询选修了课程号为查询选修了课程号为c02课程的学生姓名课程的学生姓名”的两种关系代数查询树的执行效率。的两种关系代数查询树的执行效率。（1）T(S)=1000，T(SC)=10000。选修。选修“c02” 课程的元组为课程的元组为50个。个。（2）假设数据记录均为定长记录，一个磁盘块能存储

14、）假设数据记录均为定长记录，一个磁盘块能存储10个个S元组记元组记录，或录，或100个个SC 元组记录。则元组记录。则B(S)=100， B(SC)=100。（3）对关系）对关系S和关系和关系SC的连接采用嵌套循环方法，选择关系的连接采用嵌套循环方法，选择关系S作为作为外循环关系。内存的磁盘缓冲区外循环关系。内存的磁盘缓冲区M=7，可同时容纳，可同时容纳5块关系块关系S的的磁盘块、磁盘块、1块关系块关系SC的磁盘块，的磁盘块，1块用于存放中间结果。块用于存放中间结果。（4）关系）关系S和和SC的运算结果装满一个缓冲区块后需及时地由缓冲的运算结果装满一个缓冲区块后需及时地由缓冲区存储到磁盘上的中

15、间文件中，一个缓冲区块能存储区存储到磁盘上的中间文件中，一个缓冲区块能存储10个运算结个运算结果记录。果记录。（5）假设缓冲区管理器每秒读写）假设缓冲区管理器每秒读写20个磁盘块。个磁盘块。 代数优化的必要性 第第15讲讲 关系查询与优化关系查询与优化1.计算广义笛卡尔积 SSC 代数优化Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC)第第15讲讲 关系查询与优化关系查询与优化 10个个S元组元组 100个个SC元组元组 10个个SCS元组元组 10个个S元组元组 100个个SC元组元组 10个个SCS元组元组 磁盘磁盘B(S)=100块块B(SC)=100块块T(S)

16、*T(SC)/105块块1块块1块块内存内存20次次100次次106次次代数优化第第15讲讲 关系查询与优化关系查询与优化1.计算广义笛卡尔积 SSC 读取关系读取关系S和关系和关系SC的总的磁盘块数的总的磁盘块数=读取关系读取关系S的磁盘块数的磁盘块数+ 读取关系读取关系SC的遍数的遍数 每遍读取的关系每遍读取的关系SC的磁盘块数的磁盘块数=B(S)+ (100/5) B(SC)=100+20100=2100（块）（块） 读数据时间读数据时间=2100/20=105秒秒 运算中间结果元组数运算中间结果元组数= 1000*10000 = 107 运算中间结果需占用的磁盘块数运算中间结果需占用的

17、磁盘块数=107 /10=106（块）（块） 运算中间结果写入磁盘时间运算中间结果写入磁盘时间 = 107 /10/20 = 5104秒秒 代数优化Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC)第第15讲讲 关系查询与优化关系查询与优化2. 选择操作S.Sno=SC.Sno SC.Cno= c02 选择操作执行时间选择操作执行时间=中间结果文件读取时间中间结果文件读取时间=运算中间结果写入磁盘时间运算中间结果写入磁盘时间=5104（s） 运算结果只有运算结果只有50条记录，可驻留内存。条记录，可驻留内存。3.投影操作SN 对内存的对内存的50条记录进行操作，忽略不计。

18、条记录进行操作，忽略不计。 查询查询Q1所需总时间所需总时间 =105 5104 5104 =100105（s） 27.8（h）代数优化Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC)第第15讲讲 关系查询与优化关系查询与优化1.读SC作选择和投影Sno(SC.Cno= c02 (SC) ) 读取关系读取关系SCSC的磁盘块数的磁盘块数= B(SC)=100= B(SC)=100（块）（块）读数据时间读数据时间=100/20=5=100/20=5（s s）在内存中，对读取的数据进行选择和投影操作，时间忽略不计。在内存中，对读取的数据进行选择和投影操作，时间忽略不计。满足

19、条件的中间结果元组数满足条件的中间结果元组数=50=50，驻留内存，不必用中间文件。，驻留内存，不必用中间文件。2.读S作连接和投影SN (S Sno(SC.Cno= c02 (SC) ) 读取关系读取关系S S的磁盘块数的磁盘块数= B(S)=100= B(S)=100（块）（块）读数据时间读数据时间=100/20=5=100/20=5（s s）在内存中，对读取的在内存中，对读取的S S元组与元组与5050个选课元组进行连接操作后投影，个选课元组进行连接操作后投影，时间忽略不计。时间忽略不计。 查询查询Q2所需总时间所需总时间 = 55=10（s） 代数优化Q2：SN (S Sno(SC.C

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

21、序，提高其查询效率？查询效率？第第15讲讲 关系查询与优化关系查询与优化 代数优化 关系代数表达式（查询树）的优化就是指按照关系代数表达式（查询树）的优化就是指按照一定的一定的规则规则，改变关系代数表达式中操作的次，改变关系代数表达式中操作的次序和组合，将其序和组合，将其转换转换为一个可以更高效执行的为一个可以更高效执行的关系代数表达式（查询树）。关系代数表达式（查询树）。 基于代数等价的启发式优化基于代数等价的启发式优化代数优化第第15讲讲 关系查询与优化关系查询与优化 基于代数等价的启发式优化 通过利用一些启发式规则，将一个代数表达式通过利用一些启发式规则，将一个代数表达式转换为另一个不同

22、的但等价的代数表达式，产转换为另一个不同的但等价的代数表达式，产生可被进一步优化的查询执行计划。生可被进一步优化的查询执行计划。 关系代数表达式等价：指用关系代数表达式等价：指用相同的相同的关系实例代替两关系实例代替两个表达式中相应的关系所得到的结果是相同的。个表达式中相应的关系所得到的结果是相同的。代数优化第第15讲讲 关系查询与优化关系查询与优化 基于代数等价的启发式优化 常用的等价变换规则常用的等价变换规则设设E、E1、E2等是关系代数表达式，等是关系代数表达式，F、F1、F2是条件表达式是条件表达式1.连接、笛卡尔积交换律连接、笛卡尔积交换律E1 E2 E2E1E1 E2 E2 E1

23、E1 F E2 E2 F E12. 连接、笛卡尔积的结合律连接、笛卡尔积的结合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 F1 E2) F2 E3 E1 F1 (E2 F2 E3) 代数优化第第15讲讲 关系查询与优化关系查询与优化 基于代数等价的启发式优化 常用的等价变换规则常用的等价变换规则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)代

24、数优化第第15讲讲 关系查询与优化关系查询与优化 基于代数等价的启发式优化 常用的等价变换规则常用的等价变换规则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代数优化第第15讲讲 关系查询与优化关系查询与优化 基于代数等价的启发式优化 常用的等价变换规则常用的等价变换规则6. 选择与笛卡尔积的交换律选择与笛卡尔积的交换律 F (E1E2)

25、 F (E1)E2 F中涉及的属性都是中涉及的属性都是E1中的属性中的属性 F(E1E2) F1(E1)F2 (E2) F=F1F2，并且，并且F1只涉及只涉及E1中的属性，中的属性， F2只涉及只涉及E2中的属性中的属性 F(E1E2) F2(F1(E1)E2) F=F1F2，F1只涉及只涉及E1中的属性，中的属性，F2涉及涉及E1和和E2两者的属性两者的属性代数优化第第15讲讲 关系查询与优化关系查询与优化 基于代数等价的启发式优化 常用的等价变换规则常用的等价变换规则7. 选择对自然连接的分配律选择对自然连接的分配律 F(E1 E2) F(E1) F(E2) F是只涉及是只涉及E1和和E

26、2的公共属性的公共属性8.选择对并的分配律选择对并的分配律 F(E1E2) F(E1)F(E2) E1与与E2有相同的属性或属性有对应性有相同的属性或属性有对应性 9.选择对差运算的分配律选择对差运算的分配律 F(E1-E2) F(E1) - F(E2) E1、E2有相同的属性或属性有对应性有相同的属性或属性有对应性 代数优化第第15讲讲 关系查询与优化关系查询与优化 基于代数等价的启发式优化 常用的等价变换规则常用的等价变换规则10.投影对笛卡尔积的分配律投影对笛卡尔积的分配律 A1,A2, ,An,B1,B2, ,Bm (E1E2) A1,A2, ,An(E1)B1,B2, ,Bm(E2)

27、 A1，An是是E1的属性，的属性，B1，Bm是是E2的属性的属性11.投影对并的分配律投影对并的分配律 A1,A2, ,An(E1E2) A1,A2, ,An(E1)A1,A2, ,An(E2) 12.选择与连接运算的结合选择与连接运算的结合F (E1E2) E1 F E2 F1 (E1 F2 E2) E1 F1 F2 E2 代数优化第第15讲讲 关系查询与优化关系查询与优化 基于代数等价的启发式优化 主要的启发式规则主要的启发式规则 选择运算应尽可能先做选择运算应尽可能先做 投影运算和选择运算同时进行投影运算和选择运算同时进行 将投影运算与其前面或后面的双目运算结合将投影运算与其前面或后面

28、的双目运算结合 某些选择运算同在其前面执行的笛卡尔积结合成为某些选择运算同在其前面执行的笛卡尔积结合成为一个连接运算一个连接运算 提取公共子表达式提取公共子表达式 代数优化第第15讲讲 关系查询与优化关系查询与优化 基于代数等价的启发式优化 启发式代数优化算法启发式代数优化算法 输入：一个关系代数查询树输入：一个关系代数查询树输出：计算关系代数表达式的一个优化序列输出：计算关系代数表达式的一个优化序列 步骤：步骤：（1）分解选择运算）分解选择运算（2）交换选择运算，将其尽可能移到叶端）交换选择运算，将其尽可能移到叶端（3）交换投影运算，将其尽可能移到叶端）交换投影运算，将其尽可能移到叶端（4）

29、合并串接的选择和投影运算）合并串接的选择和投影运算（5）对内结点分组）对内结点分组 每个二元运算每个二元运算(， ，-)和它所有的直接祖先为一组和它所有的直接祖先为一组。如果其后代直到叶子全是单目运算，则也将它们并入该组。如果其后代直到叶子全是单目运算，则也将它们并入该组。 （6）生成优化序列）生成优化序列代数优化第第15讲讲 关系查询与优化关系查询与优化代数优化 基于代数等价的启发式优化【例例】利用优化算法对执行效率较低的查询利用优化算法对执行效率较低的查询Q1的查的查询树进行优化。询树进行优化。Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC) SN ( S.Sno=

30、SC.Sno ( SC.Cno=c02 (SSC) SN ( S.Sno=SC.Sno ( SC.Cno=c02 (SCS) SN ( S.Sno=SC.Sno ( SC.Cno=c02 (SC)S) SN ( SC.Cno=c02 (SC) S) 第第15讲讲 关系查询与优化关系查询与优化代数优化 基于代数等价的启发式优化Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC)第第15讲讲 关系查询与优化关系查询与优化代数优化 基于代数等价的启发式优化Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC) 第第15讲讲 关系查询与优化关系查询与优化代数优化

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

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

33、，使用代价估计，使用代价估计来评价一个查询计划。来评价一个查询计划。第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 每一个每一个操作符操作符实现算法的选择是将逻辑查询计实现算法的选择是将逻辑查询计划转变为物理查询计划过程中的一个必不可少划转变为物理查询计划过程中的一个必不可少的部分。的部分。 针对各种操作符，已提出了很多算法，大体上针对各种操作符，已提出了很多算法，大体上分为三类：分为三类： 基于排序的方法基于排序的方法 基于散列的方法基于散列的方法 基于索引的方法基于索引的方法第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 对算法的描述仍使用磁

34、盘对算法的描述仍使用磁盘I/O的次数作为衡量每的次数作为衡量每个查询的代价的标准和使用如下参数：个查询的代价的标准和使用如下参数： 操作符使用的内存大小操作符使用的内存大小M。 关系关系R所占磁盘块的大小所占磁盘块的大小B(R) 关系关系R中元组的数目中元组的数目T(R) 关系关系R的一个属性列上不同值的数目的一个属性列上不同值的数目V(R,a)。第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 选择操作的实现算法选择操作的实现算法 选择操作选择操作c(R)是读取关系是读取关系R中那些满足谓词条件中那些满足谓词条件C的元组，定位这些元组的基本方法有两种：的元组，定位这些元

35、组的基本方法有两种：简单的全表扫描方法简单的全表扫描方法索引扫描法索引扫描法第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 选择操作的实现算法选择操作的实现算法 简单的全表扫描方法简单的全表扫描方法如果如果R 是聚集的，那么全表扫描的代价近似为是聚集的，那么全表扫描的代价近似为B(R)。如果如果R不是聚集的，那么全表扫描所需的不是聚集的，那么全表扫描所需的I/O代代价为价为T(R)。第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 选择操作的实现算法选择操作的实现算法 索引扫描法索引扫描法假设假设条件条件C是是a=v 的形式，的形式，a是一个存在着

36、是一个存在着索引的属性索引的属性，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)个元组。个元

37、组。T(R)/V(R,a)是估计的磁盘是估计的磁盘I/O次数。次数。第第15讲讲 关系查询与优化关系查询与优化 物理优化【例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

38、(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是一个关键字，那么基于索引的算法，是一个

39、关键字，那么基于索引的算法，不管索引是聚集的或是非聚集的，都将需要不管索引是聚集的或是非聚集的，都将需要1次次磁盘磁盘I/O。第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 连接操作的实现算法连接操作的实现算法 在下面的连接算法中，将在下面的连接算法中，将R(X,Y)与与S(Y,Z)连接，连接，Y 表表示示R和和S的所有公共属性的所有公共属性，X是是R的所有不在的所有不在S模式中模式中的属性，的属性，Z是是S的所有不在的所有不在R模式中的属性。假设模式中的属性。假设S是是较小的关系较小的关系。 第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 连接

40、操作的实现算法连接操作的实现算法 一趟连接运算一趟连接运算假设较小的关系假设较小的关系S，可存入内存的，可存入内存的M-1块中。块中。 读取读取S的所有元组，并且构造一个以的所有元组，并且构造一个以Y属性为查找关键字的属性为查找关键字的内存查找结构。内存查找结构。 将将R的每一磁盘块中的元组读到内存中剩下的那一个缓冲区的每一磁盘块中的元组读到内存中剩下的那一个缓冲区中。中。 对于对于R的每一个元组的每一个元组t，利用查找结构找到，利用查找结构找到S中与中与t在在Y的所有的所有属性上相符合的元组。对于属性上相符合的元组。对于S中每一个匹配的元组，将它与中每一个匹配的元组，将它与t配对后形成一个元

41、组，并且将结果元组移到输出文件中。配对后形成一个元组，并且将结果元组移到输出文件中。读取操作对象需要读取操作对象需要B(S)+ B(R)次磁盘次磁盘I/O，仅从磁盘，仅从磁盘读取一次数据。读取一次数据。第第15讲讲 关系查询与优化关系查询与优化S元组元组 R元组元组 RS元组元组S元组元组R元组元组 RS元组元组 磁盘磁盘B(S) M-1 M-1块块1块块1块块缓冲区缓冲区一趟连接运算 物理优化1次次1次次B(R)第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 连接操作的实现算法连接操作的实现算法 嵌套循环连接嵌套循环连接嵌套循环连接算法是对外层循环关系（如嵌套循环连接

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

43、中的关系。中的关系。 第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 连接操作的实现算法连接操作的实现算法 基于块的嵌套循环连接算法基于块的嵌套循环连接算法读取关系读取关系S的的M-1个磁盘块中的元组到内存缓冲区中。个磁盘块中的元组到内存缓冲区中。 为为S在内存中的元组创建一个查找结构，它的查找关键字是在内存中的元组创建一个查找结构，它的查找关键字是R和和S的公共属性。的公共属性。浏览浏览R的所有块，依次读取每一块到内存的所有块，依次读取每一块到内存M块中的最后一块块中的最后一块中。中。在读入在读入R的一个块后，将块中所有元组与的一个块后，将块中所有元组与S在内存中的所

44、有在内存中的所有块中的所有元组进行比较。对于那些能连接的元组，输出连块中的所有元组进行比较。对于那些能连接的元组，输出连接得到的元组。接得到的元组。重复执行前面的步骤，直到处理完重复执行前面的步骤，直到处理完S中所有磁盘块中的数据中所有磁盘块中的数据。读取数据的磁盘读取数据的磁盘I/O次数是次数是B(S)+ (B(S)B(R)/ (M-1)。 第第15讲讲 关系查询与优化关系查询与优化S元组元组S元组元组 R元组元组 RS元组元组S元组元组R元组元组 RS元组元组 磁盘磁盘B(S) M B(R)M-1块块1块块缓冲区缓冲区基于块的嵌套循环连接算法 物理优化1次次B(S)/(M-1)次次第第15

45、讲讲 关系查询与优化关系查询与优化 物理优化【例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 要略少一些，略有优势。第第15讲讲 关系查询与优

46、化关系查询与优化 物理优化 操作符的实现算法 连接操作的实现算法连接操作的实现算法 排序排序-归并连接归并连接关系关系R和和S按照连接属性按照连接属性Y有序聚集存储。两个缓冲区，一个有序聚集存储。两个缓冲区，一个给给R的当前块，另一个给的当前块，另一个给S的当前块的当前块。按照连接属性的顺序对关系按照连接属性的顺序对关系R和和S并发地进行物理顺序扫描，把关系并发地进行物理顺序扫描，把关系R和和S的首个磁盘块中的元组读入内存缓冲区。的首个磁盘块中的元组读入内存缓冲区。在读入内存的当前在读入内存的当前R和和S的元组中顺序查找连接属性的元组中顺序查找连接属性Y的最小匹配值的最小匹配值y。如果需要，从

47、排序的。如果需要，从排序的R和和/或或S中继续读取下一个磁盘块，直到找中继续读取下一个磁盘块，直到找到最小匹配值到最小匹配值y。连接内存中连接内存中R和和S的具有相同的具有相同y值的所有元组。如果一个关系在内存值的所有元组。如果一个关系在内存中已没有未考虑的元组，就顺序读取该文件的下一个磁盘块，直到中已没有未考虑的元组，就顺序读取该文件的下一个磁盘块，直到处理完两个关系中具有相同处理完两个关系中具有相同y值的所有元组。值的所有元组。在内存在内存R和和S的元组中顺序查找连接属性的元组中顺序查找连接属性Y的下一个匹配值的下一个匹配值y，从步，从步骤骤3开始重复执行。直到处理完某一关系的所有磁盘块中

48、的元组。开始重复执行。直到处理完某一关系的所有磁盘块中的元组。第第15讲讲 关系查询与优化关系查询与优化S元组元组 R元组元组 RS元组元组S元组元组R元组元组 RS元组元组 磁盘磁盘B(S)B(R)1块块1块块缓冲区缓冲区排序-归并连接算法 物理优化1次次1次次读取操作对象需要读取操作对象需要B(S)+ B(R)次磁盘次磁盘I/O，仅从磁盘读取，仅从磁盘读取一次数据。一次数据。第第15讲讲 关系查询与优化关系查询与优化 物理优化【例7-8】假定B(R)=1000，B(S)=500，M=101。假设R和S均已按属性Y排序，计算采用排序归并连接算法代价。用1500次磁盘I/O来读取R和S的每一个

49、块，仅需要101个内存块中的两个。如果需要可以使用所有101块来容纳具有公共Y值的R和S的元组。第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 连接操作的实现算法连接操作的实现算法 基于散列的连接基于散列的连接算法的基本思想是如果数据量太大以至于不能存算法的基本思想是如果数据量太大以至于不能存入内存缓冲区中，可使用一个合适的散列键散列入内存缓冲区中，可使用一个合适的散列键散列一个或多个操作对象的所有元组。然后通过一次一个或多个操作对象的所有元组。然后通过一次处理具有相同散列值的一对桶的方式执行操作。处理具有相同散列值的一对桶的方式执行操作。假设假设h是散列函数，用连接属

50、性是散列函数，用连接属性Y作散列键，来散作散列键，来散列两个关系列两个关系R和和S的元组，将元组散列到适当的散的元组，将元组散列到适当的散列桶中。如果列桶中。如果R与与S的元组能连接，那么它们必然的元组能连接，那么它们必然出现在具有某个出现在具有某个i值的对应的桶值的对应的桶Ri和和Si中。中。 第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 连接操作的实现算法连接操作的实现算法 基于散列的连接算法基于散列的连接算法每一个桶对中有一个能全部装入每一个桶对中有一个能全部装入M-1个缓冲区中。个缓冲区中。 可按桶号可按桶号i的大小将包含较少磁盘块的桶（的大小将包含较少磁盘块

51、的桶（Si中的桶）读入中的桶）读入到内存的缓冲区中，构造内存中的一个散列查找结构。到内存的缓冲区中，构造内存中的一个散列查找结构。读入另一关系读入另一关系R中的与中的与Si对应的桶对应的桶Ri，将读入的，将读入的Ri中的元组中的元组与内存中与内存中Si中的记录进行连接，将连接的结果进行输出。中的记录进行连接，将连接的结果进行输出。重复以上步骤，直到重复以上步骤，直到S中的所有桶处理完。中的所有桶处理完。连接操作读取操作对象需要连接操作读取操作对象需要B(S)+ B(R)次磁盘次磁盘I/O，仅从磁盘读取一次数据。仅从磁盘读取一次数据。 第第15讲讲 关系查询与优化关系查询与优化S元组元组 R元组

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

53、接需1500次磁盘I/O。第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 连接操作的实现算法连接操作的实现算法 基于索引的连接运算基于索引的连接运算如果一个关系（如如果一个关系（如S）有一个属性）有一个属性Y上的索引。上的索引。读入读入R的一个磁盘块，考虑块中每一个元组的一个磁盘块，考虑块中每一个元组t，令，令ty是元组是元组t中中y属性的值。属性的值。使用使用S上的索引，来找到上的索引，来找到S中所有在中所有在Y属性上具有相同属性上具有相同ty的那的那些元组所在的磁盘块，将这些元组（所在的磁盘块）读入内些元组所在的磁盘块，将这些元组（所在的磁盘块）读入内存与存与R中的

54、元组中的元组t连接起来，作为结果输出。连接起来，作为结果输出。重复以上步骤，直到重复以上步骤，直到R中的所有元组处理完。中的所有元组处理完。第第15讲讲 关系查询与优化关系查询与优化S元组元组S元组元组R元组元组 RS元组元组S(ty)元组元组R(ty) 元组元组 RS元组元组 磁盘磁盘B(S)B(R)1块块1块块缓冲区缓冲区基于索引的连接算法 物理优化tyty S的索引的索引第第15讲讲 关系查询与优化关系查询与优化 物理优化 操作符的实现算法 连接操作的实现算法连接操作的实现算法 基于索引的连接运算基于索引的连接运算如果如果R是聚集的，将需要读取是聚集的，将需要读取B(R)个块来得到个块来

55、得到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值，可能需要增加几次磁

56、盘值，可能需要增加几次磁盘I/O，用于，用于读取相关索引文件。读取相关索引文件。 第第15讲讲 关系查询与优化关系查询与优化 物理优化【例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上有一个聚集索引，需要10000500/100=50000次磁盘I/O读取S。如果R是非聚集的或S上的索引是非聚集的，代价会更高。 第第15讲讲 关系查询与优化关系查询与优化 物理优化

57、 操作符的实现算法 连接操作的实现算法连接操作的实现算法 基于索引的连接运算基于索引的连接运算 常见的连接查询的情况是与常见的连接查询的情况是与S相比，相比，R是很小的，是很小的，V(S,Y)是很大是很大的。在这种情况下，的。在这种情况下，S的大多数元组的的大多数元组的Y值根本不出现在值根本不出现在R中，这中，这些元组将无需被算法检查，即不需要读入内存。但是，不论基于些元组将无需被算法检查，即不需要读入内存。但是，不论基于排序的还是基于散列的连接方法都需检查排序的还是基于散列的连接方法都需检查S的每一个元组至少一次。的每一个元组至少一次。所以，在实际的应用中，索引选择算法仍是一种常用的方法。所

58、以，在实际的应用中，索引选择算法仍是一种常用的方法。第第15讲讲 关系查询与优化关系查询与优化【例例】分析实现分析实现“查询选修了课程号为查询选修了课程号为c02课程的学生姓名课程的学生姓名”（1）T(S)=1000，T(SC)=10000。选修。选修“c02” 课程的元组为课程的元组为50个。个。（2）一个磁盘块能存储）一个磁盘块能存储10个个S元组记录，或元组记录，或100个个SC 元组记录。则元组记录。则B(S)=100， B(SC)=100。 Q1: SELECT SN FROM S，SC WHERE S.Sno=SC.Sno AND SC.Cno= c02 ; Q1：SN (SC.C

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

60、的执行代价，使用代价估计来评价一个查询计划。来评价一个查询计划。第第15讲讲 关系查询与优化关系查询与优化 基于代价的物理优化方法基于代价的物理优化方法 查询计划的代价因素查询计划的代价因素一个查询的实际执行所需的代价包括一个查询的实际执行所需的代价包括: 磁盘访问代价：读写记录所在磁盘数据块的代价。磁盘访问代价：读写记录所在磁盘数据块的代价。 存储代价：存储由查询执行计划产生的中间结果文存储代价：存储由查询执行计划产生的中间结果文件的代价。件的代价。 计算代价：在查询执行过程中对数据缓冲区完成内计算代价：在查询执行过程中对数据缓冲区完成内存操作的代价。存操作的代价。 内存使用代价：与执行查询