Home
Blog
Milvus Ngram Indexのご紹介：エージェントワークロードのためのキーワードマッチングとLIKEクエリの高速化

Milvus Ngram Indexのご紹介：エージェントワークロードのためのキーワードマッチングとLIKEクエリの高速化

Engineering

December 16, 2025

Chenjie Tang

エージェントシステムにおいて、コンテキスト検索はパイプライン全体にわたる基礎的なビルディングブロックであり、下流の推論、計画、行動の基礎を提供する。ベクトル検索は、エージェントが大規模で構造化されていないデータセット全体の意図と意味を捉える、意味的に関連するコンテキストを検索するのに役立つ。しかし、意味的な関連性だけでは十分でないことが多い。エージェントパイプラインは、製品名、関数呼び出し、エラーコード、または法的に重要な用語など、正確なキーワード制約を強制するために全文検索にも依存しています。このサポートレイヤーは、検索されたコンテキストが関連性があるだけでなく、明確なテキスト要件を満たすことを保証します。

実際の作業負荷は一貫してこのニーズを反映している：

カスタマーサポートのアシスタントは、特定の製品や成分について言及している会話を見つけなければならない。
コーディングのコパイロットは、正確な関数名、APIコール、エラー文字列を含むスニペットを探します。
法律、医療、学術分野のエージェントは、逐語的に表示されなければならない条項や引用をドキュメントにフィルタリングします。

従来、システムはこれをSQLのLIKE 演算子で処理してきた。name LIKE '%rod%' のようなクエリはシンプルで広くサポートされていますが、高い同時実行性と大量のデータでは、このシンプルさが大きなパフォーマンス・コストになります。

インデックスがない場合、LIKE クエリはコンテキストストア全体をスキャンし、行ごとにパターンマッチングを適用します。数百万レコードの場合、1つのクエリでさえ数秒かかり、リアルタイムのエージェントインタラクションには遅すぎる。
従来の転置インデックスを使用した場合でも、%rod% のようなワイルドカードパターンの最適化は困難なままです。これは、エンジンが辞書全体をトラバースし、各エントリでパターンマッチングを実行する必要があるためです。この操作は行スキャンを回避するが、基本的には線形であるため、わずかな改善しかもたらさない。

ベクトル検索は意味的関連性を効率的に処理するが、正確なキーワードフィルタリングはパイプラインの中で最も遅いステップになることが多い。

Milvusは、メタデータフィルタリングを伴うハイブリッドベクター検索とフルテキスト検索をネイティブにサポートしている。キーワードマッチングの限界に対処するため、MilvusはNgram Indexを導入しています。これは、テキストを小さな部分文字列に分割し、効率的な検索のためにインデックス化することで、LIKE パフォーマンスを向上させます。これにより、クエリ実行中に検査されるデータ量が劇的に削減され、実際のエージェントのワークロードにおいて、LIKE クエリを数十倍から数百倍高速化することができます。

この投稿の残りの部分では、MilvusにおけるNgram Indexの仕組みについて説明し、実際のシナリオにおけるパフォーマンスを評価します。

Ngramインデックスとは？

データベースでは、テキストフィルタリングは一般的にデータの取得と管理に使用される標準的なクエリ言語であるSQLを使用して表現されます。その中で最も広く使われているテキスト演算子の一つがLIKE であり、パターンベースの文字列マッチングをサポートしている。

LIKE式は、ワイルドカードの使われ方によって、4つの一般的なパターン・タイプに大別することができます：

Infixマッチ(name LIKE '%rod%')：部分文字列ロッドがテキスト内の任意の場所に現れるレコードにマッチする。
接頭辞マッチ(name LIKE 'rod%')：テキストがrodで始まるレコードにマッチします。
接尾辞マッチ(name LIKE '%rod')：テキストがrodで終わるレコードにマッチします。
ワイルドカード一致(name LIKE '%rod%aab%bc_de')：複数の部分文字列条件(%)と1文字のワイルドカード(_)を1つのパターンで組み合わせます。

これらのパターンは見た目も表現力も異なりますが、MilvusのNgramインデックスは同じ基本的なアプローチを用いて全てのパターンを高速化します。

