200件では、近似探索の1回が31μs、全探索が30μsでした。近似のほうが遅いという結果です。
2万件になると5364μsと257μsで逆転します。件数が分かれ目になります。
件数によって有利な形が変わります。小さいうちは、素直に全部見るほうが速いです。
Weaviateには、件数で切り替わる索引があります。公式は動的な索引とは、データが小さいうちは総当たりで、大きくなるとHNSWへ切り替わるベクトルの索引であると述べています。
どこで切り替わるのか。件数を変えて実際に測って比べました。
64次元・上位10件・問い合わせ 200回。件数を変えて比べる
近似のほうは 1点あたりの枝 8本・探索の幅 64 で組み立てる
件数 全探索1回 索引を作る 近似1回 近似の再現率 追い抜くまでの問い合わせ
200件 30 μs 6 ms 31 μs 11.5% 追い抜かない
1,000件 168 μs 164 ms 94 μs 9.3% 2,201回
5,000件 987 μs 4823 ms 171 μs 7.2% 5,916回
20,000件 5364 μs 106193 ms 257 μs 9.3% 20,795回
200件では、近似が31μsで全探索が30μsです。速くなっていません。
2万件では5364μsと257μsで、20.9倍の差がつきます。件数が増えるほど近似が有利になります。
索引を作るのに2万件で106秒かかりました。1回あたりの短縮で割ると、20,795回の問い合わせで元が取れます。
1日に数百回しか問い合わせないなら、元を取るまでに数十日かかることになります。
だから件数だけでなく、問い合わせの回数も見ることになります。近似そのものの仕組みはHNSWの記事で扱いました。
件数が増えるほど、近似探索の利点が出てくる。
Dynamic - a vector index that is flat when the dataset is small and switches to HNSW when the dataset is large.原文Weaviate 公式ドキュメント「Indexing」 この内容の有効期限2027-02-18
索引を厚くするほど置く量が増えます。再現率の伸びと比べて決めることになります。
Weaviateでは、索引の設定が置く量に効きます。公式はとくに大きなデータでは索引の設定が重要である。索引を増やすほど、多くの保存領域が必要になるからだと述べています。
どれだけ増えるのか。設定を変えて実際に組み立てて数えました。
登録 20,000件（64次元）・上位10件・問い合わせ 200回
全探索 1回あたり 5450 マイクロ秒
1点あたりの枝 探索の幅 再現率 走査件数 1回あたり 全探索比 枝の総数
4本 16 5.7% 120件 50 μs 109.4倍 128,759本
4本 64 16.6% 336件 141 μs 38.7倍 128,759本
8本 16 8.9% 240件 84 μs 65.1倍 269,218本
8本 64 22.7% 617件 226 μs 24.1倍 269,218本
16本 16 10.4% 478件 167 μs 32.7倍 568,782本
16本 64 33.7% 1,050件 408 μs 13.4倍 568,782本
枝を4本から16本にすると、枝の総数が128,759本から568,782本になります。4.4倍です。
そのとき再現率は、幅16なら5.7%から10.4%です。置く量4.4倍に対して1.8倍でした。
同じ枝4本のまま幅を16から64にすると、再現率は5.7%から16.6%になります。置く量は変わりません。
つまり置く量を増やす前に、探索の幅で足りるかを試すことになります。幅は問い合わせのたびの時間としてだけ効きます。
同じ判断は索引設計の記事でも扱っていて、作るときの費用と引くときの費用を分けて見ます。
Especially for large datasets, configuring the indexes is important because the more you index, the more storage is needed.原文Weaviate 公式ドキュメント「Indexing」 この内容の有効期限2027-02-18
語から引く索引も持てます。ただし効くかどうかは、その語がどれだけ偏っているかで決まります。
Weaviateには、語から引く索引もあります。公式は転置索引は、BM25の問い合わせを可能にし、あるいは絞り込みを速くすると述べています。
どの語でも同じように速くなるのか。実際に引いて数えました。
文書 100,000件・語 20,000種。1文書は 60語まで持つ 語から文書へ引く索引の項目は合わせて 4,244,011件 引く語 その語を含む文書 全文書に対する割合 全部を見る場合との比 最もありふれた語 99,990件 99.99% 1倍 10番目 50,386件 50.39% 2倍 1000番目 436件 0.44% 229倍 真ん中の語 35件 0.03% 2857倍
いちばんありふれた語は99,990件に出てきます。全文書を見るのと変わりません。
真ん中の語なら35件で、2857倍の差です。同じ索引でも、語によって効き方が桁で違います。
2つの語をどちらも含む文書を探す。短い並びから当たるかどうかで走査が変わる 組み合わせ 長いほうから 短いほうから 差 ありふれた語＋1000番目 99,990件 436件 229倍 10番目＋1000番目 50,386件 436件 116倍 1000番目＋真ん中 436件 35件 12倍
2つの語で絞るとき、短い並びから当たれば436件で済みます。長いほうからだと99,990件です。
結果は同じで、走る量だけが229倍違います。並びの短い順に当たるという一手が効いています。
3つの計測はいずれも手元で書いた模型で、実際のWeaviateを動かしたものではありません。近似探索の実装は単純な近傍グラフで、実際のHNSWより再現率が低く出ています。索引を作る時間も総当たりで枝を選んでいるため、実際の実装よりずっと遅い値です。語の分布も生成したもので、実データとは違います。ここで見せているのは、件数が小さいうちは近似が有利にならないという点と、語の偏りによって索引の効き方が桁で変わるという点の2つです。
Inverted indexes - inverted indexes enable BM25 queries or speed up filtering.原文Weaviate 公式ドキュメント「Indexing」 この内容の有効期限2027-02-18
同じ課題を持つ会社にとって、動いている設定は「作る時間」を買えるということです。ServiceDockは自作のワークフローやテンプレートを出品できるマーケットプレイスです。手数料や出品の流れは出品者向けページにまとまっています。
出品の仕組みを見る