SQLiteインデックスの可視化

 (mrsuh.com)
3 ポイント 投稿者 GN⁺ 2024-11-16 | 1件のコメント | WhatsAppで共有
  • SQLiteインデックスが実際にディスクとメモリ上でどのように配置されるのかを確認するため、B-Tree構造を分析し、インデックスデータをダンプして可視化した
  • インデックスはPageとCell単位で構成され、Pageは右側の子リンクとCellデータを、Cellはインデックスデータ・rowId・左側の子リンクを持つ
  • sqlite3_analyzerが提供するPageサイズ、エントリ数、B-treeの深さ、使用Page数だけでは不十分だったため、SQLiteソースにデバッグ関数を追加した
  • 実験ではレコード数、ASC/DESC、式ベースのインデックス、NULLを含むUNIQUE、Partial Index、複数カラム、テキスト・REAL・整数+テキストの組み合わせを比較した
  • 1,000,000件のレコードでは、インデックスを挿入前に作成すると3,342 Pages、挿入後に作成すると2,930 Pagesとなり、VACUUMまたはREINDEX後も2,930 Pagesに減少した

SQLiteインデックスを直接のぞき込んだ理由

  • インデックスの基本構造を超えて、実際のデータ構造、アルゴリズム、ディスク保存方式を確認するための実験である
  • 目的は、DBMSがインデックスをディスクとメモリに保存し、検索過程でそれにどうアクセスするかを調べることにある
  • 実験対象としてSQLiteを選んだ理由は次のとおり
    • ブラウザ、モバイルアプリ、オペレーティングシステムで広く使われるDBMSである
    • 別途サーバーなしでクライアントアプリケーションだけでデバッグしやすい
    • MySQLやPostgreSQLよりコードベースは小さいが、インデックスには類似したデータ構造を使っている
    • オープンソースである

PageとCellで構成されるB-Tree

  • SQLiteのドキュメントによれば、インデックスはB-Tree構造で保存される
  • SQLiteでNodeに相当する単位はPageである
    • PageはCellデータを保存する
    • Pageは右側の子Pageへのリンクを持つ
  • Cellはインデックスデータ、rowId、左側の子Pageリンクを含む
  • SQLiteテーブルの各行は基本的に一意なrowIdを持ち、明示的な主キーがないときは主キーのように動作する
  • 各Pageは固定サイズを持ち、その範囲は512~65,536 bytesである
  • PageとCellヘッダーは子リンクの保存に4 bytesを使用する
    • 子Page番号を知るには、get4byte(...)関数でヘッダーを別途読み取る必要がある
  • SQLite内部構造体の例は次のとおり
    • MemPage: Page番号pgno、Cell数nCell、Cellインデックス領域aCellIdx、PageデータのディスクイメージポインタaDataなどを含む
    • CellInfo: payload開始位置を指すpPayloadなどを含む

sqlite3_analyzerの限界とデバッグ関数

  • sqlite3_analyzerでインデックスの一般情報を見ることができる
    • 出力例にはPageサイズ4096、エントリ数1000、B-treeの深さ2、使用Page数4などが含まれる
  • しかしこのツールは、インデックス内部のCellやpayloadを直接のぞき込むには概要情報にとどまる
  • 数週間の実験の後、インデックス分析用の関数を書いた
    • コード: sqlite.patch
    • sqlite3DebugGetMemoryPayload(Mem *mem)
    • sqlite3DebugGetCellPayloadAndRowId(BtCursor *pCur, MemPage * pPage, int cellIndex)
    • sqlite3DebugBtreeIndexDump(BtCursor *pCur, int pageNumber)
  • これらの関数は、選択したインデックス内容を読み取ってSTDOUTに出力する
    • 流れは SQL query -> selected index -> stdout である
    • 出力にはPage番号、右側の子Page番号、Cell番号、左側の子Page番号、payload、rowIdが含まれる
  • Dockerで実験環境を実行できる
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/dump-index.sh database.sqlite "SELECT * FROM table INDEXED BY index WHERE column=1" dump.txt

