Faiss解説シリーズ（第三回）パフォーマンス

crumbjp.hateblo.jp

インデックス毎の性能と精度のバランスを取る上で考慮すべき要素

メモリー使用量

Faissインデックスは基本的にオンメモリー上で処理を行う。

すべてのデータが何らかの形でメモリー上に展開できなければならない。

これが最優先事項

Flatにデータを展開して物理的に乗らないようならば次元圧縮などを用いてデータ量の削減をしなければならない。

インデックスにリンク構造（HNSW等）を採用するならばその分のメモリー設計も必要となる。

検索速度、ベクトル追加速度

オンラインの高速応答が必要なのか、非同期処理である程度遅くとも精度を重視するのかで大きく選択肢が異なる。

ベクトルの変換やエンコードなどを行う場合は、メモリー使用量とトレードオフの関係になり易い。

トレーニング時間、検索精度

ベクトルの変換やエンコードをする場合は、その処理が複雑になればなるほどトレーニング時間が必要となる。

精度面は神経質になるとキリがないので、ANN検索と割り切って用途として許容し得る最小限の精度に抑えた上で上記のバランスを取れる選択肢を検討していく方が設計し易いだろう。

コード解説

テストデータ

データ生成プログラム（JS）

'use strict';
const _ = require('lodash');
const normalize = (vector) => {
  let l = Math.pow(_.reduce(vector, (r, v) => r + v*v, 0), 0.5);
  return vector.map(v => v/l);
};

for(let a = 1; a <= 10000; a++) {
  let v = [
    Math.pow(a, 0.1),   // increase
    Math.cos(a/1000),   // loop
    Math.pow(a, 0.09),  // increase
    Math.pow(1/a, 0.1), // decrease
    Math.pow(a, 0.08),  // increase
    Math.sin(a/1000),   // loop
    Math.cos(a/2000),   // loop
    Math.pow(1/a, 0.09),// decrease
    Math.pow(a, 0.06),  // increase
    Math.sin(a/2000),   // loop
  ];
  if(process.argv[2]) {
    for(let i in v) {
      v[i] = v[i] * (1.0 + Math.random()/100);
    }
  }
  let n = normalize(v);
  console.log(`${n[0]},${n[1]},${n[2]},${n[3]},${n[4]},${n[5]},${n[6]},${n[7]},${n[8]},${n[9]}`);
}

1. a に対して単調増加するフィールドと、単調減少するフィールド、繰り返しフィールドがある。

　　直積量子化の際の回転（フィールドの組み合わせ）が重要になる。

2. a が近いベクトル同士の距離は近くなる。

　　近いデータを検索出来ている事が確認しやすい

生成データ： data.csv

検索用データ：上記データにランダム誤差を加えたもの random.csv

テストコード解説

コード

const (
    DIM = 10
    NRESULT = 5
    INDEX_FILE = "/tmp/faiss.idx"
    SAMPLE_INDEX = 7000
    NSEARCH = 3000
)

インデックスのサイズは一回ファイルに吐き出してからファイルサイズを取得する

func DumpIndexFileSize(index faiss.Index) {
    faiss.WriteIndex(index, INDEX_FILE)
    file, _ := os.Open(INDEX_FILE)
    defer file.Close()
    stat, _ := file.Stat()
    fmt.Printf("Index size: %v bytes\n", stat.Size())
}

測定関数（efSearchはHNSW検索の深さ、nprobeはLVFの検索クラスター数）

各種、10次元、10000ベクトルのインデックスを作成し、精度と検索時間を評価する。

