増分インデックスとは｜2万件に100件足すのに、作り直すと132倍かかった

2万件に100件足すのに、作り直すと132倍かかった

既存件数を変えて実際に測りました。差は1,000件で9倍、2万件で132倍まで開きます。

増分インデックスがどれだけ効くのかを、実際に走らせて測りました。題材は語から文書を引く転置表で、毎日100件が追加される場面を想定しています。

索引の構築も追加も本当に実行しています。所要時間は実行のたびにぶれるので、桁と比で読んでください。

// 転置表を作る。語 → その語を含む文書の一覧
const build = (docs) => {
  const idx = new Map();
  docs.forEach((t, i) => { for (const w of new Set(bigrams(t))) {
    if (!idx.has(w)) idx.set(w, []); idx.get(w).push(i); } });
  return idx;
};

// 既存の索引に、増えた分だけ足す
const addTo = (idx, docs, base) => {
  docs.forEach((t, k) => { for (const w of new Set(bigrams(t))) {
    if (!idx.has(w)) idx.set(w, []); idx.get(w).push(base + k); } });
  return idx;
};

既存件数  追加件数  全部作り直す  増えた分だけ足す  比
   1000件      100件         4617 μs              488 μs     9倍
   5000件      100件        15434 μs              454 μs    34倍
  20000件      100件        67635 μs              512 μs   132倍

削除があった場合
  索引の中に残る、削除済み文書への参照: 3,173件
  索引に載っている参照の総数: 158,765件

右の列に注目してください。差分追加は488、454、512マイクロ秒とほぼ変わりません。既存が何件でも、足す作業は100件ぶんだからです。

作り直しだけが伸びる

対して作り直しは4,617から67,635マイクロ秒まで伸びました。既存の全件を処理し直すので、件数に比例します。

だから比が9倍、34倍、132倍と開きます。件数が増えるほど、作り直しを選ぶ理由がなくなっていきます。

削除は差分では消えない

ところが下の行が問題です。50件に1件が削除された想定で、索引の中に3,173件の参照が残りました。

追加は足すだけで済みますが、削除は索引の中を探して消す必要があります。語ごとの一覧すべてから、その文書の番号を取り除く作業になります。

残った参照が返ってくる

残った参照は、検索したときに結果として返ります。すでに存在しない文書が上位に来るという形です。

取り出す段で存在を確かめれば表には出ませんが、その分だけ上位の枠が埋まります。10件返すつもりが、実際には8件しか有効でないという状態になります。

増分インデックスとは何をする仕組みなのか

既存の索引を残したまま、増えた分だけを足します。索引の方式によって、足しやすさが変わります。

増分インデックスは、索引を作り直さずに、増えた文書の分だけを足していく仕組みです。更新の手間を件数から切り離します。

方式によって足しやすさが違う

語から引く転置表は、足すのが簡単です。語ごとの一覧に、新しい文書の番号を足すだけで済みます。

ベクトルの索引では事情が変わります。組に分ける方式では、組の代表点が作った時点のデータから決まっているためです。詳しくはIVFの記事で扱っています。

学習の要らない方式

グラフ型の索引には、この学習の段がありません。pgvectorでも、組に分ける方式のような学習の段がないため、データが入っていないテーブルにも索引を作れると対比されています。

学習が要らないということは、後から足しても構造が崩れにくいということでもあります。追加が多い用途では、この差が効いてきます。

作り直しが必要になる場面

1. 削除が積み重なった。参照が残る
2. 追加が偏った。組に分ける方式では大きさが崩れる
3. 索引の設定を変えた。作る時点の設定は後から変えられない
4. 追加が続いているだけ。作り直す理由にならない

4番目に注意してください。毎日作り直す運用は、前の節の左の列を毎日払っていることになります。

増分で足し続けたときに溜まるもの

削除済み文書への参照が残ります。定期的に作り直すか、掃除する手順を決めておいてください。

増分インデックスの弱点は削除です。足すのは簡単でも、消すのは索引全体を探すことになります。

参照が溜まる

前の節では、50件に1件が削除された想定で3,173件の参照が残りました。索引に載っている参照の総数が158,765件なので、2%にあたります。

この割合は時間とともに増えます。削除するたびに残り、作り直すまで減りません。

掃除の手立て

製品側にも手順が用意されています。pgvectorでは、索引の作り直しと、テーブルの掃除を行う手順が案内されています。

作り直しを止めるのではなく、頻度を下げて必要なときだけ行うという形になります。毎回の追加では差分で足し、月に1度作り直すといった組み方です。

頻度の決め方

決め方は2つの数字からです。削除の割合と、作り直しにかかる時間を並べてください。

削除がほとんどない構成なら、作り直しは年に1度でも足ります。入れ替えが多い構成では、その分だけ頻度を上げることになります。