可視化方法の変化

  • 当初はd3-org-treeを使ってインデックス構造を可視化していた
  • ツリーが深くなり、各レベルのPageが増えると、Page間の間隔調整が難しくなって画像が大きくなりすぎ、読みにくくなった
  • JavaScriptとCSSで調整しようとしたがうまく合わず、一時はテキストベースの構造表示に切り替えた
  • テキスト出力は、全Page数、全Cell数、レベルごとのPage数・Cell数、Page情報、Cell情報とpayloadを表示する
  • その後、PHPのImageMagick拡張を使い、デザインと間隔をより細かく制御できる画像出力へ発展させた
  • 最終画像には次の情報が含まれる
    • 左上にインデックスの一般情報を表示
    • 各レベルごとに総Page数とCell数を表示
    • 各PageごとにPage番号、右側の子リンク、最初のCellと最後のCell情報を表示
    • 各レベルでは一部のPageのみを表示し、最初のPageと最後のPageを含める
    • ルートPageは最初のレベルに配置される
  • ダンプから画像を生成するコマンドは次のとおり
    • php bin/console app:render-index --dumpIndexPath=dump.txt --outputImagePath=image.webp

レコード数が変えるインデックス形状

  • column1 INT NOT NULL テーブルに column1 ASC インデックスを作成し、レコード数を変えて構造を確認した
  • 1件のレコードのインデックスは、1レベル、1 Page、1 Cellで構成される
  • 1,000件のレコードのインデックスも同じ方法で生成して可視化した
  • 1,000,000件のレコードのインデックスは次の構造を持つ
    • 3レベル
    • 2,930 Pages
    • 1,000,000 Cells
  • データは順番に追加されたため、rowId = 1のときcolumn1 = 1である

ソート方向と式インデックス

  • 同じデータに対して idx_asc と idx_desc を作成し、ASC/DESCインデックスを比較した
  • ASCインデックスはデフォルトの並び順がASCであるため、先のインデックスと同じである
    • rowId=1,000,000, column1=1,000,000, payload=1,000,000 の項目が右端Pageの最後のCellにある
    • rowId=1, column1=1, payload=1 の項目が左端Pageの最初のCellにある
  • DESCインデックスは逆に配置される
    • rowId=1, column1=1, payload=1 の項目が右端Pageの最後のCellにある
    • rowId=1,000,000, column1=1,000,000, payload=1,000,000 の項目が左端Pageの最初のCellにある
  • 式ベースのインデックスは、式が生成した文字列を保存する
    • 例ではJSONテキストから $.timestamp を抽出し、strftime('%Y-%m-%d %H:%M:%S', ..., 'unixepoch') で変換してASCインデックスを作成する
    • より複雑な式も使え、インデックスにはその結果だけが保存される

NULL、Partial Index、複数カラム

  • SQLiteはNULL値を含むUNIQUEインデックスをサポートしている
    • 例では 1、多数の NULL、1000000 の値を入れ、CREATE UNIQUE INDEX idx ON table_test (column1 ASC) を実行する
    • 可視化されたインデックスはNULLでない値だけを保存しているように見える
  • WHERE column1 IS NOT NULL 条件付きのPartial IndexはNULL値をフィルタリングする
    • このインデックスは1 Pageしか含まない
    • 先のUNIQUE例より高速な検索につながる
  • 複数カラムインデックスは、Cell内にすべてのフィールドデータを順に保存する
    • 例は (column1 ASC, column2 ASC) インデックスである
    • 可視化ではフィールドがコロン : で区切られる

インデックス作成時点と再構成の効果

  • データを入れる前にインデックスを作った場合と、すべてのデータを入れた後にインデックスを作った場合を比較した
  • 新しいデータが追加されると、ツリーは自動的に再平衡化しなければならない
  • 既存データに対してインデックスを一度に作成する方式のほうが、はるかに効率的な場合がある
  • 2つのインデックスは似て見えるが、Page数が少ない後者のインデックスのほうが速い可能性がある
  • 1,000,000 Cells基準の比較結果は次のとおり
区分 Total Pages Total Cells
挿入前に作成 3342 1000000
挿入後に作成 2930 1000000
  • 同様の最適化はVACUUMまたはREINDEXでも行える
    • VACUUM はインデックスとテーブルをデータごと再生成する
    • REINDEX idx はインデックスだけを再生成する
  • どちらのコマンドも、例ではPage数を3342から2930に減らした

データ型ごとのインデックス保存

  • テキストデータは短い文字列ならインデックスCellに直接保存されるが、長いテキストは別途保存する必要がある
    • 例では text-1 から text-1000000 までを入れ、column1 ASC インデックスを作成する
    • 実際の文字列がインデックスに直接保存されている様子を確認できる
  • REALデータもインデックスに保存して可視化した
    • 例では 1.14, 2.14, ..., 1000000.14 の値を使う
  • 整数とテキストを組み合わせた複合インデックスも確認した
    • 例では (column1 INT, column2 TEXT) テーブルに (column1 ASC, column2 ASC) インデックスを作成する
    • 整数と文字列は、インデックス作成時に指定したとおり同じCellに一緒に保存される

