SQLiteにおけるUUID主キーの危険性

 (andersmurphy.com)
1 ポイント 投稿者 GN⁺ 4 시간 전 | 1件のコメント | WhatsAppで共有
  • SQLiteの主キー実装は、通常のrowidテーブルとWITHOUT ROWIDテーブルで物理的な保存順序が異なり、ランダムなUUID4をクラスタ化インデックスとして使うと、B-treeの再平衡化と追加のページングコストが発生
  • 整数rowidのベースラインは100万行単位の挿入でおよそ毎秒100万件であり、UUID4 WITHOUT ROWIDでは挿入時間が14〜16倍遅いという結果
  • UUID4の無秩序な特性により、行はB-treeへランダムに挿入され、プロファイル結果でもツリーの平衡調整と読み書きにより多くの時間が使われた
  • UUID7 WITHOUT ROWIDは時系列順のUUIDで、UUID4の並び順の問題を軽減し、より妥当な挿入時間を示したが、16バイトのBLOBキーであるため、8バイト整数キーよりは依然として遅い
  • UUID4 WITH ROWIDは隠れたrowidの順次性を得られる一方、2つのインデックスによる書き込み増幅とランダムなインデックス挿入コストが残るため、UUID7 WITHOUT ROWIDより性能が低い

クラスタ化インデックスとは？

  • クラスタ化インデックスは、テーブル行の物理的な保存順序を決めるインデックス
  • 行は物理的に1つの方法でしか並べ替えられないため、各テーブルに存在できるクラスタ化インデックスは1つだけ
  • クラスタ化インデックスはテーブルそのものであり、非クラスタ化インデックスは、インデックス対象のカラムと実際の行データの位置を指すポインタだけを保存する

Rowid

  • すべての通常のSQLiteテーブルは、rowidという暗黙の64ビット整数主キーを持つ
  • テーブルデータは、各行ごとに1つのエントリを持つB-tree構造に保存され、rowid値がキーとして使われる
  • rowidは事実上SQLiteのクラスタ化インデックスであり、行の物理的な保存順序はrowid順となる
広告

WITHOUT ROWID

  • SQLiteはWITHOUT ROWIDテーブルをサポートしており、このテーブルには暗黙のrowidが存在しない
  • WITHOUT ROWIDテーブルでは、宣言した主キーがクラスタ化インデックスの役割を果たす
  • SQLiteのrowidテーブルは、すべての内容がリーフに保存されるB*-Treeとして実装されており、WITHOUT ROWIDテーブルでは、リーフと中間ノードの両方に内容を保存する通常のB-Treeが使われる

ベースライン: rowid整数主キー

  • ベースラインでは、id INTEGER PRIMARY KEY, data BLOB構成の通常のrowidテーブルで、100万行単位の挿入時間を測定
  • 結果表の総行数は1000万行から1億行までで、測定時間は692msから838msの範囲
  • ベースライン性能は、おおよそ毎秒100万件の挿入に相当する

UUID4 WITHOUT ROWID

  • UUID4テストでは、id BLOB PRIMARY KEY, data BLOB構成のWITHOUT ROWIDテーブルに、random-uuid4-bytes値を主キーとして挿入
  • 結果表の測定時間は、1000万行で2649ms、1億行で12586ms
  • 挿入性能は、整数rowidのベースラインより14〜16倍遅い水準

プロファイル

  • 正規化diffgraphはINTEGERとUUID4のプロファイリングスナップショットを比較し、flamegraph形式で差分を表示する
  • 正規化ビューは、2つのプロファイルの全サンプル数を同じに調整し、相対差を百分率で確認できるようにする方式
  • 青いフレームは、2番目のプロファイルであるUUID4でその関数時間がINTEGERより減った場合、赤いフレームはUUID4で増えた場合を示す
  • 色の強さは、そのフレーム自体のサンプル数の変化、つまりself time deltaの相対的な変化を表す
  • diffgraphでは、ツリーの平衡調整と読み書きにより多くの時間が使われていた
  • UUID4の無秩序な特性のため、キーがランダムな順序で並び、SQLiteがB-treeを継続的に再平衡化する構造になっている
広告

UUID7 WITHOUT ROWID

  • UUID7は時系列順のUUIDであり、UUID4の並び順の問題を解消できる方式
  • UUID7テストも、id BLOB PRIMARY KEY, data BLOB構成のWITHOUT ROWIDテーブルで実行
  • 結果表の測定時間は、1000万行で1372ms、1億行で1258ms
  • UUID7 WITHOUT ROWIDはUUID4 WITHOUT ROWIDより妥当な数値に戻ったが、ベースラインよりは依然として遅い
  • UUIDのBLOB主キーは16バイトで、整数主キーは8バイトという違いがある

