中国石油大学华东数据库课件.ppt

中国石油大学华东数据库课件.ppt

《中国石油大学华东数据库课件.ppt》由会员分享，可在线阅读，更多相关《中国石油大学华东数据库课件.ppt（92页珍藏版）》请在冰点文库上搜索。

中国石油大学计算机科学系,数据库原理第四章关系系统及其查询优化,第四章关系系统及其查询优化,4.1关系系统4.2关系系统的查询处理4.3关系系统的查询优化4.4小结,关系系统与关系模型,关系数据结构域及域上定义的关系关系操作并、交、差、广义笛卡尔积、选择、投影、连接、除等关系完整性实体完整性、参照完整性、用户自己定义的完整性,关系系统,能够在一定程度上支持关系模型的数据库管理系统是关系系统。

由于关系模型中并非每一部分都是同等重要的所以并不苛求一个实际的关系系统必须完全支持关系模型。

关系系统的定义,一个数据库管理系统可定义为关系系统，当且仅当它至少支持：

1.关系数据库（即关系数据结构）系统中只有表这种结构2.支持选择、投影和（自然）连接运算对这些运算不要求用户定义任何物理存取路径对关系系统的最低要求,关系系统的定义,不支持关系数据结构的系统显然不能称为关系系统仅支持关系数据结构，但没有选择、投影和连接运算功能的系统仍不能算作关系系统。

原因：

不能提高用户的生产率支持选择、投影和连接运算，但要求定义物理存取路径，这种系统也不能算作真正的关系系统原因：

就降低或丧失了数据的物理独立性选择、投影、连接运算是最有用的运算,关系系统的分类,分类依据：

支持关系模型的程度分类表式系统：

支持关系数据结构（即表）（最小）关系系统支持：

关系数据结构选择、投影、连接关系操作关系完备的系统支持：

关系数据结构所有的关系代数操作全关系系统支持：

关系模型的所有特征特别是:

数据结构中域的概念,关系系统的分类（续）,第四章关系系统及其查询优化,4.1关系系统4.2关系系统的查询处理4.3关系系统的查询优化4.4小结,4.2.1查询处理步骤,RDBMS查询处理分为四个阶段：

1.查询分析2.查询检查3.查询优化4.查询执行,查询处理步骤（续）,1.查询分析,对查询语句进行扫描、词法分析和语法分析从查询语句中识别出语言符号进行语法检查和语法分析,2.查询检查,根据数据字典对合法的查询语句进行语义检查根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查检查通过后把SQL查询语句转换成等价的关系代数表达式RDBMS一般都用查询树（语法分析树）来表示扩展的关系代数表达式把数据库对象的外部名称转换为内部表示,3.查询优化,查询优化：

选择一个高效执行的查询处理策略查询优化分类：

代数优化：

指关系代数表达式的优化物理优化：

指存取路径和底层操作算法的选择查询优化方法选择的依据：

基于规则（rulebased）基于代价（costbased）基于语义（semanticbased）,4.查询执行,依据优化器得到的执行策略生成查询计划代码生成器（codegenerator）生成执行查询计划的代码,4.2.2实现查询操作的算法示例,一、选择操作的实现二、连接操作的实现,一、选择操作的实现,例1Select*fromstudentwhere；考虑的几种情况：

C1：

无条件；C2：

Sno95001；C3：

Sage20；C4：

SdeptCSANDSage20；,选择操作的实现（续）,选择操作典型实现方法：

1.简单的全表扫描方法对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出适合小表，不适合大表2.索引（或散列）扫描方法适合选择条件中的属性上有索引（例如B+树索引或Hash索引）通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组,选择操作的实现（续）,例1-C2以C2为例，Sno95001，并且Sno上有索引（或Sno是散列码）使用索引（或散列）得到Sno为95001元组的指针通过元组指针在student表中检索到该学生例1-C3以C3为例，Sage20，并且Sage上有B+树索引使用B+树索引找到Sage20的索引项，以此为入口点在B+树的顺序集上得到Sage20的所有元组指针通过这些元组指针到student表中检索到所有年龄大于20的学生。

选择操作的实现（续）,例1-C4以C4为例，SdeptCSANDSage20，如果Sdept和Sage上都有索引：

算法一：

