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

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

Nice video to refer 

---

https://15445.courses.cs.cmu.edu/fall2018/notes/12-joins.pdf

---

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

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

For Block Nested loop Join - Why are you having 1620 accesses, I m having  80 * 20 = 1600, 

Why 20 extra for Block Nested loop Join..??

---

Please add formula for cost calculation of nested loop and block nested loop

---

20 will be added bcz we choose T2 priviously when apply nestesd loop join  as  a outer loop

---

just explaining calculation 20+(400×80) means bring 20 blocks of T2 in memory either one by one or in single shot(hence +20 added) then for each record (400) in this blocks bring each block of T1 (80) in memory.

 

80*20+20 means

means bring 20 blocks of T2 in memory either one by one or in single shot(hence +20 added) then for each block of T2  bring block of T1. finish all computation between this blocks (Note earlier we did not check for every record of block of T2 , we just checked for first record in T2 with first block of T1 and moved on to next block of T1)then moved on to next block of T1. If all blocks of T1  finished with checking then move on to next block of T2.

---

Could you please explain how +20 is done in the answer?

---

Smaller table should be outside bro.so 20 added

---

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)$

---

@Abhrajyoti00 Bhaiya, because of people like you I am able to understand the concept easily. Thank You for writing such good answers :))

---

helpful

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

Both question, Nested Loop Join and Block Nested Loop Join

Answer 4

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 5

🧠 Step 1: Basic Nested Loop Join

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

🧠 Step 2: Block Nested Loop Join

Now we use block-level batching. Let’s again choose T₂ as outer:

• Outer loop: T₂ has 20 blocks

• Inner loop: For each block of T₂, scan all 80 blocks of T₁

• Total accesses:

Read T₂ once=20 blocks+20⋅80=1600 accesses⇒Total=20+1600=1620

🔻 Reduction in Block Accesses:

Basic NLJ−Block NLJ=32020−1620=30400

✅ Correct Answer: B. 30400