Analyzing I/O Costs of Index Nested Loop Join

1. The Core Idea: Replacing Scans with Probes

The fundamental idea behind the Index Nested Loop Join is simple yet powerful. Instead of scanning the inner table S to find matches for tuples from the outer table R, we can use an index on S's join attribute to look them up directly.

The algorithm proceeds as follows:

1. Scan the outer table R, one tuple at a time.
2. For each tuple tr from R, take its value for the join attribute (e.g., tr.id).
3. Use this value to probe the index on the inner table S to find matching tuples.
4. For each match found, combine the tuples and add them to the result.

This process is visualized in the diagram below. For each tuple from R, we make a targeted query into the index, which then points us directly to the required tuples in S.

To see a full explanation, let's turn again to Professor Andy Pavlo from CMU.

2. Implementation and a Practical View

Given your programming background, you can think of this as replacing a nested for loop that iterates through an array with one that uses a hash map or a balanced tree for the inner loop lookups.

Here is what the algorithm looks like in pseudocode:

// R is the outer table, S is the inner table
// Assume S_index is an index on S's join attribute
for (tuple tr in R) {
    // Use the join key from the outer tuple to probe the index
    join_key = tr.join_attribute;
    list_of_matches = S_index.lookup(join_key);

    // For each matching tuple found in S, emit the joined result
    for (tuple ts in list_of_matches) {
        add <tr, ts> to the result;
    }
}

This is a clean and simple approach. The following technical blog post provides a similar pseudocode and, more importantly, shows what an EXPLAIN plan for this join looks like in a real database system like PostgreSQL.

3. Analyzing the I/O Cost

Now for the crucial part: analyzing the I/O cost. As the video mentioned, the cost formula is:

Let's break this down:

• $M$: The I/O cost to perform a full sequential scan of the outer table R. We have to read every one of its pages once.
• $m$: The total number of tuples in the outer table R. This is important: we perform one index probe for each tuple in the outer table.
• $C$: The average I/O cost for a single index probe. This includes traversing the index and fetching the actual data tuple(s) from the inner table S.

The total cost is the scan of the outer table plus the cumulative cost of all the probes into the inner table. The value of C is where the real analysis lies. It depends heavily on the type of index and how the data is stored.

The Cost of a Probe (C)

The cost C isn't just one number. It varies based on two key factors: the index structure (e.g., B+ Tree) and whether the index is clustered or unclustered.

1. With a Clustered Index on S:

   • In a clustered index, the actual data rows are stored in the leaf pages of the index itself.
   • Therefore, the cost C is simply the cost to traverse the B+ Tree from the root to the correct leaf page.
   • This typically requires 2-4 I/Os for a reasonably sized tree. Once at the leaf page, we have the data.

2. With an Unclustered Index on S:

   • In an unclustered index, the leaf pages contain the index keys and pointers (e.g., Record IDs) to the actual data pages.
   • The cost C is the cost to traverse the B+ Tree (2-4 I/Os) plus one additional I/O to fetch the data page containing the tuple from the table's heap file.
   • In a worst-case scenario where each lookup points to a different data page that isn't in the buffer pool, this can be costly. If k tuples in S match a given key, this could require up to k additional I/Os.

For a concise summary of the algorithm and its cost, please refer to the CMU lecture notes.

Conclusion

Today we explored the Index Nested Loop Join, a powerful alternative to the brute-force scanning of BNLJ. By leveraging an index, it can transform a join from a massive scanning operation into a series of quick, targeted lookups.

Key Takeaways:

• The Index Nested Loop Join algorithm avoids scanning the inner table by probing an index for each tuple of the outer table.
• The I/O cost is $M+(m\times C)$, where the efficiency is critically dependent on m (the number of outer tuples) and C (the cost per probe).
• The cost of a probe (C) is lower for a clustered index than for an unclustered index because the latter requires an extra I/O to fetch the data record.
• INLJ is most effective for joins where the outer table is small, as this minimizes the number of probes. This is common in OLTP queries like "find the customer for this one order."

Preview of the Next Lesson

INLJ is great if a suitable index exists. BNLJ is a fallback, but can be slow. What if we don't have an index, and BNLJ is too costly because both tables are large? In our next lesson, we will investigate the Sort-Merge Join, an elegant algorithm that takes a completely different approach: it sorts both tables on the join key and then merges them.