第6章_查询优化.ppt

1、第六章查询优化, 2007Jufeng Software Institute,思考几个问题,为什么数据库管理系统产品强调：一个查询中涉及的基本表的个数不要超过7个，最多不要超过10个？ 一旦发现某个查询的效率很低，如何分析低效的原因？如何改进效率？, 2007Jufeng Software Institute,学完本讲后，你应该能够了解： 基于代价的查询优化与启发式查询优化的区别与优劣； 启发式查询优化的目标； 启发式逻辑优化的一般准则； 关系代数等价变换规则是启发式逻辑优化的理论基础； 启发式逻辑优化算法的基本步骤； 多个表的连接顺序影响查询执行计划的效率 多连接查询的逻辑优化主要基于关系代

2、数的等价变换规则 - 笛卡尔积的交换律和结合律,本 讲 主 要 目 标, 2007Jufeng Software Institute,基于规则的查询优化技术的三要素是：搜索空间、代价估计技术和搜索算法 多连接查询优化的常用搜索空间是左线性树、右线性树、浓密树 代价估计技术通常考虑I/O开销、存储开销、计算开销和通信开销四个要素，并且根据它们的重要程度加不同的权值 四类搜索算法 - 穷尽、启发式、局部随机、全局随机法的特点,本 讲 主 要 目 标, 2007Jufeng Software Institute,一. 启发式查询优化 二. 多连接查询优化,内容提纲, 2007Jufeng Softw

3、are Institute,启发式 查询优化, 2007Jufeng Software Institute,启发式查询优化,精确查询优化方法面临的困境 导致QEP低效的原因 逻辑优化的一般准则 关系代数等价变换规则 关系代数表达式的优化算法 实例, 2007Jufeng Software Institute,启发式查询优化,精确查询优化方法面临的困境 策略空间随查询的复杂性程度成指数级增长 代价估计函数复杂，计算查询执行计划的代价需要大量的时间 为了计算查询执行计划的代价，需要保存大量的统计信息 ，而且这些统计信息需要随表的数据变化而更新。, 2007Jufeng Software Insti

4、tute,启发式查询优化,精确查询优化方法面临的困境,能否找到某种优化方法，不基于代价估计技术，不需要对查询执行计划进行代价比较，而在较快的时间内找到好的查询执行计划？,启发式优化方法, 2007Jufeng Software Institute,启发式查询优化,导致QEP低效的原因 冗余计算 内外存交换次数太多,提高效率的途径（启发式优化的目标） l 减少中间结果的大小 l 减少不相关的数据运算 l 减少扫描表的次数 l 减少不相关元组的读取, 2007Jufeng Software Institute,启发式查询优化,逻辑优化的一般准则 选择操作尽可能先做 目的：大大减少中间结果的大小 执

5、行连接前对关系适当地预处理 两种预处理方法：在连接属性上建立索引和对关系排序 目的： 减少扫描表的次数 减少不相关元组的读取, 2007Jufeng Software Institute,实例,索引连接方法： (1)在SC上建立S#的索引； (2)对S中的每一个元组，由S#值通过SC的索引查找相应的SC元组； (3)把这些SC元组和S元组连接起来； 效率：S和SC表均只要扫描一遍。处理时间是两个关系大小的线性函数。,排序连接方法： (1)对S和SC按S#排序； (2)取S表中第一个S#，依次扫描SC表中具有相同S#的元组，把它们连接起来； (3)当扫描到S#不相同的第一个SC元组时，返回S表扫

6、描它的下一个元组，再扫描SC表中具有相同S#的元组，把它们连接起来； 效率：S和SC表均只要扫描一遍。处理时间要加上对两个表排序的时间。,例如： S SC. 两种预处理方法：, 2007Jufeng Software Institute,启发式查询优化,逻辑优化的一般准则 投影运算和选择运算同时进行 目的：避免重复扫描表 投影同其前或其后的双目运算结合起来 目的：避免重复扫描表, 2007Jufeng Software Institute,启发式查询优化,逻辑优化的一般准则 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算 目的：减少内外存交换的信息量 找出公共子表达式 目的：减少

7、计算量, 2007Jufeng Software Institute,启发式查询优化,关系代数等价变换规则,关系代数等价变换规则是启发式方法的依据。 连接、笛卡尔积交换律 设E1和E2是关系代数表达式，F是连接运算的条件，则有： E1 E2 E2 E1 E1 E2 E2 E1,E1 E2 E2 E1,F,F, 2007Jufeng Software Institute,启发式查询优化,关系代数等价变换规则,连接、笛卡尔积结合律 （E1 E2 ） E3 = E1（E2 E3） （E1 E2 ） E3 = E1 （E2 E3）,F1,F1,F2,F2,（E1 E2 ） E3 = E1 （E2 E3

