并行Hash连接算法(数据库)

时间：2022-12-11 20:30:02 | 来源：信息时代

时间：2022-12-11 20:30:02 来源：信息时代

    并行Hash连接算法 : 把Hash连接算法并行化的一种算法。若Hash函数能把连接关系划分为大小基本相同的子集合,则并行Hash连接算法具有线性时间复杂性。主要有三种具有代表性的并行Hash连接算法。
1.简单并行Hash连接算法
简单Hash连接算法分为两个阶段。第一阶段是数据划分阶段。这一阶段使用Hash函数把连接关系R和S划分为P个可独立连接的子集合对,每对子集合送到唯一一个处理机。第二阶段是连接阶段。在这一阶段,每个处理机执行分配给它的可独立连接子集合对的连接操作,P个处理机并行地完成R和S的连接。简单Hash连接算法simple-hash-join的输入为: 处理机个数P; 分布于P个处理机上的关系R和S;R_i和S_i是处理机P_i上的子集合;Hash函数H₁和H₂; 每个处理机可用内存页数m。算法输出是关系R和S的连接结果。算法主要思想是:首先各处理器P_i并行地用H₁把S_i和R_i划分为P个子集合,并将Hash值为j的元组送处理机P_j(设处理机P_i上的R_i和S_i的子集合分别记作HR_i和HS_i),同时接收其他处理机发送来的元组; 完成关系划分后,各处理器P_i并行地使用H₂,把HR_i和HS_i划分为k≥|HR_i|/m个子集合,其中HR_i的Hash值为j的元组存入子集合HR_i,j,HS_i的Hash值为j的元组存入子集合HS_i,j;然后各处理器P_i并行地在内存中建立HR_i,j的Hash表并使用HS_i,j的每个元组匹配HR_i,j的Hash表,完成HR_i,j和HS_i,j的连接。算法中的k应该充分大,降低Hash表超出P个处理机的可用存储空间总量的概率。
2.并行Grace-Hash连接算法
并行Grace-Hash连接算法不要求每个处理机都具有一个磁盘存储器。设并行计算机系统具有P+L个处理机,其中,P个处理机具有磁盘存储器,L个处理机不具有磁盘存储器。
该算法分为两个阶段。第一阶段,使用同样的Hash函数把关系R和S分别划分为m个可独立连接的子集合对。第二阶段,并行连接R和S的m个可独立连接子集合,完成R和S的连接。子集合的个数m的选择应该足够大,使得小关系(比如说R)的每个子集合的大小不超过所有处理机的存储空间总量。这样可保证在连接每对可独立连接子集合的时候,Hash表可以建立在存储器中,减少磁盘读写时间。并行Grace-Hash连接算法在关系划分阶段使用Hash函数H₁在P个有磁盘处理机之间划分连接关系;在并行连接可独立连接子集合阶段,每个处理机使用Hash函数H₂在P+L个处理机之间分布连接关系的子集合。算法的输入为: 分布于P个处理机上的关系R和S,R_i和S_i是处理机P_i上的子集合;Hash函数H₁和H₂;所有处理机可用内存空间的总页数M;子集合数m≥|R|/M(假设R的数据量小于S的数据量)。算法输出是关系R和S的连接结果。算法主要思想如下: 首先各处理机P_i并行地使用H₁把R_i划分为m个子集合,R_i中Hash值为j的元组属于HR_j分布到P个有磁盘存储器的处理机; 然后各处理机P_i并行地使用H₁把S_i划分为m个子集合,S_i中Hash值为j的元组属于HR_j分布到P个有磁盘存储器的处理机;对于m个子集合每个分组HR_i和HS_i,P个有磁盘处理机先使用H₂并行地把HR_i分布到P+L个处理机,在P+L个处理机的内存中建立HR_i的Hash表,然后P个有磁盘处理机再使用H₂按照流水线并行方式向P+L个处理机发送HS_i的元组: 最后P+L个处理器以流水线方式接收HS_i的元组,匹配HR_i的Hash表,连接HS_i和HR_i计算连接结果。
3. 并行Hybrid-Hash连接算法
该算法是对并行Grace-Hash连接算法的改进,不把R和S的第一对可独立连接子集合写入磁盘,而直接在内存中连接。
假定系统具有P个有磁盘处理机和L个无磁盘处理机。并行Hybrid-Hash连接算法首先使用Hash函数H₁把R划分成m个子集合,并把第一个子集合使用Hash函数H₂分布到无磁盘处理机,其他子集合存入有磁盘处理机; 然后使用Hash函数H₁划分S,并使用Hash函数H₂把第一个子集合分布到无磁盘结点,与R的第一个子集合连接,其余子集合存入具有磁盘的处理机。并行Hybrid-Hash连接算法实现了数据划分和第1个子集合对连接的并行执行,提高了运行速度。