Skip to content

CONCEPT Cited by 1 source

Adaptive Hash Index

The Adaptive Hash Index (AHI) is an in-memory hash table that MySQL's InnoDB storage engine builds at runtime as an optional overlay on top of its B+tree indexes. For index values InnoDB observes being looked up repeatedly, it populates an AHI entry whose key is the (full or prefix of the) index value and whose value is a direct pointer into the target page inside the buffer pool. Future lookups of the same value short-circuit the B+tree descent: a single O(1) hash probe replaces the O(log N) tree walk.

InnoDB does not support true on-disk HASH indexes. A user- issued CREATE INDEX ... USING HASH against an InnoDB table "will instead create a B-tree index" — InnoDB silently substitutes B+tree and emits a warning. The AHI is the in-memory-only workaround that recovers hash-lookup performance for the hot subset of keys. (Source: sources/2026-04-21-planetscale-the-mysql-adaptive-hash-index.)

Architectural shape

    ┌────────────────────────────────┐
    │   Query execution (InnoDB)     │
    └──────────────┬─────────────────┘
                   │ lookup(index, key)
                   ▼
    ┌────────────────────────────────┐
    │      Adaptive Hash Index       │  ← in-memory, optional overlay
    │  key → buffer-pool page ptr    │
    └──────────────┬─────────────────┘
                   │ miss / not eligible
                   ▼
    ┌────────────────────────────────┐
    │        Buffer pool             │  ← cached 16KB pages (hot working set)
    └──────────────┬─────────────────┘
                   │ miss
                   ▼
    ┌────────────────────────────────┐
    │   B+tree on disk (via page I/O)│
    └────────────────────────────────┘

Three facts follow from this picture:

  1. AHI is a cache on top of the buffer pool, not on top of the B+tree. "The pointers in the adaptive hash index only point to data within the buffer pool." An AHI entry is valid only while the referenced page is buffer-pool-resident. Page eviction invalidates the corresponding AHI entries.
  2. AHI presupposes a sufficiently large buffer pool. "If it is small and there are a lot of evictions taking place, it is not worth using it." Small buffer pool + churn → AHI entries constantly invalidated by evictions → maintenance overhead exceeds lookup savings.
  3. AHI is adaptive both up and down. MySQL observes buffer-pool behaviour and "automatically adjust[s] its use of the AHI based on the behavior it observes … If conditions are not right for its use (few repeated lookups, small buffer pool, etc), MySQL will reduce or eliminate its use." See patterns/runtime-adaptive-in-memory-index for the general pattern.

Keys: full values vs prefixes

AHI entries can be either the full index value or a prefix of it. "If MySQL observes that a particular value is getting repeatedly looked up in a B-tree index, an entry in the AHI can be created either with the full value, or a prefix of the value." Prefix-keyed AHI entries amortise a single hash entry across multiple lookups sharing a common prefix. This mirrors prefix-index mechanics on B+tree secondary indexes without incurring the prefix's selectivity penalty — the B+tree still resolves the final page, the AHI just avoids the descent.

Config surface

Knob Default Purpose
innodb_adaptive_hash_index ON Enable/disable AHI globally
innodb_adaptive_hash_index_parts 8 (MySQL 5.7+) Partition the AHI across N independent hash tables to reduce latch contention

Operationally observable via:

SHOW ENGINE INNODB STATUS \G;

The INSERT BUFFER AND ADAPTIVE HASH INDEX section reports Hash table size, node heap has N buffer(s), and the load-bearing metric — hash searches/s vs non-hash searches/s — which directly exposes AHI hit rate.

