A database table T1 has 2000 records and occupies 80 disk blocks. Another table T2 has 800 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 at a time. No index is available on either table.
If, instead of Nested loop join, block nested loop join is used, and T2 is used in the outer loop, the reduction in number of disk block accesses required for reading the data will be
A. 0
B. 30400
C. 38400
D. 798400
GATE 2005 · Databases · Joins · medium
Answer: C. 38400 — block nested loop join (T2 outer) saves 38400 block accesses compared to tuple nested loop join (T1 outer) for the inner-table reads.
Compute inner-table reads for Tuple Nested Loop Join (T1 outer): |T1| = 2000 records (number of tuples in T1, the outer table)
B_T2 = 20 blocks (blocks of T2, the inner table)
Inner reads = 2000 × 20 = 40000 block accesses
(Plus outer reads = 80 for T1 itself, but the question focuses on the inner-table reads for the reduction calculation.)
Compute inner-table reads for Block Nested Loop Join (T2 outer): B_T2 = 20 blocks (blocks of T2, the outer table)
B_T1 = 80 blocks (blocks of T1, the inner table)
Inner reads = 20 × 80 = 1600 block accesses
(Plus outer reads = 20 for T2 itself.)
Calculate the reduction: Reduction = 40000 - 1600 = 38400 block accesses
This matches option C. 38400.