func IndexPerformance(description string, efSearch float64, nprobe float64, train bool) {
    fmt.Println("*** ", fmt.Sprintf("%s, efSearch: %v, nprobe: %v", description, efSearch, nprobe))
    searches := *GetData("random.csv", DIM)
    data := *GetData("data.csv", DIM)
    index, _ := faiss.IndexFactory(DIM, description, faiss.MetricInnerProduct)
    parameterSpace, _ := faiss. NewParameterSpace()
    if efSearch > 0 {
        parameterSpace.SetIndexParameter(index, "efSearch", efSearch)
    }
    if nprobe > 0 {
        parameterSpace.SetIndexParameter(index, "nprobe", nprobe)
    }
    if train {
        startAt := time.Now().UnixNano()
        index.Train(data)
        endAt := time.Now().UnixNano()
        fmt.Printf("Train() Elapsed: %v ms\n", (endAt - startAt) / 1000000)
    }
    {
        startAt := time.Now().UnixNano()
        index.Add(data)
        endAt := time.Now().UnixNano()
        fmt.Printf("Add() Elapsed: %v ms\n", (endAt - startAt) / 1000000)
    }
    fmt.Printf("Ntotal: %v\n", index.Ntotal())
    distances, labels, _ := index.Search(searches[SAMPLE_INDEX*DIM:(SAMPLE_INDEX+1)*DIM], NRESULT)
    fmt.Printf("Sample Distances: %v, Labels: %v\n", distances, labels)
    DumpIndexFileSize(index)
    startAt := time.Now().UnixNano()
    for i := 0; i < NSEARCH; i++ {
        index.Search(searches[i*DIM:(i+1)*DIM], NRESULT)
    }
    endAt := time.Now().UnixNano()
    fmt.Printf("Search Elapsed: %v ms\n", (endAt - startAt) / 1000000)
}

Flatインデックス

IndexPerformance("Flat", 0, 0, false)

実行結果

***  Flat, efSearch: 0, nprobe: 0
Add() Elapsed: 1 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 0.99999774], Labels: [7002 7003 7001 7004 7000]
Index size: 400045 bytes
Search Elapsed: 2369 ms

今回の測定の基準値。

誤差が無いので精度面はこの結果が正しい結果。

そのままメモリー展開するだけなので10000件の追加も一瞬。

直積量子化 エンコード

IndexPerformance("PQ2x8", 0, 0, true)
IndexPerformance("PQ2x8,RFlat", 0, 0, true)
IndexPerformance("PQ5x8", 0, 0, true)

実行結果

***  PQ2x8, efSearch: 0, nprobe: 0
Train() Elapsed: 23368 ms
Add() Elapsed: 68 ms
Ntotal: 10000
Sample Distances: [1.0010208 1.0010208 1.0010208 1.0010208 1.0010208], Labels: [7032 7033 7034 7036 7035]
Index size: 30326 bytes
Search Elapsed: 451 ms
***  PQ2x8,RFlat, efSearch: 0, nprobe: 0
Train() Elapsed: 23855 ms
Add() Elapsed: 70 ms
Ntotal: 10000
Sample Distances: [0.99997026 0.99996835 0.9999664 0.99996436 0.99996233], Labels: [7032 7033 7034 7035 7036]
Index size: 430412 bytes
Search Elapsed: 468 ms
***  PQ5x8, efSearch: 0, nprobe: 0
Train() Elapsed: 39089 ms
Add() Elapsed: 50 ms
Ntotal: 10000
Sample Distances: [1.0006516 1.0006516 1.0006516 1.0006516 1.0006516], Labels: [6942 6943 6944 6945 6941]
Index size: 60326 bytes
Search Elapsed: 756 ms

PQ2x8

10次元32bitから2次元8bitに直積量子化することで、インデックスのサイズが400kB => 30kBに激減。データが小さくなった事で、検索速度も早くなった。

ただし量子化の辞書化の為の訓練時間がかかる。またベクトル追加の際も直積処理の分時間がかかる。

検索精度もイマイチだが、Distancesが同値で、量子化の解像度が足りていない事がわかる。

PQ2x8,RFlat

生データを保存するために、インデックスサイズ＝ Flat分 + PQ2x8分となる。検索はPQ2x8部分を使っているので検索速度はPQ2x8に準ずる。

最大のメリットであるメモリー削減を失っているので用途は限定的

PQ5x8

5次元としたがPQ2x8と比較してインデックスサイズと検索時間が悪化している。量子化の解像度も足りていない。

ベクトル回転（OPQ）＆直積量子化 エンコード（PQ）