インデックスを構築する前に、Milvusは各テキスト値をn-gramと呼ばれる一定の長さの短く重なり合った部分文字列に分割する。例えば、n = 3の場合、"Milvus "という単語は以下の3-gramに分解される：「Mil"、 "ilv"、 "lvu"、 "vus "である。そして、各n-gramは、その部分文字列をそれが出現する文書IDの集合に対応付ける転置インデックスに格納される。クエリー時、LIKE の条件はn-gramのルックアップの組み合わせに変換され、milvusはほとんどのマッチしないレコードを素早くフィルタリングし、より少ない候補セットに対してパターンを評価することができる。これが、高価な文字列スキャンを効率的なインデックスベースのクエリに変えるものである。

Ngramインデックスの構築方法を制御する2つのパラメータ：min_gram とmax_gram 。これらはMilvusが生成する部分文字列の長さの範囲を定義し、インデックスを作成します。

min_gram:インデックスを作成する最も短い部分文字列の長さ。実際には、これは Ngram インデックスの恩恵を受けることができる最小のクエリ文字列長を設定します。
max_gram:インデックスを作成する最も長い部分文字列長。クエリ時には、さらに、長いクエリ文字列をn-gramに分割する際に使用される最大ウィンドウサイズを決定します。

Milvusは、長さがmin_gram からmax_gram の間にあるすべての連続した部分文字列をインデックス化することにより、サポートされているすべてのLIKE パターンタイプを高速化するための一貫した効率的な基盤を確立します。

Ngramインデックスの仕組み

Milvusは2段階のプロセスでNgram Indexを実装します：

インデックスの構築各文書のN-gramを生成し、データ取り込み時に転置インデックスを構築します。
クエリの高速化インデックスを使用して検索を小さな候補セットに絞り込み、それらの候補についてLIKE の完全一致を検証する。

具体的な例を挙げると、このプロセスが理解しやすくなる。

フェーズ1：インデックスの構築

テキストをn-gramに分解する：

以下の設定でテキスト"Apple "にインデックスを作成すると仮定する：

min_gram = 2
max_gram = 3

この設定では、milvusは長さ2と3の連続した部分文字列を全て生成する：

2-gram：Ap pp,pl 、le
3-grams：App ppl 、ple

転置インデックスを構築する：

ここで、5つのレコードからなる小さなデータセットを考える：

文書0：Apple
文書0: 文書1： Pineapple
文書2 Maple
文書3 Apply
文書4：Snapple

インジェスト中、Milvusは各レコードに対してn-gramを生成し、それを転置インデックスに挿入する。このインデックスでは

キーはn-gram(部分文字列)
値はn-gramが出現する文書IDのリスト

"Ap"  -> [0, 3]
"App" -> [0, 3]
"Ma"  -> [2]
"Map" -> [2]
"Pi"  -> [1]
"Pin" -> [1]
"Sn"  -> [4]
"Sna" -> [4]
"ap"  -> [1, 2, 4]
"apl" -> [2]
"app" -> [1, 4]
"ea"  -> [1]
"eap" -> [1]
"in"  -> [1]
"ine" -> [1]
"le"  -> [0, 1, 2, 4]
"ly"  -> [3]
"na"  -> [4]
"nap" -> [4]
"ne"  -> [1]
"nea" -> [1]
"pl"  -> [0, 1, 2, 3, 4]
"ple" -> [0, 1, 2, 4]
"ply" -> [3]
"pp"  -> [0, 1, 3, 4]
"ppl" -> [0, 1, 3, 4]

これでインデックスは完全に構築された。

第2段階：クエリーの高速化

LIKE フィルタが実行されると、MilvusはNgramインデックスを使い、以下のステップでクエリの評価を高速化する：

1.クエリー用語を抽出する：ワイルドカードを含まない連続した部分文字列がLIKE 式から抽出される（例えば、'%apple%' はapple になる）。

2.クエリ語の分解：クエリ語は、その長さ（L ）と、構成されたmin_gram とmax_gram に基づいて、n-gramに分解される。

3.各グラムを検索し、交差させる:Milvusは転置インデックスでクエリーn-gramを検索し、それらの文書IDリストを交差させ、小さな候補セットを生成する。

4.検証して結果を返す：元のLIKE 条件がこの候補セットにのみ適用され、最終結果が決定される。

実際には、クエリをn-gramに分割する方法は、パターン自体の形状に依存する。これがどのように機能するかを見るために、2つの一般的なケース、すなわち、接尾辞マッチとワイルドカードマッチに焦点を当てます。接頭辞マッチと接尾辞マッチは infix マッチと同じ挙動をするので、ここでは別々に説明しません。

