MySQL Block Nested Loop Join Explained

This article provides a comprehensive overview of the Block Nested Loop (BNL) join algorithm in MySQL, detailing how it optimizes database queries. It covers the core mechanics of the algorithm, how the join buffer is utilized to minimize disk I/O, and the step-by-step process MySQL uses to execute joins when indexes are unavailable.

The Problem with Simple Nested Loop Joins

To understand the Block Nested Loop algorithm, it is first necessary to understand the Simple Nested Loop Join (SNLJ). In a simple nested loop join, MySQL reads one row at a time from the outer table (first table), scans the entire inner table (second table) for matching rows, and repeats this process for every single row in the outer table.

If the outer table has 1,000 rows and the inner table has 10,000 rows, MySQL must read the inner table 1,000 times, resulting in 10,000,000 row comparisons and massive disk I/O if the inner table cannot fit into memory. This becomes highly inefficient when the join columns lack indexes.

How Block Nested Loop Optimizes Joins

The Block Nested Loop algorithm reduces the number of times the inner table needs to be scanned by using an in-memory buffer called the join buffer. Instead of scanning the inner table for every individual row of the outer table, BNL processes the outer table rows in batches or “blocks.”

Here is the step-by-step operational mechanism of the BNL algorithm:

1. Join Buffer Allocation: MySQL allocates a portion of memory defined by the join_buffer_size system variable.
2. Buffering Outer Rows: MySQL reads rows from the outer table and writes the selected columns into the join buffer. It continues this process until the buffer is full or all eligible rows from the outer table are read.
3. Scanning the Inner Table: Once the join buffer is filled with a block of outer rows, MySQL performs a single, full scan of the inner table.
4. In-Memory Matching: For each row read from the inner table, MySQL compares it against all the outer rows currently stored in the join buffer. Because this comparison happens entirely in RAM, it is exceptionally fast.
5. Iteration: If there are still unprocessed rows in the outer table, MySQL clears the join buffer, loads the next batch of outer rows, and performs another scan of the inner table. This cycle repeats until all rows from the outer table have been processed.

The Impact on Performance

By grouping the outer rows into a buffer, the number of scans on the inner table is drastically reduced.

For example, if the join buffer can hold 100 rows of the outer table at a time, MySQL only needs to scan the inner table 10 times instead of 1,000 times. This reduction in disk I/O leads to significant performance improvements for queries that must perform full table scans on non-indexed columns.

Key Configuration and Limitations

• The join_buffer_size Variable: The efficiency of the BNL join is directly tied to the size of the join buffer. If the buffer is too small, MySQL must perform more frequent scans of the inner table. Conversely, setting it too high can lead to excessive memory consumption, as a join buffer is allocated for each query that requires one.
• Column Selection: MySQL only buffers the columns actually needed for the query (the columns in the SELECT, WHERE, and JOIN clauses), not the entire row. This allows more rows to fit into the buffer.
• Modern MySQL Context: While BNL was the default optimization for non-indexed joins for many years, MySQL 8.0.18 and later introduced Hash Joins. In modern MySQL installations, Hash Joins have largely replaced BNL because they are generally faster and more memory-efficient for equi-joins.