数据结构域算法设计ch.12 查询处理和优化

第12章 查询处理和优化,12.1 概述 12.2 代数优化 12.3 依赖于存取路径的规则优化 12.4 代价估算优化*,12.1 概述,重要性 查询是数据库系统中最基本、最常见和最复杂的操作。对数据库的查询一般都是以查询语言（如SQL）表示。从查询请求出发，直到得到查询结果，这一过程称为查询处理。 关系数据库系统的查询语言一般是“非过程语言”，它减轻了用户选择存取路径的负担。用户只要提出干什么，不必指出怎么干。即用户不必关心查询的具体执行过程，而由DBMS确定合理的、有效的执行策略。DBMS在这方面的作用成为查询优化 。 对于使用非过程查询语言的RDBMS，查询优化是查询处理中非常重要的一环，对系统性能会产生很大的影响。,12.1 引言,查询优化的优点 查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。这是因为： 优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。 如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。,12.1 引言,查询优化的目标和途径 关系数据库查询优化的总目标是：选择有效的策略，求得给定关系表达式的值。 查询优化的途径包括： 对查询语句进行等价变换（如改变基本操作的顺序）使查询执行起来更加有效。这种优化只涉及查询语句本身，而不涉及存取路径，故称为独立于存取路径的优化，或代数优化。 根据系统提供的查询路径，选择合理的存取策略（例如是选择顺序扫描还是选择索引），这称为依赖于存取路径的优化，或称物理优化。 有些查询可根据启发式规则选择执行策略，这称为规则优化。 根据可供选择的执行策略进行代价估算，并从中选择代价最小的执行策略，这称为代价估算优化。 此外，还可以通过应用数据库的语义信息对查询进行优化，这称为语义优化。,12.1 引言,查询处理和优化的步骤 实际系统对查询优化的具体实现一般可以归纳为四个步骤： 将查询转换成某种内部表示，通常是语法树。 根据一定的等价变换规则把语法树转换成标准（优化）形式。 选择低层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。 生成查询计划。查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。 在集中式数据库中，查询的执行开销主要包括： 总代价 = I/O代价 + CPU代价 在多用户环境下： 总代价 = I/O代价 + CPU代价 + 内存代价,12.1 引言,一个简单的例子 首先看一个简单的例子，说明为什么要进行查询优化。 例：求选修了2号课程的学生姓名。用SQL语言表达： SELECT S.Sname FROM Student S，SC WHERE S.SNO=SC.SNO AND SC.CNO='2'； 假定学生-课程数据库中有l000个学生记录,l0000个选课记录，其中选修2号课程的选课记录为50个。 系统可以用多种等价的关系代数表达式来完成这一查询 1.Q1= Sname( Student.sno=sc.snosc.cno='2'(Student×SC) 2.Q2= Sname( sc.cno='2' (Student |><| sc.cno='2'(SC) 还可以写出几种等价的关系代数表达式,但分析这三种就足以说明问题了。我们将看到由于查询执行的策略不同,查询时间相差很大。,12.1 引言,查询执行策略Q1代价分析 计算广义笛卡尔积的代价 把S和SC的每个元组连接起来。一般连接的做法是：在内存中尽可能多地装人某个表(如Student表)的若干块元组，留出一块存放另一个表(如SC表)的元组。然后把SC中的每个元组和Student中每个元组连接，连接后的元组装满一块后就写到中间文件上，再从SC中读入一块和内存中的S元组连接，直到SC表处理完。这时再一次读入若干块S元组，读入一块SC元组，量复上述处理过程，直到把S表处理完。 设一个块能装l0个Student元组或l00个SC元组，在内存中存放5块Student元组 和l块SC元组，则读取总块数为： 1000/10+1000/(10 X 5) X (10000/100)=2100块 其中读Student表l00块。读SC表20遍，每遍l00块。若每秒读写20块，则总计要花105(秒)。 连接后的元组数为1000X10000。设每块能装l0个元组，则写出这些块要花1000000/20=50000( 秒)。,12.1 引言,查询执行策略Q1代价分析(续) 选择操作的代价依次读入连接后的元组，按照选择条件选取满足要求的的记录。假定内存处理时间忽略。这一步读取中间文件花费的时间(同写中间文件一样)需50000 秒。满足条件的元组假设仅50个，均可放在内存。 投影操作的代价把第2步的结果在Sname上作投影输出,得到最终结果。 因此第一种情况下执行查询的总时间约为105+2*5*10000秒10010527。8小时。这里，所有内存处理时间均忽略不计。,12.1 引言,查询执行策略Q2代价分析 计算自然连接的代价为了执行自然连接，读取Student和SC表的策略不变,总的读取块数仍为2100块，花费l05秒。但自然连接的结果比第一种情况大大减少，为 10000个。因此写出这些元组时间为 /10/20=50秒。仅为第一种情况的千分之一。 读取中间文件块，执行选择运算，花费时间也为50秒。 将第2步结果投影输出。 因此，第二种情况总的执行时间105+50+50205秒3。4分。,12.1 引言,查询执行策略Q3代价分析 先对SC表作选择运算，只需读一遍SC表，存取l00块花费时间为5秒，因为满足条件的元组仅50个，不必使用中间文件。 读取STUDENT表，把读入的STUDENT元组和内存中的SC元组作连接。也只需读一遍STUDENT表共l00块花费时间为5秒。 把连接结果投影输出。 第三种情况总的执行时间5+510秒。,12.1 引言,假如SC表的Cno字段上有索引，第l步就不必读取所有的SC元组而只需读取CNO=2的那些元组(50个)。 存取的索引块和SC中满足条件的数据块大约总共34块。若STUDENT表在Sno上也有索引，则第2步也不必读取所有的STUDENT元组，因为满足条件的SC记录仅50个，涉及最多50个STUDENT记录，因此读取STUDENT表的块数也可大大减少。总的存取时间将进一步减少到数秒。 这个简单的例子充分说明了查询优化的必要性，同时也给了我们一些查询优化方法的初步概念。如当有选择和连接操作时，应当先做选择操作，这样参加连接的元组就可以大大减少。 下面给出查询优化的一般策略。,12.2 代数优化,查询优化的一般准则 下面的优化策略一般能提高查询效率,但不一定是所有策略中最优的。其实优化一词并不确切，也许改进或改善更恰当些。 选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条。它常常可使执行时节约几个数量级，因为选择运算一般使计算的中间结果大大变小。 在执行连接前对关系适当地预处理。预处理方法主要有两种，在连接属性上建立索引和对关系排序，然后执行连接。第一种称为索引连接方法，第二种称为排序合并（SORT-MERGE）连接方法。 将投影运算和选择运算同时进行。如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完戌所有的这些运算以避免重复扫描关系。,12.2 代数优化,把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。 将某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。 找出公共子表达式。如果这种重复出现的子表达式的结果不是很大的关系，并且从外存中读人这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写人中间文件。当查询的是视图时，定义视图的表达式就可成为公共子表达式。,12.2 代数优化,关系代数等价变换规则 上面的优化策略大部分都涉及到代数表达式的变换。关系代数表达式的优化是查询优化的基本课题。而研究关系代数表达式的优化最好从研究关系表达式的等价变换规则开始。 两个关系表达式El和E2是等价的，可记为E1E2。 常用的等价变换规则有：(1)选择的串接F1(F2(R)F1 F2(R) (2) 选择的交换F1(F2(R)F2(F1(R),12.2 代数优化,(3)投影的串接. L1(L2(Ln(R) L1(R) 条件：L1 L2 Ln (4)选择与投影的交换. L(F(R)F(L(R) 条件：Attr(F)是L的子集 (5)连接笛卡儿积的交换律R|><| R R×SS×R,12.2 代数优化,(6)选择对连接笛卡儿积的分配律F(R|><|L2 (R)F F 条件： Attr(F1)Attr(S)=NULL, Attr(F2)Attr(R)=NULLAttr(F) Attr(L1L2),12.2 代数优化,(8)选择对、的分配律F(RS) F(R) F(S)F(RS) F(R)F(S) F(RS) F(R)F(S) (9)投影对的分配律.L (RS) L (R) L (S) (10) |><|T),12.2 代数优化,关系代数表达式优化算法 我们可以应用上面的变换法则来优化关系表达式，例如把选择和投影尽可能地早做(即把它们移到表达式语法树的下部)。下面给出关系表达式的优化算法。 算法：关系表达式的优化。 输入：一个关系表达式的语法树。 输出：计算该表达式的程序。步骤： 利用规则(4)把形如 F1F2.Fn(E)的表达式变换为 F1(F2(.(Fn(E).) 对每一个选择，利用规则(4)（8）尽可能把它移到树的叶端。 对每一个投影利用规则(3)，(9)，(l0)，(5)中的一般形式尽可能把它移向树的叶端。 注意，法则(3)可能回使一些投影消失，而一般形式的规则(5)则可能把一个投影分裂为两个，其中一个有可能被移向树的叶端。,12.2 代数优化,利用规则(3)(5)把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成，尽管这种变换以乎违背投影尽可能早做的原则，但这样做效率更高。 把上述得到的语法树的内节点分组。每一双目运算(×, |,，-)和它所有的直接祖先(包括 , 运算)为一组。如果其后代直到叶子全是单目运算则也将它们并入该组，但当双目运算是笛卡尔积(×)，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。 生成一个程序，每组结点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。,12.2 代数优化,例：设有下列关系：S(SNUM,SNAME,CITY)P(PNUM,PNAME,WEIGHT,SIZE)SP(SNUM,PNUM,DEPT,QUAN) 和如下查询：SELECT SNAMEFROM S,SP,PWHERE S.SNUM=SP.SNUMAND SP.PNUM=P.PNUMAND S.CITY=NJAND P.PNAME=BLOTAND SP.QUAN>10000;,