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

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

 

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

---

Why is it that we used row wise join here? Could not we have gone with block wise join to yield even smaller results of,

XY + Y = 80 * 20 + 20 = 1620

 

---

For understanding this Believe you will not find better source than this one,

Carnegie Mellon University

For Nested Loop Join : M(disk block access for outer block) + m(no. of tuples in outer block)*N(number of blocks in inner Loop)

Have a Look

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.

Answer 4

Let’s choose T₂ as outer (smaller record count → fewer iterations):

• For each of 400 records in T₂:

  • Scan all 80 blocks of T₁

• Total accesses:

Read T₂ once=20 blocks+400⋅80=32000 accesses⇒Total=20+32000=32020