数据库_连接顺序的选择资料课件.ppt

《数据库_连接顺序的选择资料课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.6连接顺序的选择汇报人：XXX学号：XXXXXXXXX导师：XXX重点介绍核心思想连接树通过动态规划来选择连接顺序和分组带有更具体的代价函数的动态规划选择连接顺序的贪婪算法基于代价的优化问题为三个或三个以上关系的（自然）连接选择顺序核心思想RSTU连接树当有两个关系的连接时，需要对参数进行排序；通常，选择估计值比较小的参数作为左参数；此外，各个参数的大小往往具有重要且可辩别的差别；一个涉及连接的查询往往会涉及至少一个属性上的选择，并且这个选择会使得一个关系的估计值大大减小连接树SELECTgradeFROMStudent,CourseWHERECourse.SId=Student

2、.SIdANDsexLIKE'%male'gradesexLIKE'%male'CourseStudentStudent.SId=Course.SIdStudent(SId,Sname,sex,...)Course(CId,SId,Cname,grade)连接树a.左深树c.右深树b.浓密树RSTU由于有着参数顺序，并且对于n个事物会有n！种方法对其进行排序，当考虑树叶的各种可能的标识时，每棵树将会代表4！=24课不同的树。左深树-一趟算法内存构造情况使用一趟算法，以左参数作为构造用关系，构造左深树；首先在主存中保留R，并且在计算RS的过程中，保留结果；主存占用：B(R)+B()；在

3、计算出之后，继续与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.将四个关系划分为两对，将每一对进行连接，再将两个结果进行连接。带有更具体的代价函数的动态规划利用关系的大小作为代价可以简化动态规划算法的计算，但是也存在缺点：在计算中没有考虑连接的实际代价例子：如果有一个可能的连接涉及只有一个元组的关系R和另外一个在连接属性b上有索引的关系S，则该连接几乎不用花费任何时间。相反，如果S上没有

6、索引，则必须对它进行扫描，即使R是一个单元组的关系，这也会花费B(S)次磁盘I/O。只考虑R、S以及的大小的代价度量不可能区分这两种情况，所以在分组中利用的代价要么会估计过高，要么会被估计不足。带有更具体的代价函数的动态规划结合连接算法对动态规划算法进行改进首先，用磁盘I/O作为我们所采用的代价度量。计算的代价时，我们将R1的代价、R2的代价，以及利用可获得的最佳算法对这两个关系进行连接所需的最小代价相加。由于后一个代价一般依赖于R1和R2的大小，我们还必须计算这些大小的估值。Selinger风格优化不仅考虑算出连接结果的最小代价，还考虑生成以几个“感兴趣”的顺序中的任意一个顺序存储

7、的关系的最小代价。这些“感兴趣”的顺序包括任何对以后的顺序连接有利或者能够生成以用户所期望的顺序排列的全部查询的输出的顺序。选择连接顺序的贪婪算法贪婪算法是启发式算法最普遍的选择在这里我们只考虑左深树的贪婪算法“贪婪”思想：希望在树的每一级保持尽可能少的中间关系基础：以估计连接大小的关系对开始，这些关系的连接成为当前树介绍：在所有还没有包含在当前树的关系中，寻找与当前树进行连接能够生成估计大小最小的关系。以旧的当前树作为左参数，被选中的关系作为右参数来形成