NGRAM

L'indice NGRAM di Milvus è costruito per accelerare le interrogazioni LIKE sui campi VARCHAR o su percorsi JSON specifici all'interno dei campi JSON. Prima di costruire l'indice, Milvus divide il testo in brevi sottostringhe sovrapposte di lunghezza fissa n, note come n-grammi. Ad esempio, con n = 3, la parola "Milvus" viene suddivisa in 3 grafemi: "Mil", "ilv", "lvu" e "vus". Questi n-grammi vengono poi memorizzati in un indice invertito che mappa ogni grammo con gli ID dei documenti in cui compare. Al momento dell'interrogazione, questo indice permette a Milvus di restringere rapidamente la ricerca a un piccolo insieme di candidati, rendendo molto più veloce l'esecuzione della query.

Si usa quando si ha bisogno di un filtro rapido con prefisso, suffisso, infisso o carattere jolly, come ad esempio:

• name LIKE "data%"

• title LIKE "%vector%"

• path LIKE "%json"

Come funziona

Milvus implementa l'indice NGRAM in un processo a due fasi:

1. Costruire l'indice: Generare n-grammi per ogni documento e costruire un indice invertito durante l'ingest.

2. Accelerazione delle query: Utilizzare l'indice per filtrare un piccolo insieme di candidati, quindi verificare le corrispondenze esatte.

Fase 1: costruire l'indice

Durante l'ingestione dei dati, Milvus costruisce l'indice NGRAM eseguendo due fasi principali:

1. Decomposizione del testo in n-grammi: Milvus fa scorrere una finestra di n su ogni stringa del campo di destinazione ed estrae le sottostringhe sovrapposte, o n-grammi. La lunghezza di queste sottostringhe rientra in un intervallo configurabile, [min_gram, max_gram].

   • min_gram: L'n-gramma più breve da generare. Questo definisce anche la lunghezza minima della sottostringa della query che può beneficiare dell'indice.

   • max_gram: L'n-gramma più lungo da generare. Al momento dell'interrogazione, viene utilizzato anche come dimensione massima della finestra quando si dividono stringhe di query lunghe.

   Ad esempio, con min_gram=2 e max_gram=3, la stringa "AI database" viene suddivisa come segue:

Costruire l'indice Ngram

- **2-grams:** `AI`, `I_`, `_d`, `da`, `at`, ...

- **3-grams:** `AI_`, `I_d`, `_da`, `dat`, `ata`, ...

<div class="alert note">

- For a range `[min_gram, max_gram]`, Milvus generates all n-grams for every length between the two values (inclusive). For example, with `[2,4]` and the word `"text"`, Milvus generates:

- **2-grams:** `te`, `ex`, `xt`

- **3-grams:** `tex`, `ext`

- **4-grams:** `text`

- N-gram decomposition is character-based and language-agnostic. For example, in Chinese, `"向量数据库"` with `min_gram = 2` is decomposed into: `"向量"`, `"量数"`, `"数据"`, `"据库"`.

- Spaces and punctuation are treated as characters during decomposition.

- Decomposition preserves original case, and matching is case-sensitive. For example, `"Database"` and `"database"` will generate different n-grams and require exact case matching during queries.

</div>

1. Creare un indice invertito: Viene creato un indice inverso che mappa ogni n-gramma generato in un elenco di ID di documenti che lo contengono.

   Per esempio, se il 2-gramma "AI" compare in documenti con ID 1, 5, 6, 8 e 9, l'indice registra {"AI": [1, 5, 6, 8, 9]}. Questo indice viene poi utilizzato al momento dell'interrogazione per restringere rapidamente l'ambito di ricerca.

Costruire l'indice Ngram 2

<div class="alert note">

