九章关系查询处理和查询优化.ppt

第九章 关系查询处理和查询优化,授课教师：王哲,复习上节课内容,索引的创建及管理建立索引的必要性索引的类型管理索引（创建、查看、修改、删除）关系数据库系统的查询处理查询分析查询检查查询优化查询执行,本次课学习内容,关系数据库系统的查询优化 代数优化物理优化,一、关系数据库系统的查询优化,查询优化在关系数据库系统中有着非常重要的地位 关系查询优化是影响RDBMS性能的关键因素 由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性,查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好；（1）优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息；（2）如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。,(3)优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。,RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案：集中式数据库执行开销主要包括：磁盘存取块数(I/O代价)处理机时间(CPU代价)查询的内存开销 I/O代价是最主要的 分布式数据库总代价=I/O代价+CPU代价+内存代价通信代价,查询优化的总目标：选择有效的策略；求得给定关系表达式的值；使得查询代价最小(实际上是较小)；,实例演示（验证为何需要查询优化？）,例1：求选修了2号课程的学生姓名。假定学生-课程数据库中有1000条学生记录，10000条选课记录；其中选修2号课程的选课记录为50条；用SQL表达：SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2,系统可以用多种等价的关系代数表达式来完成：Q1=Sname(Student.Sno=SC.SnoSc.Cno=2(StudentSC)Q2=Sname(Sc.Cno=2(Student SC)Q3=Sname(Student Sc.Cno=2(SC),1、第一种情况,分三个步骤：计算StudentSC花费时间，即计算笛卡尔积操作时间；计算Student.Sno=SC.SnoSc.Cno=2 花费时间，即计算选择操作时间；计算Sname花费时间，即计算投影操作时间；,1）计算笛卡尔积时间,把Student和SC的每个元组连接起来的做法：在内存中尽可能多地装入某个表(如Student表)的若干块，留出一块存放另一个表(如SC表)的元组；把SC中的每个元组和Student中每个元组连接，连接后的元组装满一块后就写到中间文件上；从SC中读入一块和内存中的Student元组连接，直到SC表处理完；再读入若干块Student元组，读入一块SC元组；重复上述处理过程，直到把Student表处理完；,设一个块能装10个Student元组或100个SC元组，在内存中存放5块Student元组和1块SC元组，则读取总块数为：=100+20100=2100块若每秒读写20块，则总计要花105s；连接后的元组数为103104=107；设每块能装10个元组，则写出这些块要用106/20=5104s；,2）计算选择时间,依次读入连接后的元组，按照选择条件选取满足要求的记录；假定内存处理时间忽略；读取中间文件花费的时间(同写中间文件一样)需5104s；满足条件的元组假设仅50个，均可放在内存；3）作投影操作把第2步的结果在Sname上作投影输出，得到最终结果；所有内存处理时间均忽略不计；第一种情况下执行查询的总时间105+25104105s,2、第二种情况,分三个步骤：计算Student SC花费时间，即计算自然连接操作时间；计算Sc.Cno=2 花费时间，即计算选择操作时间；计算Sname花费时间，即计算投影操作时间；,1）计算自然连接时间,读取Student和SC表的策略不变，总的读取块数仍为2100块，花费105 s；自然连接的结果比第一种情况大大减少，为104个；写出这些元组时间为103/20=50s，为第一种情况的千分之一；2）计算选择操作时间读取中间文件块，执行选择运算，花费时间也为50s；3）计算选择操作时间：把第2步结果投影输出。第二种情况下执行查询的总时间105+50+50205s,3、第三种情况,分三个步骤：先对SC表作选择运算，只需读一遍SC表，需存取100块，花费时间为5s，因为满足条件的元组仅50个，不必使用中间文件。读取Student表，把读入的Student元组和内存中的SC元组作连接。也只需读一遍Student表共100块，花费时间为5s。把连接结果投影输出；第三种情况下执行查询的总时间5+5 10s,由Q1变换为Q2、Q3得出结论：即有选择和连接操作时，先做选择操作，这样参加连接的元组就可以大大减少，这是代数优化；在Q3中：SC表的选择操作算法有全表扫描和索引扫描2种方法，经过初步估算，索引扫描方法较优；对于Student和SC表的连接，利用Student表上的索引，采用index join代价也较小，这就是物理优化；,二、代数优化,代数优化策略：通过对关系代数表达式的等价变换来提高查询效率；关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的；两个关系表达式E1和E2是等价的，可记为E1E2,1）连接、笛卡尔积交换律 设E1和E2是关系代数表达式，F是连接运算的条件，则有 E1 E2E2 E1 E1 E2E2 E1 E1 E2E2 E12）连接、笛卡尔积的结合律 设E1，E2，E3是关系代数表达式，F1和F2是连接运算的条件，则有(E1 E2)E3E1(E2 E3)(E1 E2)E3E1(E2 E3)(E1 E2)E3E1(E2 E3),1、常用的等价变换规则（P269）,2、查询树的启发式优化,启发式规则：选择运算应尽可能先做；在优化策略中这是最重要、最基本的一条；把投影运算和选择运算同时进行；如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系；把投影同其前或其后的双目运算结合起来；把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算；找出公共子表达式；,优化关系表达式的算法（P271）,算法：关系表达式的优化；输入：一个关系表达式的查询树；输出：优化的查询树；方法：1）利用等价变换规则4把形如F1F2Fn(E)变换为F1(F2(Fn(E)；2）对每一个选择，利用等价变换规则49尽可能把它移到树的叶端；3）对每一个投影利用等价变换规则3，5，10，11中的一般形式尽可能把它移向树的叶端；4）利用等价变换规则35把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影；5)把上述得到的语法树的内节点分组。,例：将例1的SQL语句的代数优化；,关系代数语法树,三、物理优化,代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径；对于一个查询语句有许多存取方案，它们的执行效率不同，仅仅进行代数优化是不够的；物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划；选择的方法：基于规则的启发式优化基于代价估算的优化两者结合的优化方法,1、基于启发式规则的存取路径选择优化P273,1）选择操作的启发式规则:对于小关系，使用全表顺序扫描，即使选择列上有索引 对于大关系，启发式规则有：对于选择条件是主码值的查询；查询结果最多是一个元组，可以选择主码索引；一般的RDBMS会自动建立主码索引；对于选择条件是非主属性值的查询，并且选择列上有索引要估算查询结果的元组数目如果比例较小(10%)可以使用索引扫描方法否则还是使用全表顺序扫描,2）连接操作的启发式规则：如果2个表都已经按照连接属性排序选用排序-合并方法如果一个表在连接属性上有索引选用索引连接方法如果上面2个规则都不适用，其中一个表较小选用Hash join方法可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数(b)较少的表，作为外表(外循环的表)。,2、基于代价的优化P274,基于代价的优化方法要计算各种操作算法的执行代价，与数据库的状态密切相关；数据字典中存储的优化器需要的统计信息：1）对每个基本表该表的元组总数(N)元组长度(l)占用的块数(B)占用的溢出块数(BO)2）对基表的每个列3）对索引(如B+树索引),代价估算示例,1）全表扫描算法的代价估算公式如果基本表大小为B块，全表扫描算法的代价 costB如果选择条件是码值，那么平均搜索代价 costB/22）索引扫描算法的代价估算公式如果选择条件是码值，若为B+树，层数为L，cost=L+1如果选择条件涉及非码属性，cost=L+S；3）嵌套循环连接算法的代价估算公式,总结,本章的目的：希望读者掌握查询优化方法的概念和技术，不要求掌握查询处理和查询优化的内部技术；本章学习内容：管理索引关系数据库系统的查询处理 关系数据库系统的查询优化 代数优化 物理优化,练习：,课本275页习题2,