ベクトルの検索を速くする素朴な方法が、あらかじめ組に分けておいて、近い組だけを見るやり方です。IVFと呼ばれます。
20,000件を64組に分けて測ったところ、1組だけ見る設定は54.7倍速で再現率34.1%。8組まで広げると再現率100%で7.5倍速でした。
64組に分けて実際に測りました。1組だけ見ると54.7倍速で再現率34.1%、8組で再現率100%・7.5倍速です。
IVFがどう効くのかを、見る組の数を変えながら測りました。用意したのは64次元のベクトル20,000件を64組に分けた索引です。
索引の構築も検索も本当に実行しています。全探索の上位10件を正解として、再現率と走査件数を数えました。時間は実行のたびにぶれるので、桁と比で読んでください。
function searchIvf(ix, q, nprobe) {
// 代表点との距離で、見る組を選ぶ
const near = ix.reps.map((r, c) => ({ c, d: d2(q, r) }))
.sort((a, b) => a.d - b.d).slice(0, nprobe);
const cand = [];
for (const { c } of near) for (const i of ix.buckets[c]) cand.push({ i, d: d2(q, vecs[i]) });
return { ids: topK(cand, K), scanned: cand.length };
}
登録 20,000件（64次元）・上位10件・問い合わせ 200回 全探索 1回あたり 5164 マイクロ秒 組の数 見る組 再現率 走査件数 1回あたり 全探索比 64組 1組 34.1% 319件 94 μs 54.7倍 64組 4組 88.2% 1,261件 381 μs 13.6倍 64組 8組 100.0% 2,484件 690 μs 7.5倍 64組 16組 100.0% 4,897件 1454 μs 3.6倍
走査件数の減り方が仕組みをそのまま表しています。20,000件が319件。62分の1しか見ていません。
問題は再現率です。1組だけ見た場合、正解の10件のうち3.4件しか取れていません。
理由は組の境目にあります。問い合わせに近い点が、必ずしも同じ組に入っているとは限りません。境目のすぐ向こう側にある点は、隣の組に入っています。
見る組を増やすと、隣の組も拾えるようになります。4組で88.2%、8組で100%。この間で境目の取りこぼしが解消しています。
8組見ても走査は2,484件で、全体の1割強です。取りこぼしなしで7.5倍速なら実用になります。
16組まで広げると走査が4,897件に倍増しますが、再現率は100%のままです。速さだけが3.6倍に落ちます。
再現率が頭打ちになったら、そこで止めるのが正解です。設定の詰め方はインデックスチューニングの記事で扱っています。
境目の取りこぼしが、4組から8組の間で埋まる。
似たベクトルを組にまとめ、組ごとの代表点を持ちます。検索では代表点だけを先に見て、行き先を絞ります。
IVFは、登録されたベクトルを組に分け、組ごとに代表点を1つ持つ索引です。検索のときは、まず代表点だけを見て、どの組を調べるかを決めます。
索引を作る段階で、どのベクトルがどの組に入るかを決めます。組の代表点を仮に置き、各ベクトルを近い代表点に割り当て、代表点を平均で置き直す。これを数回繰り返します。
この処理は学習にあたります。ですからデータがない状態では索引を作れません。pgvectorでも、別の索引方式にはこの学習の段階がないため、データが入っていなくても作れると対比されています。
引くときは2段です。代表点と比べて近い組を選び、その組に入っているベクトルとだけ距離を計算します。
64組なら代表点との比較は64回で済みます。前の節で走査が319件だったのは、この64回に加えて1組ぶんの中身を見た結果です。
見る組の数は、引くたびに変えられます。pgvectorでは既定が1組だと明記されています。
前の節のとおり、1組だけでは再現率34.1%でした。既定のまま使うと、この状態になりえます。
作ってみて分かったのは、組ごとの件数がかなり偏ることでした。データに塊があると、その塊の中にいくつも組ができ、まばらな領域は1組が広く受け持ちます。1組あたりの平均件数だけを見て設計すると、実際の走査件数と合いません。
Also, an index can be created without any data in the table since there isn’t a training step like IVFFlat.原文pgvector/pgvector README この内容の有効期限2027-02-18
作るのが軽く、記憶も食いません。ただし速さと再現率の釣り合いでは、グラフ型の索引に劣るとされています。
IVFを選ぶかどうかは、索引を作る負担と、検索の性能のどちらを優先するかで決まります。
pgvectorには両方の比較があります。グラフ型の索引について、速さと再現率の釣り合いでは優れるが、作る時間が長く、記憶をより多く使うとされています。
裏返せば、IVFは作るのが速く、記憶も食わないということです。検索の性能では譲る、という位置づけになります。
4番目は運用上の落とし穴です。空のテーブルに索引を作っておく、という手順が使えません。
組の代表点は、作った時点のデータから決まります。ですからその後に偏った追加が続くと、組の大きさが崩れます。
崩れると、同じ設定でも走査件数が増えたり再現率が落ちたりします。再現率を定期的に測り直して、落ちていたら作り直すのが運用の形になります。測り方はANN再現率の記事で扱っています。
作る負担は軽い。代わりに検索の性能では譲る。
It has better query performance than IVFFlat (in terms of speed-recall tradeoff), but has slower build times and uses more memory.原文pgvector/pgvector README この内容の有効期限2027-02-18
同じ課題を持つ会社にとって、動いている設定は「作る時間」を買えるということです。ServiceDockは自作のワークフローやテンプレートを出品できるマーケットプレイスです。手数料や出品の流れは出品者向けページにまとまっています。
出品の仕組みを見る