edited by
16,169 views
48 votes
48 votes

A database table $T_1$ has $2000$ records and occupies $80$ disk blocks. Another table $T_2$ has $400$ records and occupies $20$ disk blocks. These two tables have to be joined as per a specified join condition that needs to be evaluated for every pair of records from these two tables. The memory buffer space available can hold exactly one block of records for $T_1$ and one block of records for $T_2$ simultaneously at any point in time. No index is available on either table.

If, instead of Nested-loop join, Block nested-loop join is used, again with the most appropriate choice of table in the outer loop, the reduction in number of block accesses required for reading the data will be

  1. $0$
  2. $30400$
  3. $38400$
  4. $798400$
edited by

4 Answers

Best answer
75 votes
75 votes

In Nested loop join for each tuple in first table we scan through all the tuples in second table.

Here we will take table $T2$ as the outer table in nested loop join algorithm. The number of block accesses then will be $20 + (400 × 80) = 32020$

In block nested loop join we keep $1$ block of $T1$ in memory and $1$ block of $T2$ in memory and do join on tuples.

For every block in T1 we need to load all blocks of T2. So number of block accesses is $80$*$20 + 20 = 1620$

So, the difference is $32020 - 1620 =30400$

(B) 30400

edited by
39 votes
39 votes

rel T1 with n (2000) tuples and x (80) blocks 
rel T2 with m (400) tuples and y (20) blocks

If Nested-loop join algorithm is used to perform the join:


R join S access cost = { X+N*Y } blocks 

                                 = 80+2000*20 

                                 =40080 blocks 

S join R access cost = { Y+M*X } blocks 

                                =20+400*80 

                               =32020 blocks

but If Block nested-loop join is used to perform the join:


R join S access cost = { X+X*Y } blocks 

                                 = 80+80*20 

                                 =1680 blocks 

S join R access cost = { Y+Y*X } blocks 

                                =20+20*80 

                               =1620 blocks

 reduction in number of block accesses required for reading the data = 32020-1620

                            =30400

so ans should be B

0 votes
0 votes
  1. Bring a block of T2.
  2. Bring all blocks of T1 one at a time.
  3. Repeat above steps for T1 total block times. 

Complexity -

  1. 1 block access
  2. 80 block accesses 
  3. (80+1)*20 = 1620

Subtract it from 32020.

edited by
Answer:

Related questions

54 votes
54 votes
4 answers
4