Shared parameters — both panels update together
About this exampleMariaDB 11.x BNL
Idle
MySQL 8.4 hash join
Idle
About this example
Example query this animation executes
-- The same non-indexed join run by both engines 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
MariaDB 11.x runs this with BNL (join_cache_level=2). MySQL 8.4 runs it with a two-phase hash join. Same SQL, very different cost.
What you'll see in the animation
- Left panel — MariaDB BNL: customers rows pack into blocks; a yellow sweep bar crosses the orders table once per block. One sweep = one full scan of orders.
- Right panel — MySQL 8.4 hash join: labelled customer pills ('Acme Corp Jan') fly into month buckets (build), then labelled order pills ('#101 Jan') fly into those buckets (probe). Only one pass of each side.
- Both panels run the same input in parallel so you can feel the asymptotic difference — BNL grows quadratically with customers, hash grows linearly.
- Each panel has its own row-pair comparison counter. The ratio is shown above as 'Speedup (hash vs BNL)'. At small sizes it is close to 1×; crank the sliders and watch it grow.
- Next step moves both panels forward together by one slice; the simplified code beside the drawing highlights the line each join is on.
Cost comparison — row-pair comparisons
BNL row-pair comparisons ?Total (outer row, inner row) pairs checked by the BNL algorithm. Grows with blocks × inner_rows. This is the number that makes BNL expensive at scale.
—
Hash row comparisons ?Total rows processed by the hash join: one read of the build side + one read of the probe side. Grows linearly — much flatter than BNL.
—
Speedup (hash vs BNL) ?How many times fewer row-pair comparisons the hash join needs compared to BNL. At large scale this is 100× to 10,000× — the whole reason MySQL removed BNL.
—
BNL complexity ?BNL re-scans orders once per block of customers. The more blocks, the more rescans. Quadratic-ish growth.
O(customers · orders / buffer) = O(n·m/b)
Hash complexity ?One pass through customers (build) + one pass through orders (probe). Linear growth no matter the size.
O(customers + orders) = O(n + m)
Row-pair comparisons vs customers rows (log–log, orders fixed)
Learn more — isn't MariaDB's "hash join" the same thing?
No. MariaDB 11.x can use join_cache_level = 4
for "hashed BNL" — which is still structurally a Block Nested Loop.
Each outer block builds a small hash table and the inner is scanned
once per block. It's faster than plain BNL but still
O(outer_blocks · inner_rows).
MySQL 8.4's hash join (and PostgreSQL's, and most analytics
engines') is a two-phase algorithm: build a single in-memory
hash table from one input (usually the smaller), then stream the other
input through once. That's O(build + probe). MariaDB has
long had its hashed join buffer (BNLH, join_cache_level 3
and up), but it is not used at the default level 2, and it still works
block by block.
Takeaway: when you see "hash join" in a MariaDB EXPLAIN, check
which join_cache_level is active. In MySQL 8.4 there's
only one kind — BNL is gone (removed in
8.0.20).
Sources: MariaDB Knowledge Base "Block-based Join Algorithms", "Hash Join Support". MySQL 8.4 Reference Manual §10.2.1.4.