第4章-查询处理及优化.ppt

4.3 查询优化 2、如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 3、优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 4、优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。 关系数据库查询优化的总目标是：选择有效的策略，求得给定关系表达式的值。 4.3 查询优化 查询优化一般来说，可以归纳为四个步骤： 1、将查询转换成某种内部表示，通常是语法树。 2、根据一定的等价变换规则把语法树转换成标准（优化）形式。 3、选择低层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。 4.3 查询优化 4、生成查询计划。查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。在集中式关系数据库中，计算代价时主要考虑磁盘读写的I/O次数，也有一些系统还考虑了CPU的处理时间。 步骤（3）和步骤（4）实际上没有清晰的界限，有些系统是作为一个步骤处理的。 4.3 查询优化 目前的商品化RDBMS大都采用基于代价的优化算法。在集中式数据库中，查询的执行开销主要包括： 总代价 = I/O代价 + CPU代价 在多用户环境下，内存在多个用户间的分配情况会明显地影响这些用户查询执行的总体性能。因此，多用户数据库还应考虑查询的内存开销，即： 总代价 = I/O代价 + CPU代价 + 内存代价 4.3 查询优化 4.3.2 一个实例 [例1] 求选修了1024号课程的学生姓名。用SQL语言表达： SELECT Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=1024; 假定学生-课程数据库中有l000个学生记录，l0000个选课记录，其中选修1024号课程的选课记录为50个。 4.3 查询优化 系统可以用多种等价的关系代数表达式来完成这一查询 Q1=πSname(?Student.sno=Sc.Sno?sc.cno=1024 (Student×SC)) Q2=πSname(?sc.cno=’1024’ (Student SC)) Q3=πSname(Student ? sc.cno=1024 (SC)) 还可以写出几种等价的关系代数表达式，但分析这三种就足以说明问题了。后面将看到由于查询执行的策略不同，查询时间相差很大。 4.3 查询优化 一、第一种情况 1. 计算广义笛卡尔积 把S和SC的每个元组连接起来。一般连接的做法是：在内存中尽可能多地装入某个表(如Student表)的若干块元组，留出一块存放另一个表(如SC表)的元组。然后把SC中的每个元组和Student中每个元组连接，连接后的元组装满一块后就写到中间文件上，再从SC中读入一块和内存中的S元组连接，直到SC表处理完。这时再一次读入若干块S元组，读入一块SC元组，重复上述处理过程，直到把S表处理完。 4.3 查询优化 一、第一种情况 1. 计算广义笛卡尔积 设一个块能装l0个Student元组或l00个SC元组，在内存中存放5块Student元组 和l块SC元组，则读取总块数为： 1000/10+1000/10*5×10000/100=100+20*100=2100块 其中读Student表l00块。读SC表20遍，每遍读l00块。若每秒读写20块，则总计要花105 s。 连接后的元组数为l03×104=l07 。设每块能装l0个元组，则写出这些块要用时l06/20=5×104 s。 4.3 查询优化 2. 作选择操作 依次读入连接后的元组，按照选择条件选取满足要求的记录。假定内存处理时间忽略。这一步读取中间文件花费的时间(同写中间文件一样)需5×104 s。满足条件的元组假设仅50个，均可放在内存。 3. 作投影 把第2步的结果在Sname上作投影输出，得到最终结果。因此第一种情况下执行查询的总时间≈l05+2×5×104≈l05 s。这里，所有内存处理