NGRAM

Der Index NGRAM in Milvus wurde erstellt, um LIKE Abfragen auf VARCHAR Felder oder bestimmte JSON-Pfade innerhalb von JSON Feldern zu beschleunigen. Bevor der Index erstellt wird, zerlegt Milvus den Text in kurze, sich überschneidende Teilstrings einer festen Länge n, die als n-Gramme bezeichnet werden. Bei n = 3 wird zum Beispiel das Wort "Milvus" in 3-Gramme aufgeteilt: "Mil", "ilv", "lvu", und "vus". Diese n-Gramme werden dann in einem invertierten Index gespeichert, der jedes Gramm den Dokument-IDs zuordnet, in denen es vorkommt. Zur Abfragezeit erlaubt dieser Index Milvus, die Suche schnell auf eine kleine Gruppe von Kandidaten einzugrenzen, was zu einer viel schnelleren Ausführung der Abfrage führt.

Verwenden Sie ihn, wenn Sie eine schnelle Präfix-, Suffix-, Infix- oder Wildcard-Filterung benötigen:

• name LIKE "data%"

• title LIKE "%vector%"

• path LIKE "%json"

Wie funktioniert es?

Milvus implementiert den NGRAM Index in einem zweiphasigen Prozess:

1. Index aufbauen: Generierung von n-Grammen für jedes Dokument und Aufbau eines invertierten Index während des Ingest-Prozesses.

2. Abfragen beschleunigen: Verwenden Sie den Index, um eine kleine Kandidatengruppe herauszufiltern, und überprüfen Sie dann die exakten Übereinstimmungen.

Phase 1: Aufbau des Index

Während der Datenaufnahme baut Milvus den NGRAM-Index auf, indem es zwei Hauptschritte durchführt:

1. Zerlegen des Textes in n-Gramme: Milvus schiebt ein Fenster von n über jede Zeichenkette im Zielfeld und extrahiert überlappende Teilzeichenketten, oder n-Gramme. Die Länge dieser Teilstrings fällt in einen konfigurierbaren Bereich, [min_gram, max_gram].

   • min_gram: Das kürzeste zu erzeugende n-Gramm. Dies definiert auch die minimale Abfrage-Teilstringlänge, die vom Index profitieren kann.

   • max_gram: Das längste zu erzeugende n-Gramm. Zur Abfragezeit wird es auch als maximale Fenstergröße verwendet, wenn lange Abfragezeichenfolgen aufgeteilt werden.

   Zum Beispiel wird bei min_gram=2 und max_gram=3 die Zeichenfolge "AI database" wie folgt aufgeteilt:

Ngram-Index erstellen

- **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. Erstellen Sie einen invertierten Index: Es wird ein invertierter Index erstellt, der jedes generierte n-Gramm auf eine Liste der Dokument-IDs abbildet, die es enthalten.

   Wenn zum Beispiel das 2-Gramm "AI" in Dokumenten mit den IDs 1, 5, 6, 8 und 9 vorkommt, verzeichnet der Index {"AI": [1, 5, 6, 8, 9]}. Dieser Index wird dann zur Abfragezeit verwendet, um den Suchbereich schnell einzugrenzen.

Ngramm-Index 2 erstellen

<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>

Phase 2: Abfragen beschleunigen

Wenn ein LIKE Filter ausgeführt wird, verwendet Milvus den NGRAM-Index, um die Abfrage in den folgenden Schritten zu beschleunigen:

Abfragen beschleunigen

1. Extrahieren des Suchbegriffs: Die zusammenhängende Teilzeichenkette ohne Platzhalter wird aus dem Ausdruck LIKE extrahiert (z. B. wird "%database%" zu "database").

2. Zerlegen des Abfragebegriffs: Der Abfrageterm wird in n-Gramme zerlegt, basierend auf seiner Länge (L) und den Einstellungen min_gram und max_gram.

   • Wenn L < min_gram, kann der Index nicht verwendet werden und die Abfrage fällt auf einen vollständigen Scan zurück.

   • Bei min_gram ≤ L ≤ max_gram wird der gesamte Abfragebegriff als ein einziges n-Gramm behandelt, und es ist keine weitere Zerlegung erforderlich.

   • Bei L > max_gram wird der Abfragebegriff in sich überschneidende n-Gramme zerlegt, wobei eine Fenstergröße verwendet wird, die max_gram entspricht.

   Wenn zum Beispiel max_gram auf 3 gesetzt ist und der Abfragebegriff "database" eine Länge von 8 hat, wird er in 3-Gramm-Substrings wie "dat", "ata", "tab", usw. zerlegt.

