Block Nested Loop Join

Question

Could Anybody tell me the concept of this block nested join?

I have a dount regarding that whether we have to check each block of S for each block of R or each record of R....If R is the outer Loop

Answer 1

The major difference between nested loop join which is normal and default one and block nested loop join is that :

a) In default nested loop join , for each tuple of 1st and outer relation in this question let it be r(R) , each of the tuple of the second relation s(S) is going to be compared for doing the nested loop join.

In other words , for each tuple of relation r(R) all the blocks of s(S) is required .

Number of blocks for s(S) given   =   m

Number of tuples in r(R)   =   No of tuples in 1 block * No of blocks

                                     =    R_n * n

As mentioned each tuple of r(R) is going to be compared with all tuples of s(S) , in other words all blocks of s(S) are accessed.

So access cost  =  m * R_n * n

Also while accessing the records of r(R) if we consider usage of all tuples of r(R) which needs to be done in join , then the blocks of r(R) is also going to be accessed but each block gets accessed exactly once and that too for all the records within this block , no further access is required as r(R) is in outer loop of the nested loop join (since we compare a given record of r(R) in the outer loop with all records of s(S) and then it is done).So blocks of r(R) is also considered.

Hence total access cost  =   n + m * R_n * n   without block nested loop join

It can be shown in code as :

for ( i = 1 ; i <= n*R_n  ; i++)

{

       for(j = 1 ; j <= m ; j++)

             Compare(r(R)_{i   ,}  s(S)_j)

}

But in the question we are given that block nested loop join needs to be used.

b) So in nested loop join instead of each record of outer loop , each block of outer loop is joined with every block of records of inner relation which is s(S) according to our assumption.

So in this case , the blocks of inner relation is not going to be accessed repeatedly for each tuple of outer relation but will be accessed for each block of outer relation instead , thus reducing the access cost drastically.

So here we require for each block of r(R) , no of blocks required to be accessed of s(S)  =  m

So for n blocks  of r(R) , no of blocks required to be accessed of s(S)  =  n * m

Also in the outer loop like in the previous case , the blocks of r(R) are also accessed but once only since they are in outer loop.

So total no of blocks accessed for outer loop = No of blocks of r(R)  =  n

Hence total access cost i.e. no of blocks accessed  =  n + n * m using block nested loop join and provided r(R) is in outer loop and s(S) is in inner loop.

Hence A) is the correct option.

Comments

@Habibkhan In which book this concept is given?

---

@Habibkhan I got your explanation, but I have a doubt here in nested loop join, I think if every tuple of the outer relation is compared with every tuple of inner relation, then shouldn’t the total access cost for nested loop join be n+(m*Rm*n*Rn), where all the symbols are according to your explanation only, but Rm is the number of tuples in one block of inner relation?