IndexPerformance("OPQ2,PQ2x8", 0, 0, true)
IndexPerformance("OPQ5,PQ5x8", 0, 0, true)

実行結果

***  OPQ2,PQ2x8, efSearch: 0, nprobe: 0
Train() Elapsed: 52593 ms
Add() Elapsed: 70 ms
Ntotal: 10000
Sample Distances: [1.0000875 1.0000875 1.0000875 1.0000875 1.0000875], Labels: [6970 6971 6972 6973 6969]
Index size: 30797 bytes
Search Elapsed: 480 ms
***  OPQ5,PQ5x8, efSearch: 0, nprobe: 0
Train() Elapsed: 103295 ms
Add() Elapsed: 54 ms
Ntotal: 10000
Sample Distances: [1.0009259 1.0009259 1.0009259 1.0008681 1.0008681], Labels: [7008 7010 7009 6967 6965]
Index size: 60797 bytes
Search Elapsed: 767 ms

OPQ2,PQ2x8

直積量子化の前に同じような傾向を持つフィールドが固まるように回転させる。

しかし元データが、単純増加、単純減少、繰り返しのパターンなので、2次元では足りていない。

フィールドの組み合わせを探す為、トレーニング時間が劇的に増加

OPQ5,PQ5x8

劇的に精度が改善している

フィールドの組み合わせパターンが増えた分、トレーニング時間が増加している。

物凄いざっくり

f:id:hiroppon:20210507183021p:plain:w800 OPQについて

うーん。。ここの解説はどうしたら良いんだ。。簡潔である程度正確なイメージが作れない。

SQ8

scalar quantizer が何なのか良く解らなかったが、データサイズ（8bit/32bitに近い）や実行時間（10次元の量子化オーバーヘッド）から見て、やはり単純なベクトル量子化のようだ。

原始的過ぎて積極的に採用する理由がない

IndexPerformance("SQ8", 0, 0, true)

実行結果

***  SQ8, efSearch: 0, nprobe: 0
Train() Elapsed: 0 ms
Add() Elapsed: 2 ms
Ntotal: 10000
Sample Distances: [1.000603 1.0004168 1.000348 1.0003289 1.0003289], Labels: [6993 6928 7039 6991 6990]
Index size: 100161 bytes
Search Elapsed: 6255 ms

HNSW

階層型のインデックスで、精度とメモリー使用量のトレードオフの関係にある。

階層毎に保持するネイバーの数が問題となる。

IndexPerformance("HNSW2", 2, 0, false)
IndexPerformance("HNSW4", 2, 0, false)
IndexPerformance("HNSW8", 2, 0, false)
IndexPerformance("OPQ5,HNSW8_PQ5x8", 2, 0, true)

実行結果

***  HNSW2, efSearch: 2, nprobe: 0
Add() Elapsed: 415 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 -3.4028235e+38], Labels: [7002 7003 7001 7004 -1]
Index size: 759350 bytes
Search Elapsed: 1409 ms
***  HNSW4, efSearch: 2, nprobe: 0
Add() Elapsed: 262 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 -3.4028235e+38], Labels: [7002 7003 7001 7004 -1]
Index size: 892782 bytes
Search Elapsed: 1488 ms
***  HNSW8, efSearch: 2, nprobe: 0
Add() Elapsed: 249 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 0.99999774], Labels: [7002 7003 7001 7004 7000]
Index size: 1205650 bytes
Search Elapsed: 1435 ms
***  OPQ5,HNSW8_PQ5x8, efSearch: 2, nprobe: 0
Train() Elapsed: 70060 ms
Add() Elapsed: 313 ms
Ntotal: 10000
Sample Distances: [1.2529714e-05 1.2529714e-05 1.2529714e-05 1.2529714e-05 1.2529714e-05], Labels: [6993 7001 7006 6999 6991]
Index size: 866402 bytes
Search Elapsed: 1591 ms

HNSW2 efSearch2

検索精度は問題ないが、ネイバー数と探索深度が足りず、5件目が帰っていない。

今回は、投入に非常に近い値で検索しているので、良い精度が得られている。