infix マッチ

infix マッチの場合、実行はリテラル部分文字列 (L) のmin_gram とmax_gram からの相対的な長さに依存します。

1.min_gram ≤ L ≤ max_gram(例:strField LIKE '%ppl%')

リテラル部分文字列ppl は、設定されたn-gramの範囲内にあります。milvusは直接、転置インデックスでn-gram"ppl" を検索し、候補文書ID[0, 1, 3, 4] を生成します。

リテラル自体がインデックス付きn-gramであるため、すべての候補はすでにinfix条件を満たしている。最後の検証ステップではレコードは削除されず、結果は[0, 1, 3, 4] のままとなる。

2.L > max_gram(例:strField LIKE '%pple%')

リテラル部分文字列pple はmax_gram より長いため、max_gram のウィンドウ・サイズを使用して重複するn-gramに分解される。max_gram = 3 を使用すると、"ppl" と"ple" のn-gramが生成される。

milvusは各n-gramを転置インデックスで検索する：

"ppl" →[0, 1, 3, 4]
"ple" →[0, 1, 2, 4]

これらのリストを交差させると、候補セット[0, 1, 4] が得られる。そして、これらの候補に元のLIKE '%pple%' フィルタが適用される。3つとも条件を満たすので、最終結果は[0, 1, 4] のままである。

3.L < min_gram(例:strField LIKE '%pp%')

リテラル部分文字列はmin_gram より短いため、インデックス付き n-gram に分解できない。この場合、Nグラムインデックスは使用できず、Milvusはデフォルトの実行パスに戻り、パターンマッチによるフルスキャンでLIKE 条件を評価します。

ワイルドカード一致(例:strField LIKE '%Ap%pple%')

このパターンには複数のワイルドカードが含まれているため、Milvusはまず、"Ap" と"pple" という連続したリテラルに分割します。

その後、Milvusは各リテラルを個別に処理します：

"Ap" は長さ2でn-gramの範囲に入る。
"pple" はmax_gram より長く、"ppl" と"ple" に分解されます。

これにより、クエリは以下のn-gramに縮小される：

"Ap" →[0, 3]
"ppl" →[0, 1, 3, 4]
"ple" →[0, 1, 2, 4]

これらのリストを交差させると、[0] という一つの候補ができる。

最後に、元のLIKE '%Ap%pple%' フィルタを文書0（"Apple" ）に適用する。これは完全なパターンを満たさないので、最終的な結果セットは空になる。

Ngramインデックスの限界とトレードオフ

Ngram インデックスは、LIKE クエリー性能を大幅に向上させることができるが、実世界での展開において考慮すべきトレードオフをもたらす。

インデックスサイズの増大

Ngram インデックスの主なコストは、より高いストレージオーバーヘッドである。インデックスには、長さがmin_gram からmax_gram の間にある連続した部分文字列がすべて格納されるため、この範囲が拡大するにつれて生成されるn-gramの数が急速に増加します。n-gramの長さが増えるごとに、テキスト値ごとに重複する部分文字列の完全なセットが追加され、インデックスキーの数も投稿リストの数も増える。実際には、たった1文字範囲を拡張するだけで、標準的な転置インデックスと比較して、インデックスサイズはおよそ2倍になる。

すべてのワークロードに有効ではない

Ngramインデックスは全ての作業負荷を高速化するわけではない。クエリーパターンが非常に不規則であったり、非常に短いリテラルを含んでいたり、フィルタリングの段階でデータセットを小さな候補セットまで減らすことができなかったりする場合、パフォーマンスの利点は制限される可能性があります。このような場合、インデックスが存在しても、クエリの実行はフルスキャンのコストに近づく可能性がある。

LIKEクエリにおけるNgramインデックスの性能評価

このベンチマークの目的は、Ngramインデックスが実際にLIKE クエリをどれだけ効果的に高速化するかを評価することである。

テスト方法

Ngramインデックスの性能の背景を理解するために、2つのベースライン実行モードと比較する：

マスター：マスター：インデックスを使用しない強引な実行。
マスター反転：従来の転置インデックスを用いた実行。

異なるデータ特性をカバーするために2つのテストシナリオを設計した：

Wikiテキストデータセット：100,000行、各テキストフィールドは1KBに切り捨て。
単一単語データセット：1,000,000行、各行が1単語を含む。

