Shared parameters — both panels update together
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: orange build-tuples fly into hash buckets (phase 1), then teal probe-tuples fly into those buckets (phase 2). 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.
MariaDB 11.x BNL
Idle
MySQL 8.4 hash join
Idle
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 the smaller input, then stream the larger input
through once. That's O(build + probe). Hash join has
existed in MariaDB in a limited form since 10.4 but is not the
default, and its heuristics are different from MySQL's.
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.