TRIE

MilvusのTRIE インデックスは、VARCHAR フィールドの値をプレフィックス木（トライ）として整理します。文字列の各文字は木内の辺に対応し、共通するプレフィックスは1回だけ格納されます。この構造により、フィールド内のすべての値をスキャンすることなく、文字列の完全一致検索やプレフィックスマッチングを高速に行うことができます。

次のようなクエリを頻繁に実行する場合は、TRIE インデックスを使用してください：

• 文字列値の完全一致（例：category == "books"

• 次のような接頭辞フィルタリングname LIKE "abc%"

サポートされているデータ型

• VARCHAR フィールド。詳細については、「文字列フィールド」を参照してください。

TRIE は、VARCHAR フィールドでのみサポートされています。JSON フィールド内の文字列値をインデックス登録するには、パスをVARCHAR にキャストし、代わりにNGRAMインデックスを使用してください。

仕組み

Milvus は、TRIE を 2 つのフェーズで実装しています:

1. インデックスの構築

   • 取り込み処理中、Milvusはインデックス化対象フィールドの各値を読み込みます。

   • これらの値はトライに挿入されます。文字はエッジに沿って格納され、各末端ノードには、その文字列を共有するエンティティ ID が記録されます。

   • 完成したツリーはインデックスとして永続化されます。

2. クエリの高速化

   • 等価性チェックの場合、Milvus はツリーを 1 文字ずつ順に辿り、正確な値に対応するノードに到達すると、そのエンティティ ID を返します。

   • 前置詞の検索では、Milvus は前置詞に一致するノードまでツリーを辿り、そのサブツリーにあるエンティティ ID を収集します。

   • 一致するエンティティ ID は、最終的な結果の組み立てのためにクエリ実行部に渡されます。

等価およびプレフィックスフィルタの場合、検索コストはエンティティの数ではなく文字列の長さに比例するため、大規模なコレクションでもこれらのクエリを高速に実行できます。

TRIE インデックスの作成

VARCHAR フィールドに対して、TRIE インデックスを作成できます。追加のパラメータは必要ありません。

以下の例は、VARCHAR フィールドにTRIE インデックスを作成する方法を示しています：

from pymilvus import MilvusClient

client = MilvusClient(uri="http://localhost:19530")

# Assume you have defined a VARCHAR field named "category" in your collection schema

# Prepare index parameters
index_params = client.prepare_index_params()

# Add TRIE index on the "category" field
index_params.add_index(
    field_name="category",     # Target VARCHAR field
    index_type="TRIE",         # Index type is TRIE
    index_name="category_trie" # Optional, name your index
)

# Create the index on the collection
client.create_index(
    collection_name="product_catalog",
    index_params=index_params
)

import io.milvus.v2.client.ConnectConfig;
import io.milvus.v2.client.MilvusClientV2;
import io.milvus.v2.common.IndexParam;
import io.milvus.v2.service.index.request.CreateIndexReq;
import java.util.Collections;

MilvusClientV2 client = new MilvusClientV2(ConnectConfig.builder()
        .uri("http://localhost:19530")
        .build());

client.createIndex(CreateIndexReq.builder()
        .collectionName("product_catalog")
        .indexParams(Collections.singletonList(IndexParam.builder()
                .fieldName("category")
                .indexType(IndexParam.IndexType.TRIE)
                .indexName("category_trie")
                .build()))
        .build());

import (
    "context"
    "log"

    "github.com/milvus-io/milvus/client/v3/index"
    "github.com/milvus-io/milvus/client/v3/milvusclient"
)

ctx := context.Background()

cli, err := milvusclient.New(ctx, &milvusclient.ClientConfig{
    Address: "http://localhost:19530",
})

if err != nil {
    log.Fatal("failed to connect to milvus server: ", err.Error())
}

_, err = cli.CreateIndex(ctx, milvusclient.NewCreateIndexOption("product_catalog", "category", index.NewTrieIndex()).WithIndexName("category_trie"))

if err != nil {
    log.Fatal("failed to create index: ", err.Error())
}

use milvus::v2::prelude::*;

let config = ConnectConfig::new().uri("http://localhost:19530");

let client = ClientV2::new(&config).await?;

client
    .create_index(
        CreateIndexRequest::builder()
            .collection_name("product_catalog")
            .index_param(
                IndexParam::new()
                    .field_name("category")
                    .index_type(IndexType::Trie)
                    .index_name("category_trie"),
            )
            .build()?,
    )
    .await?;

#include <iostream>
#include "milvus/MilvusClientV2.h"

auto client = milvus::MilvusClientV2::Create();

auto status = client->Connect(milvus::ConnectParam("http://localhost:19530"));

if (!status.IsOk()) {
    std::cout << status.Message() << std::endl;
}

status = client->CreateIndex(milvus::CreateIndexRequest().WithCollectionName("product_catalog")
        .AddIndex(milvus::IndexDesc("category", "category_trie", milvus::IndexType::TRIE)));

if (!status.IsOk()) {
    std::cout << status.Message() << std::endl;
}

import { MilvusClient } from "@zilliz/milvus2-sdk-node";

const client = new MilvusClient({ address: "http://localhost:19530" });

