Page 212 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Unit 12: Query Processing and Optimization

12.4.2 Block Nested-loop Join Notes

This is a variant of nested-loop join in which a complete block of outer loop is joined with the
block of inner loop.
The algorithm for this may be written has:

for each block s of STUDENT
{
for each block m of MARKS
{
for each tuple si in s
{
for each tuple mi in m
{
Check if (si and mi) satisfy the join condition
if they do output joined tuple to the result
};
};
};
};
Worst case of block accesses in this case = Number of Blocks of outer relation
(STUDENT) ×Number of blocks of inner relation (MARKS) + Number of blocks of outer relation
(STUDENT).
Best case: Blocks of STUDENT + Blocks of MARKS
Number of block transfers assuming worst case:
100 × 500 + 100 = 50,100 (much less than nested-loop join)
Number of block transfers assuming best case:

400 + 100 = 500 (same as with nested-loop join)

Improvements to Block Nested-loop Algorithm

The following modifications improve the block Nested method:
Use M – 2 disk blocks as the blocking unit for the outer relation, where M = memory size in
blocks.

Use one buffer block to buffer the inner relation.
Use one buffer block to buffer the output.
This method minimizes the number of iterations.

12.4.3 Indexed Nested-loop Join

Index scans can replace file scans if the join is an equi-join or natural join, and an index is
available on the inner relation’s join attribute.
For each tuple si in the outer relation STUDENT, use the index to look up tuples in MARKS that
satisfy the join condition with tuple si.
In a worst case scenarios, the buffer has space for only one page of STUDENT, and, for each tuple
in MARKS, then we should perform an index lookup on MARKS index.

LOVELY PROFESSIONAL UNIVERSITY 205