UUID4 WITH ROWID

  • UUID4 WITH ROWIDテストでは、WITHOUT ROWIDを使わないid BLOB PRIMARY KEY, data BLOBテーブルを使用
  • この構成では、隠れたrowidがクラスタ化インデックスであり、rowidの利点は順次性にある
  • 欠点は、テーブルにインデックスが2つできることで、それに伴う書き込み増幅が発生する点
  • 結果表の測定時間は、1000万行で2003ms、1億行で7119ms
  • UUID4 WITH ROWIDはUUID7 WITHOUT ROWIDほど高性能ではなく、クラスタ化インデックスでなくても、ランダム挿入によってインデックスを継続的に構築し続ける構造になる

結論

  • SQLiteにおけるUUID主キーは、クラスタ化インデックスとキーの順序性によって挿入性能が大きく変わりうる選択肢である
  • ランダムUUIDの問題はSQLiteに限らず、クラスタ化インデックスを使う他のデータベースにも広がる問題である
  • ベンチマークコード全体はGitHubリポジトリで公開されている

関連記事

1件のコメント

 
GN⁺ 4 시간 전
Lobste.rsの意見

  • 良い。rowidテーブルで整数キーが単調増加ではなくランダムな場合の数値も見られると興味深そう
    記事で抜けている重要な点は、rowidテーブルの主インデックスはB+木で、without rowidテーブルはB木だということ
    そのため一般に、平均レコードサイズがあるしきい値を超えると後者は理想的ではない。インデックスの内部ノードがレコード全体を保持するからで、記憶ではSQLiteマニュアルはページサイズの1/20を経験則として挙げている

  • UUIDの性能を測るのにそこまで労力をかけたのに、自然キーは考慮していない
    整数でもUUIDでもその他の形式でも、代理キーは複雑さを増し、情報を追加せず、正規化の誤りを隠す
    筆者はUUIDを使う理由として「重複防止」を挙げているが、それは理由になっていない。あらゆるデータベースのあらゆるテーブルのあらゆる行は、その行を一意に識別する列の組であるキーを少なくとも1つ持つべきだ
    そうしたキーがないデータベースは重複情報を抱え、論理的不整合に弱い。そうしたキーがすでにあるデータベースに代理キーは不要だ。自然キーがすでに存在し、しかも強制されているなら、「性能のために必要だ」という主張は追加コストと不要な複雑性を意味するので、立証が必要だ

    • 想像力が足りないだけかもしれないが、現実世界から来るデータを扱うとき、本物の自然キーを見つけるのはたいてい難しいと思う
      一見ユニークに見える値が期待したほど一意でなかったり、不変だと思っていた値が結局変わらざるを得なかったりする
      一方で代理キーを使えば、他人が識別性をどう定義したか、あるいはたいていはきちんと定義していないことに依存せず、自分のシステム内で同一性を定義できる
      例外はある。モデル全体を自分で定義し、データがいわゆる現実世界から来ないなら、自然キーのほうが理にかなう。ただ、完全に正規化されているとは思えない現実のデータを入れるスキーマを設計するときは、代理キーが役立つことが多い
    • 単調増加する整数の代理キーには、すぐに役立つ実用性がかなりある
      どんな行でも整数で参照できるのでアクセスが大幅に単純になり、人が覚えたりクエリに書いたりするのも簡単だ
      単調増加なら、それ自体で情報も持っている。重複情報ではあるが事実だ
      参照速度も最適化される。B木、ビットマップなどでインデックスするのにほぼ最適なケースだ
      人々がUUIDを主に使うのは、だいたい混乱のためだと思う。たいていはキーを難読化して推測不能にしたいという理屈だが、なぜその目的のための別個の識別子ではなく、主キーにまでそれを強いるべきだと考えるのかは理解を諦めた
    • 「重複防止」という表現はブログ記事には出てこない。実際、記事ではUUIDをなぜ使うのか自体まったく述べられていない

  • UUIDバージョン7は先頭に48ビットのタイムスタンプがあるので、このようなランダム分布にはならない。そのため過剰なページングや再平衡も減るはずだ

    • その通り。記事で扱っているのはUUID7だ

  • 人々は本当にUUIDを主キーとして使っているのか？ UUIDが必要なときに補助キーとして持つのではなく、そうする利点は何なのか気になる

    • スケール拡張のためだ。多くのコンピュータと世界中の複数データセンターで高速に、たとえばS3アップロードのように一意IDを分散生成するなら、単一の増加整数にロックをかけたくはない。ロックは世界規模で同期するには遅い
      GUIDとUUIDは構造的にこの問題を解決する
      v1とv6はマシンIDとタイムスタンプをエンコードするので、各マシンごとの名前空間を持つ自動増分整数に近い
      多くの人がUUIDはランダムだと決めつけることから混乱が生じる。それはv4にだけ当てはまり、残念ながらv4を選ぶことにはコストがある
      データを整理したり、性能や衝突保証のためにv3、v5、v7のようなある程度の決定性が必要になることは多い
    • ランダムUUIDや均等分布のランダム値を補助キーに置いても、挿入は依然として遅くなる。クラスタ化インデックスではなくても、そのインデックスのB木では依然としてランダム挿入が起きるからだ