分别用上面两种方法分别找到SdeptCS的一组元组指针和Sage20的另一组元组指针求这2组指针的交集到student表中检索得到计算机系年龄大于20的学生算法二：

找到SdeptCS的一组元组指针通过这些元组指针到student表中检索对得到的元组检查另一些选择条件（如Sage20）是否满足把满足条件的元组作为结果输出。

二、连接操作的实现,连接操作是查询处理中最耗时的操作之一本节只讨论等值连接（或自然连接）最常用的实现算法例2SELECT*FROMStudent，SCWHEREStudent.Sno=SC.Sno；,连接操作的实现（续）,1.嵌套循环方法（nestedloop）2.排序-合并方法（sort-mergejoin或mergejoin）3.索引连接（indexjoin）方法4.HashJoin方法,连接操作的实现（续）,1.嵌套循环方法（nestedloop）对外层循环（Student）的每一个元组（s），检索内层循环（SC）中的每一个元组（sc）检查这两个元组在连接属性（sno）上是否相等如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止,连接操作的实现（续）,2.排序-合并方法（sort-mergejoin或mergejoin）适合连接的诸表已经排好序的情况排序合并连接方法的步骤：

如果连接的表没有排好序，先对Student表和SC表按连接属性Sno排序取Student表中第一个Sno，依次扫描SC表中具有相同Sno的元组，把它们连接起来,连接操作的实现（续）,排序合并连接方法的步骤（续）：

当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来重复上述步骤直到Student表扫描完,连接操作的实现（续）,Student表和SC表都只要扫描一遍如果2个表原来无序，执行时间要加上对两个表的排序时间对于2个大表，先排序后使用sort-mergejoin方法执行连接，总的时间一般仍会大大减少,连接操作的实现（续）,3.索引连接（indexjoin）方法步骤：

在SC表上建立属性Sno的索引，如果原来没有该索引对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组把这些SC元组和Student元组连接起来循环执行，直到Student表中的元组处理完为止,连接操作的实现（续）,4.HashJoin方法把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个hash文件中步骤：

划分阶段（partitioningphase）：

对包含较少元组的表（比如R）进行一遍处理把它的元组按hash函数分散到hash表的桶中试探阶段（probingphase）：

也称为连接阶段（joinphase）对另一个表（S）进行一遍处理把S的元组散列到适当的hash桶中把元组与桶中所有来自R并与之相匹配的元组连接起来,连接操作的实现（续）,上面hashjoin算法前提：

假设两个表中较小的表在第一阶段后可以完全放入内存的hash桶中以上的算法思想可以推广到更加一般的多个表的连接算法上,第四章关系系统及其查询优化,4.1关系系统4.2关系系统的查询处理4.3关系系统的查询优化4.4小结,4.3关系系统的查询优化,4.3.1查询优化概述4.3.2查询优化的必要性4.3.3关系代数等价变换规则4.3.4查询树的启发式优化4.3.5物理优化,4.3.1查询优化概述,查询优化的必要性查询优化极大地影响RDBMS的性能。

查询优化的可能性关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。

由DBMS进行查询优化的好处,用户不必考虑如何最好地表达查询以获得较好的效率系统可以比用户程序的优化做得更好

（1）优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息,由DBMS进行查询优化的好处,

（2）如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。

在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。

（3）优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。

（4）优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。

系统的自动优化相当于使得所有人都拥有这些优化技术,代价模型,RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案集中式数据库单用户系统总代价=I/O代价+CPU代价多用户系统总代价=I/O代价+CPU代价+内存代价分布式数据库总代价=I/O代价+CPU代价+内存代价+通信代价,查询优化目标,查询优化的总目标选择有效策略求得给定关系表达式的值使得查询代价最小（实际上是较小）,实际系统的查询优化步骤,1.将查询转换成某种内部表示，通常是语法树2.根据一定的等价变换规则把语法树转换成标准（优化）形式3.选择低层的操作算法对于语法树中的每一个操作计算各种执行算法的执行代价选择代价小的执行算法4.生成查询计划（查询执行方案）查询计划是由一系列内部操作组成的。

4.3.2查询优化的必要性,例：

求选修了2号课程的学生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=2;,查询优化的必要性（续）,假设1：

外存：

Student:

1000条,SC:

10000条,选修2号课程:

50条假设2：

一个内存块装元组:

10个Student,或100个SC,内存中一次可以存放:

