朝、自分の端末の検索欄に「猫」と打つと、結果が空でした。
打ち直しても同じです。たしかに、打った瞬間に結果が空になります。カタログには猫のタイトルが600枚以上あります。エラーログには何も残っていません。クラッシュもしていません。ただ、0件。
原因は、その前の週に私自身が入れた検索インデックスでした。件数が増えてきたので「そろそろ線形走査は限界だろう」と考え、SQLite の FTS5 に載せ替えたところだったのです。速くはなりました。ただ、日本語で最も打たれやすい長さのクエリが、まるごと落ちていました。
この記事は、その後で腰を据えて計測をやり直した記録です。線形走査・bigram 転置索引・FTS5 trigram の3つを同じデータで走らせ、どの規模でどれを選ぶべきかを実数で決め直しました。結論から言えば、私は索引を捨てて線形走査に戻しています。
計測の土台 — 再現可能なカタログを作る
実データをそのまま貼ると再現できないので、壁紙カタログを模した擬似データを決定論的に生成しました。タイトルは「修飾＋被写体＋接尾」、タグは3つです。1件あたり正規化後およそ13〜20文字という、実物に近い分布になっています。
// gen.mjs — 線形合同法で決定論的に生成（同じ seed なら同じカタログ） let seed = 20260802 ; const rnd = () => (seed = (seed * 1103515245 + 12345 ) & 0x7fffffff ) / 0x7fffffff ; const pick = ( a ) => a[Math. floor ( rnd () * a. length )];
const subj = [ "夜景" , "桜" , "富士山" , "海" , "星空" , "猫" , "森" , "雪原" , "花火" , "滝" , "紅葉" , "銀河" ]; const mod = [ "静かな" , "淡い" , "鮮やかな" , "霧の" , "真夜中の" , "冬の" , "黄昏の" , "雨上がりの" ]; const suf = [ "の風景" , "のシルエット" , "のグラデーション" , "のパノラマ" , "" , "" ]; const tagp = [ "ミニマル" , "ダーク" , "パステル" , "モノクロ" , "和風" , "自然" , "高解像度" , "縦向き" ];
export function makeCatalog ( n ) { const out = []; for ( let i = 0 ; i < n; i ++ ) { out. push ({ id: "w" + i, title: pick (mod) + pick (subj) + pick (suf), tags: [ pick (tagp), pick (tagp), pick (tagp)], }); } return out; } 正規化は3層です。NFKC で全角半角を潰し、小文字化し、カタカナをひらがなへ寄せ、空白を落とします。表記ゆれの吸収そのものは以前まとめたとおりですが、今回はこの関数の実行コストが主役になります。
const norm = ( s ) => s . normalize ( "NFKC" ) . toLowerCase () . replace ( / [ァ-ヶ] / g , ( c ) => String. fromCharCode (c. charCodeAt ( 0 ) - 0x60 )) . replace ( / \s + / g , "" ); 計測環境は Linux コンテナ上の Node 22.22 と Python 3.10（SQLite 3.37.2）です。手元の iPhone ではありません。以下の数値は絶対値ではなく比率と桁を読むためのものとして扱ってください。実機での倍率は今回測り切れておりませんので、ご自身の端末で測り直していただければ幸いです。
素朴な線形走査は、思っていたよりずっと遠くまで走る
まず「何もしない」実装を測ります。読み込み時に正規化済みのキー配列を作り、クエリごとに indexOf で舐めるだけの実装です。
// 正規化済みキーを平坦な文字列配列で保持する const keys = new Array (items. length ); for ( let i = 0 ; i < items. length ; i ++ ) { keys[i] = norm (items[i].title + items[i].tags. join ( "" )); }
function search ( q ) { const nq = norm (q); const hits = []; for ( let i = 0 ; i < keys. length ; i ++ ) { if (keys[i]. indexOf (nq) >= 0 ) hits. push (i); } return hits; } 8種類のクエリを各20回、中央値を取った結果です。比較のため { id, k } のオブジェクト配列に対する filter も並べました。
60fps のフレーム予算は16.7ms です。この環境では20万件まで1フレームに収まりました。実機ではもっと遅くなるはずですが、数万件規模なら線形走査で十分に戦えます。
同じデータ・同じ判定でありながら、平坦な配列とオブジェクト配列で1.4倍の差が出ている点は覚えておく価値があります。プロパティアクセスが1段挟まるだけの違いですが、走査回数が件数分あるので効いてきます。索引を設計する前に、まずここを平坦にするほうが費用対効果は高いです。
私が最初に索引へ手を伸ばした判断は、この表を作る前のものでした。「2万件は多い」という体感だけで動いていたわけです。数字を見ないまま設計を進めてしまうのが、いちばん高くつく癖だったのかもしれません。
bigram 転置索引は、成果よりも荷物のほうが重かった
次に、正攻法とされる転置索引を作ります。正規化済みキーを2文字ずつに割り、gram ごとに文書 ID の集合を持たせる形です。
function buildBigram ( items ) { const idx = Object. create ( null ); for ( let i = 0 ; i < items. length ; i ++ ) { const k = norm (items[i].title + items[i].tags. join ( "" )); for ( let j = 0 ; j + 2 <= k. length ; j ++ ) { (idx[k. slice (j, j + 2 )] ||= []). push (i); } } for ( const g in idx) idx[g] = [ ...new Set (idx[g])]; return idx; }
function queryBigram ( idx , keys , q ) { const nq = norm (q); if (nq. length < 2 ) return null ; // ← ここが後で問題になります const grams = []; for ( let j = 0 ; j + 2 <= nq. length ; j ++ ) grams. push (nq. slice (j, j + 2 ));
let cand = null ; for ( const g of grams) { const posting = idx[g]; if ( ! posting) return []; if (cand === null ) cand = posting; else { const s = new Set (posting); cand = cand. filter (( x ) => s. has (x)); } if (cand. length === 0 ) return []; } // gram の並び順は保証されないので、最後に実文字列で確認する return cand. filter (( i ) => keys[i]. includes (nq)); } 検索そのものは確かに速くなりました。20,000件で0.093ms、線形走査の8分の1です。問題はその外側にありました。
索引のサイズが、元のカタログとほぼ同じです。50,000件では97%。つまり検索を速くするために、配布物を約2倍にすることになります。ダウンロードサイズが App Store の表示に出る以上、これは軽い判断ではありません。
そして検証中に、線形走査との結果比較でずれが出ました。
MISMATCH 20000 滝 linear=708件 bigram=0件
nq.length < 2 で早期リターンしている箇所です。1文字のクエリは bigram を1つも作れないため、索引だけでは原理的に引けません。日本語では「猫」「桜」「月」「海」のような1文字が普通に打たれます。索引を入れた時点で、この層が丸ごと落ちていました。
ここまでは、まだ自分の実装の穴です。次が本題でした。
FTS5 の trigram は、2文字以下を例外なしで捨てる
「自前の索引が雑だったのだ」と考えて、SQLite の FTS5 に移しました。Expo なら expo-sqlite で使えますし、CJK に対して trigram トークナイザが用意されています。素性の確かな実装に任せるほうが安全だと考えたわけです。
# 20,000件を trigram トークナイザで格納し、plain テーブルと突き合わせる c.execute( "CREATE VIRTUAL TABLE s USING fts5(id UNINDEXED, k, tokenize='trigram')" ) c.executemany( "INSERT INTO s VALUES (?,?)" , rows)
c.execute( "CREATE TABLE plain(id TEXT, k TEXT)" ) c.executemany( "INSERT INTO plain VALUES (?,?)" , rows)
for q in [ "夜景" , "猫" , "桜" , "星空の" , "高解像度" ]: m = c.execute( "SELECT count(*) FROM s WHERE k MATCH ?" , ( '"' + q + '"' ,)).fetchone()[ 0 ] l = c.execute( "SELECT count(*) FROM plain WHERE k LIKE ?" , ( '%' + q + '%' ,)).fetchone()[ 0 ] print (q, len (q), m, l) 出力です。
例外は投げません。警告も出ません。3文字未満のクエリは、trigram を1つも構成できないため、そのまま空集合になります。仕様としては当然の帰結ですが、アプリの画面上では「該当なし」と区別がつきません。ユーザーから見れば「この壁紙アプリには猫がない」のです。
trigram という名前は「3文字単位で索引する」ことしか語っていません。「3文字未満は引けない」は、その裏側にある帰結です。英語で cat を引けば3文字ですから、英語圏の感覚では問題として立ち上がりません。日本語で「猫」は1文字。この非対称が、そのまま落とし穴になっていました。
もう一つ、この記事の初稿では「仮想テーブルに LIKE を投げると0件になる」と書いておりました。今回、SQLite 3.53.1 で試し直したところ、その記述は誤りでした。trigram トークナイザのテーブルでは、LIKE も部分一致で正しい件数を返します。
-- FTS5 仮想テーブル（trigram）に対する LIKE SELECT count ( * ) FROM s WHERE k LIKE '%猫%' ; -- 1文字でも件数が返る SELECT count ( * ) FROM s WHERE k MATCH '"猫"' ; -- こちらは 0 気づいたのは、ハイブリッドの表を作り直そうと、仮想テーブルへ直接 LIKE を当てた瞬間でした。初稿を書いた環境の SQLite は 3.37.2 で、そちらで同じ結果になるかは、今回の環境に入れていないため確かめられていません。確かめた範囲だけをお伝えします。
そのうえで、短いクエリを仮想テーブルの LIKE に任せた場合と、同じ内容の通常テーブルに任せた場合を測りました。カタログは今回作り直した擬似データ（20,000件）で、件数は上の表と一致しません。比べていただきたいのは、同じ表のなかの列どうしです。
3文字未満では索引が使えず、仮想テーブルの LIKE は全件走査になります。この環境では、通常テーブルの約2倍の時間でした。つまり、短いクエリの経路を別の通常テーブルにする意味は「正しさ」ではなく「速さ」にあります。速さを諦めて3ms前後で足りるなら、データを二重に持たずに済む、という選び方もあるのです。
ハイブリッドにしたら、遅いほうの経路に引きずられた
素直な対処は、クエリ長で経路を分けることです。3文字以上は FTS5、2文字以下は通常テーブルへの LIKE。書いて測りました。
正しさは戻りました。ただ、この表を眺めていて手が止まりました。
同じ20,000件に対する JavaScript の線形走査は0.80msです。ハイブリッドの遅いほうの経路（4.7〜5.3ms）は、その6倍前後かかっています。速いほうの経路ですら、ヒット件数が増えると4.46msまで落ちます。
つまりこの規模では、SQLite を挟んだ全経路が、素朴な線形走査に負けていました。索引の理論上の優位は、20,000件という規模では実測に現れません。現れるどころか、シリアライズとブリッジ越えの固定費のほうが大きいのです。
FTS5 のデータベースファイルは20,000件で3.3MB、50,000件で9.4MBでした。挿入も20,000件で252ms、50,000件で628msかかります。この費用を払って得たものが「線形走査より遅い検索」だったことになります。
判断として整理すると、こうなります。
索引を足すかどうかは、検索の速さではなく、短いクエリと起動の費用を測ってから決めます。 この一文を、次の設計のたびに読み返しています。
本当のボトルネックは検索ではなく、起動時の正規化だった
ここまで検索の応答ばかり測ってきましたが、体感を支配していたのは別の場所でした。読み込み時に全件へ norm() を掛けるパスです。
20,000件で39.5ms。検索1回の0.80msに対して、実に49倍です。私は0.8msを0.09msに縮める作業に週末を使い、その手前にある39.5msを見ていませんでした。
しかもこれは JavaScript スレッドを占有します。実機ではこれより重くなりますので、10万件規模なら起動が目に見えて重くなる水準です。
対処は単純でした。正規化をビルド時に済ませ、結果だけを配布します。
// scripts/build-search-keys.mjs — ビルド時に1回だけ走らせる import fs from "node:fs" ;
const norm = ( s ) => s . normalize ( "NFKC" ) . toLowerCase () . replace ( / [ァ-ヶ] / g , ( c ) => String. fromCharCode (c. charCodeAt ( 0 ) - 0x60 )) . replace ( / \s + / g , "" );
const items = JSON . parse (fs. readFileSync ( "assets/catalog.json" , "utf8" ));
// 改行区切りの単一文字列として出す。id は行番号で対応させる const keys = items. map (( it ) => norm (it.title + it.tags. join ( "" ))); if (keys. some (( k ) => k. includes ( " \n " ))) { throw new Error ( "正規化後のキーに改行が混入しています。区切り文字を見直してください" ); } fs. writeFileSync ( "assets/search-keys.txt" , keys. join ( " \n " )); console. log ( `wrote ${ keys . length } keys / ${ Buffer . byteLength ( keys . join ( " \n " )) } bytes` ); アプリ側は読み込んで split するだけです。
import { Asset } from "expo-asset" ; import * as FileSystem from "expo-file-system" ;
let KEYS = null ;
export async function loadSearchKeys () { if ( KEYS ) return KEYS ; const asset = Asset. fromModule ( require ( "../assets/search-keys.txt" )); await asset. downloadAsync (); const raw = await FileSystem. readAsStringAsync (asset.localUri); KEYS = raw. split ( " \n " ); return KEYS ; }
export function searchByKeys ( nq ) { const hits = []; for ( let i = 0 ; i < KEYS . length ; i ++ ) { if ( KEYS [i]. indexOf (nq) >= 0 ) hits. push (i); } return hits; } JSON 配列ではなく改行連結にしたのは、実測で速く、かつ小さかったからです。20,000件で JSON.parse が1.6ms・1,118KB に対し、split は1.1ms・1,078KB。100,000件では7.5ms 対 3.9ms と、差が開きます。引用符とカンマの分だけ素直に軽くなる、という納得のいく結果でした。
改行を区切りに使う以上、キーに改行が混入したら全体がずれます。ビルドスクリプト側で必ず弾いてください。私は一度これを省いて、タグに改行が入った1件のせいで以降のインデックスが1つずれる状態を本番に出しました。検索結果の画像が全部となりの壁紙になるという、原因が分かるまで気持ちの悪い不具合でした。
私が最終的に採った構成
現在の壁紙アプリは、次の形に落ち着いています。カタログは約24,000件です。
FTS5 は外しました。件数が今の4倍を超え、実測でフレーム予算を割るようになったら戻す予定です。そのときは短いクエリ用の通常テーブルを最初から用意します。
私はこの、依存を1つ減らして手で読める構成を好みます。速さのためではなく、0件が返ってきたときに原因を10行の中から探せるからです。同じカタログを Google Play 側のビルドでも使っていますが、共有しているのは正規化関数とキー生成スクリプトだけで済んでいます。
判断の分かれ目を表にしておきます。手元の環境で測り直したうえで使ってください。
Rork や Expo でこの部分を生成させる場合、「検索機能を付けてください」だけでは、まず英語圏の前提が入ります。私は次のように仕様まで書いて渡すようにしました。
アプリ内検索を実装してください。要件は以下です。
- 検索対象は正規化済みのキー配列（assets/search-keys.txt を改行区切りで読む）
- 正規化: NFKC → 小文字化 → カタカナをひらがなへ → 空白除去。クエリ側にも同じ関数を適用
- 1文字のクエリでも必ず動作すること。n-gram 索引や FTS5 の trigram は使わないでください
- 入力は 200ms の debounce。前回の検索は AbortController 相当で打ち切る
- 0件のときは「該当なし」ではなく、タグ候補を3つ提示する画面にしてください
3行目を明示するようになったのは、今回の一件のあとです。生成されたコードが速いかどうかより、日本語で1文字が引けるかどうかを先に確かめるようになりました。
次の一歩
もし手元のアプリに検索があるなら、まず1文字のクエリを1つ打ってみてください。よく使われる被写体を1つ、ひらがな1文字でも構いません。件数が返ってくるか、0件になるか。それだけで、索引の設計が日本語を想定しているかが分かります。
そのうえで、検索の応答ではなく起動時の準備コストを測ってみてください。私の場合、縮める余地は検索側に0.7ms、起動側に38msありました。時間を使うべき場所は、測るまで分からないものです。
数字はすべて私自身の環境で実際に走らせて取ったものです。桁と比率は参考になるはずですが、絶対値はぜひご自身の端末で確かめてみてください。お読みいただきありがとうございました。