GATE IT 2005 | Question: 82a

Question

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

• A. $800000$
• B. $40080$
• C. $32020$
• D. $100$

Comments

Concept explained: 

https://www.youtube.com/watch?v=b0xbiYvZAdQ

---

help full video 

https://www.youtube.com/watch?v=3Ui4tCS4iKM&list=PLC36xJgs4dxEKjYXHSoKN35wRb_MJx9Yn&index=54

---

Thanks @neel19 :) Great video, now even if they have variation in buffer space then also we can handle the variation in formula

Answer 1

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.

Comments

Yes, this must be selected as a "Best answer" as it also can be solved in 3 minutes and is more conceptual than just mugging up the formula.

#Answer by @Vishesh Bajpai

---

why cant it be 20*80?

---

https://www.geeksforgeeks.org/join-algorithms-in-database/

 

Read This if you don’t know the concept of Nested Loop Join...

Answer 2

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.

Answer 3

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

Comments

records means rows and blocks means columns?

---

@Lakshman Patel RJIT 

Nope.

Block means "Disk Block" which contains multiple tuples of given relation.

Actually, in this join .. even outer loop is accessed using blocks but for every new tuple it fetches new block hence expression has a term " $n_r*B_s$ " .

This algo is naive and not much efficient. 

 

p.s : i guess u assumed it as we do in 2d array access.,but thats thats not the case here.

---

thanks

---

@Lakshman Patel RJIT 

this may help.