SQLiteのパフォーマンスをプリソートで向上させる
SQLite improving performance with pre-sort (andersmurphy.com)
要約
この記事では、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 rows | time in ms |
|---|---|
| 1000000 | 2478 |
| 2000000 | 4927 |
| 3000000 | 6262 |
| 4000000 | 7195 |
| 5000000 | 8257 |
| 6000000 | 8704 |
| 7000000 | 9244 |
| 8000000 | 9771 |
| 9000000 | 10387 |
| 10000000 | 11103 |
毎秒約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 rows | time in ms |
|---|---|
| 1000000 | 1987 |
| 2000000 | 2251 |
| 3000000 | 2296 |
| 4000000 | 2614 |
| 5000000 | 2687 |
| 6000000 | 3244 |
| 7000000 | 3118 |
| 8000000 | 3311 |
| 9000000 | 3485 |
| 10000000 | 3835 |
面白い!オーバーヘッドがあるにもかかわらず、バッチをソートすることでパフォーマンスが約2〜3倍向上しました。
Conclusion
この投稿が、バッチ処理がいかに順不同なデータを扱う際にプリソートのような有用な最適化を開くかを示す助けになれば幸いです。
完全なベンチマークコードはこちらで見つけることができます。
Thanks to この投稿のドラフトを読み、フィードバックをくれたDatastar discordの皆さん。