投入データと少し遠い値で検索を掛けた時は精度が劇的に落ちる。

一見、検索速度は遅く見えるが、ツリー探索の特性上、処理量はデータ数に対数的に振る舞うので大規模データに強い。

（メモリーどうすんだ？という問題が残るが）

HNSW4 efSearch2

ネイバーが4の時点で、Flatインデックスの倍のサイズになった。

5件目が帰っていない理由は不明。枝の末端だったのだろうか？

HNSW8 efSearch2

OPQ5,HNSW8_PQ5x8

PQを掛けてメモリーサイズを減らしつつ、ネイバー数も稼ぐアプローチ

IVF

個人的にはIVF,PQが小規模でも大規模でも使い易く第一選択肢だと思っている

nlists = 100

   IndexPerformance("IVF100,Flat", 0, 1, true)
    IndexPerformance("IVF100,Flat", 0, 2, true)
    IndexPerformance("IVF100,Flat", 0, 100, true)
    IndexPerformance("OPQ5,IVF100,PQ5x8", 0, 1, true)
    IndexPerformance("OPQ5,IVF100,PQ5x8", 0, 2, true)

実行結果

***  IVF100,Flat, efSearch: 0, nprobe: 1
Train() Elapsed: 103 ms
Add() Elapsed: 32 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 0.99999774], Labels: [7002 7003 7001 7004 7000]
Index size: 484939 bytes
Search Elapsed: 99 ms
***  IVF100,Flat, efSearch: 0, nprobe: 2
Train() Elapsed: 97 ms
Add() Elapsed: 32 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 0.99999774], Labels: [7002 7003 7001 7004 7000]
Index size: 484939 bytes
Search Elapsed: 128 ms
***  IVF100,Flat, efSearch: 0, nprobe: 100
Train() Elapsed: 103 ms
Add() Elapsed: 32 ms
Ntotal: 10000
Sample Distances: [0.99999785 0.99999785 0.9999978 0.99999774 0.99999774], Labels: [7002 7003 7001 7004 7000]
Index size: 484939 bytes
Search Elapsed: 2731 ms
***  OPQ5,IVF100,PQ5x8, efSearch: 0, nprobe: 1
Train() Elapsed: 108424 ms
Add() Elapsed: 56 ms
Ntotal: 10000
Sample Distances: [1.0002648 1.0001966 1.0001966 1.0001553 1.0001428], Labels: [7018 7005 7006 7072 7065]
Index size: 145691 bytes
Search Elapsed: 423 ms
***  OPQ5,IVF100,PQ5x8, efSearch: 0, nprobe: 2
Train() Elapsed: 106859 ms
Add() Elapsed: 55 ms
Ntotal: 10000
Sample Distances: [1.0002648 1.0002615 1.0002615 1.0002615 1.0002488], Labels: [7018 6998 6996 6997 6982]
Index size: 145691 bytes
Search Elapsed: 407 ms

IVF100,Flat nprobe: 1

精度も検索速度も優秀。

インデックスサイズもそれほど大きくならない。

検索負荷 = Flat負荷 x 1/100 + オーバーヘッド

IVF100,Flat nprobe: 2

検索負荷 = Flat負荷 x 2/100 + オーバーヘッド

IVF100,Flat nprobe: 100

検索負荷 = Flat負荷 x 100/100 + オーバーヘッド

全クラスターへ検索しに行っているので、Flatインデックスの検索量と同じ。オーバーヘッドは思ったより小さく優秀。

OPQ5,IVF100,PQ5x8 nprobe: 1

量子化により、大幅にデータサイズを抑えつつ高速化。精度面を若干妥協。

OPQ5,IVF100,PQ5x8 nprobe: 2

nprobe の調整により、かなり近いデータも取得できている。

一覧表

	Train	Add	Search	Size	精度	備考
