edited by
8,619 views
51 votes
51 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 Nested-loop join algorithm is employed to perform the join, with the most appropriate choice of table to be used in outer loop, the number of block accesses required for reading the data are

  1. $800000$
  2. $40080$
  3. $32020$
  4. $100$
edited by

3 Answers

Best answer
101 votes
101 votes

We just have to think which table would be in the outer loop. To minimize block accesses, we have to put that table outside having fewer records because for each outer record, one block access inside will be required.

Therefore, putting $2$nd table outside,

  • for each of $400$ records
    • $80$ block accesses in the first table $ \implies 32000$ accesses.
  • $20$ block accesses of the outer table.

So, the answer comes out to be $32000+20 = 32020$

Correct answer: C.

edited by
44 votes
44 votes

Reference: http://en.wikipedia.org/wiki/Nested_loop_join

As per this reference this algorithm will involve $nr*bs+ br$ block transfers

$T_1$ can be either $R$ or $T_2$

  • If $R$ is $T_1$ then total number of block accesses is $2000 \times 20 + 80 = 40080$
  • If $R$ is $T_2$ then total number of block accesses is $400 \times 80+20 = 32020$

So, better is the second case $(32020)$ Hence, I go for option C.

12 votes
12 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 employed 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

edited by
Answer:

Related questions

54 votes
54 votes
4 answers
4