HN 日本語サマリー

← 一覧へ戻る
プログラミング

SQLiteのパフォーマンスをプリソートで向上させる

SQLite improving performance with pre-sort (andersmurphy.com)

43 pointsby tosh4 コメント

要約

この記事では、SQLiteへのランダムなデータ挿入がUUID4と同様に遅くなる問題に対し、プリソート(事前ソート)がどのようにパフォーマンスを向上させるかを探ります。特に、セッショントークンなどに使われる予測不可能なランダムなIDを挿入する際に、事前にデータをソートすることで、挿入速度が2〜3倍に改善されることを実証しています。

全文翻訳

SQLite improving performance with pre-sort

07 Jun 2026


前回の投稿では、UUID4のランダム性が挿入速度に大きな影響を与えること、そしてUUID7がどのように役立つかを示しました。しかし、ランダムな性質を持つ他のデータについてはどうでしょうか?UUID7で問題を解決できない場合はどうすればよいでしょうか?

Random data

ここでは、この記事で説明されているものと同様に、SecureRandomによって生成される160ビット(20バイト)のランダム値を使用します。なぜなら、セッショントークンのようなものにはUUID7を使用しない方が良い(情報漏洩のリスク、ユースケースによっては十分なエントロピーがないなど)からです。これは、プライマリキーがランダム(あるいはより具体的には順不同)であるあらゆるデータを表すこともできます。

以下はそれらを生成するコードです。

(defn random-unguessable-uid []
  (let [buffer (byte-array 20)]
    (.nextBytes secure-random buffer)))

これがどのようにパフォーマンスを発揮するか見てみましょう。

(d/q writer
  ["CREATE TABLE IF NOT EXISTS event(id BLOB PRIMARY KEY, data BLOB) WITHOUT ROWID"])
  
(dotimes [_ 10]
  (time
    (d/with-write-tx [db writer]
      (dotimes [_ 1000000]
        (d/q db ["INSERT INTO event (id, data) values (?, ?)"
                 (random-unguessable-id) data])))))

結果:

total rowstime in ms
10000002478
20000004927
30000006262
40000007195
50000008257
60000008704
70000009244
80000009771
900000010387
1000000011103

毎秒約10万件の挿入。UUID4の場合と同様に、遅いです。

Pre sort

B+ツリーの定義上の特徴は、それが順序付けられていることです。シーケンシャルな書き込みは高速です。ランダムなデータは、ページのフラッシング、ページの分割、ツリーの再編成を引き起こし、パフォーマンスを低下させます。これは良い状況ではありません。

しかし、私たちはすでにデータをバッチ処理しています。では、挿入前にソートしたらどうなるでしょうか?

まず、ランダムなIDを高速に比較する方法が必要です。20バイトなので、すべてをイテレートしたくありません。代わりに、最初の8バイトを取り出し、それをlongに変換します。良いソートを得るためには、バイト配列全体を比較する必要はないでしょう。重要なのは、この比較が無署名であり、SQLiteに一致することです。

When two BLOB values are compared, the result is determined using memcmp().

注意: これはランダムなデータをソートする最速の方法ではないかもしれません。私はインターネット接続なしでブログ記事を書きます(気が散りすぎるため)。検索も最近はひどいです。そのため、主にオフラインドキュメントと、dash(Linuxではzealが同等)を使用したあいまいテキスト検索で作業しています。Java/Clojureでバイト配列をソートするより高速で良い方法を知っているなら、教えてください!

(defn bytes->long [^bytes bytes]
  (-> (ByteBuffer/wrap bytes 0 8)
    (ByteBuffer/.getLong 0)))
    
(defn byte-compare
  "Compares the first 8 most significant bytes of a byte array.
  Big Endian (matches SQLites blob sort)."
  [a b]
    (Long/compareUnsigned
      (bytes->long a)
      (bytes->long b)))

これがどのようにパフォーマンスを発揮するか見てみましょう。

(d/q writer
  ["CREATE TABLE IF NOT EXISTS event(id BLOB PRIMARY KEY, data BLOB) WITHOUT ROWID"])

(dotimes [_ 10]
  (time
    (d/with-write-tx [db writer]
      (->> (repeatedly 1000000 random-unguessable-id)
        (sort byte-compare)
        (run!
          (fn [id]
            (d/q db ["INSERT INTO event (it, data) values (?, ?)"
                     id data])))))))

結果:

total rowstime in ms
10000001987
20000002251
30000002296
40000002614
50000002687
60000003244
70000003118
80000003311
90000003485
100000003835

面白い!オーバーヘッドがあるにもかかわらず、バッチをソートすることでパフォーマンスが約2〜3倍向上しました。

Conclusion

この投稿が、バッチ処理がいかに順不同なデータを扱う際にプリソートのような有用な最適化を開くかを示す助けになれば幸いです。

完全なベンチマークコードはこちらで見つけることができます。

Thanks to この投稿のドラフトを読み、フィードバックをくれたDatastar discordの皆さん。

Discussion