Block nested loop join: MariaDB's defaultMariaDB 11.4

Watch join_buffer_size decide how many times the inner table is re-scanned. Bigger buffer, fewer blocks, less I/O.

Lesson familyJoin operator

Parameters (MariaDB 11.x Block Nested Loop)

About this example
Ready: press Next step, or Play to run it all
0.0s 0.0s

About this example

Example query this animation executes

-- Non-indexed join executed by MariaDB 11.x BNL
SELECT c.country, SUM(o.total) AS revenue
FROM   customers c
JOIN   orders    o  ON  c.signup_month = o.signup_month
GROUP  BY c.country;   -- no index on signup_month → BNL

BNL kicks in whenever the ON clause has no usable index on the inner side.

What you'll see in the animation

  • Yellow blocks on top = chunks of customers rows packed into the join buffer (one block holds as many rows as join_buffer_size allows).
  • Blue table below = the orders table. It is a full table — every row lives here.
  • Labelled pills ('Acme Corp (Jan)') flow from the active block down above the orders table: the customers rows now in the join buffer, each one compared with every order.
  • A yellow sweep bar moves left-to-right across the orders table. That sweep is one full scan of orders.
  • Each block triggers exactly one full scan of orders. 10 blocks = 10 full scans. That is why bigger join_buffer_size → fewer blocks → less work.
  • Next step fills the buffer with one block, then scans orders once for it; the simplified code beside the drawing highlights the lines each step runs.

Cost readout (MariaDB 11.x BNL)

customers per block ?How many outer rows fit in one join_buffer_size chunk. Bigger buffer = more rows per block = fewer blocks = fewer inner rescans.

—

Blocks ?The outer table is split into this many blocks. Each block triggers one complete re-scan of the inner table.

—

Inner re-scans of orders ?The orders table is read from disk (or buffer pool) this many times — once per outer block. This is the main cost driver of BNL.

—

Row-pair comparisons ?Total number of (outer row, inner row) pairs compared. For BNL this is blocks × inner_rows × rows_per_block. Grows fast!

—

Complexity ?BNL re-scans orders once per block of customers. Doubling join_buffer_size halves the blocks and the rescans.

O(customers · orders / buffer) = O(n·m/b)

Row-pair comparisons vs customer rows (log–log, orders fixed)

Learn more — why does MariaDB still use BNL?

MariaDB controls block-based join algorithms mainly with join_cache_level (0–8); the optimizer_switch flags join_cache_incremental, join_cache_hashed and join_cache_bka (on by default) can turn individual algorithms off. The join_cache_level default is 2: block nested loop with incremental (linked) buffers and no hashing. Levels 3 and 4 add hashed buffers (BNLH; 3 is flat, 4 incremental), and levels 5 to 8 add batched key access for joins that have an index.

MariaDB's "hashed BNL" (levels 3 and 4) is not the same algorithm as MySQL 8.4's hash join. It's still BNL structurally — each outer block builds a tiny hash table, then the inner is scanned once per block and probed into that hash table. It's faster than plain BNL but still O(outer_blocks × inner_rows), not O(outer + inner). See the BNL vs hash lesson for the visual.

MySQL 8.0.20 removed the block nested loop executor: a join the optimizer plans with a join buffer now runs as a two-phase hash join. In MySQL 8.4 the block_nested_loop switch (and the BNL and NO_BNL hints) still decide whether that hash join may be used; the hash_join switch no longer has any effect.

One more MariaDB limit: while optimize_join_buffer_size is on (the default), all the join buffers of one query share join_buffer_space_limit (2 MiB by default), so raising join_buffer_size past that changes nothing unless you raise the limit too. The model above leaves that cap out.

Sources: MariaDB Knowledge Base "Block-based Join Algorithms"; "What's New in MySQL 8.0.20" release notes.