# Learned Index ## 定義 Learned Index は、索引構造をキーからレコード位置または存在を予測するモデルとして捉え、データ分布を学習するモデルと補助データ構造で従来索引の意味論的保証を回復する設計アプローチである。Kraska らは、B-Tree をソート済み配列上の位置予測モデル、ハッシュ索引を位置写像モデル、Bitmap/Bloom filter を存在判定モデルとして再解釈し、深層学習モデルを含む学習モデルで置換または補完できると提案した。(Source: [[@2017__arXiv__The Case for Learned Index Structures]]) ## 設計原理 - **範囲索引**: キーから位置を予測することは、ソート済みデータの CDF を近似することに等しい。予測位置の最小/最大誤差を保存し、局所探索で正しい上限/下限境界を回復する。 - **Recursive Model Index**: 上位モデルが CDF の大局形状を学び、下位モデルが局所領域を担当する。モデルサイズと実行コストを分離し、ラストマイルの誤差を小さくする。 - **ハイブリッド化**: 学習しにくい局所領域は B-Tree に置き換えられる。これにより最悪ケース性能を B-Tree に近づける。 - **点索引**: CDF モデルを $h(K)=F(K)*M$ としてスケールし、学習ハッシュ関数として使う。 - **存在索引**: 分類器と漏れ受け用 Bloom filter を組み合わせ、偽陰性ゼロの制約を保ちながらメモリを削減する。 ## 横断的知見 - **B-Tree は「古い索引」ではなく、学習索引の補助構造・フォールバックとして再配置される**: [[B-Tree]] はページング、範囲スキャン、リカバリ、更新との統合に強い。一方、[[@2017__arXiv__The Case for Learned Index Structures]] は B-Tree を CDF を近似する回帰木として再解釈し、RMI の下位段または難しい領域のフォールバックとして使う。したがって学習索引の論点は「B-Tree の完全置換」ではなく、データ分布が予測可能な領域だけをモデル化し、意味論的保証を既存構造で補う分担設計である。(Source: [[@2017__arXiv__The Case for Learned Index Structures]], [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]) - **DBMS への機械学習適用は、外付けのチューニングから内部データ構造の置換へ踏み込む**: [[データベースノブチューニング]] や [[クエリレイテンシ予測]] は DBMS を外から観測・最適化する。一方、学習索引は索引そのものをモデルに置き換える。これは ML for DBMS が「助言器」から「ストレージエンジン内部の構成部品」へ移る設計空間を開く。(Source: [[@2017__arXiv__The Case for Learned Index Structures]], [[@2017__SIGMOD__Automatic Database Management System Tuning Through Large-scale Machine Learning]], [[@2024__arXiv__OS Pre-trained Transformer - Predicting Query Latencies across Changing System Contexts]]) ## 未解決の問い - Learned index は更新・削除・MVCC・WAL・ページ分割を含む OLTP ストレージエンジンで、B-Tree の統合上の利点をどこまで保てるか。([[@2017__arXiv__The Case for Learned Index Structures]]) - 分布変化を検知し、再学習・delta-index・オンライン学習を切り替える運用ポリシーはどう設計すべきか。([[@2017__arXiv__The Case for Learned Index Structures]]) - 学習ハッシュ関数の衝突削減は、RDMA・分散ハッシュテーブル・大きなペイロードのどの条件でモデル実行コストを上回るか。([[@2017__arXiv__The Case for Learned Index Structures]]) - 学習 Bloom filter の「実クエリ分布での FPR」前提は、攻撃的クエリや共変量シフトがある環境でどのように保証できるか。([[@2017__arXiv__The Case for Learned Index Structures]]) ## 関連 - ソース: [[@2017__arXiv__The Case for Learned Index Structures]] - 概念: [[B-Tree]] / [[Bigtable]] / [[データベースノブチューニング]] / [[クエリレイテンシ予測]] - エンティティ: [[Tim Kraska]] / [[Alex Beutel]] / [[Ed H. Chi]] / [[Jeffrey Dean]] / [[Neoklis Polyzotis]] - 関連 MOC: [[structures/000 Index|000 Index]] ## 出典 - [[@2017__arXiv__The Case for Learned Index Structures]]（索引=モデル、CDF 定式化、RMI、学習ハッシュ関数、学習 Bloom filter、更新・ページング課題） - [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]（B-Tree の現代的な可ページング・CPU/cache 最適化）