Block Nested Loop


#1

Consider a relation R with 2000 records and relation S with 500 records. Size of each record is 5 Byte and block size is 100 Byte, then minimum number of block access that are needed block nested loop join.


#2

No of records in each block = 100B / 5B = 20

No of blocks in relation R = 2000 / 20 = 100

No of blocks in relation S = 500 / 20 = 25

Minimum Number of block access = Min(25+100*25 , 100+100*25) = Min(2525, 2600) = 2525


#4

Say you have 10 blocks in R1 and 20 blocks in R2.

The process works like this.

For(int i=1;i<=10:i++) {
AccessBlock(r[i]);
For(int j=1:j<=20;j++) {
AccessBlock(s[j]);
}
}

You can clearly see the number of block accesses = 10 + 10*20


If you reverse it.like this.

For(int i=1;i<=20:i++) {
AccessBlock(s[i]);
For(int j=1:j<=10;j++) {
AccessBlock(r[j]);
}
}

Now the number of clock accesses = 20 + 10*20

We have to just take the minimum of the above two cases.