Flat		1 ms	2369 ms	400045 bytes	7002 7003 7001 7004 7000
PQ2x8	23368 ms	68 ms	451 ms	30326 bytes	7032 7033 7034 7036 7035	精度が悪い
PQ2x8,RFlat	23855 ms	70 ms	468 ms	430412 bytes	7032 7033 7034 7035 7036	良い所無し
PQ5x8	39089 ms	50 ms	756 ms	60326 bytes	6942 6943 6944 6945 6941	精度が悪い
OPQ2,PQ2x8	52593 ms	70 ms	480 ms	30797 bytes	6970 6971 6972 6973 6969
OPQ5,PQ5x8	103295 ms	54 ms	767 ms	60797 bytes	7008 7010 7009 6967 6965	メモリーと精度が良い
SQ8	0 ms	2 ms	6255 ms	100161 bytes	6993 6928 7039 6991 6990	検索遅すぎ
HNSW2, efSearch: 2		415 ms	1409 ms	759350 bytes	7002 7003 7001 7004 -1	メモリー効率悪い
HNSW4, efSearch: 2		262 ms	1488 ms	892782 bytes	7002 7003 7001 7004 -1	メモリー効率悪い
HNSW8, efSearch: 2		249 ms	1435 ms	1205650 bytes	7002 7003 7001 7004 7000	メモリー効率悪い
OPQ5,HNSW8_PQ5x8, efSearch: 2	70060 ms	313 ms	1591 ms	866402 bytes	6993 7001 7006 6999 6991	メモリー効率悪い
IVF100,Flat, nprobe: 1	103 ms	32 ms	99 ms	484939 bytes	7002 7003 7001 7004 7000	高速
IVF100,Flat, nprobe: 2	97 ms	32 ms	128 ms	484939 bytes	7002 7003 7001 7004 7000	高速
IVF100,Flat, nprobe: 100	103 ms	32 ms	2731 ms	484939 bytes	7002 7003 7001 7004 7000
OPQ5,IVF100,PQ5x8, nprobe: 1	108424 ms	56 ms	423 ms	145691 bytes	7018 7005 7006 7072 7065	全てのバランスが良い
OPQ5,IVF100,PQ5x8, nprobe: 2	106859 ms	55 ms	407 ms	145691 bytes	7018 6998 6996 6997 6982	全てのバランスが良い

OPQ深堀り

この記事を書きながら気付いた点を追加検証。

今回のデータは意図的に同じような振る舞いをする次元がシャッフルされて組み込まれている。

OPQを掛ける時に

1. サブベクトルに分けずに全フィールドを見通せば精度が劇的に上がるのではないか？

2. OPQの後にPQを掛けるので、OPQの出力次元は、PQの次元と合わせた方が速度、精度共に有利ではないか？

IndexPerformance("OPQ1_2,PQ2x8", 0, 0, true)
IndexPerformance("OPQ1_5,PQ5x8", 0, 0, true)
IndexPerformance("OPQ1_5,HNSW8_PQ5x8", 2, 0, true)
IndexPerformance("OPQ1_5,IVF100,PQ5x8", 0, 1, true)
IndexPerformance("OPQ1_5,IVF100,PQ5x8", 0, 2, true)

実行結果

***  OPQ1_2,PQ2x8, efSearch: 0, nprobe: 0
Train() Elapsed: 37700 ms
Add() Elapsed: 25 ms
Ntotal: 10000
Sample Distances: [0.07687946 0.07687946 0.07687946 0.0767533 0.0767533], Labels: [7062 7061 7063 6998 6997]
Index size: 22285 bytes
Search Elapsed: 446 ms
***  OPQ1_5,PQ5x8, efSearch: 0, nprobe: 0
Train() Elapsed: 57581 ms
Add() Elapsed: 44 ms
Ntotal: 10000
Sample Distances: [0.22191425 0.22191425 0.22191425 0.22183329 0.22178258], Labels: [6984 6985 6986 7044 7011]
Index size: 55477 bytes
Search Elapsed: 842 ms
***  OPQ1_5,HNSW8_PQ5x8, efSearch: 2, nprobe: 0
Train() Elapsed: 22025 ms
Add() Elapsed: 296 ms
Ntotal: 10000
Sample Distances: [1.4171669e-06 1.4171669e-06 1.4171669e-06 1.4171669e-06 1.4171669e-06], Labels: [7006 7001 7007 7003 7002]
Index size: 861082 bytes
Search Elapsed: 1744 ms
***  OPQ1_5,IVF100,PQ5x8, efSearch: 0, nprobe: 1
Train() Elapsed: 59567 ms
Add() Elapsed: 56 ms
Ntotal: 10000
Sample Distances: [0.22194861 0.22186598 0.22186598 0.22186598 0.22186598], Labels: [7027 7053 7055 7054 7052]
Index size: 138371 bytes
Search Elapsed: 408 ms
***  OPQ1_5,IVF100,PQ5x8, efSearch: 0, nprobe: 2
Train() Elapsed: 60427 ms
Add() Elapsed: 52 ms
Ntotal: 10000
Sample Distances: [0.22194861 0.22186598 0.22186598 0.22186598 0.22186598], Labels: [7027 7053 7055 7054 7052]
Index size: 138371 bytes
Search Elapsed: 412 ms