3. Suche nach jeder Grammatik und Überschneidung: Milvus sucht jede Grammatik der Anfrage im invertierten Index und überschneidet dann die resultierenden Dokument-ID-Listen, um eine kleine Menge von Kandidatendokumenten zu finden. Diese Kandidaten enthalten alle Grammatiken der Abfrage.

4. Überprüfen Sie die Ergebnisse und geben Sie sie zurück: Der ursprüngliche LIKE Filter wird dann als abschließende Prüfung nur auf die kleine Kandidatenmenge angewendet, um die exakten Übereinstimmungen zu finden.

Erstellen eines NGRAM-Index

Sie können einen NGRAM-Index für ein Feld VARCHAR oder für einen bestimmten Pfad innerhalb eines Feldes JSON erstellen.

Beispiel 1: Erstellen auf einem VARCHAR-Feld

Für ein Feld VARCHAR geben Sie einfach field_name an und konfigurieren min_gram und 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
)

Diese Konfiguration erzeugt 2-Gramme und 3-Gramme für jede Zeichenkette in text und speichert sie im invertierten Index.

Beispiel 2: Erstellen auf einem JSON-Pfad

Für ein Feld JSON müssen Sie zusätzlich zu den Gram-Einstellungen auch Folgendes angeben

• params.json_path - den JSON-Pfad, der auf den Wert verweist, den Sie indizieren möchten.

• params.json_cast_type - muss "varchar" sein (Groß- und Kleinschreibung wird nicht berücksichtigt), da die NGRAM-Indizierung mit Zeichenketten arbeitet.

# 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 diesem Beispiel:

• Nur der Wert unter json_field["body"] wird indiziert.

• Der Wert wird vor der n-gram-Tokenisierung in VARCHAR umgewandelt.

• Milvus erzeugt Teilstrings der Länge 2 bis 4 und speichert sie im invertierten Index.

Weitere Informationen über die Indizierung eines JSON-Feldes finden Sie unter JSON-Indizierung.

Durch NGRAM beschleunigte Abfragen

Damit der NGRAM-Index angewendet werden kann:

• Die Abfrage muss auf ein VARCHAR Feld (oder einen JSON Pfad) abzielen, das einen NGRAM Index hat.

• Der literale Teil des LIKE Musters muss mindestens min_gram Zeichen lang sein.(Wenn z.B. der kürzeste erwartete Abfragebegriff 2 Zeichen beträgt, setzen Sie min_gram=2 beim Erstellen des Index).

Unterstützte Abfragetypen:

• Präfix-Übereinstimmung

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

• Suffix-Abgleich

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

• Infix-Abgleich

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

• Wildcard-Übereinstimmung

  Milvus unterstützt sowohl % (null oder mehr Zeichen) als auch _ (genau ein Zeichen).

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

• JSON-Pfadabfragen

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

Weitere Informationen zur Syntax von Filterausdrücken finden Sie unter Grundlegende Operatoren.

Einen Index löschen

Verwenden Sie die Methode drop_index(), um einen vorhandenen Index aus einer Sammlung zu entfernen.

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

Hinweise zur Verwendung

• Feldtypen: Unterstützt für die Felder VARCHAR und JSON. Für JSON müssen Sie sowohl params.json_path als auch params.json_cast_type="varchar" angeben.

• Unicode: Die NGRAM-Dekomposition ist zeichenbasiert und sprachunabhängig und schließt Leerzeichen und Interpunktion ein.

• Kompromiss zwischen Platz und Zeit: Breitere Grammbereiche [min_gram, max_gram] erzeugen mehr Gramm und größere Indizes. Wenn der Speicherplatz knapp ist, sollten Sie den Modus mmap für große Buchungslisten in Betracht ziehen. Weitere Informationen finden Sie unter Verwendung von mmap.

• Unveränderlichkeit: min_gram und max_gram können nicht an Ort und Stelle geändert werden - bauen Sie den Index neu auf, um sie anzupassen.

Bewährte Praktiken

• Wählen Sie min_gram und max_gram entsprechend dem Suchverhalten

  • Beginnen Sie mit min_gram=2, max_gram=3.

  • Setzen Sie min_gram auf das kürzeste Literal, das Sie erwarten, dass die Benutzer eingeben.

  • Setzen Sie max_gram auf die typische Länge sinnvoller Teilstrings; eine größere max_gram verbessert die Filterung, erhöht aber den Platzbedarf.

• Vermeiden Sie Gramm mit geringer Selektivität

  Sich stark wiederholende Muster (z. B. "aaaaaa") bieten eine schwache Filterung und können nur begrenzte Vorteile bringen.

• Einheitlich normalisieren

  Wenden Sie dieselbe Normalisierung auf eingelesenen Text und Abfrageliterale an (z. B. Kleinschreibung, Trimmen), wenn Ihr Anwendungsfall dies erfordert.