再現方法と次の作業

  • この実験は、SQLiteインデックスがどのように構造化されるか、レコードデータがメモリにどう保存されるか、B-Treeがデータをどう構成しアクセスするかを示している
  • 可視化は、異なるインデックスを分析し比較するために使われる
  • すべての例は次のコマンドで再現できる
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/test-index.sh
  • コードと例は mrsuh/sqlite-index にある
  • 次の作業はインデックスベース検索の可視化と、いくつかのSQLクエリの探索である

関連記事

1件のコメント

 
GN⁺ 2024-11-16
Hacker News のコメント

  • SQLite のテーブルの各行には基本的に一意の rowId があり、明示的な主キーがない場合は主キーのように振る舞うとされているが、実際には主キーがあっても rowidを使う
    WITHOUT ROWID テーブルの主キーインデックスを可視化してみるとよさそう。そういうインデックスは特に興味深い
    2つのインデックスが似て見えても、2つ目のインデックスのページ数が少ないからといって、すぐに高速だという意味にはならない。重要なのは木の高さで、その次に、インデックスで値を見つけたあと残りのデータを別テーブル（rowid）から読む必要があるのか、それとも WITHOUT ROWID のようにデータがその場にあるのか、という点。特に where 50 <= col <= 100 のような範囲クエリでは差が大きい

    • 単一アクセスだけで見れば木の高さで合っているが、インデックスに頻繁にアクセスするなら、全体サイズもキャッシュヒット率にとって非常に重要になり得る
    • 主キーがあっても rowid を使う、という話には例外が1つある。INTEGER PRIMARY KEY を作ると、SQLite はそれを代わりに使う [1]
      [1]: https://sqlite.org/rowidtable.html

  • SQLite はほぼあらゆる処理方式でかなり独特な部類で、特にクエリ処理ではなおさらだと思う
    SQLite は性能より単純さを好む傾向があるので、私が扱ったことのある他のデータベースとは違う方法で実装していることが多い。SQLite は他のデータベースと競合するというより、永続保存用の JSON/XML ファイルと競合している。だから SQLite の実装を見ても、実際のデータベースが同じことをどう行っているかについて多くを知れるわけではない

    • どちらとも競合している。SQLite がローカルの永続ストレージとして使われるのは確かだが、別途サーバープロセスが不要な状況では、他のリレーショナルデータベース管理システムとも競合する
      要件が大きく違うという意味ではあるが、用途が JSON/XML ファイルの代替だけにとどまるわけではない
    • SQLite は本物のデータベースエンジンだ。おそらくデータベースサーバーとは競合しない、という意味に近いのだと思う
    • 他のデータベース管理システムのサーバーがストレージやインデックスを扱う方法と大きくかけ離れてはいない。原理はほぼ同じで、特に SQLite が WAL モードで動作しているときはそうだ

  • Webサイトがとても読みやすくて、実際に読みたくなる

    • iPhone で見ると本文のフォントサイズが大きすぎる。図表内の重要なテキストはずっと小さいので、本文を見るにはスマホを顔から遠ざけ、図表を読むにはまた近づける必要があってぎこちない
    • ぎっしり詰まった広告なしでコンテンツを読めるのは本当に快適。記事もとてもよい

  • “indexes” は動詞 “to index” の三人称単数現在形でもあり、“index” の複数名詞形でもある。一方 “indices” は伝統的な複数形で、特に数学・科学の文脈でよく使われる
    一般英語では “indexes” が一般的だが、技術分野では言語的な正確さのために indices を好む場合がある。この文脈で “indices” を使うと、索引付けの作業とインデックスの複数形を区別でき、明確さが増す

    • どちらでもよい（https://www.nasdaq.com/articles/indexes-or-indices-whats-the...）。SQLite と PostgreSQL のドキュメントも代表例として indexes を使っている
    • “time series” を複数形にしようとすると、なかなか難しい
      フィンランドでは、複数形として “time series” を使い、単数形として “time serie” を使う例を見たことがある
    • どういう権威でそう言っているのかわからない
      主要なリレーショナルデータベース管理システムはすべて indexes という用語を使っている
    • 対象読者による。学術界向けなら indices を使い、一般読者向けなら “indices” は気取っているように見えるかもしれない

  • PostgreSQL が同じことをどうやっているのかも見てみたい。比較しながら学べる点が多そう

  • より少ない作業でさまざまなレイアウトを見るには、yEd 用の TGF を出力するようにしてもよさそう