华中科技大学数据库课件第09章 关系查询处理和查询优化

©2011by1AnIntroductiontoDatabaseSystem9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.5小结第9章关系查询处理和查询优化©2011by2AnIntroductiontoDatabaseSystem9.1.1查询处理步骤9.1.2实现查询操作的算法示例9.1关系数据库系统的查询处理©2011by3AnIntroductiontoDatabaseSystemRDBMS查询处理分4个阶段:1.查询分析2.查询检查3.查询优化4.查询执行9.1.1查询处理步骤©2011by4AnIntroductiontoDatabaseSystem1查询分析语句扫描、词法分析和语法分析符合SQL语法？2查询检查根据数据字典对合法的查询语句进行语义检查。属性、关系名存在否？权限和完整性约束？SQL→关系代数表达式用查询树、语法分析树表达关系代数表达式数据库外部名称转换为内部表示9.1.1查询处理步骤©2011by5AnIntroductiontoDatabaseSystem3查询优化选择一个高效的查询处理策略查询优化分类代数优化物理优化查询优化方法选择的依据基于规则(rulebased)基于代价(costbased)基于语义(semanticbased)9.1.1查询处理步骤©2011by6AnIntroductiontoDatabaseSystem4查询执行根据优化器得到的执行策略生成查询计划由代码生成器生成执行这个查询计划的代码9.1.1查询处理步骤©2011by7AnIntroductiontoDatabaseSystem9.1.1查询处理步骤©2011by8AnIntroductiontoDatabaseSystem9.1.1查询处理步骤9.1.2实现查询操作的算法示例9.1关系数据库系统的查询处理©2011by9AnIntroductiontoDatabaseSystem查询运算很多：选择、投影、笛卡尔积、连接以选择和连接为例简单描述算法思想9.1.2查询操作算法示例©2011by10AnIntroductiontoDatabaseSystem【例1】Select*fromstudentwhere条件表达式考虑条件表达式的几种情况：C1：无条件；C2：Sno＝'200215121'；C3：Sage20；C4：Sdept＝'CS'ANDSage209.1.2查询操作算法示例©2011by11AnIntroductiontoDatabaseSystem选择操作典型实现方法：简单的全表扫描方法索引(或散列)扫描方法选择条件中的属性上有索引(例如B+树索引或Hash索引)通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在基本表中找到元组9.1.2查询操作算法示例©2011by12AnIntroductiontoDatabaseSystem【例2】SELECT*FROMStudent,SCWHEREStudent.Sno=SC.Sno嵌套循环方法(nestedloop)排序-合并方法(sort-mergejoin或mergejoin)索引连接(indexjoin)方法HashJoin方法9.1.2查询操作算法示例©2011by13AnIntroductiontoDatabaseSystem9.1.2查询操作算法示例200215121200215122200215123200215124...200215121192200215121285200215121388200215122290200215122380...排序-合并连接方法示意图©2011by14AnIntroductiontoDatabaseSystem9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.5小结第9章关系查询处理和查询优化©2011by15AnIntroductiontoDatabaseSystem必要性查询优化在关系数据库系统中有着非常重要的地位关系查询优化是影响RDBMS性能的关键因素可行性由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性9.2关系数据库系统的查询优化©2011by16AnIntroductiontoDatabaseSystem查询优化的优点用户不必考虑HowToDo系统可以比用户做得更好(更“优化”)1)优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。9.2关系数据库系统的查询优化©2011by17AnIntroductiontoDatabaseSystem3)优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术9.2关系数据库系统的查询优化©2011by18AnIntroductiontoDatabaseSystem代价模型集中式数据库磁盘存取块数(I/O代价)*处理机时间(CPU代价)查询的内存开销(多用户情形)分布式数据库I/O代价+CPU代价+内存代价＋通信代价9.2关系数据库系统的查询优化©2011by19AnIntroductiontoDatabaseSystem查询优化的总目标选择有效的策略求得给定关系表达式的值使得查询代价最小(实际上是较小)一个实例(说明为什么要优化)9.2关系数据库系统的查询优化©2011by20AnIntroductiontoDatabaseSystem【例3】求选修了2号课程的学生姓名。用SQL语言表达:selectstudent.snamefromstudent,SCwherestudent.sno=SC.snoandSC.cno=‘2’假定数据库中有1000个学生记录，10000个选课记录，其中选2号课程的记录为50个。9.2关系数据库系统的查询优化©2011by21AnIntroductiontoDatabaseSystem系统至少有以下三种等价的关系代数表达式来完成这一查询(用S代表Student):Q1=Sname(S.sno=SC.sno∧SC.Cno=‘2’(S×SC))Q2=Sname(SC.Cno=‘2’(SSC))Q3=Sname(SSC.Cno=‘2’(SC))我们仅以上述三种情况为代表，来作分析。9.2关系数据库系统的查询优化©2011by22AnIntroductiontoDatabaseSystem系统假设:元组数：student1000个,SC10000个，其中有关2号课程的50个内存数：5个内存块用于装student,1个内存块用于装SC块大小：一个内存块可装10个student元组(或10个student与SC笛卡尔积元组)，或100个SC元组读写速度:20块/秒(读写速度一样)连接方法：基于数据块的嵌套循环法连接后的元组装满一块后就写到中间文件上9.2关系数据库系统的查询优化©2011by23AnIntroductiontoDatabaseSystemQ1:Sname(S.sno=SC.sno∧SC.Cno=‘2’(S×SC))9.2关系数据库系统的查询优化学号Sno姓名Sname05001李勇05002刘晨S(1000行)学号Sno课程号Cno成绩Grade05001192050012850500138805002290SC(10000行)×=(10000000行)©2011by24AnIntroductiontoDatabaseSystemQ1:Sname(S.sno=SC.sno∧SC.Cno=‘2’(S×SC))1.计算笛卡尔积S×SC读一遍S表需读的总块数=1000/10=100块读一遍SC表需读的总块数=10000/100=100块S表要分几次读入内存?100/5=20次S表的每一部分读入内存，SC表都需读一遍,SC共需读入的块数=100×20=2000块笛卡尔积运算读取的总块数=100+2000=2100块读取时间T1=2100/20=105秒中间结果大小=1000*10000写中间结果的时间T2=(1000*10000)/10/20=50000秒9.2关系数据库系统的查询优化©2011by25AnIntroductiontoDatabaseSystemQ1(续):2.作选择运算S.sno=SC.sno∧SC.Cno=‘2’(…)只需将中间结果读取一遍,并依次判断，选取满足条件的元组(处理时间不计，只计读取时间)读取数据的总时间T3=50000秒3.作投影运算忽略不计Q1总时间=T1+T2+T3=105秒+50000秒+50000秒=100105秒=27.8小时9.2关系数据库系统的查询优化©2011by26AnIntroductiontoDatabaseSystemQ2:Sname(SC.Cno=‘2’(SCS))9.2关系数据库系统的查询优化学号Sno姓名Sname05001李勇05002刘晨S(1000行)学号Sno课程号Cno成绩Grade05001192050012850500138805002290SC(10000行)=10000行©2011by27AnIntroductiontoDatabaseSystemQ2:Sname(SC.Cno=‘2’(SCS))1.计算自然连接SCS读取时间T1=2100/20=105秒(与Q1一样)中间结果大小=10000写中间结果的时间T2=10000/10/20=50秒2.作选择运算SC.Cno=‘2’()读中间数据的时间T3=50秒3.投影(时间忽略不计)Q2总时间=T1+T2+T3=105秒+50秒+50秒=205秒9.2关系数据库系统的查询优化©2011by28AnIntroductiontoDatabaseSystemQ3:Sname(SSC.Cno=‘2’(SC))9.2关系数据库系统的查询优化学号Sno姓名Sname05001李勇05002刘晨S(1000行)学号Sno课程号Cno成绩Grade0500128505002290…(SC)(50行)=50行©2011by29AnIntroductiontoDatabaseSystemQ3:Sname(SSC.Cno=‘2’(SC))1.计算SC1=SC.Cno=‘2’(SC):读SC并选择读SC时间T1=10000/100/20=5秒中间结果大小=50,不必写入外存,写中间结果的时间忽略不计2.计算SSC1读S时间T2=1000/10/20=5秒注：虽然S需分20次读入，且每读一部分都要遍历一遍SC1,但因SC1只有50个元组，全在内存，无I/O操作，这部分时间忽略不计，只计读S一遍的时间即可。计算的结果仍只有50个元组，不计I/O时间。9.2关系数据库系统的查询优化©2011by30AnIntroductiontoDatabaseSystemQ3(续):3.投影(时间忽略不计)Q3总时间=T1+T2=5秒+5秒=10秒Q4:假定SC在cno上建有索引，S表在sno上建有索引，如仍用Q3方法，则第1步选择时，根本不用读SC表全部，只需读取cno=‘2’的那些元组(50个),第2步也不需读取所有S表元组，只需读出相关的50个，这样总的时间可进一步大大减少(10秒)。9.2关系数据库系统的查询优化©2011by31AnIntroductiontoDatabaseSystemQ4:Sname(SSC.Cno=‘2’(SC))9.2关系数据库系统