时间：2022-11-07 06:30:01 | 来源：信息时代
时间：2022-11-07 06:30:01 来源：信息时代
嵌套循环连接 : 用双层循环来实现连接的算法,包括基于元组的连接方法和基于块的连接方法。它对内存要求较小。
1.基于元组的嵌套循环连接方法
对于R(X,Y)和S(Y,Z)的基于元组的嵌套循环连接方法(假设连接属性为Y),其连接过程为:
首先在外层循环表(R)中找到第一条元组,然后从头开始扫描内层循环表(S)中的每一条元组,逐一查找满足连接条件的元组,找到后就将外层循环表中的第一条元组与该元组拼接起来,形成结果表中的一条元组。
内层循环表(S)全部查找完后,再找外层循环表(R)中第二条元组,然后再从头开始扫描内层循环表(S),逐一查找满足连接条件的元组,找到后就将外层循环表(R)中的第二条元组与该元组拼接起来,形成结果表中一条元组。
重复上述操作,直到外层循环表(R)中的全部元组都处理完毕为止。
具体算法如下:
FOR each tuple r in R DO
FOR each tuple s in S DO
IF s and r join to make a tuple t THEN
output t;
很明显,基于元组的嵌套循环连接方法其I/O代价很大,对于外层关系R的每条元组,都要从头读一遍内层关系,即内层关系读取的遍数等于外层关系的元组个数。假设B(R)和B(S)分别代表关系R和S占用的磁盘块数,T(R)和T(S)分别代表关系R和S的元组数,假设R是较小的关系,即B(R)≤B(S),则基于元组的嵌套循环连接方法的磁盘I/O次数为:T(R)+T(R)*B(S)。
2.基于块的嵌套循环连接方法
如果对作为操作对象的两个关系的访问均以块为单位,并用尽可能多的内存来存储外层循环表(R)的元组,将S的每一条元组与能装入内存的尽可能多的R元组连接,则可以减少读取R表的遍数,从而节省连接操作的代价。假设有M块内存缓冲区,其连接过程为:
(1)把外层循环表(R)尽可能多地读入内存(比如读入M-1块),读入一块内层循环表(S)。①对于R在内存中的第一条元组,从头开始扫描内层循环表(S)在内存中的每一条元组,逐一查找满足连接条件的元组,找到后就将外层循环表中的第一条元组与该元组拼接起来,形成结果表中一条元组。②内层循环表(S)在内存中的部分全部查找完后,再找外层循环表(R)在内存中第二条元组,然后再从头开始扫描内层循环表(S),逐一查找满足连接条件的元组,找到后就将外层循环表(R)中的第二条元组与该元组拼接起来,形成结果表中一条元组。③重复上述操作,直到外层循环表(R)在内存部分的全部元组都处理完毕为止。
(2) 内层表S的在内存中的数据块淘汰,读入S的下一块数据,重复操作1,直到内层循环表(S)全部处理完毕为止。
(3)外层表R的M-1块数据全部淘汰,再读入M—1块数据进来,重复操作1和2,直到外层循环表(R)的全部元组都处理完毕为止。
假设B(R)和B(S)分别代表关系R和S占用的磁盘块数,其中R是较小的关系,即B(R)≤B(S),则基于块的嵌套循环连接方法的磁盘I/O次数为
B(R)/M-1(M-1+B(S))或B(R)+B(R)B(S)/M-1。
在线咨询
