Selecting Indexes - Physical Database Design - page 65

4.4.2 Block Nested-loop Join

The block nested-loop join is a variation of the nested-loop join where the inner loop
table is scanned once per block of the outer loop table instead of once per row. Once a
block of the outer loop table is held in the buffer, the algorithm can scan all the rows in
that block as a main memory operation with no I/Os. This process can greatly reduce
the number of I/O operations required for the join and is generally preferred over the
basic nested-loop approach. We look again at Example Query 4.1 and evaluate the two
possible cases for the outer loop table.

Nested-loop Case 1: assignedTo is the outer loop table.

join I/O time = scan assignedTo once, scan project 77 prefetch
buffer times
= (77 buffers + 77 scans × 1 buffer) × 5.8 ms

= .89 seconds.

Nested-loop Case 2: Project is the outer loop table.

join I/O time = scan project once, scan assignedTo m times.
= (1 buffer + 1 scan

× 77 buffers) × 5.8 ms

= .45 seconds.

The block nested-loop configurations are both dramatically faster than the basic
nested-loop configurations. We also note that making the project table the outer table is
the better strategy for either set of configurations.

4.4.3 Indexed Nested-loop Join

The indexed nested-loop join is a useful alternative to the block nested-loop join when
the join selectivity is low so that only a small subset of rows of the joined tables need to
be accessed. Let's take another look at Example Query 4.1 and modify it by adding a
WHERE condition to reduce the selectivity.

Example Query 4.2

This is a variation of Example Query 4.1 for low-selectivity joins.

SELECT p.projectName, p.projectLeader, a.empId
FROM project AS p, assignedTo AS a
WHERE p.projectName = a.projectName
AND p.projectName = 'financial analysis';