8.13.12.2. Block Nested-Loop Algorithm for Outer Joins and Semi-Joins

In MySQL 5.6, the original implementation of the BNL algorithm is extended to support outer join and semi-join operations.

When these operations are executed with a join buffer, each row put into the buffer is supplied with a match flag.

If an outer join operation is executed using a join buffer, each row of the table produced by the second operand is checked for a match against each row in the join buffer. When a match is found, a new extended row is formed (the original row plus columns from the second operand) and sent for further extensions by the remaining join operations. In addition, the match flag of the matched row in the buffer is enabled. After all rows of the table to be joined have been examined, the join buffer is scanned. Each row from the buffer that does not have its match flag enabled is extended by NULL complements (NULL values for each column in the second operand) and sent for further extensions by the remaining join operations.

As of MySQL 5.6.3, the block_nested_loop flag of the optimizer_switch system variable controls how the optimizer uses the Block Nested-Loop algorithm. By default, block_nested_loop is on. See Section 8.8.5.2, "Controlling Switchable Optimizations".

Before MySQL 5.6.3, the optimizer_join_cache_level system variable controls join buffer management. For the possible values of this variable and their meanings, see the description in Section 5.1.4, "Server System Variables".

In EXPLAIN output, use of BNL for a table is signified when the Extra value contains Using join buffer (Block Nested Loop) and the type value is ALL, index, or range.

For information about semi-join strategies, see Section 8.13.16.1, "Optimizing Subqueries with Semi-Join Transformations"