数据库_连接顺序的选择合编.ppt

HAPTER 5.6 连接顺序的选择 汇报人：XXX 学号：XXXXXXXXX 导师：XXX 重点介绍 核心思想 连接树 通过动态规划来选择连接顺序和分组 带有更具体的代价函数的动态规划 选择连接顺序的贪婪算法 基于代价的优化问题 为三个或三个以上关系的（自然）连接 选择顺序 连接树 当有两个关系的连接时，需要对参数进行排序； 通常，选择估计值比较小的参数作为左参数； 此外，各个参数的大小往往具有重要且可辩别的差别； 一个涉及连接的查询往往会涉及至少一个属性上的选择，并且这个选择会使得一个关系的估计值大大减小 连接树 SELECT grade FROM Student, Course WHERE 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) 连接树 a. 左深树 c. 右深树 b. 浓密树 由于有着参数顺序，并且对于n个事物会有n！种方法对其进行排序，当考虑树叶的各种可能的标识时，每棵树将会代表 4！=24课不同的树。 左深树-一趟算法内存构造情况 使用一趟算法，以左参数作为构造用关系，构造左深树； 首先在主存中保留R，并且在计算R S的过程中，保留结果； 主存占用：B(R)+B( )； 在计算出 之后，继续与T进行连接，此时B(R)不在需要，B(R)的原内存位置，将会被( ) T的结果取代； 同样的在与U进行连接的时候，连接结果会占用 B(R)+B(S)+B(T) 左深树-嵌套循环内存构造情况 使用嵌套循环连接，构造左深树； 迭代器(每个连接关系都有一个迭代器)； 关系已存储(R、S、T、U分别表示已存储关系，而非表达式); 根迭代器主动为左参数 获得主存大小的块，该块会主动与已经存储的全部U进行连接，这个过程只需要对U进行扫描，而不用构建。 同理，为了获取 的块，就要把 的块放入内存，并且对T进行扫描。 在所有的过程中，只有已存储的关系要读入几次，当主存不足以保留整个关系时，这种反复读入会出现人为痕迹。 左深树作为可能的连接顺序的双重优点 1. 用于连接的左深树可以和通用的连接算法进行很好的交互，尤其是嵌套循环连接和一趟连接。 -基于左深树和这些算法的查询计划将会比非左深树所用的同样的算法更有效。 2. 有利于形成有效的计划。 -如果使用一趟连接，并且“构造用关系”在左边，则任何时候所需的内存都比同样关系用右深树或浓密树的情况要小。 通过动态规划来选择连接顺序和分组 动态规划思想：填写一个代价表，只记住推出结论所需的最少信息。 动态规划方法：可以用于或者考虑所有顺序，或者只考虑特定子集。 对 进行连接操作，要为包含n个关系中的一个或多个关系的每一个子集构建带有一个表项的表，表中记录如下： 这些关系的连接的大小估计值 计算这些关系的连接的最小代价 得到最小代价的表达式 通过动态规划来选择连接顺序和分组 V(R,a)表示在关系R中，a属性的大小 R、S、T、U每个关系有1000个元组 四个关系连接的通用方法： 1.以可能的最佳方法选择三个进行连接，然后与第四个进行连接； 2.将四个关系划分为两对，将每一对进行连接，再将两个结果进行连接。 带有更具体的代价函数的动态规划 利用关系的大小作为代价可以简化动态规划算法的计算，但是也存在缺点：在计算中没有考虑连接的实际代价 例子： 如果有一个可能的连接 涉及只有一个元组的关系R和另外一个在连接属性b上有索引的关系S，则该连接几乎不用花费任何时间。 相反，如果S上没有索引，则必须对它进行扫描，即使R是一个单元组的关系，这也会花费B(S)次磁盘I/O。 只考虑R、S以及 的大小的代价度量不可能区分这两种情况，所以在分组中利用 的代价要么会估计过高，要么会被估计不足。 HAPTER