TRIE

Milvus의 TRIE 인덱스는 VARCHAR 필드의 값들을 접두사 트리( 트리) 형태로 구성합니다. 문자열의 각 문자는 트리의 한 노드에 해당하며, 공통된 접두사는 한 번만 저장됩니다. 이러한 구조 덕분에 필드의 모든 값을 일일이 스캔하지 않고도 정확한 문자열 조회 및 접두사 일치를 빠르게 수행할 수 있습니다.

다음과 같은 쿼리를 자주 실행하는 경우 TRIE 인덱스를 사용하십시오.

• 다음과 같은 문자열 값에 대한 정확한 등가 비교: category == "books"

• 다음과 같은 접두사 필터링 name LIKE "abc%"

지원되는 데이터 유형

• VARCHAR 필드. 자세한 내용은 ‘문자열 필드’를 참조하십시오.

TRIE 는 VARCHAR 필드에서만 지원됩니다. JSON 필드 내의 문자열 값을 인덱싱하려면 경로를 VARCHAR 로 형변환하고 대신 NGRAM 인덱스를 사용하십시오.

작동 원리

Milvus는 TRIE 를 두 단계로 구현합니다:

1. 인덱스 구축

   • 데이터 수집 과정에서 Milvus는 인덱싱된 필드의 각 값을 읽습니다.

   • 이 값들은 트라이(trie)에 삽입됩니다. 문자는 에지에 저장되며, 각 터미널 노드는 해당 문자열을 공유하는 엔티티 ID를 기록합니다.

   • 완성된 트리는 인덱스로 영구 저장됩니다.

2. 쿼리 가속화

   • 동일성 조회의 경우, Milvus는 트리를 문자 단위로 탐색하여 정확한 값에 해당하는 노드에 도달한 후 해당 엔티티 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 ` 필드에서만 작동합니다. 데이터 유형에 대한 자세한 내용은 ` String Field`를 참조하십시오.

• 매개변수: 인덱스 매개변수는 필요하지 않습니다.

• 패턴 매칭: ` TRIE `는 등가 및 접두사 필터링에 가장 빠릅니다. 범위 필터링도 지원되지만, 인덱싱된 여러 문자열을 검색해야 할 수 있습니다. 접미사, 부분 문자열 및 일반 ` LIKE ` 패턴은 평가될 수 있지만, 인덱싱된 많은 문자열을 스캔해야 할 수 있습니다.

모범 사례

• 필터가 정확한 조회나 접두사 일치 위주로 이루어지는 경우 TRIE 를 사용하십시오.

• 워크로드가 부분 문자열(LIKE "%abc%") 또는 정규식 필터에 의존하는 경우, 정확한 앵커 매칭을 위해 FMINDEX를 사용하거나 후보 범위를 좁히기 위해 NGRAM을 대신 사용하십시오.