数据库_连接顺序的选择

1、5.6 连接顺序的选择连接顺序的选择汇报人：汇报人：XXX学号：学号：XXXXXXXXX导师：导师：XXX重点介绍重点介绍n核心思想核心思想n连接树连接树n通过通过动态规划动态规划来来选择连接顺序选择连接顺序和和分组分组n带有带有更具体的代价函数更具体的代价函数的动态规划的动态规划n选择连接顺序的选择连接顺序的贪婪算法贪婪算法基于代价的优化问题基于代价的优化问题为三个或三个以上关系的（自然）连接为三个或三个以上关系的（自然）连接选择顺序选择顺序核心思想核心思想连接树连接树n当有两个关系的连接时，需要当有两个关系的连接时，需要对参数对参数进行进行排序排序；n通常，选择通常，选择估计值比较小估计值

2、比较小的参数作为的参数作为左参数左参数；n此外，各个参数的大小往往具有重要且可辩别的差别；此外，各个参数的大小往往具有重要且可辩别的差别；n一个涉及连接的查询往往会涉及一个涉及连接的查询往往会涉及至少一个属性至少一个属性上的选择，并且这个上的选择，并且这个选择会使得一个关系的估计值大大减小选择会使得一个关系的估计值大大减小连接树连接树SELECT gradeFROM Student, CourseWHERE Course.SId = Student.SId ANDsex LIKE %malegradesex LIKE %maleCourseStudentStudent.SId = Course

3、.SIdStudent (SId, Sname, sex,.)Course( CId, SId, Cname,grade)连接树连接树a. 左深树c. 右深树b. 浓密树 由于有着参数顺序，并且对于由于有着参数顺序，并且对于n n个事物会有个事物会有n n！种方法对其进！种方法对其进行排序，当考虑树叶的各种可能的标识时，每棵树将会代表行排序，当考虑树叶的各种可能的标识时，每棵树将会代表4 4！=24=24课不同的树。课不同的树。左深树左深树-一趟算法一趟算法内存构造情况内存构造情况n使用一趟算法，以使用一趟算法，以左参数左参数作为作为构造用关系构造用关系，构造左深树；，构造左深树；n首先在首先

4、在主存主存中中保留保留R R，并且在计算，并且在计算R SR S的过程中，的过程中，保留结果保留结果；n主存占用：主存占用：B(R)+B( )B(R)+B( )； n在计算出在计算出 之后，继续之后，继续与与T T进行连接，此时进行连接，此时B(R)B(R)不不在在需要需要，B(R)B(R)的原内存位置，将会被的原内存位置，将会被( ) T( ) T的结果的结果取代取代；n同样的在同样的在与与U U进行进行连接连接的时候，连接结果会的时候，连接结果会占用占用nB(R)+B(S)+B(T)B(R)+B(S)+B(T)左深树左深树-嵌套循环嵌套循环内存构造情况内存构造情况n使用使用嵌套循环嵌套循环

5、连接，构造左深树；连接，构造左深树；n迭代器迭代器( (每个连接关系每个连接关系都有一个都有一个迭代器迭代器) )；n关系关系已存储已存储( (R R、S S、T T、U U分别表示已存储关系，而非表达式分别表示已存储关系，而非表达式););n根迭代器根迭代器主动为左参数主动为左参数 获得获得主存大小的块主存大小的块，该块会主动，该块会主动与已经存储与已经存储的的全部全部U U进行连接，这个过程进行连接，这个过程只需要对只需要对U U进行进行扫描扫描，而，而不不用构建用构建。 n同理，为了获取同理，为了获取 的块，就要把的块，就要把 的块放的块放入内存，并且对入内存，并且对T T进行扫描。进行

6、扫描。n在所有的过程中，在所有的过程中，只有已存储的关系要读入几次只有已存储的关系要读入几次，当，当主主存不足以保留整个关系存不足以保留整个关系时，这种反复读入会出现时，这种反复读入会出现人为痕人为痕迹迹。 左深树作为可能的连接顺序的双重优点左深树作为可能的连接顺序的双重优点1. 用于连接的左深树可以用于连接的左深树可以和通用的连接算法进行很好的交互和通用的连接算法进行很好的交互，尤其是嵌，尤其是嵌套循环连接和一趟连接。套循环连接和一趟连接。- -基于左深树和这些算法的查询计划将会比非左深树所用的同样基于左深树和这些算法的查询计划将会比非左深树所用的同样的算法更有效。的算法更有效。2. 2.

7、有利于形成有效的计划有利于形成有效的计划。- -如果使用一趟连接，并且如果使用一趟连接，并且“构造用关系构造用关系”在左边，则任何时候在左边，则任何时候所需的内存都比同样关系用右深树或浓密树的情况要小。所需的内存都比同样关系用右深树或浓密树的情况要小。通过动态规划来选择连接顺序和分组通过动态规划来选择连接顺序和分组n动态规划思想：填写一个动态规划思想：填写一个代价表代价表，只记住只记住推出推出结论结论所需的所需的最少最少信息。信息。n动态规划方法：可以用于或者考虑动态规划方法：可以用于或者考虑所有顺序所有顺序，或者只考虑，或者只考虑特定子集特定子集。n对对 进行连接操作，要为包含进行连接操作，

