ビットセット

このトピックでは、Milvusの属性フィルタリングや削除操作などの主要な機能を実現するビットセットメカニズムについて紹介します。

概要

ビットセットはビットの集合です。ビットは2つの値しか持たない要素であり、最も一般的なものは0 と1 、またはブール値true とfalse です。Milvusでは、ビットセットはビット番号0 と1 の配列であり、intやfloat、charsとは異なり、特定のデータをコンパクトかつ効率的に表現するために使用することができます。ビット番号はデフォルトで0 、特定の条件を満たした場合のみ1 。

ビットセットに対する演算はブーリアンロジックで行われ、出力値は有効か無効かのどちらかになり、それぞれ1 、0 。例えば、論理演算子 AND は、同じインデックス位置にある項目に基づいて2つのビットセットを比較し、その結果を新しいビットセットとして生成するために使用できます。ある位置にある2つの項目が同じであれば、新しいビットセットではその位置に1 、異なる場合は0 。

実装

BitsetはMilvusがTime Travelで属性フィルタリング、データ削除、クエリを実行するためのシンプルかつ強力なメカニズムです。

属性フィルタリング

ビットセットには2つの値しか含まれないため、属性フィルタリングの結果を保存するのに最適です。指定された属性フィルタの要件を満たすデータは1 でマークされます。

データの削除

ビットセットは、セグメント内の行が削除されたかどうかの情報を格納するコンパクトな方法として機能する。削除されたエンティティは、対応するビットセットに1 でマークされます。これは、検索中やクエリ中に計算されることはありません。

例

ここでは、Milvusにおけるビットセットの使用方法を説明する3つの例を示す。この3つの例では、8つのエンティティを持つセグメントがあり、一連のデータ操作言語（DML）イベントが以下の順序で行われる。

• primary_keysがそれぞれ[1、2、3、4]であるエンティティのうち4つは、タイムスタンプts が100になったときに挿入される。
• primary_keysが[5, 6, 7, 8]である残りの4つのエンティティは、タイムスタンプts が200になったときに挿入される。
• primary_keysが[7, 8]であるエンティティは、タイムスタンプts が300になったときに削除される。
• primary_keyが [1, 3, 5, 7] であるエンティティだけが、属性フィルタリングの条件を満たす。

DMLイベントの順序

ケース1

この場合、ユーザはtime_travel を 150 に設定する。これは、ts = 150 を満たすデータに対してクエリを実行することを意味する。ビットセット生成プロセスを図1に示す。

最初のフィルタリング段階では、filter_bitset は[1, 0, 1, 0, 1, 0, 1, 0] であるべきである。ここで、エンティティ [1、3、5、7] は有効なフィルタリング結果であるため、1 としてマークされる。

しかし、エンティティ[4, 5, 6, 7]は、ts が 150 のとき、ベクトルデータベースに挿入されなかった。したがって、これら4つのエンティ ティは、フィルタリング条件に関係なく0とマークされるべきである。これで、ビットセットの結果は[1, 0, 1, 0, 0, 0, 0, 0] となる。

データ削除で説明したように、1 でマークされたエンティ ティは、検索中またはクエリ中は無視される。ビットセットの結果は、削除ビットマップと結合するために反転する必要があり、[0, 1, 0, 1, 1, 1, 1, 1] が得られます。

削除ビットセットdel_bitset に関しては、初期値は[0, 0, 0, 0, 0, 0, 1, 1] であるべきである。しかし、エンティティ7と8は、ts が300になるまで削除されない。したがって、ts が150のとき、エンティ ティ7と8はまだ有効である。その結果、タイムトラベル後のdel_bitset の値は[0, 0, 0, 0, 0, 0, 0, 0] となる。

これで、Time Travelと属性フィルタリング後の2つのビットセットができあがった:filter_bitset [0, 1, 0, 1, 1, 1, 1, 1] とdel_bitset [0, 0, 0, 0, 0, 0, 0, 0] 。 この2つのビットセットをOR 二項論理演算子で結合する。result_bitsetの最終的な値は[0, 1, 0, 1, 1, 1, 1, 1] 。つまり、次の検索またはクエリの段階では、エンティティ1と3のみが計算されます。

図1.タイムトラベル=150での検索。

ケース2

この場合、ユーザはtime_travel を 250 に設定する。ビットセット生成プロセスを図2に示す。

ケース1と同様に、最初のfilter_bitset は[1, 0, 1, 0, 1, 0, 1, 0] である。

ts = 250のとき、すべてのエンティ ティはベクトルデータベースにある。したがって、タイムスタンプを考慮しても、filter_bitset は変わらない。この場合も、結果を反転して[0, 1, 0, 1, 0, 1, 0, 1] を得る必要がある。

削除ビットセットdel_bitset に関しては、初期値は[0, 0, 0, 0, 0, 0, 1, 1] である。ただし、エンティティ7と8は、ts が300になるまで削除されなかった。したがって、ts が250 のとき、エンティティ7と8はまだ有効である。その結果、タイムトラベル後のdel_bitset は[0, 0, 0, 0, 0, 0, 0, 0] となる。

これで、Time Travelと属性フィルタリング後の2つのビットセットができあがった:filter_bitset [0, 1, 0, 1, 0, 1, 0, 1] とdel_bitset [0, 0, 0, 0, 0, 0, 0, 0] 。この2つのビットセットをOR 二項論理演算子で結合する。結果_ビットセットは[0, 1, 0, 1, 0, 1, 0, 1] 。つまり、エンタイト[1,3,5,7]だけが、次の検索またはクエリーの段階で計算される。

図2.Time Travel = 250 での検索。

ケース3

この場合、ユーザーはtime_travel を 350 と設定する。ビットセット生成プロセスを図3に示す。

前のケースと同様に、最初のfilter_bitset は[0, 1, 0, 1, 0, 1, 0, 1] である。

ts= 350のとき、すべてのエンティ ティがベクトルデータベースにある。したがって、最終的に反転されたfilter_bitset は[0, 1, 0, 1, 0, 1, 0, 1] 、ケース2と同じである。

削除ビットセットdel_bitset については、ts = 350 の時点でエンティ ティ7と8がすでに削除されているため、del_bitset の結果は[0, 0, 0, 0, 0, 0, 1, 1] となる。

タイムトラベルと属性フィルタリングの結果、filter_bitset [0, 1, 0, 1, 0, 1, 0, 1] 、del_bitset [0, 0, 0, 0, 0, 0, 1, 1] 。 この2つのビットセットをOR 二項論理演算子で結合する。究極のresult_bitset は[0, 1, 0, 1, 0, 1, 1, 1] 。つまり、エンティティ[1, 3, 5]だけが、次の検索またはクエリの段階で計算される。

図3.タイムトラベル=350での検索。

次のステップ

Milvusでビットセットがどのように機能するのかがわかったところで、次のこともやってみましょう：

• 文字列を使って検索結果をフィルタリングする方法を学ぶ。
• Milvusでデータがどのように処理されるかを理解する。