Skip to content

PATTERN Cited by 1 source

Runtime-adaptive in-memory index

Problem. A primary index structure (B+tree, skip list, LSM) is already optimised for the general case, but under production workloads a small subset of keys gets hit disproportionately often. Every repeated lookup pays the full index cost — O(log N) pointer chases, per-level latch acquisition, per-level key comparisons — even though the answer is essentially static for the lifetime of that key's residency.

Context. The storage engine has low-level visibility into access patterns: which keys, how often, against which index, at what inter-arrival distance. It can distinguish hot keys from cold keys at runtime with no schema change, no hint, no configuration.

Solution. Build a secondary, in-memory, hash-keyed index as an overlay on top of the primary index. Key it on (full or prefix of) the index value; value-point it directly into whichever on-top cache layer holds the target data (for InnoDB that's the buffer pool). Populate it adaptively — insert an overlay entry only once the engine has observed a value being looked up repeatedly, and invalidate overlay entries when the underlying cached page is evicted. Expose one boolean config knob for operators who know their workload doesn't benefit. Turn it off automatically when the observed workload doesn't justify the maintenance overhead.

This is the shape of MySQL's Adaptive Hash Index (AHI), canonicalised in Ben Dicken 2024-04-24. Ben Dicken's verbatim framing: "As its name suggests, the adaptive hash index (AHI) is constructed at runtime, and its usage adapts to the characteristics of your workload. … MySQL is able to automatically adjust its use of the AHI based on the behavior it observes in the buffer pool. If conditions are not right for its use (few repeated lookups, small buffer pool, etc), MySQL will reduce or eliminate its use."

Canonical implementation

MySQL's Adaptive Hash Index is the canonical implementation within database internals:

  1. Observation window. InnoDB tracks recent lookups on each B+tree index internally (not a user-visible structure). The tracking is per-page-per-index.
  2. Promotion trigger. A value observed being looked up sufficiently often is promoted to the AHI as a hash entry keyed on the value (full or prefix).
  3. Entry shape. Hash key → direct pointer into the corresponding page in the buffer pool. No copy of the row data lives in the AHI itself.
  4. Eviction coupling. If the target page is evicted from the buffer pool, the AHI entry becomes invalid. The AHI is fundamentally a cache on top of a cache.
  5. Auto-throttle. MySQL monitors the AHI's effectiveness (hit rate vs maintenance overhead) and scales its use up or down. If the workload shape changes — e.g., a batch scan blows through the buffer pool — AHI usage is reduced automatically.
  6. Operator override. innodb_adaptive_hash_index=0 turns the whole mechanism off. Observability via SHOW ENGINE INNODB STATUS \G;.

Measured benefit

From Dicken's 390M-row user-table benchmarks with username B+tree secondary index at 4 levels depth:

Workload AHI off AHI on Speed-up
Single-value repeated 14,044 QPS 16,701 QPS +16%
1000-value hot-set random 9,232 QPS 11,562 QPS +20%

Dicken's explicit scaling claim: "workloads using deeper B-tree indexes may see even more performance improvement." Depth-aware scaling is the pattern's load-bearing justification — an O(1) overlay on an O(1) structure is not worth the overhead, but an O(1) overlay on an O(log N) structure with deep N is.

Design trade-offs

Pro: no schema change, no hint, no configuration. Users don't have to know AHI exists. Hot-workload subsets of a table get accelerated without the DBA explicitly adding a hash index. In fact InnoDB doesn't permit true on-disk hash indexes at all — the AHI is the workaround.

Pro: adapts when the workload shifts. A batch job that inverts hotness temporarily doesn't leave a permanent AHI footprint — InnoDB scales AHI down as the workload shifts and back up when the OLTP pattern returns.

Con: overlay on a cache is an overlay on an overlay. The AHI depends on the buffer pool being stable enough that hot pages don't get evicted. A workload that thrashes the buffer pool pays the AHI's maintenance cost without getting its lookup benefit.

Con: latch contention at the overlay level. Before MySQL 5.7's innodb_adaptive_hash_index_parts partitioning (default 8), very-high-concurrency OLTP workloads contention on the single AHI latch, sometimes making AHI net-negative. The pattern is vulnerable to this failure mode; the fix is to partition the overlay.

Con: the maintenance cost is always-on. Even if the AHI isn't being consulted, insertion / invalidation logic runs on every mutation. MySQL auto-throttles usage but not the cost of observing. Operators with workloads known not to benefit can turn AHI off entirely.

The runtime-adaptive overlay driven by observed behaviour shape is a recurring system-design pattern, appearing at different altitudes:

Seen in

  • sources/2026-04-21-planetscale-the-mysql-adaptive-hash-index — Ben Dicken (PlanetScale, 2024-04-24) canonicalises MySQL InnoDB's Adaptive Hash Index as the archetype of this pattern. The mechanism turns O(log N) B+tree descents into O(1) hash probes for frequently looked-up values, with promotion/demotion driven entirely by InnoDB's observation of buffer-pool behaviour. No schema change, no configuration knob beyond on/off + partition count. Benchmarks demonstrate 16–20% speed-ups on repeated-lookup workloads. Canonical verbatim framing: "As its name suggests, the adaptive hash index (AHI) is constructed at runtime, and its usage adapts to the characteristics of your workload."
Last updated · 470 distilled / 1,213 read