Analyzing Block Nested Loop Join I/O Costs

1. The Join Problem and a Naive First Attempt

First, let's set the stage. Joins are necessary because we normalize our database schemas to avoid data redundancy. A join operation reconstructs the original, un-normalized data on the fly. As with external sorting, our primary concern for disk-based databases is the I/O cost.

The following video from Carnegie Mellon University's database course introduces the join problem and establishes I/O cost as our primary performance metric.

Simple Nested Loop Join: The Brute-Force Method

Given your background in programming, the most intuitive way to join two sets of data (let's call the tables R and S) is with nested loops. This is the simple nested loop join.

The logic is exactly what it sounds like:

// For each tuple in the outer table R...
for (tuple tr in R) {
    // ...iterate through every single tuple in the inner table S
    for (tuple ts in S) {
        if (tr and ts match on the join condition) {
            add <tr, ts> to the result;
        }
    }
}

This is simple, but horrendously inefficient for a disk-based database. Why? Because for every single tuple in the outer table, we might have to scan the entire inner table from disk.

To understand just how bad this is, let's watch the next segment of the video, which analyzes its I/O cost.

As the video explained, if R is the outer table and S is the inner table, the cost is:

Where:

• $M$: number of pages in R
• $m$: number of tuples in R
• $N$: number of pages in S

The $m\times N$ term is the killer. If R has millions of tuples, we are scanning the entire S table millions of times. Clearly, we need a better way.

2. The Block Nested Loop Join (BNLJ)

The key inefficiency of the simple nested loop join is that it operates tuple-by-tuple, ignoring the fact that data is read from disk in pages (or blocks). The block nested loop join leverages this insight. Instead of fetching one tuple at a time, we fetch one block at a time.

The algorithm becomes:

// For each block of the outer table R...
for (block br in R) {
    // ...iterate through every block of the inner table S
    for (block bs in S) {
        // Now, compare all tuples within the two in-memory blocks
        for (tuple tr in br) {
            for (tuple ts in bs) {
                if (tr and ts match on the join condition) {
                    add <tr, ts> to the result;
                }
            }
        }
    }
}

This simple change has a massive impact on I/O. We are now scanning the inner relation S once for each page of R, not for each tuple.

The cost formula changes to:

This is a significant improvement, replacing the huge number of tuples ($m$) with the much smaller number of pages ($M$).

3. Optimizing BNLJ with the Buffer Pool

We can do even better. The algorithm above assumes we only have enough memory for one page of R and one page of S. But in our previous lessons, we've seen the power of using the buffer pool. If we have B buffer pages available, how can we use them?

The strategy is to dedicate as much memory as possible to holding a "chunk" or "block" of the outer relation, R.

• We use 1 page for scanning the inner relation S.
• We use 1 page for the output buffer.
• This leaves B-2 pages to hold a chunk of the outer relation R.

The improved algorithm is:

// Iterate through the outer relation R in chunks of size (B-2)
for (chunk_of_R of size (B-2) pages) {
    // Read the entire inner relation S from disk
    for (block bs in S) {
        // Compare all tuples in the chunk_of_R with the tuples in bs
        for (block br in chunk_of_R) {
            for (tuple tr in br) {
                for (tuple ts in bs) {
                    // ... join logic ...
                }
            }
        }
    }
}

This reduces the number of times we have to scan the inner relation S. Instead of scanning it M times, we now only scan it $\lceil M/(B-2)\rceil$ times.

The final I/O cost formula for Block Nested Loop Join is:

This next video segment explains this optimization and the final cost formula.

For a different perspective and a concrete numerical example, the following video walks through the entire process, including the cost calculation.

As you saw, one of the most important and simplest optimizations is to choose the smaller relation as the outer relation. Since M appears in the multiplicative term of the cost formula, making M as small as possible will yield the greatest benefit.

For a final summary of the algorithm and its cost, these lecture notes are an excellent reference.

Conclusion

Today we took our first step into the world of join algorithms. We saw how a naive, tuple-at-a-time approach is prohibitively expensive and how moving to a block-oriented mindset dramatically improves performance.

Key Takeaways:

• The Simple Nested Loop Join is too slow for disk-based systems due to its $M+(m\times N)$ I/O cost.
• The Block Nested Loop Join improves this by processing data page-by-page, reducing the cost to $M+(M\times N)$.
• By utilizing the buffer pool effectively, we can hold a chunk of the outer relation in memory, further reducing the cost to $M+\left(\lceil \frac{M}{B-2}\rceil \times N\right)$.
• For BNLJ, always choose the smaller relation (in pages) as the outer relation to minimize the number of scans over the inner relation.

Preview of the Next Lesson

The Block Nested Loop Join, while better than the naive approach, still repeatedly scans the entire inner relation. If the outer relation is large, this is still very costly. In our next lesson, we will explore the Index Nested Loop Join. We'll see how leveraging an index on the inner table's join key can allow us to avoid full scans entirely, turning expensive scans into highly efficient lookups.