A wider `[min_gram, max_gram]` range creates more grams and larger mapping lists. If memory is tight, consider mmap mode for very large posting lists. For details, refer to [Use mmap](https://zilliverse.feishu.cn/wiki/P3wrwSMNNihy8Vkf9p6cTsWYnTb).

</div>

Fase 2: accelerazione delle query

Quando viene eseguito un filtro LIKE, Milvus utilizza l'indice NGRAM per accelerare la query nelle fasi seguenti:

Accelerare le query

1. Estrarre il termine della query: La sottostringa contigua senza caratteri jolly viene estratta dall'espressione LIKE (ad esempio, "%database%" diventa "database").

2. Decomposizione del termine della query: Il termine di query viene scomposto in n-grammi in base alla sua lunghezza (L) e alle impostazioni di min_gram e max_gram.

   • Se L < min_gram, l'indice non può essere usato e la query torna a una scansione completa.

   • Se min_gram ≤ L ≤ max_gram, l'intero termine della query viene trattato come un singolo n-gramma e non sono necessarie ulteriori scomposizioni.

   • Se L > max_gram, il termine della query viene scomposto in n-grammi sovrapposti utilizzando una finestra di dimensioni pari a max_gram.

   Ad esempio, se max_gram è impostato su 3 e il termine di query è "database", che ha una lunghezza di 8, viene scomposto in sottostringhe di 3 grami come "dat", "ata", "tab", e così via.

3. Ricerca di ogni grammo e intersezione: Milvus cerca ogni grammo della query nell'indice invertito e poi interseca gli elenchi di ID documento risultanti per trovare un piccolo insieme di documenti candidati. Questi candidati contengono tutti i grammi della query.

4. Verificare e restituire i risultati: Il filtro originale LIKE viene quindi applicato come verifica finale solo al piccolo insieme di candidati per trovare le corrispondenze esatte.

Creare un indice NGRAM

È possibile creare un indice NGRAM su un campo VARCHAR o su un percorso specifico all'interno di un campo JSON.

Esempio 1: Creazione su un campo VARCHAR

Per un campo VARCHAR, è sufficiente specificare field_name e configurare min_gram e max_gram.

from pymilvus import MilvusClient

client = MilvusClient(uri="http://localhost:19530") # Replace with your server address

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

# Prepare index parameters
index_params = client.prepare_index_params()

# Add NGRAM index on the "text" field
index_params.add_index(
    field_name="text",   # Target VARCHAR field
    index_type="NGRAM",           # Index type is NGRAM
    index_name="ngram_index",     # Custom name for the index
    min_gram=2,                   # Minimum substring length (e.g., 2-gram: "st")
    max_gram=3                    # Maximum substring length (e.g., 3-gram: "sta")
)

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

Questa configurazione genera 2-grammi e 3-grammi per ogni stringa in text e li memorizza nell'indice invertito.

Esempio 2: Creazione su un percorso JSON

Per un campo JSON, oltre alle impostazioni del grammo, è necessario specificare anche:

• params.json_path - il percorso JSON che punta al valore da indicizzare.

• params.json_cast_type - deve essere "varchar" (senza distinzione tra maiuscole e minuscole), perché l'indicizzazione NGRAM opera sulle stringhe.

# Assume you have defined a JSON field named "json_field" in your collection schema, with a JSON path named "body"

# Prepare index parameters
index_params = client.prepare_index_params()

# Add NGRAM index on a JSON field
index_params.add_index(
    field_name="json_field",              # Target JSON field
    index_type="NGRAM",                   # Index type is NGRAM
    index_name="json_ngram_index",        # Custom index name
    min_gram=2,                           # Minimum n-gram length
    max_gram=4,                           # Maximum n-gram length
    params={
        "json_path": "json_field[\"body\"]",  # Path to the value inside the JSON field
        "json_cast_type": "varchar"                  # Required: cast the value to varchar
    }
)

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

In questo esempio:

• Viene indicizzato solo il valore in json_field["body"].

• Il valore viene trasformato in VARCHAR prima della tokenizzazione n-gram.

• Milvus genera sottostringhe di lunghezza compresa tra 2 e 4 e le memorizza nell'indice invertito.

Per ulteriori informazioni su come indicizzare un campo JSON, consultare Indicizzazione JSON.

Query accelerate da NGRAM

Per applicare l'indice NGRAM:

• La query deve puntare a un campo VARCHAR (o a un percorso JSON) che abbia un indice NGRAM.

• La parte letterale del pattern LIKE deve essere lunga almeno min_gram caratteri(ad esempio, se il termine di query più breve previsto è di 2 caratteri, impostare min_gram=2 durante la creazione dell'indice).

Tipi di query supportati:

• Corrispondenza di prefisso

  # Match any string that starts with the substring "database"
  filter = 'text LIKE "database%"'
  

• Corrispondenza a suffisso

  # Match any string that ends with the substring "database"
  filter = 'text LIKE "%database"'
  

• Corrispondenza infix

  # Match any string that contains the substring "database" anywhere
  filter = 'text LIKE "%database%"'
  

• Corrispondenza con caratteri jolly

  Milvus supporta sia % (zero o più caratteri) che _ (esattamente un carattere).

  # Match any string where "st" appears first, and "um" appears later in the text 
  filter = 'text LIKE "%st%um%"'
  

• Query di percorso JSON

  filter = 'json_field["body"] LIKE "%database%"'
  

Per ulteriori informazioni sulla sintassi delle espressioni di filtro, consultare gli Operatori di base.

Eliminare un indice

Usare il metodo drop_index() per rimuovere un indice esistente da una collezione.

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

Note d'uso

• Tipi di campo: Supportato sui campi VARCHAR e JSON. Per JSON, fornire sia params.json_path che params.json_cast_type="varchar".

• Unicode: La decomposizione NGRAM è basata sui caratteri, è indipendente dalla lingua e include gli spazi bianchi e la punteggiatura.

• Trade-off spazio-tempo: intervalli di grammi più ampi [min_gram, max_gram] producono più grammi e indici più grandi. Se la memoria è limitata, considerare la modalità mmap per elenchi di posting di grandi dimensioni. Per ulteriori informazioni, fare riferimento a Utilizzare mmap.

• Immutabilità: min_gram e max_gram non possono essere modificati sul posto; per modificarli, ricostruire l'indice.

Migliori pratiche

• Scegliere min_gram e max_gram in base al comportamento di ricerca.

  • Iniziare con min_gram=2, max_gram=3.

  • Impostate min_gram al letterale più breve che vi aspettate venga digitato dagli utenti.

  • Impostare max_gram vicino alla lunghezza tipica delle sottostringhe significative; max_gram più grande migliora il filtraggio ma aumenta lo spazio.

• Evitare i grammi a bassa selettività

  Gli schemi altamente ripetitivi (ad esempio, "aaaaaa") forniscono un filtraggio debole e possono produrre guadagni limitati.

• Normalizzare in modo coerente

  Applicare la stessa normalizzazione al testo ingerito e ai letterali della query (ad esempio, minuscoli, tagli) se il caso d'uso lo richiede.