await client.createIndex({
    collection_name: "product_catalog",
    field_name: "category",
    index_type: "TRIE",
    index_name: "category_trie",
});

export CLUSTER_ENDPOINT="http://localhost:19530"
export TOKEN="root:Milvus"

curl --request POST \
--url "${CLUSTER_ENDPOINT}/v2/vectordb/indexes/create" \
--header "Authorization: Bearer ${TOKEN}" \
--header "Content-Type: application/json" \
--header "Request-Timeout: 10" \
-d '{
    "collectionName": "product_catalog",
    "indexParams": [
        {
            "fieldName": "category",
            "indexName": "category_trie",
            "indexType": "TRIE"
        }
    ]
}'

# {
#     "code": 0,
#     "data": {}
# }

TRIE によって高速化されるクエリ

TRIE インデックスは、VARCHAR フィールドに対する以下のフィルタパターンを高速化します：

• 等価性

  filter = 'category == "books"'
  

• メンバーシップ

  filter = 'category in ["books", "electronics"]'
  

• プレフィックスマッチ

  filter = 'category LIKE "elec%"'
  

• 範囲

  filter = 'category >= "a" and category < "m"'
  

  範囲評価では、複数のインデックス化された文字列が参照される場合があります。

サフィックス、部分文字列、および一般的なLIKE パターンも、インデックス化された文字列に対して評価できますが、多くの異なる値を参照する必要がある場合があります。ワークロードが部分文字列や正規表現のマッチングが中心である場合は、代わりにFMINDEXまたはNGRAMインデックスの使用を検討してください。

インデックスの削除

drop_index() メソッドを使用して、コレクションから既存のインデックスを削除します。

client.drop_index(
    collection_name="product_catalog",   # Name of the collection
    index_name="category_trie"           # Name of the index to drop
)

import io.milvus.v2.client.ConnectConfig;
import io.milvus.v2.client.MilvusClientV2;
import io.milvus.v2.service.index.request.DropIndexReq;

MilvusClientV2 client = new MilvusClientV2(ConnectConfig.builder()
        .uri("http://localhost:19530")
        .build());

client.dropIndex(DropIndexReq.builder()
        .collectionName("product_catalog")
        .indexName("category_trie")
        .build());

import (
    "context"
    "log"

    "github.com/milvus-io/milvus/client/v3/milvusclient"
)

ctx := context.Background()

cli, err := milvusclient.New(ctx, &milvusclient.ClientConfig{
    Address: "http://localhost:19530",
})

if err != nil {
    log.Fatal("failed to connect to milvus server: ", err.Error())
}

err = cli.DropIndex(ctx, milvusclient.NewDropIndexOption("product_catalog", "category_trie"))

if err != nil {
    log.Fatal("failed to drop index: ", err.Error())
}

use milvus::v2::prelude::*;

let config = ConnectConfig::new().uri("http://localhost:19530");

let client = ClientV2::new(&config).await?;

client
    .drop_index(
        DropIndexRequest::builder()
            .collection_name("product_catalog")
            .index_name("category_trie")
            .build()?,
    )
    .await?;

#include <iostream>
#include "milvus/MilvusClientV2.h"

auto client = milvus::MilvusClientV2::Create();

auto status = client->Connect(milvus::ConnectParam("http://localhost:19530"));

if (!status.IsOk()) {
    std::cout << status.Message() << std::endl;
}

status = client->DropIndex(milvus::DropIndexRequest()
        .WithCollectionName("product_catalog")
        .WithIndexName("category_trie"));

if (!status.IsOk()) {
    std::cout << status.Message() << std::endl;
}

import { MilvusClient } from "@zilliz/milvus2-sdk-node";

const client = new MilvusClient({ address: "http://localhost:19530" });

await client.dropIndex({
    collection_name: "product_catalog",
    index_name: "category_trie",
});

export CLUSTER_ENDPOINT="http://localhost:19530"
export TOKEN="root:Milvus"

curl --request POST \
--url "${CLUSTER_ENDPOINT}/v2/vectordb/indexes/drop" \
--header "Authorization: Bearer ${TOKEN}" \
--header "Content-Type: application/json" \
--header "Request-Timeout: 10" \
-d '{
    "collectionName": "product_catalog",
    "indexName": "category_trie"
}'

# {
#     "code": 0,
#     "data": {}
# }

使用上の注意

• フィールド型： VARCHAR フィールドでのみ使用可能です。データ型の詳細については、「文字列フィールド」を参照してください。

• パラメータ：インデックス用のパラメータは不要です。

• パターンマッチング： TRIE は、等価フィルタおよびプレフィックスフィルタにおいて最も高速です。範囲フィルタもサポートされていますが、複数のインデックス化された文字列を参照する場合があります。サフィックス、部分文字列、および一般的なLIKE パターンは評価可能ですが、多くのインデックス化された文字列をスキャンする必要がある場合があります。

ベストプラクティス

• フィルタが完全一致検索や接頭辞マッチングが中心である場合は、TRIE を使用してください。

• ワークロードが部分文字列（LIKE "%abc%" ）や正規表現フィルターに依存している場合は、代わりに、アンカー付き完全一致にはFMINDEX を、候補の絞り込みにはNGRAMを使用してください。