数据库查询处置和优化专业知识讲座.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,15,讲 关系查询与优化,*,文档来源于网络，文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,实例,应用实例,假设学生,-,课程数据库中有,1000,个学生，,10000,个选课记录，其中选修“,c02”,课程的记录为,50,个。,一个磁盘块能存储,10,个,S,元组，或,100,个,SC,元组。,用,SQL,语句表达查询：选修了“,c02”,课程的学生姓名。,用多种等价的关系代数表达式来完成这一查询。,分析该查询在不同存储结构和索引结构的磁盘,I/O,次数。,1,实例,【,例,】,查询选修了,“,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,）,；,2,实例,【,例,】,查询选修了“,c02”,课程的学生姓名,Sn,(,S.Sno=SC.Sno SC.Cno=2,(SSC),Sn,(,SC.Cno=2,(S,SC),Sn,(S,SC.Cno=2,(SC),3,关系查询与优化,查询处理步骤,查询优化技术,代数优化,物理优化,4,查询语句,查询解析器,查询分析,查询预处理器,关系代数查询树,查询优化器,查询计划的执行代码,执行引擎,执行结果,查询预处理,查询优化,查询执行,数据字典,数据库系统的查询处理步骤,SELECT Sn,FROM S,，,SC,WHERE S.Sno=SC.Sno,AND SC.Cno=c02;,语法分析树,关系代数优化查询树,查询代码生成器,生成执行代码,查询处理器的组成和查询处理的典型步骤,5,查询分析与预处理,查询分析,接受类似,SQL,这样的高级查询语言表示的查询，并进行词法分析和语法分析。,6,【,例,】,在“学生,-,课程”数据库中查询选修了课程号为“,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,）,7,【,例,】,在“学生,-,课程”数据库中查询选修了课程号为“,c02”,课程的学生姓名。,查询分析与预处理,用查询语句,Q1,实现两个关系的连接查询的语法分析树,8,【,例,】,在“学生,-,课程”数据库中查询选修了课程号为“,c02”,课程的学生姓名。,查询分析与预处理,用查询语句,Q2,实现两个关系的嵌套查询的语法分析树,9,查询分析与预处理,查询有效性检查,根据数据字典对合法的查询语句进行语义检查。,检查语句中的数据库对象在所查询的特定数据库模式中是否为有效且有语义含义的名字。,检查所有属性的类型是否与其使用相对应，以及根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。,10,查询分析与预处理,生成关系代数初始查询树,查询预处理器采用一些相应的规则，用一个或多个关系代数运算符替换语法树上的结点与结构，生成一个对应于,SQL,查询的关系代数初始查询树。,关系代数查询树是一个树数据结构，在查询树中，查询的输入关系表示为叶结点，关系代数操作表示为内部结点，一元关系操作符只有一个子结点，二元关系操作符有两个子结点。,11,查询分析与预处理,每个内部节点用关系操作符来标记，每个叶子结点用关系名来标记。一元关系操作符只有一个孩子，二元操作符有两个孩子。,Q1,查询的关系代数查询树,【,例,】,在“学生,-,课程”数据库中查询选修了课程号为“,c02”,课程的学生姓名。,Q1,：,SN,(,S.Sno=SC.Sno SC.Cno=c02,(SSC),12,查询分析与预处理,Q2,查询的关系代数查询树,【,例,】,在“学生,-,课程”数据库中查询选修了课程号为“,c02”,课程的学生姓名。,Q2,：,SN,(S,Sno,(,SC.Cno=c02,(SC),13,查询语句,查询解析器,查询预处理器,关系代数查询树,查询优化器,查询计划的执行代码,执行引擎,执行结果,数据字典,查询分析与预处理,SELECT Sn,FROM S,，,SC,WHERE S.Sno=SC.Sno,AND SC.Cno=c02;,语法分析树,关系代数优化查询树,查询代码生成器,Sn,(,S.Sno=SC.Sno SC.Cno=c02,(SSC),14,由查询优化器将查询预处理器所生成的,关系代数初始查询树,转换成一个预期所需执行时间较小的等价的,关系代数查询树,，得到一个可被转换成最有效的物理查询计划的一个,“优化”的逻辑查询计划,。,代数优化,15,代数优化的必要性,代数优化,【,例,】,分析实现“查询选修了课程号为,c02,课程的学生姓名”的两种关系代数查询树的执行效率。,Q1,：,SN,(,S.Sno=SC.Sno SC.Cno=c02,(SSC),Q2,：,SN,(S,Sno,(,SC.Cno=c02,(SC),16,代数优化的必要性,代数优化,在衡量代价时，需要使用如下一些参数：,操作符使用的内存大小,M,。,假设内存被分成缓冲区，缓冲区的大小与磁盘块的大小相同。,M,表示一个特定的操作符执行时可以获得的内存缓冲区的数目。,关系,R,所占磁盘块的大小,B(R),通常假设,R,聚集存储,在,B,个块或近似,B,个块中。,关系,R,中元组的数目,T(R),一个块中能容纳的,R,的元组数可表示为,T/B,。,关系,R,的一个属性列上不同值的数目,V(R,a,),。,17,代数优化,【,例,】,分析实现“查询选修了课程号为,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,个磁盘块。,代数优化的必要性,18,1,.,计算广义笛卡尔积,SSC,代数优化,Q1,：,SN,(,S.Sno=SC.Sno SC.Cno=c02,(SSC),19,10,个,S,元组,100,个,SC,元组,10,个,SC,S,元组,10,个,S,元组,100,个,SC,元组,10,个,SC,S,元组,磁盘,B(S)=100,块,B(SC)=100,块,T(S)*T(SC),/10,5,块,1,块,1,块,内存,20,次,100,次,10,6,次,代数优化,20,1.,计算广义笛卡尔积,SSC,读取关系,S,和关系,SC,的总的磁盘块数,=,读取关系,S,的磁盘块数,+,读取关系,SC,的遍数,每遍读取的关系,SC,的磁盘块数,=B(S)+(100/5)B(SC),=100+20100=2100,（块）,读数据时间,=2100/20=105,秒,运算中间结果元组数,=1000*10000=10,7,运算中间结果需占用的磁盘块数,=10,7,/10=10,6,（块）,运算中间结果写入磁盘时间,=10,7,/10/20=510,4,秒,代数优化,Q1,：,SN,(,S.Sno=SC.Sno SC.Cno=c02,(SSC),21,2.,选择操作,S.Sno=SC.Sno SC.Cno=c02,选择操作执行时间,=,中间结果文件读取时间,=,运算中间结果写入磁盘时间,=510,4,（,s,）,运算结果只有,50,条记录，可驻留内存。,3.,投影操作,SN,对内存的,50,条记录进行操作，忽略不计。,查询,Q1,所需总时间,=105,510,4,510,4,=100105,（,s,）,27.8,（,h,）,代数优化,Q1,：,SN,(,S.Sno=SC.Sno SC.Cno=c02,(SSC),22,1.,读,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),23,代数优化的必要性,对于实现同一查询的不同的关系代数表达式（查询树），其操作的次序不同，查询效率不同，查询时间相差很大。,有必要对查询预处理器产生的关系代数初始查询树进行优化，得到较优的逻辑查询计划，而不管用户书写的,SQL,查询是什么形式。,代数优化,如何改变关系代数表达式的操作次序，提高其查询效率？,24,代数优化,关系代数表达式（查询树）的优化就是指按照一定的,规则,，改变关系代数表达式中操作的次序和组合，将其,转换,为一个可以更高效执行的关系代数表达式（查询树）。,基于代数等价的启发式优化,代数优化,25,基于代数等价的启发式优化,通过利用一些启发式规则，将一个代数表达式转换为另一个不同的但等价的代数表达式，产生可被进一步优化的查询执行计划。,关系代数表达式等价：指用,相同的,关系实例代替两个表达式中相应的关系所得到的结果是相同的。,代数优化,26,基于代数等价的启发式优化,常用的等价变换规则,设,E,、,E1,、,E2,等是关系代数表达式，,F,、,F1,、,F2,是条件表达式,1.,连接、笛卡尔积交换律,E1 E2 E2E1,E1 E2 E2 E1,E1,F,E2 E2 ,F,E1,2.,连接、笛卡尔积的结合律,(E1E2)E3 E1 (E2E3),(E1 E2)E3 E1 (E2 E3),(E1,F1,E2),F2,E3 E1,F1,(E2 ,F2,E3),代数优化,27,基于代数等价的启发式优化,常用的等价变换规则,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),代数优化,28,基于代数等价的启发式优化,常用的等价变换规则,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,代数优化,29,基于代数等价的启发式优化,常用的等价变换规则,6.,选择与笛卡尔积的交换律,F,(E1E2),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,两者的属性,代数优化,30,基于代数等价的启发式优化,常用的等价变换规则,7.,选择对自然连接的分配律,F,(E1E2),F,(E1),F,(E2),F,是只涉及,E1,和,E2,的公共属性,8.,选择对并的分配律,F,(E1E2),F,(E1),F,(E2),E1,与,E2,有相同的属性或属性有对应性,9.,选择对差运算的分配律,F,(E1-E2),F,(E1)-,F,(E2),E1,、,E2,有相同的属性或属性有对应性,代数优化,31,基于代数等价的启发式优化,常用的等价变换规则,10.,投影对笛卡尔积的分配律,A1,A2,An,B1,B2,Bm,(E1E2),A1,A2,An,(E1),B1,B2,Bm,(E2),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,代数优化,32,基于代数等价的启发式优化,主要的启发式规则,选择运算应尽可能先做,投影运算和选择运算同时进行,将投影运算与其前面或后面的双目运算结合,某些选择运算同在其前面执行的笛卡尔积结合成为一个连接运算,提取公共子表达式,代数优化,33,基于代数等价的启发式优化,启发式代数优化算法,输入：一个关系代数查询树,输出：计算关系代数表达式的一个优化序列,步骤：,（,1,）分解选择运算,（,2,）交换选择运算，将其尽可能移到叶端,（,3,）交换投影运算，将其尽可能移到叶端,（,4,）合并串接的选择和投影运算,（,5,）对内结点分组,每个二元运算,(,，,，,-),和它所有的直接祖先为一组。如果其后代直到叶子全是单目运算，则也将它们并入该组。,（,6,）生成优化序列,代数优化,34,代数优化,基于代数等价的启发式优化,【,例,】,利用优化算法对执行效率较低的查询,Q1,的查询树进行优化。,Q1,：,SN,(,S.Sno=SC.Sno SC.Cno=c02,(SSC),SN,(,S.Sno=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),35,代数优化,基于代数等价的启发式优化,Q1,：,SN,(,S.Sno=SC.Sno SC.Cno=c02,(SSC),36,代数优化,基于代数等价的启发式优化,Q1,：,SN,(,S.Sno=SC.Sno SC.Cno=c02,(SSC),37,代数优化,基于代数等价的启发式优化,【,例,7-5】,供应商零件数据库中有供应商、零件、项目和供应四个基本关系：,供应商关系,S(Sno,，,Sname,，,Status,，,City),零件关系,P(Pno,，,Pname,，,Color,，,Weight),工程项目关系,J(Jno,，,J name,，,City),供应情况关系,SPJ(Sno,，,Pno,，,Jno,，,Qty),查询：检索使用上海供应商生产的红色零件的工程号。,试写出该查询尽可能优化的关系代数表达式，并画出对应的关系代数查询树。,38,物理优化,物理优化,从一个逻辑查询计划产生物理查询计划时，为逻辑查询计划的每一个,操作符,选择实现算法并选择这些操作符的执行顺序，还包括许多实现细节。,被查询的关系是怎样被访问的，即获得所,存储数据的方式,以及一个关系何时或是否应当被,排序,等；,必须估计每个可能选项的,执行代价,，使用代价估计来评价一个查询计划。,39,物理优化,操作符的实现算法,每一个,操作符,实现算法的选择是将逻辑查询计划转变为物理查询计划过程中的一个必不可少的部分。,针对各种操作符，已提出了很多算法，大体上分为三类：,基于排序的方法,基于散列的方法,基于索引的方法,40,物理优化,操作符的实现算法,对算法的描述仍使用磁盘,I/O,的次数作为衡量每个查询的代价的标准和使用如下参数：,操作符使用的内存大小,M,。,关系,R,所占磁盘块的大小,B(R),关系,R,中元组的数目,T(R),关系,R,的一个属性列上不同值的数目,V(R,a,),。,41,物理优化,操作符的实现算法,选择操作的实现算法,选择操作,c(R,),是读取关系,R,中那些满足谓词条件,C,的元组，定位这些元组的基本方法有两种：,简单的全表扫描方法,索引扫描法,42,物理优化,操作符的实现算法,选择操作的实现算法,简单的全表扫描方法,如果,R,是聚集的，那么全表扫描的代价近似为,B(R),。,如果,R,不是聚集的，那么全表扫描所需的,I/O,代价为,T(R),。,43,物理优化,操作符的实现算法,选择操作的实现算法,索引扫描法,假设,条件,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,次数。,44,物理优化,【,例,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,。,45,物理优化,操作符的实现算法,连接操作的实现算法,在下面的连接算法中，将,R(X,Y),与,S(Y,Z),连接，,Y,表示,R,和,S,的所有公共属性,，,X,是,R,的所有不在,S,模式中的属性，,Z,是,S,的所有不在,R,模式中的属性。假设,S,是较小的关系,。,46,物理优化,操作符的实现算法,连接操作的实现算法,一趟连接运算,假设较小的关系,S,，可存入内存的,M-1,块中。,读取,S,的所有元组，并且构造一个以,Y,属性为查找关键字的内存查找结构。,将,R,的每一磁盘块中的元组读到内存中剩下的那一个缓冲区中。,对于,R,的每一个元组,t,，利用查找结构找到,S,中与,t,在,Y,的所有属性上相符合的元组。对于,S,中每一个匹配的元组，将它与,t,配对后形成一个元组，并且将结果元组移到输出文件中。,读取操作对象需要,B(S)+B(R),次磁盘,I/O,，仅从磁盘读取一次数据。,47,S,元组,R,元组,R,S,元组,S,元组,R,元组,R,S,元组,磁盘,B(S),M-1,M-1,块,1,块,1,块,缓冲区,一趟连接运算,物理优化,1,次,1,次,B(R),48,物理优化,操作符的实现算法,连接操作的实现算法,嵌套循环连接,嵌套循环连接算法是对外层循环关系（如,S,）中的每条元组，检查内层循环关系（如,R,）中的每个元组是否满足连接条件，如果满足条件，则连接后作为结果输出，直到外层循环关系中的元组处理完为止。,基于块的嵌套循环连接,算法,对作为操作对象的两个关系的访问均按块组织，假定,B(S)B(R),，并且,B(S),M,。,使用尽可能多的内存来存储属于较小关系,S,的元组，,S,是外层循环,中的关系。,49,物理优化,操作符的实现算法,连接操作的实现算法,基于块的嵌套循环连接算法,读取关系,S,的,M-1,个磁盘块中的元组到内存缓冲区中。,为,S,在内存中的元组创建一个查找结构，它的查找关键字是,R,和,S,的公共属性。,浏览,R,的所有块，依次读取每一块到内存,M,块中的最后一块中。,在读入,R,的一个块后，将块中所有元组与,S,在内存中的所有块中的所有元组进行比较。对于那些能连接的元组，输出连接得到的元组。,重复执行前面的步骤，直到处理完,S,中所有磁盘块中的数据。,读取数据的磁盘,I/O,次数是,B(S)+(B(S)B(R)/(M-1),。,50,S,元组,S,元组,R,元组,R,S,元组,S,元组,R,元组,R,S,元组,磁盘,B(S),M,B(R),M-1,块,1,块,缓冲区,基于块的嵌套循环连接算法,物理优化,1,次,B(S)/(M-1),次,51,物理优化,【,例,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,要略少一些，略有优势。,52,物理优化,操作符的实现算法,连接操作的实现算法,排序,-,归并连接,关系,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,开始重复执行。直到处理完某一关系的所有磁盘块中的元组。,53,S,元组,R,元组,R,S,元组,S,元组,R,元组,R,S,元组,磁盘,B(S),B(R),1,块,1,块,缓冲区,排序,-,归并连接算法,物理优化,1,次,1,次,读取操作对象需要,B(S)+B(R),次磁盘,I/O,，仅从磁盘读取一次数据。,54,物理优化,【,例,7-8】,假定,B(R)=1000,，,B(S)=500,，,M=101,。假设,R,和,S,均已按属性,Y,排序，计算采用排序归并连接算法代价。,用,1500,次磁盘,I/O,来读取,R,和,S,的每一个块，仅需要,101,个内存块中的两个。,如果需要可以使用所有,101,块来容纳具有公共,Y,值的,R,和,S,的元组。,55,物理优化,操作符的实现算法,连接操作的实现算法,基于散列的连接,算法的基本思想是如果数据量太大以至于不能存入内存缓冲区中，可使用一个合适的散列键散列一个或多个操作对象的所有元组。然后通过一次处理具有相同散列值的一对桶的方式执行操作。,假设,h,是散列函数，用连接属性,Y,作散列键，来散列两个关系,R,和,S,的元组，将元组散列到适当的散列桶中。如果,R,与,S,的元组能连接，那么它们必然出现在具有某个,i,值的对应的桶,Ri,和,Si,中。,56,物理优化,操作符的实现算法,连接操作的实现算法,基于散列的连接算法,每一个桶对中有一个能全部装入,M-1,个缓冲区中。,可按桶号,i,的大小将包含较少磁盘块的桶（,Si,中的桶）读入到内存的缓冲区中，构造内存中的一个散列查找结构。,读入另一关系,R,中的与,Si,对应的桶,Ri,，将读入的,Ri,中的元组与内存中,Si,中的记录进行连接，将连接的结果进行输出。,重复以上步骤，直到,S,中的所有桶处理完。,连接操作读取操作对象需要,B(S)+B(R),次磁盘,I/O,，仅从磁盘读取一次数据。,57,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),58,物理优化,【,例,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,。,59,物理优化,操作符的实现算法,连接操作的实现算法,基于索引的连接运算,如果一个关系（如,S,）有一个属性,Y,上的索引。,读入,R,的一个磁盘块，考虑块中每一个元组,t,，令,ty,是元组,t,中,y,属性的值。,使用,S,上的索引，来找到,S,中所有在,Y,属性上具有相同,ty,的那些元组所在的磁盘块，将这些元组（所在的磁盘块）读入内存与,R,中的元组,t,连接起来，作为结果输出。,重复以上步骤，直到,R,中的所有元组处理完。,60,S,元组,S,元组,R,元组,R,S,元组,S(ty),元组,R(ty),元组,R,S,元组,磁盘,B(S),B(R),1,块,1,块,缓冲区,基于索引的连接算法,物理优化,ty,ty,S,的索引,61,物理优化,操作符的实现算法,连接操作的实现算法,基于索引的连接运算,如果,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,，用于读取相关索引文件。,62,物理优化,【,例,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,上的索引是非聚集的，代价会更高。,63,物理优化,操作符的实现算法,连接操作的实现算法,基于索引的连接运算,常见的连接查询的情况是与,S,相比，,R,是很小的，,V(S,Y),是很大的。在这种情况下，,S,的大多数元组的,Y,值根本不出现在,R,中，这些元组将无需被算法检查，即不需要读入内存。但是，不论基于排序的还是基于散列的连接方法都需检查,S,的每一个元组至少一次。所以，在实际的应用中，索引选择算法仍是一种常用的方法。,64,【,例,】,分析实现“查询选修了课程号为,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.Cno=c02,(SC)S),R,物理优化,65,物理优化,物理优化,从一个逻辑查询计划产生物理查询计划时，为逻辑查询计划的每一个,操作符,选择实现算法并选择这些操作符的执行顺序，还包括许多实现细节。,被查询的关系是怎样被访问的，即获得所,存储数据的方式,以及一个关系何时或是否应当被,排序,等；,必须估计每个可能选项的执行代价，使用代价估计来评价一个查询计划。,66,基于代价的物理优化方法,查询计划的代价因素,一个查询的实际执行所需的代价包括,:,磁盘访问代价：读写记录所在磁盘数据块的代价。,存储代价：存储由查询执行计划产生的中间结果文件的代价。,计算代价：在查询执行过程中对数据缓冲区完成内存操作的代价。,内存使用代价：与执行查询所需内存缓冲区数相关的代价。,通信代价：将查询与查询结果从一个数据库站点传送到另一个站点（或发出查询的终端）的代价。,物理优化,67,基于代价的物理优化方法,查询计划的代价因素,代价用的磁盘,I/O,次数受以下因素影响：,在选择逻辑查询计划时所选取的用于实现查询的逻辑查询运算符，例如进行乘积运算还是连接运算。,中间关系的大小。,用于实现逻辑查询运算符的物理查询运算符，例如连接运算算法的选择，对给定关系是否加以排序等其他运算。,由一个物理运算符向下一个物理运算符传递参数的方式，例如，通过在磁盘上保存中间结果还是通过使用迭代算子每次传送一个参数的一个元组或一个主存缓冲区。,物理优化,68,基于代价的物理优化方法,查询计划的代价因素,在对由给定的逻辑查询计划导出可能的物理查询计划进行评价时，我们需要知道各个物理计划的代价是多少。,在不执行查询计划的情况下，我们不能准确知道其代价。,由于执行一个查询计划比查询编译器选择一个计划所做的工作要多得多，我们需要不执行查询计划而估计该计划的代价。,要准确估计不同查询计划的代价，查询优化器需要从数据库中有效地获得某些重要的参数信息，即从数据字典中获取代价估计所需的各种信息。,物理优化,69,基于代价的物理优化方法,代价估计基于的数据信息,对每个关系表文件，该表的记录总数（,T,）、记录长度、占用的块数（,B,）、占用的溢出块数（,BO,）；,对关系表文件的每个属性，该属性不同值的个数（,V,）、选择率（具有该值的记录数,/T,）、该属性最大值、最小值，该属性上是否已建索引，何种索引（,B+,树索引、散列索引、聚集索引）；,对于索引，比如,B+,树索引，该索引的层数（,L,）、不同索引值的个数、索引的选择基数,S,（有,S,个元组有某个索引值）、索引的叶结点数（,Y,）等等。,物理优化,优化器可以根据这些信息作出正确的估算，选择高效的执行计划。,70,基于代价的物理优化方法,物理查询计划的选择方法,由给定的逻辑查询计划可有,多个可能的,物理查询计划，要穷尽所有的查询计划进行代价估算往往是不可行的，会造成查询优化本身付出的代价大于获得的益处。,常常先使用,启发式规则,，选取若干较优的候选方案，减少代价估算的工作量；然后分别,计算,这些候选方案的执行,代价,，较快地选出最终的优化方案。,物理优化,71,基于代价的物理优化方法,物理查询计划的选择方法,启发式选择,某些操作（如选择和连接操作）可以有多种执行这个操作的算法，可以根据一些启发式规则来选择代价较小的实现操作的算法。,物理优化,72,基于代价的物理优化方法,物理查询计划的选择方法,常用的启发式规则,（,1,）,选择操作,若关系,R,的元组数较小，比如,T(R)M,，可采用简单的全表扫描方法，即使选择列上有索引。,如果逻辑计划需要进行,a=v(R),操作，且关系,R,在属性,a,上有索引，则使用索引扫描法。,对于更一般的选择操作，如选择涉及,a=v,那样的一个条件以及其他条件，可以先进行一次索引扫描，然后对选中的元组作进一步选择（也称过滤）。,物理优化,73,基于代价的物理优化方法,物理查询计划的选择方法,常用的启发式规则,（,2,）,连接操作,如果两个关系都已经按照连接属性,排序,，则选用排序,-,归并算法。,如果一个关系在连接属性上有,索引,，则选用索引连接方法，其中该关系在算法内层循环中（即算法中的关系,S,，可通过连接运算的交换律来满足）。,如果前两个规则不适用，而其中一个,关系较小,，则可以选用散列连接方法。,最后可以选用嵌套循环方法，并选择其中较小的关系，即占用的磁盘块数较小的关系作为算法的外循环中的关系（即算法中的关系,S,）。,物理优化,74,基于代价的物理优化方法,物理查询计划的选择方法,基于代价估算的选择,查询优化器可通过估计每一个可能的物理查询计划的代价，比较并选择估计代价最小的查询计划。,以选择操作为例说明在逻辑查询计划到物理查询计划的转换中如何进行代价估计，并根据查询计划代价的估算来选择物理查询计划。,物理优化,75,基于代价的物理优化方法,物理查询计划的选择方法,基于代价估算的选择,假设操作是,C(R),，其中条件,C,是一个或多个项的,AND,。,（,1,）全表扫描进行过滤的代价,将关系逐个磁盘块读入内存，并检查每个元组是否是满足条件的元组。,如果,R,被聚集存储，则查询的代价,cost=B(R),。,如果,R,没被聚集存储，则查询的代价,cost=T(R),。,物理优化,76,基于代价的物理优化方法,物理查询计划的选择方法,基于代价估算的选择,假设操作是,C(R),，其中条件,C,是一个或多个项的,AND,。,（,2,）索引扫描进行过滤的代价,从条件,C,中选出一个等值选项，如,a=10,的形式，若存在关于该属性的索引，利用索引扫描来找出匹配元组，然后对这些元组进行过滤看它们是否满足全部条件,C,。,如果索引是聚集的，则查询的代价,cost=B(R)/V(R,a),。,如果索引不是聚集的，则查询的代价,cost=T(R)/V(R,a),。,从条件,C,中选出一个不等值选项，如,b20,，若存在关于属性,b,的索引，利用索引扫描来找出匹配元组，然后对这些元组进行过滤看它们是否满足全部条件,C,。,如果索引是聚集的，则查询的代价,cost=B(R)/2,。,如果索引不是聚集的，则查询的代价,cost=T(R)/2,。,物理优化,77,物理优化,【,例,7-11】,关系,R(a,b,c),上的一个选择,a=1 AND b=2 AND c5,(R),。同时令,T(R)=5000,，,B(R)=200,，,V(R,a)=100,，,V(R,b)=500,。另外，假设,R,是聚集的，并且所有,a,、,b,以及,c,上都有索引，只有,c,上的索引是聚集的。,表扫描后进行过滤，因为,R,是聚集的，其代价是,B(R),，即,200,次,磁盘,I/O,。,使用,a,的索引进行索引扫描，找出,a=1,的元组，再从中过滤出,b=2,和,c5,的元组