どちらのシナリオでも、以下の設定が一貫して適用される：

クエリーはinfixマッチパターン(%xxx%)を使用。
Ngram インデックスは、min_gram = 2 で設定されています。max_gram = 4
クエリの実行コストを分離し、結果の実体化のオーバーヘッドを避けるため、すべてのクエリは完全な結果セットではなくcount(*) を返す。

結果

wikiのテスト、各行は1000で切り捨てられた内容のwikiテキスト、100K行

	リテラル	時間(ms)	スピードアップ	カウント
マスター	スタジアム	207.8		335
マスター逆転		2095		335
Nグラム		1.09	190 / 1922	335

マスター	中等学校	204.8		340
逆修士		2000		340
Nグラム		1.26	162.5 / 1587	340

マスター	男女共学の中等教育機関。	223.9		1
マスター反転		2100		1
Ngram		1.69	132.5 / 1242.6	1

単一単語のテスト、1M行

	リテラル	時間(ms)	スピードアップ	カウント
マスター	マスター	128.6		40430
マスター反転		66.5		40430
Nグラム		1.38	93.2 / 48.2	40430

マスター	ナット	122		5200
マスター反転		65.1		5200
Nグラム		1.27	96 / 51.3	5200

マスター	ナティ	118.8		1630
マスター反転		66.9		1630
Nグラム		1.21	98.2 / 55.3	1630

マスター	ネイティオ	118.4		1100
マスターインバーテッド		65.1		1100
エヌグラム		1.33	89 / 48.9	1100

マスター	国家	118		1100
マスター国		63.3		1100
Nグラム		1.4	84.3 / 45.2	1100

注：これらの結果は5月に実施されたベンチマークに基づく。それ以降、Masterブランチでは性能の最適化が行われたため、ここで観測された性能差は現在のバージョンでは小さくなっていると予想される。

ベンチマークの結果は、明確なパターンを浮き彫りにしている。Ngramインデックスは、すべてのケースでLIKEクエリを大幅に高速化し、クエリの実行速度がどの程度速くなるかは、基礎となるテキストデータの構造と長さに強く依存する。

1,000バイトに切り詰められたWikiスタイルのドキュメントのような長いテキストフィールドの場合、パフォーマンスの向上は特に顕著です。インデックスなしの総当り実行と比較すると、Ngramインデックスはおよそ100～200倍のスピードアップを達成する。従来の転置インデックスと比較すると、さらに劇的な改善が見られ、1,200-1,900倍に達する。これは、長いテキストに対するLIKEクエリが従来のインデックス作成アプローチにとって特に高価であるのに対し、N-gramルックアップは検索空間を非常に小さな候補セットに素早く絞り込むことができるためである。
単一単語で構成されるデータセットでは、利益は小さくなるが、それでも相当なものである。このシナリオでは、Ngramインデックスはブルートフォース実行よりも約80～100倍、従来の転置インデックスよりも45～55倍高速に動作する。短いテキストは本質的にスキャンコストが低いが、それでもN-gramベースのアプローチは不必要な比較を回避し、一貫してクエリーコストを削減する。

結論

Ngramインデックスは、テキストを固定長のN-gramに分割し、転置構造を用いてインデックスを作成することで、LIKE クエリを高速化する。この設計は、高価な部分文字列マッチングを効率的なn-gramルックアップに変え、その後に最小限の検証を行う。その結果、LIKE の正確なセマンティクスが保たれたまま、全文スキャンが回避される。

実際には、このアプローチは幅広い作業負荷に有効であり、特に長いテキストフィールドのファジィマッチングに強い結果をもたらす。したがって、Ngramインデックスは、コード検索、カスタマーサポートエージェント、法律・医療文書検索、企業知識ベース、学術検索など、正確なキーワードマッチングが不可欠なリアルタイムシナリオに適している。

同時に、Ngram インデックスは慎重な設定によって恩恵を受ける。適切なmin_gram 、max_gram 値を選択することは、インデックスサイズとクエリパフォーマンスのバランスをとる上で非常に重要である。実際のクエリーパターンを反映するようにチューニングすれば、Ngram Indexは、本番システムにおけるハイパフォーマンスなLIKE クエリーのための、実用的でスケーラブルなソリューションを提供します。

Ngram Indexの詳細については、以下のドキュメントを参照して下さい：