B-treeたどりを飛ばす近道

適応的ハッシュインデックス（Adaptive Hash Index）は、点検索（等価検索）を速くするための機構です。通常のB-tree検索では、ルートから中間ノードを経てリーフまで複数ページをたどる必要があります。もし同じキーへの検索が何度も繰り返されるなら、毎回この経路をたどるのは無駄です。適応的ハッシュインデックスは、InnoDBがB-treeの検索パターンを監視し、よくアクセスされるリーフページについて、キー値からバッファプール上の着地レコードへ直接飛べる参照を自動で構築します。

user_id='alice01'、name='Alice'を探すとき、ハッシュに載っていればルートと中間ノードを経ずに、リーフ上のそのレコードへ着地します。

左が毎回たどるページ、右がハッシュから同じリーフへ飛ぶ参照です。着地点はバッファプール上のレコードなので、対象ページがメモリにないときはこの近道は使えません。

「適応的」というのは、開発者が設定するのではなく、InnoDBが実際の検索傾向を見て必要なところだけ勝手に作る、という意味です。テーブルがほぼメモリに収まり、適したワークロードであれば、この近道によってインメモリデータベースに近い検索性能が得られます。トランザクション機能や信頼性を犠牲にするわけではありません。有効・無効はinnodb_adaptive_hash_indexで切り替えられます。MySQL 8.4では既定がOFFですが、8.0系では既定がONでした。

何をキーにハッシュを作るか

各ハッシュエントリは、インデックスキーのプレフィックス（先頭部分）からハッシュ値を計算し、そのプレフィックスに対応するバッファプール上の着地レコードへの参照を持ちます。点検索でキーが指定されると、ハッシュテーブルを引いて該当レコード（とそのページ）へ直接アクセスします。

プレフィックスはn_fields（列数）とn_bytes（バイト数）で定義されます。n_fieldsはプレフィックスに含めるインデックスキー列の数で、先頭からn_fields列を列全体として使います。n_bytesは、その次の列の先頭何バイトを含めるかです。列の境界でちょうど終わるならn_bytesは0になります。

例えば(user_id, name)の複合セカンダリインデックスで、user_id='alice01'、name='Alice'という行を考えます。n_fields=2、n_bytes=0なら、プレフィックスはuser_idとnameをまるごと使った'alice01' + 'Alice'です。一方n_fields=1、n_bytes=3なら、user_id列全体に加えて次のname列の先頭3バイトだけを使い、'alice01' + 'Ali'がプレフィックスになります。

構築のきっかけも決まっています。同じ検索パターン（同じプレフィックス）でのヒットが連続した回数を、InnoDBがインデックスごとにメモリ上のカウンタで数えており、テーブルの列やユーザーが直接参照・設定できるものではありません。この回数が一定を超えると、そのとき検索していたページに対してハッシュエントリが作られます。検索パターンが変わるとカウンタはリセットされます。逆に、ハッシュでヒットしない検索が続くと、新規の構築は控えられます（すでにあるエントリを消すわけではありません）。

検索パターンに合わせて調整する

プレフィックスの具体的な長さ（n_fieldsとn_bytes）は固定ではなく、検索でヒットしやすく、かつエントリ数を抑えられる長さが選ばれます。

同一リーフページ内で同じプレフィックスを持つレコードは1つのグループになり、各グループからは左端または右端の1件だけがハッシュに登録されます。1ページあたりのエントリ数を抑えるためです。ハッシュの目的は、正確なレコード位置をピンポイントで当てることではなく、該当ページ（またはページ内の着地点）へ到達することにあります。だからプレフィックスがユニークでなくても構いません。代表レコードに着いたあと、ページ内を少し走査して目的のキーを探せば足ります。ユニークにしなければ1エントリで複数レコードをカバーでき、メモリ効率が良くなります。左端と右端のどちらを取るかは、そのインデックスの検索パターンに応じて決まります。

検索頻度の高いページほど構築の閾値に達しやすく、限られた容量の中で優先的にハッシュ化されます。検索パターンが変わったときには推奨プレフィックスが更新され、ハッシュが作り直されます。

エントリが消えるとき

適応的ハッシュインデックスは増える一方ではなく、次の契機で削除されます。

参照先のB-treeリーフページがバッファプールから追い出されると、そのページを指すハッシュエントリは削除されます。メモリ上にないページへの参照は無効だからです。また、ページ分割やページ破棄などB-tree構造が変わったときも、該当するエントリが削除されます。ハッシュエントリは「キーKはページPにある」と記録していますが、分割でレコードが別のページへ移ると、この対応が壊れてしまうためです。

右端への連続昇順挿入で分割が起きる場合は、この削除の影響が小さく済みます。新しく挿入されたレコードだけが新ページへ移り、既存レコードはページ番号ごと旧ページにそのまま残るため、既存キーと「そのキーがどのページにあるか」という対応関係は分割の前後で変わりません。そのため、旧ページのハッシュエントリが分割で消えたあとに同じキーへ検索が来ても、B-treeをたどれば以前と同じ旧ページに行き着いてすぐ見つかり、以前と同じ対応関係でハッシュエントリがすぐに作り直されます。