How MySQL Batched Key Access Join Optimization Works

Batched Key Access (BKA) is a highly efficient join optimization algorithm in MySQL designed to accelerate index lookups during table joins. By buffering keys from an outer table and using the Multi-Range Read (MRR) interface to group and sort them, BKA minimizes random disk I/O and transforms random database reads into sequential ones. This article explains the underlying mechanics of BKA, its execution flow, and how to enable it to improve query performance.

The Problem with Standard Nested-Loop Joins

In a standard Index Nested-Loop Join, MySQL reads a row from the outer (driving) table, extracts the join key, and immediately searches the index of the inner table to find matching rows. It repeats this process row by row.

If the index lookups point to data scattered across different physical locations on the disk, this approach triggers high amounts of random disk I/O. On mechanical hard drives or even modern SSDs, excessive random I/O severely bottlenecks query execution speed.

How Batched Key Access Solves This

BKA optimizes the join process by breaking the one-row-at-a-time cycle. It introduces a buffering phase and collaborates with MySQL’s Multi-Range Read (MRR) feature to fetch data in bulk.

Here is the step-by-step execution process of a BKA join:

  1. Key Accumulation in the Join Buffer: Instead of immediately querying the inner table for every outer row, MySQL reads rows from the outer table and accumulates their join keys in the join_buffer_size.
  2. Passing Keys to MRR: Once the join buffer is full, MySQL passes the accumulated keys to the Multi-Range Read (MRR) engine.
  3. Sorting by Disk Address: The MRR engine sorts the keys according to the physical disk addresses of the actual data blocks they point to in the inner table’s index.
  4. Sequential Data Retrieval: Using the sorted keys, MySQL accesses the inner table’s index and data pages sequentially. This reduces disk head movement and maximizes the efficiency of OS and storage-level page caching.
  5. Returning the Join Results: The matched rows are paired up and returned to the client, the join buffer is cleared, and the process repeats for any remaining outer table rows.

Prerequisites and Enabling BKA

Because BKA relies heavily on Multi-Range Read to execute the sorted disk lookups, both BKA and MRR must be enabled in the MySQL optimizer settings.

By default, BKA is often disabled because MySQL uses a cost-based optimizer that might favor traditional joins for small, in-memory datasets. To force or allow BKA execution, you can modify the optimizer_switch system variable:

SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

Additionally, you must ensure that your join_buffer_size is configured with enough memory to hold a viable batch of keys. If the buffer is too small, MySQL will perform frequent, smaller batches, reducing the performance gains of the optimization.