Why it pays off (and when it doesn't)

B+tree descents in InnoDB are already close to memory-speed when the relevant pages are buffer-pool-resident. What AHI still eliminates:

  1. Per-level page lookups. "There's still a (small) cost to looking up a page in the buffer pool." — hash- table lookup, latch acquisition, metadata bookkeeping at each level. For a 4-level tree, that's four per-level lookups replaced by one.
  2. Per-level key comparisons. Each internal node requires a binary-search through the node's keys; a deep enough tree accumulates hundreds of comparisons per lookup.

The benefit scales with (a) tree depth — "workloads using deeper B-tree indexes may see even more performance improvement" — and (b) workload concentration on a small repeated key set.

Benchmark: Dicken 2024-04-24

Two benchmark runs against a 390M-row user table with a username B+tree secondary index (4 levels deep):

Workload AHI off AHI on Δ
Single-value repeated (WHERE username='willpeace1', 500k iter) 35.6 s / 14,043 QPS / 0 hash/s / 418k non-hash/s 29.94 s / 16,701 QPS / 350,953 hash/s / 50,985 non-hash/s +16%
1000-value hot-set random (500k iter) 54.16 s / 9,232 QPS 43.24 s / 11,562 QPS +20%

Canonical framing: "even with such a large data set, the B-tree index … was only 4 levels deep … Running these types of workloads on tables with smaller indexes, and therefore shorter B-tree indexes, may result in less noticeable speedup. On the other hand, workloads using deeper B-tree indexes may see even more performance improvement."

Non-hash searches remain nonzero even with AHI on because "the query still needs to access the actual data in the row, not just the index value" — secondary-index lookups in InnoDB require a second B+tree walk into the clustered index to fetch the row data. AHI only accelerates the first (secondary-index) walk.

Relationship to other InnoDB in-memory structures

  • Buffer pool — the substrate. AHI entries point into it; AHI is nothing without it. Common 50–70% of RAM sizing.
  • Change buffer — deferred secondary-index write batching. Orthogonal to AHI (which accelerates reads). Both sit between SQL execution and the B+tree.
  • Doublewrite buffer — durability mechanism for partial-page-write protection. Not a cache; no performance role.
  • Adaptive hash index — this page. Read-side O(1) overlay on top of buffer-pool-resident hot pages.

When operators disable AHI

Two common reasons to set innodb_adaptive_hash_index=0:

  1. Latch contention at very high concurrency — before MySQL 5.7's AHI partitioning, the single btr_search_latch mutex became a bottleneck at dozens of concurrent B+tree lookups per second. Historically this produced the canonical "disable AHI on high- concurrency OLTP" advice still repeated in older references. MySQL 5.7's innodb_adaptive_hash_index_parts (default 8) largely closed this gap.
  2. Workload shape mismatch — analytic / scan-heavy workloads with low temporal locality pay AHI's maintenance overhead without getting lookup savings. Dicken frames this as the primary decision criterion in 2024-04-24.

Seen in

  • sources/2026-04-21-planetscale-the-mysql-adaptive-hash-index — Ben Dicken (PlanetScale, 2024-04-24) canonicalises AHI as InnoDB's in-memory substitute for true on-disk hash indexes, a runtime-adaptive overlay on top of the buffer pool that turns O(log N) B+tree descents into O(1) hash probes for frequently looked-up values. Two benchmarks at 390M rows quantify the benefit: 16% speed-up on single-value repeated lookups (14,044 → 16,701 QPS), 20% on 1000-value hot-set random lookups (9,232 → 11,562 QPS). Canonical disclosures: (1) AHI pointers go into the buffer pool, so buffer pool size + eviction rate determine whether AHI is worthwhile; (2) AHI keys can be prefixes, not just full values; (3) AHI usage auto-scales up and down as MySQL observes workload behaviour; (4) observable via SHOW ENGINE INNODB STATUS \G; under the INSERT BUFFER AND ADAPTIVE HASH INDEX section (hash searches/s vs non-hash searches/s); (5) tuned via innodb_adaptive_hash_index (on/off) and innodb_adaptive_hash_index_parts (partition count, for latch-contention mitigation).
Last updated · 470 distilled / 1,213 read