8、要为包含n n个关系个关系中的中的一个或多个一个或多个关系关系的的每一个子集每一个子集构建带有一个表项的构建带有一个表项的表表，表中记录如下：，表中记录如下： 这些关系的连接的大小估计值这些关系的连接的大小估计值 计算这些关系的连接的最小代价计算这些关系的连接的最小代价 得到最小代价的表达式得到最小代价的表达式通过动态规划来选择连接顺序和分组通过动态规划来选择连接顺序和分组V(R,a)V(R,a)表示在关系表示在关系R R中，中，a a属性的大小属性的大小R R、S S、T T、U U每个关系每个关系有有10001000个元组个元组四个关系连接的通用方法：四个关系连接的通用方法：1.1.以可能

9、的最佳方法选择以可能的最佳方法选择三个进行连接，然后与第三个进行连接，然后与第四个进行连接；四个进行连接；2.2.将四个关系划分为两对，将四个关系划分为两对，将每一对进行连接，再将将每一对进行连接，再将两个结果进行连接。两个结果进行连接。带有带有更具体的代价函数更具体的代价函数的动态规划的动态规划n利用关系的大小作为代价可以简化动态规划算法的计算，但是也存利用关系的大小作为代价可以简化动态规划算法的计算，但是也存在缺点：在缺点：在计算中没有考虑连接的实际代价在计算中没有考虑连接的实际代价n例子：例子： 如果有一个可能的连接如果有一个可能的连接 涉及只有一个元组的关系涉及只有一个元组的关系R R

10、和另外和另外一个在连接属性一个在连接属性b b上有索引的关系上有索引的关系S S，则该连接几乎不用花费任何时间。，则该连接几乎不用花费任何时间。 相反，如果相反，如果S S上没有索引，则必须对它进行扫描，即使上没有索引，则必须对它进行扫描，即使R R是一个单元组的关系，是一个单元组的关系，这也会花费这也会花费B(S)B(S)次磁盘次磁盘I/OI/O。 只考虑只考虑R R、S S以及以及 的大小的代价度量不可能区分这两种情况，所以在分的大小的代价度量不可能区分这两种情况，所以在分组中利用组中利用 的代价要么会估计过高，要么会被估计不足。的代价要么会估计过高，要么会被估计不足。带有带有更具体的代价

11、函数更具体的代价函数的动态规划的动态规划n结合结合连接算法连接算法对对动态规划动态规划算法进行算法进行改进改进 首先，首先，用磁盘用磁盘I/OI/O作为我们所采用的代价度量作为我们所采用的代价度量。计算。计算 的代价时，我们的代价时，我们将将R1R1的代价、的代价、R2R2的代价，以及利用可获得的最佳算法对这两个关系进行连接的代价，以及利用可获得的最佳算法对这两个关系进行连接所需的最小代价相加。由于后一个代价一般依赖于所需的最小代价相加。由于后一个代价一般依赖于R1R1和和R2R2的大小，我们还必的大小，我们还必须计算这些大小的估值。须计算这些大小的估值。 SelingerSelinger风格

12、优化风格优化不仅考虑算出连接结果的最小代价，还考虑生成以几个不仅考虑算出连接结果的最小代价，还考虑生成以几个“感兴趣感兴趣”的顺序中的任意一个顺序存储的关系的最小代价。这些的顺序中的任意一个顺序存储的关系的最小代价。这些“感兴趣感兴趣”的顺序包括任何对以后的顺序连接有利或者能够生成以用户所期望的顺序排的顺序包括任何对以后的顺序连接有利或者能够生成以用户所期望的顺序排列的全部查询的输出的顺序。列的全部查询的输出的顺序。选择连接顺序的贪婪算法选择连接顺序的贪婪算法n贪婪算法是贪婪算法是启发式算法启发式算法最普遍的选择最普遍的选择n在这里我们在这里我们只考虑左深树只考虑左深树的贪婪算法的贪婪算法n“

13、贪婪贪婪”思想：希望在树的思想：希望在树的每一级每一级保持保持尽可能少尽可能少的的中间关系中间关系n基础：以基础：以估计连接大小估计连接大小的的关系对关系对开始，这些关系的连接成为开始，这些关系的连接成为当前树当前树n介绍：在所有还没有包含在当前树的关系中，寻找与当前树进行连介绍：在所有还没有包含在当前树的关系中，寻找与当前树进行连接能够生成接能够生成估计大小估计大小最小最小的关系。以的关系。以旧的当前树旧的当前树作为作为左参数左参数，被选被选中的关系中的关系作为作为右参数右参数来形成新的当前树。来形成新的当前树。选择连接顺序的贪婪算法选择连接顺序的贪婪算法n基本步骤是基本步骤是找出连接结果最小的一对关系找出连接结果最小的一对关系。n从图中可以计算从图中可以计算 代价为代价为10001000，为最小，作为，为最小，作为“当前树当前树”n下一步考虑是否将下一步考虑是否将R R和和S S连接进树，比较连接进树，比较 和和 的大小，前的大小，前者者1000010000，后者，后者20002000，所以，所以 作为当前树作为当前树n最后已经没有选择了，就是要连接最后已经没有选择了，就是要连接R R，在连接之后总的代价为，