《数据库连接顺序的选择课件》由会员分享，可在线阅读，更多相关《数据库连接顺序的选择课件（16页珍藏版）》请在金锄头文库上搜索。
1、5.6 连接顺序的选择,汇报人：XXX 学号：XXXXXXXXX 导师：XXX,重点介绍,核心思想 连接树 通过动态规划来选择连接顺序和分组 带有更具体的代价函数的动态规划 选择连接顺序的贪婪算法,基于代价的优化问题,为三个或三个以上关系的（自然）连接 选择顺序,核心思想,连接树,当有两个关系的连接时，需要对参数进行排序； 通常，选择估计值比较小的参数作为左参数； 此外，各个参数的大小往往具有重要且可辩别的差别； 一个涉及连接的查询往往会涉及至少一个属性上的选择，并且这个选择会使得一个关系的估计值大大减小,连接树,SELECT grade FROM Student, Course WHERE
2、Course.SId = Student.SId AND sex LIKE %male,grade,sex LIKE %male,Course,Student,Student.SId = Course.SId,Student (SId, Sname, sex,.) Course( CId, SId, Cname,grade),连接树,由于有着参数顺序，并且对于n个事物会有n！种方法对其进行排序，当考虑树叶的各种可能的标识时，每棵树将会代表 4！=24课不同的树。,左深树-一趟算法内存构造情况,使用一趟算法，以左参数作为构造用关系，构造左深树； 首先在主存中保留R，并且在计算R S的过程中，保留
3、结果； 主存占用：B(R)+B( )； 在计算出 之后，继续与T进行连接，此时B(R)不在需要，B(R)的原内存位置，将会被( ) T的结果取代； 同样的在与U进行连接的时候，连接结果会占用 B(R)+B(S)+B(T),左深树-嵌套循环内存构造情况,使用嵌套循环连接，构造左深树； 迭代器(每个连接关系都有一个迭代器)； 关系已存储(R、S、T、U分别表示已存储关系，而非表达式); 根迭代器主动为左参数 获得主存大小的块，该块会主动与已经存储的全部U进行连接，这个过程只需要对U进行扫描，而不用构建。,同理，为了获取 的块，就要把 的块放入内存，并且对T进行扫描。 在所有的过程中，只有已存储的关
4、系要读入几次，当主存不足以保留整个关系时，这种反复读入会出现人为痕迹。,左深树作为可能的连接顺序的双重优点,1. 用于连接的左深树可以和通用的连接算法进行很好的交互，尤其是嵌套循环连接和一趟连接。 -基于左深树和这些算法的查询计划将会比非左深树所用的同样的算法更有效。,2. 有利于形成有效的计划。 -如果使用一趟连接，并且“构造用关系”在左边，则任何时候所需的内存都比同样关系用右深树或浓密树的情况要小。,通过动态规划来选择连接顺序和分组,动态规划思想：填写一个代价表，只记住推出结论所需的最少信息。 动态规划方法：可以用于或者考虑所有顺序，或者只考虑特定子集。 对 进行连接操作，要为包含n个关系
5、中的一个或多个关系的每一个子集构建带有一个表项的表，表中记录如下： 这些关系的连接的大小估计值 计算这些关系的连接的最小代价 得到最小代价的表达式,通过动态规划来选择连接顺序和分组,V(R,a)表示在关系R中，a属性的大小,R、S、T、U每个关系有1000个元组,四个关系连接的通用方法： 1.以可能的最佳方法选择三个进行连接，然后与第四个进行连接； 2.将四个关系划分为两对，将每一对进行连接，再将两个结果进行连接。,带有更具体的代价函数的动态规划,利用关系的大小作为代价可以简化动态规划算法的计算，但是也存在缺点：在计算中没有考虑连接的实际代价 例子： 如果有一个可能的连接 涉及只有一个元组的关
6、系R和另外一个在连接属性b上有索引的关系S，则该连接几乎不用花费任何时间。 相反，如果S上没有索引，则必须对它进行扫描，即使R是一个单元组的关系，这也会花费B(S)次磁盘I/O。 只考虑R、S以及 的大小的代价度量不可能区分这两种情况，所以在分组中利用 的代价要么会估计过高，要么会被估计不足。,带有更具体的代价函数的动态规划,结合连接算法对动态规划算法进行改进 首先，用磁盘I/O作为我们所采用的代价度量。计算 的代价时，我们将R1的代价、R2的代价，以及利用可获得的最佳算法对这两个关系进行连接所需的最小代价相加。由于后一个代价一般依赖于R1和R2的大小，我们还必须计算这些大小的估值。 Seli
7、nger风格优化不仅考虑算出连接结果的最小代价，还考虑生成以几个“感兴趣”的顺序中的任意一个顺序存储的关系的最小代价。这些“感兴趣”的顺序包括任何对以后的顺序连接有利或者能够生成以用户所期望的顺序排列的全部查询的输出的顺序。,选择连接顺序的贪婪算法,贪婪算法是启发式算法最普遍的选择 在这里我们只考虑左深树的贪婪算法 “贪婪”思想：希望在树的每一级保持尽可能少的中间关系 基础：以估计连接大小的关系对开始，这些关系的连接成为当前树 介绍：在所有还没有包含在当前树的关系中，寻找与当前树进行连接能够生成估计大小最小的关系。以旧的当前树作为左参数，被选中的关系作为右参数来形成新的当前树。,选择连接顺序的贪婪算法,基本步骤是找出连接结果最小的一对关系。 从图中可以计算 代价为1000，为最小，作为“当前树” 下一步考虑是否将R和S连接进树，比较 和 的大小，前者10000，后者2000，所以 作为当前树 最后已经没有选择了，就是要连接R，在连接之后总的代价为3000，即两个中间关系大小的和。 最终取得的结果与前面动态规划算法所得到的树是相同的。 贪婪算法寻找最佳结果会有失败的情况，而动态规划能够保证找到最佳结果。,R、S、T、U每个关系有1000个元组,Thank you ！,
