九章关系查询处理和查询优化-ppt课件

1、第九章第九章 关系查询处置和查询优化关系查询处置和查询优化授课教师：王哲复习上节课内容复习上节课内容v索引的创建及管理索引的创建及管理v建立索引的必要性建立索引的必要性v索引的类型索引的类型v管理索引创建、查看、修正、删除管理索引创建、查看、修正、删除v关系数据库系统的查询处置关系数据库系统的查询处置v查询分析查询分析v查询检查查询检查v查询优化查询优化v查询执行查询执行本次课学习内容本次课学习内容v关系数据库系统的查询优化 v代数优化v物理优化 一、关系数据库系统的查询优化一、关系数据库系统的查询优化 v查询优化在关系数据库系统中有着非常重要的位置 v关系查询优化是影响RDBMS性能的关键要

2、素 v由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的能够性 v查询优化的优点不仅在于用户不用思索如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化做得更好 ；v1优化器可以从数据字典中获取许多统计信息，而用户程序那么难以获得这些信息；v2假设数据库的物理统计信息改动了，系统可以自动对查询重新优化以选择相顺应的执行方案。在非关系系统中必需重写程序，而重写程序在实践运用中往往是不太能够的。 (3)优化器可以思索数百种不同的执行方案，程序员普通只能思索有限的几种能够性。 (4)优化器中包括了很多复杂的优化技术，这些优化技术往往只需最好

3、的程序员才干掌握。系统的自动优化相当于使得一切人都拥有这些优化技术。vRDBMS经过某种代价模型计算出各种查询执行战略的执行代价，然后选取代价最小的执行方案：v集中式数据库v执行开销主要包括：v磁盘存取块数(I/O代价)v处置机时间(CPU代价)v查询的内存开销 vI/O代价是最主要的 v分布式数据库v总代价=I/O代价+CPU代价+内存代价通讯代价v查询优化的总目的：v选择有效的战略；v求得给定关系表达式的值；v使得查询代价最小(实践上是较小) ；实例演示验证为何需求查询优化？实例演示验证为何需求查询优化？例例1： 求选修了求选修了2号课程的学生姓名。号课程的学生姓名。假定学生假定学生-课程

