The idea: a shortcut InnoDB builds by itself
Every InnoDB index is a B+ tree. To find id = 29, InnoDB starts at the root page and goes down, one page per level, until it reaches the leaf that holds the record. With a tree of 3 or 4 levels that is 3 or 4 page latches and binary searches for every lookup, even when the same few rows are asked for again and again. The adaptive hash index (AHI) is a hash table in memory that InnoDB builds by itself for those hot rows: key → pointer to the record. A lookup that finds its key there goes straight to the leaf and skips the tree.
The page has one table, t (id INT PRIMARY KEY, …). Its clustered index PRIMARY has a root P3, two internal pages and four leaves of up to 4 records each. You are thread T1; T2 to T4 only act in the last demo. Nobody creates the AHI: there is no CREATE INDEX for it. You can only turn it on or off.
The normal path: a B+ tree descent
btr_cur_search_to_nth_level() takes an S (shared) latch on the root, binary-searches its keys, picks the child, latches the child, releases the parent, and repeats down to the leaf (Demo: a lookup walks the B+ tree). Each step is cheap, but each step is a latch on a page that every other thread reading this index also latches, a few cache misses, and a binary search. The root is the hottest page in the whole server. See B+ Tree and Database Index for the tree itself.
How InnoDB decides to build
Every index has a small search info struct (btr_search_info), and every page in the buffer pool has a few counters. After each tree walk InnoDB updates them:
| Counter | What it counts | MySQL | This page |
|---|---|---|---|
hash_analysis | searches on the index; analysis starts after this many | 17 (BTR_SEARCH_HASH_ANALYSIS) | 17 |
n_hash_potential | searches in a row that a hash on the same prefix would have answered | build at 100 (BTR_SEARCH_BUILD_LIMIT) | build at 3 |
n_hash_helps (per page) | how often that pattern landed on this page | more than n_recs / 16 | at least 2 |
The pattern is the recommended prefix: how many leading fields of the key (n_fields) the searches use. For WHERE id = ? it is 1 field. When the same pattern keeps winning and a page is visited often enough, InnoDB calls btr_search_build_page_hash_index() for that page: one entry per record (Demo: a hot key earns hash entries). Only the hot pages get entries; a cold page like P9 never does.
What a hash entry is
An entry maps fold(prefix), a hash of the first n_fields columns, to a pointer to the record inside a buffer-pool page. A lookup folds its key, looks in one cell, follows the pointer, buffer-fixes the page and checks that the record really has that key (btr_search_check_guess()). If the key is not there, it is a hash miss: InnoDB sets last_hash_succ to false and walks the tree. While last_hash_succ is false it does not even try the hash, so a workload that never hits does not pay for probing.
What the AHI can't do
A hash keeps no order. It can answer "where is id = 29" but not "what comes after 29". So these always walk the tree and then follow the leaf chain (Demo: a range scan ignores the hash):
- range scans:
BETWEEN,<,>; LIKE 'ab%'prefix searches andORDER BYon the index;- lookups on a prefix shorter than the recommended one.
A different pattern also resets n_hash_potential, so a mixed workload builds fewer entries. For how MySQL picks an index and access method at all, see MySQL index access.
When entries go away
An entry points into a page frame, so it must go away before the frame changes or is reused:
| Event | What InnoDB does |
|---|---|
| page split, merge or reorganize | btr_search_drop_page_hash_index(): the records move, so the page's entries are removed (Demo: a page split drops hash entries) |
| page evicted from the buffer pool | buf_LRU_free_page() drops the page's entries first (Demo: eviction drops hash entries) |
| insert / delete on a hashed page | add or remove one entry, under the partition's X latch |
DROP TABLE, TRUNCATE, ALTER TABLE | drop every entry of the table's indexes (it used to stall big servers) |
innodb_adaptive_hash_index = OFF | empty the whole table |
A page whose entries were dropped has to earn them again through the counters. Page splits and the LRU list are on Inside an InnoDB page and the InnoDB buffer pool.
Partitions and latch contention
The AHI is split into innodb_adaptive_hash_index_parts partitions (default 8, up to 512), each with its own rw-latch and hash table. But the partition is chosen by index id, not by key: every entry of one index lives in one partition. A single hot table therefore means a single hot latch.
Readers take the latch in S mode, so they don't block each other. Every insert, delete or split on a hashed page needs it in X mode. Writers then wait for readers and for each other, and a reader that finds the latch X-held skips the AHI and walks the tree, so the shortcut is lost exactly when the server is busy (Demo: writers fight over one AHI latch). In SHOW ENGINE INNODB STATUS this shows up as many waits on btr0sea.cc in the SEMAPHORES section. Shared vs exclusive latches are on Readers-Writer Lock.
Should you turn it off?
The AHI helps a read-mostly workload of repeated equality lookups whose hot set fits in the buffer pool: fewer latches on the upper pages, less CPU. It helps little or hurts with heavy writes, many range scans, a working set much bigger than memory (entries are built and dropped all the time), or frequent DROP/TRUNCATE. For these reasons MySQL 8.4 changed the default of innodb_adaptive_hash_index to OFF (it was ON through 8.0). It is dynamic, so you can measure both ways. Look at the status section:
------------------------------------- INSERT BUFFER AND ADAPTIVE HASH INDEX ------------------------------------- Hash table size 34679, node heap has 3 buffer(s) ... 1520.33 hash searches/s, 210.18 non-hash searches/s
A high ratio of hash to non-hash searches says the AHI is used. Many btr0sea.cc waits under SEMAPHORES say it costs more than it saves. The canvas shows the same counters as totals instead of rates.
What the page leaves out
Real InnoDB hashes the first n_fields fields plus n_bytes of the next one, and chooses whether an entry points to the leftmost or rightmost record of a run of equal prefixes. Secondary indexes get entries too, and an AHI hit can also position a cursor for PAGE_CUR_LE searches. The counters are scaled down here (3 instead of 100), the hash table has 8 cells instead of tens of thousands, entries live in heap blocks taken from the buffer pool, and many threads run at once instead of one step at a time.