《第九章 关系查询处理和查询优化课件.ppt》由会员分享，可在线阅读，更多相关《第九章 关系查询处理和查询优化课件.ppt（48页珍藏版）》请在三一办公上搜索。
1、An Introduction to Database System,上海第二工业大学 计算机与信息学院,数据库系统概论An Introduction to Database System第九章 关系查询处理和查询优化,An Introduction to Database System,第九章 关系查询处理和查询优化,9.1 关系数据库的查询处理9.2 关系数据库系统的查询优化9.3 代数优化9.4 物理优化,An Introduction to Database System,9.1 关系数据库的查询处理,9.1.1 查询处理的步骤查询分析：对查询语句进行语法和词法分析查询检查：检查语义：
2、语句中使用的对象的存在性和有效性用户权限和和完整性检查检查通过后，把查询语句转换成等价的关系代数表达式（查询树即语法分析树）,An Introduction to Database System,语法分析树：,An Introduction to Database System,查询优化：选择一个高效的查询处理策略，方法有代数优化、物理优化，选择的依据有基于规则、基于代价或基于语义执行查询：依据优化器得到的策略生成查询计划，由代码生成器生成可执行代码。,An Introduction to Database System,9.1.2 实现查询操作的算法示例,1.选择操作的常用算法全表扫描，选出
3、符合条件的元组使用索引可快速获取符合选择条件的元组指针，如sage=20或sage20。组合条件如：sage20 and sdept=CS方法1：分别选出符合sage20条件的元组指针和符合sdept=CS条件的元组指针，然后求它们的交集方法2：先选出符合sage20条件的元组指针，然后对选出的元组判断是否符合sdept=CS条件。第一种方法在sage和sdept上均有索引的情况下比较有效，第二种方法应该优先选出选择条件中有索引的元组。,An Introduction to Database System,2.连接操作的常用算法（假定为等值连接）：Select a.sno,a.sname,o,
4、b.grade from student a,sc b where a.sno=b.sno连接的总体思路：扫描student，对每一元组的sno，扫描grade的sno，把相同值的元组和student对应元组进行连接后输出。,An Introduction to Database System,循环嵌套方法：嵌套扫描两个表，总循环次数为两个元组个数的乘积。排序-合并方法：根据两个表的sno进行排序，两个循环均不必进行全表扫描。效率大大提高。索引连接方法：对sc关于sno建立索引，内层循环中由于sc建立的索引，所以不必全表扫描。,An Introduction to Database Syste
5、m,Hash join方法：适用大表和小表的连接1 依据Hash函数把小表数据放入内存（可保留少量数据在临时表空间中）（小表数据的一次扫描） 2 每读取大表的一条记录（大表数据的一次扫描） ，就和小表中内存中的数据进行比较（有了hash函数，比较就不需要扫描小表），如果符合，则立即输出数据。而如果大表的数据与小表中临时表空间的数据相符合，先不输出，而等大表的所有数据都读取完毕，才一起输出（减少读取硬盘的次数）。 3.Hash Join方法只需要对两个表进行一次扫描，并且极大地降低了读取硬盘的次数。,An Introduction to Database System,9.2.1 查询优化概述,
6、查询效率是衡量RDBMS重要性能指标。RDBMS通过查询优化提升查询效率。关系的结构化查询语言SQL高级别的语义（只需指出做什么而不必给出怎么做），使RDBMS进行查询优化成为可能。RDBMS的查询优化，使用户不必考虑如何最好地表达查询以获得较好的效率。,An Introduction to Database System,系统进行优化较用户优化的优势：,优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划而不必重写程序。优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。优
7、化器中包括了很多复杂的优化技术。,An Introduction to Database System,查询优化目标,查询优化的总目标 选择有效策略，求得给定关系代数表达式的值（关系），使得查询代价最小。查询执行策略的代价构成：总代价=I/O代价 + CPU代价 + 内存代价 + 通信代价,An Introduction to Database System,9.2.2 查询优化的必要性,例：求选修了课程2的学生姓名SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno=2; 以下考察不同的执行策略对数据读写
8、上需要的时间,An Introduction to Database System,查询优化的必要性（续）,假设：1：Student:1000条，SC:10000条， 选修2号课程:50条2：一个内存块可存放元组:10个Student，或100个SC，内存容量可以存放: 5块Student元组、 1块SC元组和若干块连接结果元组3：读写速度：20块/秒4：连接方法：基于数据块的嵌套循环法,An Introduction to Database System,执行策略1:笛卡尔积、选择、投影,Q1sname(Student.Sno=SC.SnoSC.Cno=2 (StudentSC) Stude
9、ntSC： 读取总块数= 读Student表块数 + 读SC表遍数 *每遍块数=1000/10+(1000/(105) (10000/100) =100+20100=2100 读数据时间=2100/20=105秒,每次可读student的10X5个元组，然后以块为单位读入全部SC，产生笛卡尔积,An Introduction to Database System,中间结果大小 = 1000*10000 = 107 写中间结果时间 = 10000000/10/20 = 50000秒（假设每个内存块可存放10个元组的中间结果）读数据时间 = 50000秒总时间 =1055000050000秒 =
10、100105秒 = 27.8小时,An Introduction to Database System,执行策略2：自然连接、选择、投影,2. 2 name(SC.Cno= 2 (Student SC)读取总块数= 2100块读数据时间=2100/20=105秒中间结果大小=10000 （减少1000倍）写中间结果时间=10000/10/20=50秒读数据时间=50秒时间1055050秒205秒=3.4分,An Introduction to Database System,执行策略3：选择、自然连接、投影,3. 3 Sname(Student SC.Cno= 2 (SC)读SC表总块数= 1
11、0000/100=100块读数据时间=100/20=5秒中间结果大小=50条 不必写入外存读Student表总块数= 1000/10=100块读数据时间=100/20=5秒 总时间55秒10秒,An Introduction to Database System,9.3 代数优化,关系代数表达式：关系代数运算符经过有限次复合后得到的式子，其值仍为关系。（P60）关系代数表达式等价：即关系代数表达式E1和E2中代入相同的关系，其结果相同，记为：E1E2。,An Introduction to Database System,9.3.1 关系代数表达式等价变换规则,设E1、E2等是关系代数表达式，
12、F是条件表达式l. 连接、笛卡尔积交换律E1 E2 E2E1E1 E2E2 E1 E1 F E2E2 F E1,An Introduction to Database System,关系代数等价变换规则（续）,2. 连接、笛卡尔积的结合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F1 F2 F1 F2,An Introduction to Database System,关系代数等价变换规则（续）,3. 投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E)假设：1
13、)E是关系代数表达式2)Ai(i=1，2，n), Bj(j=l，2，m)是属性名3)A1, A2, , An构成Bl，B2，Bm的子集,An Introduction to Database System,关系代数等价变换规则（续）,4. 选择的串接定律 F1 （ F2（E） F1 F2(E)选择的串接律说明选择条件可以合并这样一次就可检查全部条件。,An Introduction to Database System,关系代数等价变换规则（续）,5. 选择与投影的交换律(1)假设: 选择条件F只涉及属性A1，An F (A1,A2, ,An(E) A1,A2, ,An(F(E)(2)假设:
14、F中有不属于A1, ,An的属性B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An(F (A1,A2,An,B1,B2, ,Bm(E),An Introduction to Database System,关系代数等价变换规则（续）,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),An Introduction to Database System,关
15、系代数等价变换规则（续）,(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),An Introduction to Database System,关系代数等价变换规则（续）,9. 投影与笛卡尔积的交换假设：E1和E2是两个关系表达式， A1，An是E1的属性， B1，Bm是E2的属性 A1,A2, ,An,B1,B2
16、, ,Bm （E1E2) A1,A2, ,An（E1) B1,B2, ,Bm(E2),An Introduction to Database System,关系代数等价变换规则（续）,l0. 投影与并的交换假设：E1和E2 有相同的属性名： A1,A2, ,An(E1E2) A1,A2, ,An(E1) A1,A2, ,An(E2),An Introduction to Database System,小结,1-2: 连接、笛卡尔积的交换律、结合律3： 合并或分解投影运算4： 合并或分解选择运算5-8： 选择运算与其他运算交换5，9，10： 投影运算与其他运算交换,An Introductio
17、n to Database System,9.3.2 关系代数的启发式的优化算法,选择运算应尽可能先做：选择运算减小了中间关系中元组数量在执行连接操作前对关系适当进行预处理按连接属性排序在连接属性上建立索引投影运算和选择运算同时做：在扫描关系时同时进行投影运算和选择运算，避免重复扫描关系将投影运算与其前面或后面的双目运算(关系代数的运算符除投影和选择外均为双目运算符)一起做。,An Introduction to Database System,某些选择运算同它前面要执行的笛卡尔积结合起来成为连接运算，连接运算比产生笛卡尔后进行选择运算要快的多提取公共子表达式：可把满足公共子表达式的关系（不太
18、大的情况下）读入内存以提高查询效率。,An Introduction to Database System,遵循启发式规则，运用等价变换规则优化关系表达式的算法：,算法：关系代数表达式的优化算法输入：依据一个关系表达式的查询树。算法输出：优化的查询树方法：（1）分解选择运算利用规则4把形如F1 F2 Fn (E)变换为 F1 (F2( (Fn(E) ) ，为（2）做准备。,An Introduction to Database System,关系代数表达式的优化算法 (续),（2）对每一个选择运算，利用规则48尽可能把它移到树的叶端。（选择优先）（3）对每一个投影运算，利用规则3，5，l0，1
19、1中的一般形式尽可能把它移向树的叶端。（投影优先）选择和投影运算均能减少中间结果，具体哪个更优先，取决于具体关系中行和列哪个数据量更大。,An Introduction to Database System,（4）利用等价变化3-5，合并串接的选择运算成一个选择运算和合并串接的投影运算成一个投影运算，以便能在一次扫描中完成运算，如：A3 (A5(E) ) A3 (E) A1(A1,A2(E) A1(E),An Introduction to Database System,关系代数表达式的优化算法 (续),（5）对内结点（除叶结点外的所有结点）分组：每一双目运算(， ，-)和它所有的直接祖先为
20、一组(这些直接祖先是，运算)，如下例第1，3组；如果其后代直到叶子全是单目运算，则也将它们并入该组。如下例第1组。当双目运算是笛卡尔积()，而且其后的选择不能与它结合为等值连接时，可把这些单目运算单独分为一组。 如下例中注释部分。每组结点对应计算程序中的一步，各步程序的顺序可任意，但任何一组的计算必须在它的父代组之前计算。如下例中第1和第2组结果必须在第3组计算之间产生。,An Introduction to Database System,分组实例：查询男同学选课学分大于4分的姓名和课程名,An Introduction to Database System,9.4 物理优化,物理优化指存取
21、路径和底层操作算法的选择，主要研究根据查询的不同特点，选择操作和连接操作中对9.1.2中各种算法的选择。有基于启发式、基于代价估算和两者结合的优化方法。,An Introduction to Database System,基于启发式的优化：,一.选择操作的优化规则对于小关系，不论是否有索引，均使用全表扫描。下面规则则对大关系而言。包含主码等值的查询，一定使用主码索引。包含非主属性等值查询，若有关于该非主属性的索引，则估算查询结果的元组数量，与整个元组数量比例大的话，使用全表扫描，否则使用索引扫描。,An Introduction to Database System,对and连接的条件，若有
22、相应的组合索引，则使用索引扫描；若部分有索引，则先使用索引扫描，选出符合部分条件的元组，在其中再选出符合其他条件的元组。对or连接的条件，一般使用全表扫描。例如关于A,B有索引，（not A） or （not B）可优化为not (A and B)，事实上一些DBMS也会作此优化(前者若使用索引，必须两次全表扫描，而后者一次全表，一次在前一次结果上再扫描)。,An Introduction to Database System,二.连接操作的优化规则,连接属性均排序，使用排序-合并方法仅一个表的连接属性有索引，使用索引连接方法。上述条件均不满足，若一个表较小，则可以选用Hash join方法嵌
23、套循环方法不需要任何前提条件，但较小的表的扫描应作为外循环，可减少读块的次数。（极端情况下，小表只要读一次）,An Introduction to Database System,基于代价估算的优化,根据数据库的状态计算各种操作算法的执行代价，选择代价最小的算法。执行代价的计算方法：在数据字典中存放优化器所需要的统计信息，如表的元组数，元组长度、列值个数、最大、最小值、列上是否有索引等。根据以上的统计信息，计算各种算法的代价估值。,An Introduction to Database System,优化的一般步骤 (续),（1）把查询转换成某种内部表示例：求选修了课程2的学生姓名SELECT
24、 Student.SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno=2;,An Introduction to Database System,（1）把查询转换成某种内部表示,语法树,An Introduction to Database System,关系代数语法树,An Introduction to Database System,（2）代数优化,利用优化算法把语法树转换成标准（优化）形式,An Introduction to Database System,（3）物理优化：选择低层的存取路径,- 优化器查找数据字典获得当前数
25、据库状态信息选择字段上是否有索引连接的两个表是否有序连接字段上是否有索引然后根据一定的优化规则选择存取路径 如本例中若SC表上建有Cno的索引，则应该利用这个索引，而不必顺序扫描SC表。,An Introduction to Database System,（4）生成查询计划，选择代价最小的,在作连接运算时，若两个表(设为R1，R2)均无序，连接属性上也没有索引，则可以有下面几种查询计划： 对两个表作排序预处理 对R1在连接属性上建索引 对R2在连接属性上建索引 在R1，R2的连接属性上均建索引对不同的查询计划计算代价，选择代价最小的一个。在计算代价时主要考虑磁盘读写的I/O数，内存CPU处理
26、时间在粗略计算时可不考虑。,同结果查询语句效率存在较大差异的实例(在对datadate索引下，后者执行效率高很多),select * from datedata a where datadate=all (select datadate from datedata b where a.stockid=b.stockid and datadate2014-1-1)select * from datedata a where datadate= (select max(datadate) from datedata b where a.stockid=b.stockid and datadate2014-1-1),An Introduction to Database System,