4、数据库中有课程数据库中有1000条学生记录，条学生记录，10000条条选课记录；选课记录；其中选修其中选修2号课程的选课记录为号课程的选课记录为50条；条； 用用SQL表达：表达： SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SCo=2 v系统可以用多种等价的关系代数表达式来完成：vQ1=Sname(Student.Sno=SC.SnoSco=2 (StudentSC)vQ2=Sname(Sco=2 (Student SC)vQ3=Sname(Student Sco=2(SC)v1、第一种情况、第一种情况v

5、 分三个步骤：v 计算StudentSC破费时间，即计算笛卡尔积操作时间；v 计算Student.Sno=SC.SnoSco=2 破费时间，即计算选择操作时间；v 计算Sname破费时间，即计算投影操作时间；1计算笛卡尔积时间计算笛卡尔积时间v把Student和SC的每个元组衔接起来的做法：v在内存中尽能够多地装入某个表(如Student表)的假设干块，留出一块存放另一个表(如SC表)的元组；v把SC中的每个元组和Student中每个元组衔接，衔接后的元组装满一块后就写到中间文件上；v从SC中读入一块和内存中的Student元组衔接，直到SC表处置完；v再读入假设干块Student元组，读入一

6、块SC元组；v反复上述处置过程，直到把Student表处置完；v 设一个块能装10个Student元组或100个SC元组，在内存中存放5块Student元组和1块SC元组，那么读取总块数为：v v =100 + 20100=2100块v 假设每秒读写20块，那么总计要花105s ；v 衔接后的元组数为103104=107；v 设每块能装10个元组，那么写出这些块要用106/20=5104s ；1010005101000100100002计算选择时间计算选择时间v 依次读入衔接后的元组，按照选择条件选取满足要求的记录； v 假定内存处置时间忽略；v 读取中间文件破费的时间(同写中间文件一样)需5

7、104s ；v 满足条件的元组假设仅50个，均可放在内存； v 3作投影操作v 把第2步的结果在Sname上作投影输出，得到最终结果 ；v 一切内存处置时间均忽略不计；v 第一种情况下执行查询的总时间105 + 25104105s2、第二种情况、第二种情况v 分三个步骤：v 计算Student SC破费时间，即计算自然衔接操作时间；v 计算Sco=2 破费时间，即计算选择操作时间；v 计算Sname破费时间，即计算投影操作时间；1计算自然衔接时间计算自然衔接时间v 读取Student和SC表的战略不变，总的读取块数仍为2100块，破费105 s ；v 自然衔接的结果比第一种情况大大减少，为10

8、4个 ；v 写出这些元组时间为103/20=50s，为第一种情况的千分之一；v 2计算选择操作时间v 读取中间文件块，执行选择运算，破费时间也为50s；v 3计算选择操作时间：把第2步结果投影输出。 v 第二种情况下执行查询的总时间105+50+50205s 3、第三种情况、第三种情况v 分三个步骤：v 先对SC表作选择运算，只需读一遍SC表，需存取100块，破费时间为5s，由于满足条件的元组仅50个，不用运用中间文件。v 读取Student表，把读入的Student元组和内存中的SC元组作衔接。也只需读一遍Student表共100块，破费时间为5s。v 把衔接结果投影输出；v 第三种情况下执

9、行查询的总时间5+5 10sv由Q1变换为Q2、 Q3得出结论：v即有选择和衔接操作时，先做选择操作，这样参与衔接的元组就可以大大减少，这是代数优化；v在Q3中：vSC表的选择操作算法有全表扫描和索引扫描2种方法，经过初步估算，索引扫描方法较优 ；v对于Student和SC表的衔接，利用Student表上的索引，采用index join代价也较小，这就是物理优化； 二、代数优化二、代数优化v代数优化战略：代数优化战略：v经过对关系代数表达式的等价变换来提高查询效率；经过对关系代数表达式的等价变换来提高查询效率；v关系代数表达式的等价：指用一样的关系替代两个表关系代数表达式的等价：指用一样的关系

10、替代两个表达式中相应的关系所得到的结果是一样的；达式中相应的关系所得到的结果是一样的；v两个关系表达式两个关系表达式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 E

11、2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) 1、常用的等价变换规那么、常用的等价变换规那么P2692、查询树的启发式优化、查询树的启发式优化v启发式规那么：启发式规那么：v选择运算应尽能够先做；在优化战略中这是最重要、选择运算应尽能够先做；在优化战略中这是最重要、最根本的一条；最根本的一条；v把投影运算和选择运算同时进展；把投影运算和选择运算同时进展；v如有假设干投影和选择运算，并且它们都对同一个关如有假设干投影和选择运算，并且它们都对同一个关系操作，那么可以在扫描此关系的同时完成一切的这系操作，那么可以在扫描此关系的同时完成一切的这些运算以防止反复扫描关系；些运

12、算以防止反复扫描关系；v把投影同其前或其后的双目运算结合起来；把投影同其前或其后的双目运算结合起来；v把某些选择同在它前面要执行的笛卡尔积结合起来成把某些选择同在它前面要执行的笛卡尔积结合起来成为一个衔接运算；为一个衔接运算；v找出公共子表达式；找出公共子表达式；优化关系表达式的算法优化关系表达式的算法P271 算法：关系表达式的优化；算法：关系表达式的优化；输入：一个关系表达式的查询树；输出：优化的查询树；输入：一个关系表达式的查询树；输出：优化的查询树；方法：方法：1利用等价变换规那么利用等价变换规那么4把形如把形如F1F2Fn(E)变换为变换为F1(F2(Fn(E)；2对每一个选择，利用

13、等价变换规那么对每一个选择，利用等价变换规那么49尽能够把它移到树的叶尽能够把它移到树的叶端；端；3对每一个投影利用等价变换规那么对每一个投影利用等价变换规那么3，5，10，11中的普通方式尽中的普通方式尽能够把它移向树的叶端；能够把它移向树的叶端；4利用等价变换规那么利用等价变换规那么35把选择和投影的串接合并成单个选择、把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影；单个投影或一个选择后跟一个投影；5) 把上述得到的语法树的内节点分组。把上述得到的语法树的内节点分组。v例：将例例：将例1的的SQL语句的代数优化；语句的代数优化； 关系代数语法树 三、物理优化三、物理优化v

14、 代数优化改动查询语句中操作的次序和组合，不涉及底层的存取途径；对于一个查询语句有许多存取方案，它们的执行效率不同， 仅仅进展代数优化是不够的 ；v 物理优化就是要选择高效合理的操作算法或存取途径，求得优化的查询方案 ；v 选择的方法：v 基于规那么的启发式优化v 基于代价估算的优化v 两者结合的优化方法1、基于启发式规那么的存取途径选择优化、基于启发式规那么的存取途径选择优化P2731 选择操作的启发式规那么:对于小关系，运用全表顺序扫描，即使选择列上有索引 对于大关系，启发式规那么有：对于选择条件是主码值的查询；查询结果最多是一个元组，可以选择主码索引；普通的RDBMS会自动建立主码索引；

15、对于选择条件是非主属性值的查询，并且选择列上有索引要估算查询结果的元组数目假设比例较小(10%)可以运用索引扫描方法否那么还是运用全表顺序扫描2 衔接操作的启发式规那么：假设2个表都曾经按照衔接属性排序选用排序-合并方法假设一个表在衔接属性上有索引选用索引衔接方法假设上面2个规那么都不适用，其中一个表较小选用Hash join方法可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数(b)较少的表，作为外表(外循环的表) 。2、基于代价的优化、基于代价的优化P274v基于代价的优化方法要计算各种操作算法的执行代价，与数据库的形状亲密相关 ；v数据字典中存储的优化器需求的统计信息： v1对每个根本表v该表的元组总数(N)v元组长度(l)v占用的块数(B)v占用的溢出块数(BO)v2对基表的每个列v3对索引(如B+树索引)代价估算例如代价估算例如 1全表扫描算法的代价估算公式假设根本表大小为B块，全表扫描算法的代价