NPTEL

Question

Consider the simple nested-loop join of the following two relations r and s.

 

  Relation                 r                    s

Tuples (n)            2400              1500

Blocks (b)            40                   50

 

Assuming the worst case memory availability, i.e., the memory can hold only one block of each relation at a time, what is the number of block transfers and seeks?

 

1. Transfers = 120040, seeks = 4800

2. Transfers = 4800, seeks = 120040

3. Transfers = 60050, seeks = 3000

4. Transfers = 3000, seeks = 60050

Answer 1

In nested loop join,

In the worst case, if there is enough memory only to hold one block of each relation, the estimated cost is  ( n_r * b_s + b_r ) block transfer.

n_r =  2400

b_s=  50

b_r = 40

so total number of block transfer is :

(2400 * 50) + 40 

= 120,000 + 40

= 120,040

and total number of seek = n_r + b_r  =  2400 + 40 = 2440

but it is given as  2 * 2400 = 4800  seeks ..

I think number of seek in given option is wrong, it should be 2440.

option A is only correct .

Answer 2

As Relation s has less number of records hence it should be placed in the outer loop.
 

therefore number of block transfers is given by:   b(s)+b(r)*n(s)   where b(s) is the number of blocks in relation s and b(r) is number of blocks in relation r and n(s) is number of tuples in relation s .

substituting the values we get transfers=50+1500*40====60050

 

now, number of seeks is given by 2*n(s)=2*1500=3000

therefore option (3) is correct