Understanding the Construction Process of Adaptive Hash Index (AHI) in MySQL 8.0.32

When optimizing slow queries, the author often saw TRUNCATE in the logs and wondered why it could be slow. After moving to database development, similar long‑running TRUNCATE operations were observed, causing brief MySQL stalls. Source‑code analysis revealed that the issue is related to Adaptive Hash Index (AHI), prompting a deep dive into its mechanics.

Table of Contents

1. Preparation

2. Benefits of AHI

3. Principle Overview

4. Construction Process 4.1 Index Counting 4.2 Construction‑Info Counting 4.3 Data‑Page Counting 4.4 Build AHI

5. Summary

1. Preparation

Create a test table:

CREATE TABLE `t1` (
  `id` int unsigned NOT NULL AUTO_INCREMENT,
  `i1` int DEFAULT '0',
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_i1` (`i1`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb3;

Insert test data:

INSERT INTO `t1`(`id`,`i1`) VALUES
  (10,101), (20,201), (30,301);

Sample query used later:

SELECT * FROM `t1`
WHERE `i1` >= 101 AND `i1` < 301;

2. Benefits of AHI

Adaptive Hash Index (AHI) is an index that stores hash tables internally. Its creation, usage, and removal are fully managed by InnoDB, without user intervention.

InnoDB primary and secondary indexes are B+ trees. Locating a record in the leaf node is required for INSERT (to find the predecessor), and for SELECT/UPDATE/DELETE during both optimization and execution phases (to find the first and last record of a range).

Because B+ trees are shallow (typically 3‑4 levels), locating a leaf node is fast, but for frequently executed queries there is still room for improvement. AHI aims to jump directly to the leaf node by using a hash lookup.

The diagram shows a B+ tree of height 4; locating a leaf record requires traversing nodes ① → ② → ③ → ④.

AHI stores multiple hash buckets that map hash values to record addresses. The orange block in the picture represents a linked list of record addresses that share the same bucket slot.

When locating a record, the hash of the relevant fields is computed and the corresponding bucket is consulted. If multiple records map to the same slot, the linked list is traversed to find the target.

3. Principle Overview

AHI improves record location efficiency at the cost of extra memory for hash‑value‑to‑address mappings and the time spent building those mappings.

InnoDB only builds AHI when certain thresholds are met, ensuring that the performance gain outweighs the overhead.

The construction follows a "group‑construction" logic based on data pages. When a data page satisfies specific conditions, AHI is built for all records on that page.

4. Construction Process

4.1 Index Counting (Step 1)

Each time a leaf‑node record is located, btr_search_info_update() increments the index counter index->search_info->hash_analysis . When the counter reaches 17, the process proceeds to Step 2; otherwise it returns.

void btr_search_info_update(btr_cur_t *cursor) {
  const auto index = cursor->index;
  const auto hash_analysis_value = ++index->search_info->hash_analysis;
  if (hash_analysis_value < BTR_SEARCH_HASH_ANALYSIS) {
    return; // do nothing
  }
  btr_search_info_update_slow(cursor);
}

4.2 Construction‑Info Counting (Step 2)

When the index counter is ≥ 17, btr_search_info_update_hash() evaluates the lower and upper bounds (generated during record location) to determine the construction info ( prefix_info ) and updates its counter n_hash_potential . If the new bounds match previously stored construction info, the counter is incremented; otherwise it is reset.

static void btr_search_info_update_hash(btr_cur_t *cursor) {
  dict_index_t *index = cursor->index;
  const uint16_t n_unique = static_cast
(dict_index_get_n_unique_in_tree(index));
  auto info = index->search_info;
  if (info->n_hash_potential != 0) {
    const auto prefix_info = info->prefix_info.load();
    if (prefix_info.n_fields == n_unique &&
        std::max(cursor->up_match, cursor->low_match) == n_unique) {
      info->n_hash_potential++;
      return;
    }
    // additional checks using left_side, low_matches_prefix, up_matches_prefix ...
  }
  // else determine new prefix_info and reset counters
}

4.3 Data‑Page Counting (Step 3)

After construction‑info counting, btr_search_update_block_hash_info() updates the data‑page counter block->n_hash_helps . If the page’s stored construction info matches the current one, the counter is incremented; otherwise it is reset to 1 and the new construction info is saved.

static bool btr_search_update_block_hash_info(...) {
  const auto info = cursor->index->search_info;
  info->last_hash_succ = false;
  if (block->n_hash_helps > 0 && info->n_hash_potential > 0 &&
      block->ahi.recommended_prefix_info.load() == info->prefix_info.load()) {
    if (block->ahi.index && block->ahi.prefix_info.load() == info->prefix_info.load()) {
      info->last_hash_succ = true;
    }
    block->n_hash_helps++;
  } else {
    block->n_hash_helps = 1;
    block->ahi.recommended_prefix_info = info->prefix_info.load();
  }
  return false;
}

When both the construction‑info counter (≥ 100) and the data‑page counter (> 1/16 of the page’s record count) are satisfied, the engine decides whether to build or rebuild AHI for that page.

4.4 Build AHI (Step 4)

The actual building iterates over all records on the page, computes a hash for each record based on the determined prefix_info , and stores the hash‑value‑to‑record‑address mapping in the hash table. The left_side flag decides whether the first or the last record of a prefix‑identical group is used.

static void btr_search_build_page_hash_index(...) {
  const auto page = buf_block_get_frame(block);
  const auto prefix_info = block->ahi.recommended_prefix_info.load();
  const auto n_fields_for_offsets = btr_search_get_n_fields(prefix_info);
  // Drop previous AHI if construction info changed
  if (block->ahi.index && block->ahi.prefix_info.load() != prefix_info) {
    btr_search_drop_page_hash_index(block);
  }
  const auto n_recs = page_get_n_recs(page);
  auto rec = page_rec_get_next(page_get_infimum_rec(page));
  Rec_offsets offsets;
  const auto index_hash = btr_hash_seed_for_record(index);
  auto hash_value = rec_hash(rec, offsets.compute(rec, index, n_fields_for_offsets),
                            prefix_info.n_fields, prefix_info.n_bytes, index_hash, index);
  size_t n_cached = 0;
  if (prefix_info.left_side) {
    hashes[n_cached] = hash_value;
    recs[n_cached] = rec;
    n_cached++;
  }
  for (;;) {
    const auto next_rec = page_rec_get_next(rec);
    if (page_rec_is_supremum(next_rec)) {
      if (!prefix_info.left_side) {
        hashes[n_cached] = hash_value;
        recs[n_cached] = rec;
        n_cached++;
      }
      break;
    }
    const auto next_hash_value = rec_hash(next_rec,
                                          offsets.compute(next_rec, index, n_fields_for_offsets),
                                          prefix_info.n_fields, prefix_info.n_bytes,
                                          index_hash, index);
    if (hash_value != next_hash_value) {
      if (prefix_info.left_side) {
        hashes[n_cached] = next_hash_value;
        recs[n_cached] = next_rec;
        n_cached++;
      } else {
        hashes[n_cached] = hash_value;
        recs[n_cached] = rec;
        n_cached++;
      }
    }
    rec = next_rec;
    hash_value = next_hash_value;
  }
  // Reset page counter and store construction info
  block->n_hash_helps = 0;
  block->ahi.prefix_info = prefix_info;
  block->ahi.index = index;
  // Insert hash entries into the AHI hash table
  const auto table = btr_get_search_table(index);
  for (size_t i = 0; i < n_cached; i++) {
    ha_insert_for_hash(table, hashes[i], block, recs[i]);
  }
}
5. Summary
The AHI construction process consists of three hierarchical checks:
Index‑level: how many times the index has been hit.
Construction‑info level: how often a particular lower/upper‑bound pattern appears.
Data‑page level: how many times the same construction info has been observed for a specific page.
Only when all thresholds are satisfied does InnoDB build AHI for a page, and it may rebuild the hash index if the construction info changes or if the page is accessed enough times after the previous build.
This mechanism allows MySQL to accelerate repeated range scans while keeping memory and CPU overhead under control.
If you found this article helpful, please share, like, or comment.
For further MySQL discussions, feel free to add the author on WeChat (ID:
csch52
).
Public Account:
一树一溪
WeChat ID:
csch52