《数据库原理课件--09_关系查询处理和查询优化》由会员分享，可在线阅读，更多相关《数据库原理课件--09_关系查询处理和查询优化（62页珍藏版）》请在金锄头文库上搜索。
1、1,数据库系统概论 An Introduction to Database System第九章 关系查询处理和查询优化,2,第九章 关系查询处理和查询优化,9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 代数优化 9.4 物理优化 9.5 小结,3,9.1 关系数据库系统的查询处理,9.1.1 查询处理步骤 9.1.2 实现查询操作的算法示例,4,9.1.1 查询处理步骤,查询分析：对查询语句进行扫描、词法分析和语法分析，判断它是否符合SQL语法规则。 查询检查：根据数据字典对合法的查询语句进行语义检查，即查询语句中的数据库对象，如属性名、关系名，是否存在和是否有效
2、。还要根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。通过后便把SQL查询语句转换成等价的关系代数表达式，用查询树（语法分析树）来表示。,5,9.1.1 查询处理步骤（续）,3. 查询优化：从多个可供选择的执行策略和操作算法中选择一个高效执行的查询处理策略。按优化的层次一般可分为代数优化和物理优化。 代数优化：指关系代数表达式的优化，即按照一定的规则，改变代数表达式中操作的次序和组合，使查询执行更高效。 物理优化：指存取路径和底层操作算法的选择。,6,9.1.1 查询处理步骤（续）,4. 查询执行：依据优化器得到的执行策略生成查询计划，由代码生成器生成执行这个查询计划的代码。
3、 见课本P264 图9.1,7,8,9.1.2 实现查询操作的算法示例,一、选择操作的实现 例1 select * from student where 的几种情况：C1：无条件C2：sno=200215121C3：sage20C4：sdept=CS and sage20,9,9.1.2 实现查询操作的算法示例(续),1.简单的全表扫描方法 对基本表进行顺序扫描，逐一检查每个元组是否满足选择条件。对于小表简单有效，对于大表则效率低下。 2.索引扫描方法 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。,10,选择操作的实现（续）,例1-C2以C2为例，S
4、no200215121，并且Sno上有索引 使用索引得到Sno为200215121 元组的指针 通过元组指针在student表中检索到该学生例1-C3以C3为例，Sage20，并且Sage上有B+树索引 使用B+树索引找到Sage20的索引项，以此为入口点在B+树的顺序集上得到Sage20的所有元组指针 通过这些元组指针到student表中检索到所有年龄大于20的学生。,11,选择操作的实现（续）,例1-C4以C4为例，SdeptCS AND Sage20，如果Sdept和Sage上都有索引： 算法一：分别用上面两种方法分别找到SdeptCS的一组元组指针和Sage20的另一组元组指针 求这2
5、组指针的交集 到student表中检索 得到计算机系年龄大于20的学生算法二：找到SdeptCS的一组元组指针， 通过这些元组指针到student表中检索 对得到的元组检查另一些选择条件(如Sage20)是否满足 把满足条件的元组作为结果输出。,12,9.1.2 实现查询操作的算法示例(续),二、连接操作的实现 例2 select * from student,sc where student.sno=sc.sno 嵌套循环方法 排序-合并方法 索引连接方法 Hash join方法,13,9.1.2 实现查询操作的算法示例,1、嵌套循环方法,14,9.1.2 实现查询操作的算法示例,2、排序合
6、并方法,SNO,SNO,CNO,15,9.1.2 实现查询操作的算法示例,3、索引连接方法,SNO,SNO,CNO,索引表,16,9.1.2 实现查询操作的算法示例,4、Hash Join方法,1,200215123,3,200215122,5,200215121,3,200215122,2,200215121,1,200215123,3,200215123,2,200215121,SNO,SNO,CNO,17,9.2 关系数据库系统的查询优化,9.2.1 查询优化概述 查询优化在关系数据库系统中有着非常重要的地位 关系查询优化是影响RDBMS性能的关键因素,18,9.2.1 查询优化概述（续
7、）,由DBMS进行查询优化的好处 用户不必考虑如何最好地表达查询以获得较好的效率 系统可以比用户程序的优化做得更好(1) 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。,19,9.2.1 查询优化概述（续）,(2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 (3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 (4)优化器中包括了很多复杂的优化技术。,20,9.2.1 查询优化概述（续）,RDBMS通过某种代价模型计算出各种查询执行策略
8、的执行代价，然后选取代价最小的执行方案 集中式数据库 执行开销主要包括： 磁盘存取块数(I/O代价) 处理机时间(CPU代价) 查询的内存开销 I/O代价是最主要的 分布式数据库 总代价=I/O代价+CPU代价+内存代价通信代价,21,9.2.1 查询优化概述（续）,查询优化的总目标 选择有效策略，求得给定关系表达式的值，使得查询代价最小（实际上是较小）。,22,9.2.2 一个实例,例：求选修了2号课程的学生姓名SELECT SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno=2;,23,假设1：外存：Student:1000条，S
9、C：10000条, 选修2号课程：50条 假设2：一个内存块装元组:10个Student, 或100个SC，内存中一次可以存放: 5块Student元组,1块SC元组和若干块连接结果元组 假设3：读写速度：20块/秒 假设4：连接方法：基于数据块的嵌套循环法,24,一个实例（续）,系统可以用多种等价的关系代数表达式来完成这一查询 Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 (StudentSC) Q2=Sname(Sc.Cno=2 (Student SC) Q3=Sname(Student Sc.Cno=2(SC),25,执行策略1,1=sname(Student.
10、Sno=SC.Sno SC.Cno=2 (StudentSC) StudentSC 读取总块数= 读Student表块数 + 读SC表遍数*每遍块数=1000/10+(1000/(105) (10000/100)=100+20100=2100 读数据时间=2100/20=105秒 中间结果大小 = 1000*10000 = 107 (1千万条元组) 写中间结果时间 = 10000000/10/20 = 50000秒,26,不同的执行策略,考虑I/O时间,Student.Sno=SC.Sno SC.Cno=2 读数据时间 = 50000秒 name 总时间 =1055000050000秒 = 1
11、00105秒= 27.8小时,27,执行策略2,2 sname(SC.Cno= 2 (Student SC) 读取总块数= 2100块 读数据时间=2100/20=105秒 中间结果大小=10000 （减少1000倍） 写中间结果时间=10000/10/20=50秒 读数据时间=50秒 总时间1055050秒205秒=3.4分,28,执行策略3,3 Sname(Student SC.Cno= 2 (SC) 读SC表总块数= 10000/100=100块 读数据时间=100/20=5秒 中间结果大小=50条 不必写入外存 读Student表总块数= 1000/10=100块 读数据时间=100/
12、20=5秒 总时间55秒10秒,29,执行策略4,4 sname(Student SC.Cno=2 (SC) 假设SC表在Cno上有索引，Student表在Sno上有索引 读SC表索引= 读SC表总块数= 50/1001块 读数据时间 中间结果大小=50条 不必写入外存 读Student表索引= 读Student表总块数= 50/10=5块 读数据时间 总时间10秒,30,9.3 代数优化,代数优化策略：通过对关系代数表达式的等价变换来提高查询效率 关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的两个关系表达式E1和E2是等价的，可记为E1E2,31,常用的等
13、价变换规则,设E1、E2等是关系代数表达式，F是条件表达式l. 连接、笛卡尔积交换律E1 E2 E2E1E1 E2E2 E1 E1 F E2E2 F E1,32,关系代数等价变换规则（续）,2. 连接、笛卡尔积的结合律(E1E2) E3 E1 (E2E3)(E1 E2) E3 E1 (E2 E3)(E1 E2) E3 E1 (E2 E3) F F F F,33,关系代数等价变换规则（续）,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
14、, A2, , An构成Bl，B2，Bm的子集,34,关系代数等价变换规则（续）,4. 选择的串接定律F1 （ F2（E） F1 F2(E) 选择的串接律说明选择条件可以合并 这样一次就可检查全部条件,35,关系代数等价变换规则（续）,5. 选择与投影的交换律 (1)假设: 选择条件F只涉及属性A1，AnF (A1,A2, ,An(E) A1,A2, ,An(F(E)(2)假设: F中有不属于A1, ,An的属性B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An(F (A1,A2, ,An,B1,B2, ,Bm(E),36,关系代数等价变换规则（续）,6. 选择与笛卡尔积的
15、交换律 (1) 假设：F中涉及的属性都是E1中的属性F (E1E2)F (E1)E2 (2) 假设：F=F1F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性则由上面的等价变换规则1，4，6可推出：F(E1E2) F1(E1)F2 (E2),37,关系代数等价变换规则（续）,(3) 假设： F=F1F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性F(E1E2) F2(F1(E1)E2)它使部分选择在笛卡尔积前先做,38,关系代数等价变换规则（续）,7. 选择与并的交换假设：E=E1E2，E1，E2有相同的属性名F(E1E2) F(E1) F(E2)8. 选择与差运算的交换假设：E1与E2有相同的属性名F(E1-E2) F(E1) - F(E2),