5块Student元组,1块SC元组和若干块连接结果元组假设3：

读写速度：

20块/秒假设4：

连接方法：

基于数据块的嵌套循环法,执行策略1,1.Q1name（Student.Sno=SC.SnoSC.Cno=2（StudentSC）StudentSC读取总块数=读Student表块数+读SC表遍数*每遍块数=1000/10+（1000/（105）（10000/100）=100+20100=2100块读数据时间=2100/20=105秒,不同的执行策略,考虑I/O时间,中间结果大小=1000*10000=107（1千万条元组）写中间结果时间=10000000/10/20=50000秒读数据时间=50000秒总时间=1055000050000秒=100105秒=27.8小时,查询优化的必要性（续）,2.2name（SC.Cno=2（StudentSC）读取总块数=2100块读数据时间=2100/20=105秒中间结果大小=10000（减少1000倍）写中间结果时间=10000/10/20=50秒读数据时间=50秒总时间1055050秒205秒=3.4分,查询优化的必要性（续）,3.3Sname（StudentSC.Cno=2（SC）读SC表总块数=10000/100=100块读数据时间=100/20=5秒中间结果大小=50条不必写入外存读Student表总块数=1000/10=100块读数据时间=100/20=5秒总时间55秒10秒,查询优化的必要性（续）,4.3name（StudentSC.Cno=2（SC）假设SC表在Cno上有索引，Student表在Sno上有索引读SC表索引=23块读SC表总块数=50/1001块读数据时间中间结果大小=50条不必写入外存,查询优化的必要性（续）,读Student表索引=读Student表总块数=50/10=5块读数据时间总时间10秒,查询优化的必要性（续）,把代数表达式Q1变换为Q2、Q3，即有选择和连接操作时，先做选择操作，这样参加连接的元组就可以大大减少，这是代数优化Q3中SC表的选择操作算法有全表扫描和索引扫描2种方法，经过初步估算，索引扫描方法较优对于Student和SC表的连接，利用Student表上的索引，采用indexjoin代价也较小，这就是物理优化,4.3.3关系代数等价变换规则,代数优化策略：

通过对关系代数表达式的等价变换来提高查询效率关系代数表达式等价指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的上面的优化策略大部分都涉及到代数表达式的变换,常用的等价变换规则,设E1、E2等是关系代数表达式，F是条件表达式l.连接、笛卡尔积交换律E1E2E2E1E1E2E2E1E1FE2E2FE1,关系代数等价变换规则（续）,2.连接、笛卡尔积的结合律（E1E2）E3E1（E2E3）（E1E2）E3E1（E2E3）（E1E2）E3E1（E2E3）F1F2F1F2,关系代数等价变换规则（续）,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）F1F2（E）选择的串接律说明选择条件可以合并这样一次就可检查全部条件。

关系代数等价变换规则（续）,5.选择与投影的交换律

（1）假设:

选择条件F只涉及属性A1，AnF（A1,A2,An（E）A1,A2,An（F（E）

（2）假设:

F中有不属于A1,An的属性B1,BmA1,A2,An（F（E）A1,A2,An（F（A1,A2,An,B1,B2,Bm（E）,关系代数等价变换规则（续）,6.选择与笛卡尔积的交换律

（1）假设：

F中涉及的属性都是E1中的属性F（E1E2）F（E1）E2

（2）假设：

F=F1F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性则由上面的等价变换规则1，4，6可推出：

F（E1E2）F1（E1）F2（E2）,关系代数等价变换规则（续）,（3）假设：

F=F1F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性F（E1E2）F2（F1（E1）E2）它使部分选择在笛卡尔积前先做,关系代数等价变换规则（续）,7.选择与并的分配律假设：

E=E1E2，E1，E2有相同的属性名F（E1E2）F（E1）F（E2）8.选择与差运算的分配律假设：

E1与E2有相同的属性名F（E1-E2）F（E1）-F（E2）,关系代数等价变换规则（续）,9.选择对自然连接的分配律F只涉及E1与E2的公共属性F（E1E2）F（E1）F（E2）,关系代数等价变换规则（续）,10.投影与笛卡尔积的分配律假设：

E1和E2是两个关系表达式，A1，An是E1的属性，B1，Bm是E2的属性A1,A2,An,B1,B2,Bm（E1E2）A1,A2,An（E1）B1,B2,Bm（E2）,关系代数等价变换规则（续）,11.投影与并的分配律假设：