OPQの段階で次元が減った分、PQの辞書次元が減り、若干インデックスサイズが小さくなった。

精度は少し良くなった様な感じはあるが誤差の範囲だろう。

OPQチューニングの正解

ちょっとズルだが、元データの構造を知っているので OPQ1_3 が一番良いはずだ。

IndexPerformance("OPQ1_3,PQ3x8", 0, 0, true)
IndexPerformance("OPQ1_3,HNSW8_PQ3x8", 2, 0, true)
IndexPerformance("OPQ1_3,IVF100,PQ3x8", 0, 1, true)
IndexPerformance("OPQ1_3,IVF100,PQ3x8", 0, 2, true)

実行結果

***  OPQ1_3,PQ3x8, efSearch: 0, nprobe: 0
Train() Elapsed: 43282 ms
Add() Elapsed: 37 ms
Ntotal: 10000
Sample Distances: [0.07851314 0.07850463 0.07850463 0.07850028 0.078476], Labels: [6888 6853 6854 6878 6861]
Index size: 33349 bytes
Search Elapsed: 585 ms
***  OPQ1_3,HNSW8_PQ3x8, efSearch: 2, nprobe: 0
Train() Elapsed: 19069 ms
Add() Elapsed: 286 ms
Ntotal: 10000
Sample Distances: [8.4947663e-07 8.4947663e-07 8.4947663e-07 8.4947663e-07 8.4947663e-07], Labels: [7006 7001 7004 7005 6999]
Index size: 838954 bytes
Search Elapsed: 1576 ms
***  OPQ1_3,IVF100,PQ3x8, efSearch: 0, nprobe: 1
Train() Elapsed: 43502 ms
Add() Elapsed: 42 ms
Ntotal: 10000
Sample Distances: [0.07815711 0.07815711 0.07815711 0.07815711 0.07815711], Labels: [7014 7015 7016 7017 7013]
Index size: 115443 bytes
Search Elapsed: 244 ms
***  OPQ1_3,IVF100,PQ3x8, efSearch: 0, nprobe: 2
Train() Elapsed: 43467 ms
Add() Elapsed: 40 ms
Ntotal: 10000
Sample Distances: [0.07864998 0.07864998 0.07864998 0.07864998 0.07864998], Labels: [6996 6997 6998 6999 6995]
Index size: 115443 bytes
Search Elapsed: 275 ms

OPQ1_3,PQ3x8 だけちょっと納得が行かないが、その他は大きく精度が向上した。

次回

もうちょっと複雑なやつ

中年engineerの独り言 - crumbjp

LinuxとApacheの憂鬱

インデックス毎の性能と精度のバランスを取る上で考慮すべき要素

メモリー使用量

検索速度、ベクトル追加速度

トレーニング時間、検索精度

コード解説

テストデータ

テストコード解説

Flatインデックス

直積量子化 エンコード

ベクトル回転（OPQ）＆直積量子化 エンコード（PQ）

物凄いざっくり

SQ8

HNSW

IVF

一覧表

OPQ深堀り

OPQチューニングの正解

次回