时间：2022-12-12 08:30:01 | 来源：信息时代
时间：2022-12-12 08:30:01 来源：信息时代
并行嵌套循环连接算法 : 采用嵌套循环连接的方法所构成的一种并行算法,该算法首先把两个被连接关系中的小关系均匀地分布到多个处理机,然后把大关系的元组以流水线方式向各处理机广播,各处理机并行地完成连接操作。传统的嵌套循环连接算法必须存取两个关系的笛卡儿乘积,在顺序计算机环境中一直被认为是效率较低的连接算法。然而,嵌套循环连接算法很容易并行化,而且可通过附加的计算减少多处理机间的通信开销。并行嵌套循环连接算法的输入为:处理机个数P; 分布在P个处理机上的关系R、S,其初始数据偏斜度分别为sR和sS; 连接属性A。算法输出为关系R和S的连接结果。算法主要思想如下: 首先将关系S均匀地分布到多个处理机,设Si是S在结点i上的子集合; 各处理机Pi并行地按照连接属性值排序Si: 然后各处理机以流水线方式向P个处理机广播R的元组; 最后各处理机Pi以流水线方式并行地接收并按连接属性值排序其他处理机发来的R元组,对磁盘上的Si和内存中的R元组做合并连接。
在具有大量处理机的系统中或在R和S的大小差别非常大的情况下,并行嵌套循环连接算法的效率高于其他并行连接算法。
在线咨询