E1和E2有相同的属性名A1,A2,An（E1E2）A1,A2,An（E1）A1,A2,An（E2）,小结,1-2:

连接、笛卡尔积的交换律、结合律3：

合并或分解投影运算4：

合并或分解选择运算5-9：

选择运算与其他运算交换5，10，11：

投影运算与其他运算交换,4.3.4查询树的启发式优化,典型的启发式规则：

1.选择运算应尽可能先做。

在优化策略中这是最重要、最基本的一条2.把投影运算和选择运算同时进行如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系,查询树的启发式优化（续）,3.把投影同其前或其后的双目运算结合起来4.把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算5.找出公共子表达式如果这种重复出现的子表达式的结果不是很大的关系并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的当查询的是视图时，定义视图的表达式就是公共子表达式的情况,查询树的启发式优化（续）,遵循这些启发式规则，应用上节的等价变换公式来优化关系表达式的算法。

算法：

关系表达式的优化输入：

一个关系表达式的查询树输出：

优化的查询树方法：

（1）分解选择运算利用规则4把形如F1F2Fn（E）变换为F1（F2（Fn（E）,查询树的启发式优化（续）,

（2）通过交换选择运算，将其尽可能移到叶端对每一个选择，利用规则49尽可能把它移到树的叶端。

（3）通过交换投影运算，将其尽可能移到叶端对每一个投影利用规则3，5，10，11中的一般形式尽可能把它移向树的叶端。

注意：

规则3使一些投影消失规则5把一个投影分裂为两个，其中一个有可能被移向树的叶端,查询树的启发式优化（续）,（4）合并串接的选择和投影，以便能同时执行或在一次扫描中完成利用规则35把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。

使多个选择或投影能同时执行，或在一次扫描中全部完成尽管这种变换似乎违背“投影尽可能早做”的原则，但这样做效率更高。

查询树的启发式优化（续）,（5）对内结点分组把上述得到的语法树的内节点分组。

每一双目运算（，-）和它所有的直接祖先为一组（这些直接祖先是，运算）。

如果其后代直到叶子全是单目运算，则也将它们并入该组。

但当双目运算是笛卡尔积（），而且其后的选择不能与它结合为等值连接时除外。

把这些单目运算单独分为一组。

查询树的启发式优化（续）,代数优化示例：

求选修了课程2的学生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=2;,查询树的启发式优化（续）,

（1）把SQL语句转换成查询树，如下图所示,结果,project（Sname）,select（SC.Cno=2）,join（Student.Sno=SC.Sno）,Student,SC,关系代数语法树,Sname,SC.Cno=2,Student.Sno=SC.Sno,Student,SC,查询树的启发式优化（续）,

（2）代数优化：

利用优化算法把语法树转换成标准（优化）形式,4.3.5物理优化,代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径对于一个查询语句有许多存取方案，它们的执行效率不同，仅仅进行代数优化是不够的物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划,物理优化（续）,选择的方法：

基于规则的启发式优化基于代价估算的优化两者结合的优化方法,基于启发式规则的存取路径选择优化,一、选择操作的启发式规则:

1.对于小关系，使用全表顺序扫描，即使选择列上有索引对于大关系，启发式规则有：

2.对于选择条件是主码值的查询查询结果最多是一个元组，可以选择主码索引一般的RDBMS会自动建立主码索引。

基于启发式规则的存取路径选择优化（续）,3.对于选择条件是非主属性值的查询，并且选择列上有索引要估算查询结果的元组数目如果比例较小（10%）可以使用索引扫描方法否则还是使用全表顺序扫描,基于启发式规则的存取路径选择优化（续）,4.对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引要估算查询结果的元组数目如果比例较小（10%）可以使用索引扫描方法否则还是使用全表顺序扫描,基于启发式规则的存取路径选择优化（续）,5.对于用AND连接的合取选择条件如果有涉及这些属性的组合索引优先采用组合索引扫描方法如果某些属性上有一般的索引则可以用例1-C4中介绍的索引扫描方法否则使用全表顺序扫描6.对于用OR连接的析取选择条件，一般使用全表顺序扫描,基于启发式规则的存取路径选择优化（续）,二、连接操作的启发式规则:

1.如果2个表都已经按照连接属性排序选用排序-合并方法2.如果一个表在连接属性上有索引选用索引连接方法3.如果上面2个规则都不适用，其中一个表较小选用Hashjoin方法,基于启发式规则的存取路径选择优化（续）,4.可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数（b）较少的表，作为外表（外循环的表）。

理由：

设连接表R与S分别占用的块数为Br与Bs连接操作使用的内存缓冲区块数为K分配K-1块给外表如果R为外表，则嵌套循环法存取的块数为Br+BrBs/（K-1）显然应该选块数小的表作为外表,基于代价的优化,启发式规则优化是定性的选择，适合解释执行的系统解释执行的系统，优化开销包含在查询总开销之中编译执行的系统中查询优化和查询执行是分开的可以采用精细复杂一些的基于代价的优化方法,基于代价的优化（续）,一、统计信息基于代价的优化方法要计算各种操作算法的执行代价，与数据库的状态密切相关数据字典中存储了优化器需要的统计信息：

1.对每个基本表该表的元组总数（N）元组长度（l）占用的块数（B）占用的溢出块数（BO）,基于代价的优化（续）,2.对基表的每个列该列不同值的个数（m）选择率（f）如果不同值的分布是均匀的，f1/m如果不同值的分布不均匀，则每个值的选择率具有该值的元组数/N该列最大值该列最小值该列上是否已经建立了索引索引类型（B+树索引、Hash索引、聚集索引）,基于代价的优化（续）,3.对索引（如B+树索引）索引的层数（L）不同索引值的个数索引的选择基数S（有S个元组具有某个索引值）索引的叶结点数（Y）,基于代价的优化（续）,二、代价估算示例1.全表扫描算法的代价估算公式如果基本表大小为B块，全表扫描算法的代价costB如果选择条件是码值，那么平均搜索代价costB/2,基于代价的优化（续）,2.索引扫描算法的代价估算公式如果选择条件是码值如例1-C2，则采用该表的主索引若为B+树，层数为L，需要存取B+树中从根结点到叶结点L块，再加上基本表中该元组所在的那一块，所以cost=L+1如果选择条件涉及非码属性如例1-C3，若为B+树索引，选择条件是相等比较，S是索引的选择基数（有S个元组满足条件）最坏的情况下，满足条件的元组可能会保存在不同的块上，此时，cost=L+S,基于代价的优化（续）,如果比较条件是，操作假设有一半的元组满足条件就要存取一半的叶结点通过索引访问一半的表存储块cost=L+Y/2+B/2如果可以获得更准确的选择基数，可以进一步修正Y/2与B/2,基于代价的优化（续）,3.嵌套循环连接算法的代价估算公式前面已经讨论过了嵌套循环连接算法的代价costBr+BrBs/（K-1）如果需要把连接结果写回磁盘，costBr+BrBs/（K-1）+（Frs*Nr*Ns）/Mrs其中Frs为连接选择性（joinselectivity），表示连接结果元组数的比例Mrs是存放连接结果的块因子，表示每块中可以存放的结果元组数目,基于代价的优化（续）,4.排序-合并连接算法的代价估算公式如果连接表已经按照连接属性排好序，则costBr+Bs+（Frs*Nr*Ns）/Mrs。

如果必须对文件排序需要在代价函数中加上排序的代价对于包含B个块的文件排序的代价大约是（2*B）+（2*B*log2B）,第四章关系系统及其查询优化,4.1关系系统4.2关系系统的查询处理4.3关系系统的查询优化4.4小结,4.4小结,关系系统关系系统的定义一个数据库管理系统可定义为关系系统，当且仅当它至少支持：

1关系数据库（即关系数据结构）2支持选择、投影和（自然）连接运算，且不要求用户定义任何物理存取路径,小结（续）,关系系统的分类表式系统（最小）关系系统关系完备系统全关系系统,小结（续）,查询处理是RDBMS的核心，查询优化技术是查询处理的关键技术关系系统的查询优化代数优化：

关系代数表达式的优化关系代数等价变换规则关系代数表达式的优化算法物理优化：

存取路径和低层操作算法的选择,小结（续）,比较复杂的查询，尤其是涉及连接和嵌套的查询不要把优化的任务全部放在RDBMS上应该找出RDBMS的优化规律，以写出适合RDBMS自动优化的SQL语句对于RDBMS不