GATE IT 2005 | Question: 82b

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, 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

• A. $0$
• B. $30400$
• C. $38400$
• D. $798400$

Comments

Direct formula & a good explanantion - https://www.youtube.com/watch?v=rT4eI3p3tVk&t=228s

---

awesome explanation.

Thank u.

---

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

Nice video to refer 

Answer 1

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

Comments

you have to add 20 extra block accesses, for outer table T1

---

Can somebody explain, number of seeks required for nested-loop join and block nested-loop join?

---

In Nested Loop Join, each record in outer table joins with every block of inner table + # blocks in Outer Table cost.

 If we would have taken table $T1$ outside, then number of block accesses would have been : $2000*20+80 = 40080 \ which \ is > 32020$. Hence most appropriate choice of table in the outer loop is $T2 \ (table \ with \ fewer \ records)$

In Block nested loop join, each block in outer table joins with every block of inner table + # blocks in Outer Table cost.

If we would have taken table $T2$ outside, then number of block accesses would have been : $80*20+80 = 1680 \ which \ is > 1620$. Hence most appropriate choice of table in the outer loop is $T2 \ (table \ with \ fewer \ blocks)$

Answer 2

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

Comments

outer table should have less records

Then no need to calculate all records

---

It is well explained.

https://gateoverflow.in/76143/block-nested-loop-join

Answer 3

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.

Answer 4

Both question, Nested Loop Join and Block Nested Loop Join