Deep Dive into MySQL Join Algorithms: Principles, Implementation, and Optimization

Essence of Join Operations

Join combines rows from multiple tables based on a join condition. Core challenges are data‑scale (M×N comparisons), memory limits, index utilization, and join order selection.

MySQL Join Algorithms

1. Nested‑Loop Join (NLJ)

Definition : Basic algorithm that iterates the outer table and for each outer row scans the inner table.

Core principle :

for outer_row in outer_table:
    for inner_row in inner_table:
        if match(join_condition):
            output_result()

Complexity :

Best case (inner table indexed): O(M log N)

Worst case (full scan): O(M × N)

Pros :

Low memory consumption (row‑by‑row)

Supports all join types (equi and non‑equi)

Can use index lookups (Index‑Nested‑Loop variant)

Cons :

Poor performance without an index

Response time grows exponentially with large data sets

2. Block Nested‑Loop Join (BNLJ)

Definition : Improves NLJ by buffering a block of outer rows to reduce inner‑table scans.

Core principle :

buffer = []
for outer_row in outer_table:
    buffer.append(outer_row)
    if buffer_full():
        for inner_row in inner_table:
            for buf_row in buffer:
                if match(buf_row, inner_row):
                    output_result()
        buffer.clear()
# process remaining rows

Key parameters : join_buffer_size – controls block size (default 256 KB) optimizer_switch – enables BNLJ

Performance characteristic :

Total I/O = ceil(M / B) * N
where M = outer rows, B = buffer capacity (rows), N = inner pages

Example : M = 1,000,000 rows, B = 1,000 rows → traditional NLJ needs 1e12 comparisons, BNLJ needs only 1,000 full scans of the inner table.

Pros :

Reduces inner‑table scans

Efficient memory usage

Works without an index

Cons :

Requires appropriate buffer size

Performance still degrades on very large tables

Does not optimize non‑equi joins

3. Hash Join

Definition : Hash‑based equi‑join introduced in MySQL 8.0+, builds a hash table on the build side.

Core principle :

# Build phase
hash_table = {}
for build_row in build_table:
    key = hash(build_row.join_key)
    hash_table.setdefault(key, []).append(build_row)

# Probe phase
for probe_row in probe_table:
    key = hash(probe_row.join_key)
    if key in hash_table:
        for build_row in hash_table[key]:
            if build_row.join_key == probe_row.join_key:
                output_result()

Advanced optimization : Grace Hash Join partitions data to disk when the hash table exceeds memory; Mixed Hash Join dynamically balances memory and disk usage.

Pros :

Excellent performance for equi‑joins

Suitable for large tables when memory is sufficient

Resistant to data skew

Cons :

Supports only equi‑joins

Higher memory consumption

Build phase requires a full scan of the build table

Algorithm Comparison Matrix

Feature                | Nested‑Loop Join | Block NLJ | Hash Join
-----------------------------------------------------------------
Join type support      | All types        | All types | Equi‑join only
Index dependency       | Needs inner index| No index  | No index
Memory consumption     | Low (row‑by‑row) | Medium    | High
Best data size         | Small‑medium (indexed) | Small‑medium (no index) | Large tables (equi‑join)
Typical complexity     | O(M·log N)       | O(M·N/B)  | O(M+N)
Disk I/O pattern       | Random (index)   | Sequential| Sequential + memory hash
Version support        | All versions     | All versions| MySQL 8.0+

Decision Tree for Algorithm Selection

Deep‑Optimization Practices

Case 1: Index Misuse

Problem: EXPLAIN shows Using where instead of Using index because the literal type does not match the column type.

SELECT * FROM users
JOIN orders ON users.id = orders.user_id
WHERE users.id = '100';  -- id is integer, literal is string

Solution: Align column types and force the index.

ALTER TABLE orders MODIFY user_id INT;
SELECT * FROM users
JOIN orders FORCE INDEX(idx_user_id) ON users.id = orders.user_id;

Case 2: BNLJ Parameter Tuning

SHOW VARIABLES LIKE 'join_buffer_size';
SET SESSION join_buffer_size = 4 * 1024 * 1024;  -- 4 MiB
# Permanent setting
[mysqld]
join_buffer_size = 4M

Case 3: Forcing Hash Join (MySQL 8.0+)

SELECT /*+ HASH_JOIN(t1, t2) */ *
FROM t1 JOIN t2 ON t1.id = t2.t1_id;

EXPLAIN Deep Dive

Key columns

type : ref (index lookup) vs ALL (full scan)

Extra : Using index (covering index), Using join buffer (BNLJ or Hash Join)

JSON format example

{
  "query_block": {
    "select_id": 1,
    "nested_loop": [
      {
        "table": {
          "table_name": "employees",
          "access_type": "ALL",
          "rows_examined_per_scan": 1000,
          "filtered": "100.00"
        }
      },
      {
        "table": {
          "table_name": "salaries",
          "access_type": "ref",
          "key": "idx_emp_no",
          "used_join_buffer": "Hash Join"
        }
      }
    ]
  }
}

Understanding these details helps design better schemas, tune server parameters, write efficient SQL, and locate performance bottlenecks. Combining EXPLAIN ANALYZE with Optimizer Trace is recommended for real‑world analysis.