8、）, 2007Jufeng Software Institute,启发式查询优化,关系代数等价变换规则,笛卡尔积的交换律和结合律是正确的，连接运算的交换律和结合律也正确吗？,？, 2007Jufeng Software Institute,启发式查询优化,关系代数等价变换规则 例如：S SC C 表达式中的代表自然连接，若利用交换律，交换SC和 C，就变换成 S C SC 表达式利用结合率，就变换成 （S C） SC 在表达式中，关系S和C没有公共属性，所以不可能进行自然连接操作，即自然连接操作构成的关系代数表达式如果基于公式1和2进行变换，就会出现问题。, 2007Jufeng Softwa

9、re Institute,启发式查询优化,关系代数等价变换规则 投影的串接定律 A1，A2，An(B1，B2，Bm (E) A1，A2，An(E) 这里， E是关系代数表达式，Ai（i = 1,2, ,n），Bj（j = 1,2, ,m）是属性名，且 A1，A2，An 构成 B1，B2，Bm 的子集。, 2007Jufeng Software Institute,启发式查询优化,关系代数等价变换规则 选择的串接定律 F1（F2（E） F1F2（E）, 2007Jufeng Software Institute,启发式查询优化,关系代数等价变换规则,选择与投影的交换律 F(A1，A2，An (E

10、)A1，A2，An(F (E) 这里，选择条件F只涉及属性A1，An。 一般规则为： A1，A2，An(F (E) A1，A2，An(F（A1，A2，An ,B1，B2，Bm (E), 2007Jufeng Software Institute,启发式查询优化,关系代数等价变换规则,选择与笛卡尔积交换律 如果F中涉及的属性都是E1中的属性，则 F（E1 E2） F（E1） E2 如果F = F1F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则 F（E1 E2） F1（E1） F2（E2） 如果F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则 F（E1 E2） F2（F1（E

11、1）E2） 它使部分选择在笛卡尔积前先做。, 2007Jufeng Software Institute,启发式查询优化,关系代数等价变换规则,选择与并的交换 F（E1E2） F（E1）F（E2） 选择与差运算的交换 F（E1 - E2） F（E1）- F（E2）, 2007Jufeng Software Institute,启发式查询优化,关系代数等价变换规则,投影与笛卡尔积的交换 设是E1和E2两个关系代数表达式，A1，A2，An 是E1的属性，B1，B2，Bm是E2的属性，则 A1，A2，An, B1，B2，Bm（E1 E2） A1，A2，An（E1） B1，B2，Bm（E2）, 200

12、7Jufeng Software Institute,启发式查询优化,关系代数等价变换规则,投影与并的交换 A1，A2，An（E1 E2） A1，A2，An（E1） A1，A2，An（E2）, 2007Jufeng Software Institute,启发式查询优化,关系代数表达式的优化算法 常用的关系代数表达式的启发式方法 针对一棵语法树，有下列常用的启发式： 选择操作下移 投影操作下移 选择和投影的串接合并 内结点分组, 2007Jufeng Software Institute,启发式查询优化,关系代数表达式的优化算法 关系代数表达式的优化算法 算法：关系表达式的优化 输入：一个表达式

13、的语法树 输出：计算该表达式的程序, 2007Jufeng Software Institute,启发式查询优化,关系代数表达式的优化算法 方法： (1)利用规则4进行选择条件分解 (2)对每一个选择，利用规则4-8尽量把它移到树的叶端 (3)对每一个投影，利用规则3，9，10，5中的一般形式尽可能把它下移移到树的叶端 (4)利用规则3-5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影 (5)把上述得到的语法树的内结点分组 (6) 生成一个程序，每组结点的计算是程序中的一步, 2007Jufeng Software Institute,启发式查询优化,实例,设有三个关系 A（

14、a1,a2,a3,）、 B（b1,b2,b3, ）、C（a1,b1,c1,c2, ） 现在其上有一个查询请求： SELECT A.a1 FROM A，B，C WHERE A. a1 =C. a1 AND B. b1 =C. b1 AND f(c1), 2007Jufeng Software Institute,启发式查询优化,实例,首先，将查询语言转换成语法树：,SELECT A.a1 FROM A，B，C WHERE A. a1 =C. a1 AND B. b1 =C. b1 AND f(c1), 2007Jufeng Software Institute,启发式查询优化,选择条件分解（规则

15、4）, 2007Jufeng Software Institute,启发式查询优化,选择操作下移 选择操作下移过程中，遇到： 选择操作，则直接下移（规则4） 投影操作，则直接下移（规则5） 双目运算，则下移到相关分支，若同时与两个分支相关，则不下移（规则6，7，8） 将选择操作尽量朝叶端移动。, 2007Jufeng Software Institute,启发式查询优化,选择操作下移, 2007Jufeng Software Institute,启发式查询优化,选择操作下移,下移 B. b1 =C. b1, 2007Jufeng Software Institute,启发式查询优化,投影操作下

16、移 投影操作下移过程中，遇到： 选择操作，则(根据规则5)分两种情况： （1）若选择条件在投影属性范围内，则直接下移 （2）否则，在选择操作下增加一个投影操作，该投影操作包含选择操作涉及的属性与原投影属性，并继续下移新投影操作 投影操作，则合并（规则3） 双目运算，则下移到相关分支（规则9，10） 将投影操作尽量朝叶端移动。, 2007Jufeng Software Institute,启发式查询优化,投影操作下移,下移 a1, 2007Jufeng Software Institute,启发式查询优化,投影操作下移,下移 a1,两个a1都 继续下移, 2007Jufeng Software

17、Institute,启发式查询优化,投影操作下移,下移 a1, 2007Jufeng Software Institute,启发式查询优化,投影操作下移,下移 a1,b1,A.a1 =C. a1, 2007Jufeng Software Institute,启发式查询优化,投影操作下移,下移 a1,b1, 2007Jufeng Software Institute,启发式查询优化,选择和投影的串接合并（规则5）,串接合并, 2007Jufeng Software Institute,启发式查询优化,内结点分组,A.a1 =C. a1,f(c1),C,B,A,b1, 2007Jufeng Sof

18、tware Institute,Questions?, 2007Jufeng Software Institute,多连接 查询优化, 2007Jufeng Software Institute,多连接查询优化,多连接查询优化的必要性 多连接查询优化的概念 搜索空间 代价估计技术 搜索算法, 2007Jufeng Software Institute,多连接查询优化,多连接查询优化的必要性,例.S、SC与C三个关系的自然连接，假定： S有10,000个元组，10个属性; SC有300,000个元组，3个属性; C有2,000个元组，4个属性。,有必要进行多连接查询优化吗？, 2007Jufen

19、g Software Institute,多连接查询优化,列举三种连接操作顺序： （1）(SSC) C （2） S(SCC)(结合律) （3） S(CSC)(交换律),S (10,000),SC (300,000),C (2,000),三个表的大小图示,中间表的大小差别,？,两张连接表的左右顺序差别, 2007Jufeng Software Institute,多连接查询优化,三种连接操作顺序： （1）(SSC)C （2） S(SCC) （3） S(CSC),SSC (300,000元组 12个属性),SCC (300,000元组 6个属性),中间表的大小图示,中间表的大小 有差别！, 200

20、7Jufeng Software Institute,多连接查询优化,CSC,结论,两张连接表的左右 顺序对效率有影响！,SC (300,000元组 300块),C (2,000元组 2块),比较SCC与CSC,输入块数：300 + 150 * 2 = 600,输入块数：2 + 1 * 300 = 302,SCC需要输入的块数 比 CSC输入的块数多！,SCC, 2007Jufeng Software Institute,多连接查询优化的定义 简称MJQO，就是对于由N个（N 10）关系的连接操作构成的一个查询请求，在合理的时间内找到一个最佳的查询执行计划（QEP）。,多连接查询优化,多连接查

21、询优化的概念, 2007Jufeng Software Institute,多连接查询的表示形式 查询图 JOIN树 操作树,S,SC,图1 自然连接操作的查询图,C#,S#,C,join,join,SC,S,C,图2 join树,Sort-merge,Nested-loop,SC,S,C,图3 棵操作树,多连接查询优化,多连接查询优化的概念, 2007Jufeng Software Institute,多连接查询优化,多连接查询优化的基本原理,多连接查询优化的概念, 2007Jufeng Software Institute,多连接查询优化,多连接查询优化的基本原理 逻辑优化的基本原理 逻辑

22、优化根据的是join操作的等价变换规则 （1）笛卡尔积的交换律 E1E2 = E2 E1 （2）笛卡尔积的结合律（E1E2）E3 = E1（E2E3） 物理优化的基本原理 物理优化就是根据查询执行引擎提供的实现join操作的各种物理操作，选取合适的物理操作，构成QEP，然后利用代价估计函数，计算QEP的代价，从中找出具有最小代价的QEP。,多连接查询优化的概念, 2007Jufeng Software Institute,多连接查询优化,多连接查询优化的概念,查询优化的三个子问题,搜索空间的选取 代价估计模型的准确程度 搜索算法的有效性, 2007Jufeng Software Institu

23、te,策略空间和搜索空间 策略空间 一个多连接查询对应的所有QEP构成了该查询的策略空间。策略空间的大小取决于遵循的等价转换规则集和查询执行引擎支持的物理操作集。 搜索空间 策略空间一般很大，因此，查询优化算法通常在最佳QEP可能存在的一个策略空间子集中进行搜索，这个子集就称为搜索空间。,多连接查询优化,搜索空间, 2007Jufeng Software Institute,逻辑搜索空间,多连接查询优化,搜索空间, 2007Jufeng Software Institute,物理搜索空间 常用的实现自然连接操作的算法有三种： (1)嵌套循环法（nested loop join） (3)排序归并

24、法（sort-merge） (4)散列法（Hash） 如果查询执行引擎提供的连接操作的物理实现方法有M个，则对于每一个有N个连接操作的join树，都有NM个QEP与之对应。很显然，物理优化的策略空间也是非常大的,多连接查询优化,搜索空间, 2007Jufeng Software Institute,代价估计必须尽量精确有效 优化的好坏程度由代价估计的精确程度来决定，所以，代价估计必须尽量精确。既然查询优化过程中要频繁估计代价，因此，代价估计技术必须是有效的。,多连接查询优化,代价估计技术, 2007Jufeng Software Institute,查询执行计划的代价组成 访问外存的开销（简称

25、I/O开销） 存储开销：主要指存储中间文件的开销。 计算开销：主要指在内存（缓冲区）执行各类操作，如定位、排序、归并记录和计算属性值的开销。 通信开销：主要指分布式数据库系统中，数据在各结点之间传输的开销。 若已知I/O开销、存储开销、计算开销和通信开销分别为I、S、C和E，且分别取权值Pi，Ps，Pc和Pe，则QEP的代价为： cost = Pi * I+ Ps* S + Pc * C + Pe* E 其中 Pi + Ps + Pc + Pe = 1,多连接查询优化,代价估计技术, 2007Jufeng Software Institute,一个简单的逻辑代价模型,基本假设 属性值均匀分布

26、中间结果的记录数的总和 决定QEP的代价,其中，V(A,r)表示关系r中属性A的不同取值的个数,内部结点ti，ti = r join s，C 是关系r与关系s的公共属性,(1),(3),(2), 2007Jufeng Software Institute,穷尽搜索算法 启发式方法 局部随机搜索算法 全局随机搜索算法,多连接查询优化,搜索算法, 2007Jufeng Software Institute,多连接查询优化,搜索算法, 2007Jufeng Software Institute,多连接查询优化,搜索算法, 2007Jufeng Software Institute,穷尽搜索算法 穷尽

27、搜索算法就是穷尽搜索空间内的每一个QEP，以找到最佳的QEP。SYSTEM-R算法是一个典型的进行逻辑优化的穷尽搜索算法，目的是找到一个具有最小代价的join树。它以左线性树作为搜索空间，但它并不是逐个比较每一个join树，而是采用动态规划（dynamic programming）搜索方法。,多连接查询优化,搜索算法, 2007Jufeng Software Institute,穷尽搜索算法 SYSTEM-R算法基本思想是：先构造包括两个关系的最小代价join树，再构造包括三个关系的最小代价join树，直到把所有的关系都包括进去。即构造n个关系的最小代价join树时，利用前面已求得的n个关系的

28、子集构造的最小代价join树。很显然，在构造的过程中，需存储n个关系中任意i个关系的最小代价join树（i = 2,3,4, ，n），因此存储空间要求非常大。,多连接查询优化,搜索算法, 2007Jufeng Software Institute,穷尽搜索算法 SYSTEM-R算法的缺点是在构造join树的过程中要保留和处理非常多的join树构造块，这些构造块的个数随着join树的构造长度le每增加1，就相应地增加Cle+1n个构造块，而且构造块的大小也在不断地增大，这意味着巨大的CPU代价、存储空间和I/O代价。若N为一个查询包含的关系个数，则SYSTEM-R算法的最坏时间复杂性为O（2N）

29、，并要求极大的存储空间。当N超过一定值（这个值的大小受硬件的影响，所以，不同的文献指定为不同的值，如某些商用数据库产品指定为7，10， 16时，算法的效率太低，变得不可行。因此，该算法不能优化关系个数太大的查询。,多连接查询优化,搜索算法, 2007Jufeng Software Institute,启发式方法 启发式方法采用两段优化原理，启发式方法最大的特点是不需要比较QEP的代价，当然就不需要估算QEP的代价，从而，使代价估算开销为零。 逻辑启发式：避免笛卡尔积这种启发式信息。 启发式方法也是一种构造式搜索方法。根据启发式规则构造QEP的过程中，也在不断地缩小搜索空间，但与SYSTEM-R的动态规划方法不同的是，它不能保证缩小了的搜索空间中一定保存了最佳QEP，而只是使缩小了的搜索空间中的不好的解越来越少。,多连接查询优化,搜索算法, 2007