Index Erklärt

Ein Index ist eine zusätzliche Struktur, die über den Daten aufgebaut wird. Seine interne Struktur hängt von dem verwendeten Algorithmus für die ungefähre Suche nach dem nächsten Nachbarn ab. Ein Index beschleunigt die Suche, verursacht aber zusätzliche Vorverarbeitungszeit, Speicherplatz und RAM während der Suche. Außerdem wird durch die Verwendung eines Indexes in der Regel die Wiederfindungsrate gesenkt (obwohl der Effekt vernachlässigbar ist, ist er dennoch von Bedeutung). In diesem Artikel wird daher erläutert, wie die Kosten für die Verwendung eines Indexes minimiert und gleichzeitig der Nutzen maximiert werden kann.

Überblick

In Milvus sind Indizes feldspezifisch, und die anwendbaren Indextypen variieren je nach den Datentypen der Zielfelder. Als professionelle Vektordatenbank konzentriert sich Milvus darauf, sowohl die Leistung der Vektorsuche als auch der skalaren Filterung zu verbessern, weshalb es verschiedene Indextypen anbietet.

In der folgenden Tabelle ist die Zuordnungsbeziehung zwischen Felddatentypen und anwendbaren Indextypen aufgeführt.

Felddatentyp	Anwendbare Indextypen
FLOAT_VECTOR FLOAT16_VECTOR BFLOAT16_VECTOR INT8_VECTOR	FLAT IVF_FLAT IVF_SQ8 IVF_PQ IVF_RABITQ HNSW HNSW_SQ HNSW_PQ HNSW_PRQ DISKANN SCANN AISAQ GPU_CAGRA GPU_IVF_FLAT GPU_IVF_PQ GPU_BRUTE_FORCE
BINÄR_VECTOR	BIN_FLAT BIN_IVF_FLAT MINHASH_LSH
SPARSE_FLOAT_VECTOR	SPARSE_INVERTIERTER_INDEX
VARCHAR	INVERTED (empfohlen) BITMAP Trie
BOOL	BITMAP (Empfohlen) INVERTED
INT8 INT16 INT32 INT64	INVERTED STL_SORT
FLOAT DOUBLE	INVERTED
ARRAY (Elemente der Typen BOOL, INT8/16/32/64 und VARCHAR)	BITMAP (empfohlen)
ARRAY (Elemente der Typen BOOL, INT8/16/32/64, FLOAT, DOUBLE und VARCHAR)	INVERTED
JSON	INVERTED

Dieser Artikel konzentriert sich auf die Auswahl geeigneter Vektorindizes. Für skalare Felder können Sie immer den empfohlenen Indextyp verwenden.

Die Auswahl eines geeigneten Indextyps für eine Vektorsuche kann die Leistung und den Ressourcenverbrauch erheblich beeinflussen. Bei der Auswahl eines Indextyps für ein Vektorfeld müssen verschiedene Faktoren berücksichtigt werden, darunter die zugrunde liegende Datenstruktur, der Speicherverbrauch und die Leistungsanforderungen.

Anatomie des Vektorindex

Wie im untenstehenden Diagramm dargestellt, besteht ein Index-Typ in Milvus aus drei Kernkomponenten, nämlich der Datenstruktur, der Quantisierung und dem Verfeinerer. Quantisierung und Refiner sind optional, werden aber aufgrund eines signifikanten Nutzen-Kosten-Verhältnisses häufig verwendet.

Anatomie des Vektorindex

Während der Indexerstellung kombiniert Milvus die gewählte Datenstruktur und die Quantisierungsmethode, um eine optimale Expansionsrate zu bestimmen. Zum Zeitpunkt der Abfrage ruft das System topK × expansion rate Kandidatenvektoren ab, wendet den Refiner an, um die Abstände mit höherer Genauigkeit neu zu berechnen, und gibt schließlich die genauesten Ergebnisse zurück topK. Dieser hybride Ansatz stellt ein Gleichgewicht zwischen Geschwindigkeit und Genauigkeit her, indem er die ressourcenintensive Verfeinerung auf eine gefilterte Teilmenge von Kandidaten beschränkt.

Datenstruktur

Die Datenstruktur bildet die grundlegende Schicht des Indexes. Übliche Typen sind:

• Invertierte Datei (IVF)

  IVF-Indextypen ermöglichen es Milvus, Vektoren durch eine auf dem Zentroid basierende Partitionierung in Bereiche zu gruppieren. Im Allgemeinen kann man davon ausgehen, dass alle Vektoren in einem Bucket wahrscheinlich nahe am Abfragevektor liegen, wenn der Bucket-Schwerpunkt nahe am Abfragevektor liegt. Ausgehend von dieser Prämisse scannt Milvus nur die Vektoreinbettungen in denjenigen Buckets, deren Zentroide sich in der Nähe des Abfragevektors befinden, anstatt den gesamten Datensatz zu untersuchen. Diese Strategie senkt die Rechenkosten und gewährleistet gleichzeitig eine akzeptable Genauigkeit.

  Diese Art der Indexdatenstruktur ist ideal für große Datensätze, die einen schnellen Durchsatz erfordern.

• Graphenbasierte Struktur

  Eine graphenbasierte Datenstruktur für die Vektorsuche, wie z. B. Hierarchical Navigable Small World(HNSW), konstruiert einen mehrschichtigen Graphen, bei dem jeder Vektor mit seinen nächsten Nachbarn verbunden ist. Abfragen navigieren durch diese Hierarchie, wobei sie von groben oberen Schichten ausgehen und durch die unteren Schichten wechseln, was eine effiziente Suchkomplexität in logarithmischer Zeit ermöglicht.

  Diese Art von Indexdatenstruktur eignet sich hervorragend für hochdimensionale Räume und Szenarien, die Abfragen mit geringer Latenz erfordern.

Quantisierung

Die Quantisierung reduziert den Speicherplatzbedarf und die Rechenkosten durch eine gröbere Darstellung:

• Die Skalarquantisierung (z. B. SQ8) ermöglicht Milvus die Komprimierung jeder Vektordimension in ein einziges Byte (8-Bit), wodurch der Speicherbedarf im Vergleich zu 32-Bit-Fließkommazahlen um 75 % reduziert wird, wobei eine angemessene Genauigkeit erhalten bleibt.

• Die Produktquantisierung(PQ) ermöglicht es Milvus, Vektoren in Untervektoren aufzuteilen und sie mit Hilfe von Codebuch-basiertem Clustering zu kodieren. Dadurch werden höhere Komprimierungsraten (z. B. 4-32x) auf Kosten einer geringfügig reduzierten Wiederauffindbarkeit erreicht, was es für Umgebungen mit begrenztem Speicherplatz geeignet macht.

Verfeinerungsprogramm

Quantisierung ist von Natur aus verlustbehaftet. Um die Wiederfindungsrate aufrechtzuerhalten, produziert die Quantisierung durchweg mehr Top-K-Kandidaten als nötig, so dass die Verfeinerer eine höhere Präzision verwenden können, um die Top-K-Ergebnisse aus diesen Kandidaten weiter auszuwählen, was die Wiederfindungsrate erhöht.

Der FP32-Verfeinerer bearbeitet beispielsweise die von der Quantisierung zurückgegebenen Suchergebniskandidaten, indem er die Abstände unter Verwendung der FP32-Präzision anstelle der quantisierten Werte neu berechnet.

Dies ist von entscheidender Bedeutung für Anwendungen, bei denen ein Kompromiss zwischen Sucheffizienz und Präzision erforderlich ist, wie z. B. bei der semantischen Suche oder bei Empfehlungssystemen, bei denen geringfügige Abstandsabweichungen die Ergebnisqualität erheblich beeinträchtigen.

Zusammenfassung

Diese mehrstufige Architektur - grobe Filterung über Datenstrukturen, effiziente Berechnung durch Quantisierung und Präzisionsabstimmung über Verfeinerung - ermöglicht Milvus eine adaptive Optimierung des Kompromisses zwischen Genauigkeit und Leistung.

Leistungsabwägungen

Bei der Bewertung der Leistung ist es von entscheidender Bedeutung, ein Gleichgewicht zwischen Erstellungszeit, Abfrage pro Sekunde (QPS) und Wiederfindungsrate herzustellen. Die allgemeinen Regeln lauten wie folgt:

• Graphenbasierte Indextypen übertreffen in der Regel die IVF-Varianten in Bezug auf die QPS.

• IVF-Varianten eignen sich besonders für Szenarien mit einem großen TopK (z. B. über 2.000).

• PQ bietet typischerweise eine bessere Wiederauffindungsrate bei ähnlichen Kompressionsraten im Vergleich zu SQ, obwohl letztere eine schnellere Leistung bietet.

• Die Verwendung von Festplatten für einen Teil des Index (wie bei DiskANN) hilft bei der Verwaltung großer Datenmengen, führt aber auch zu potenziellen IOPS-Engpässen.

Kapazität

Bei der Kapazität geht es in der Regel um das Verhältnis zwischen Datengröße und verfügbarem RAM. Wenn es um die Kapazität geht, sollten Sie Folgendes bedenken:

• Wenn ein Viertel Ihrer Rohdaten in den Speicher passt, sollten Sie DiskANN wegen der stabilen Latenzzeit in Betracht ziehen.

• Wenn alle Ihre Rohdaten in den Speicher passen, sollten Sie speicherbasierte Indextypen und mmap in Betracht ziehen.

• Mit den quantisierungsbasierten Indextypen und mmap können Sie Genauigkeit gegen maximale Kapazität eintauschen.

Rückruf

Beim Recall handelt es sich in der Regel um das Filterverhältnis, das sich auf die Daten bezieht, die vor der Suche herausgefiltert werden. Beim Recall ist Folgendes zu beachten:

• Wenn das Filterverhältnis weniger als 85 % beträgt, sind graphbasierte Indextypen besser als IVF-Varianten.

• Liegt das Filterverhältnis zwischen 85% und 95%, sollten IVF-Varianten verwendet werden.

• Bei einem Filterverhältnis von über 98% sollten Sie Brute-Force (FLAT) verwenden, um die genauesten Suchergebnisse zu erhalten.

Leistung

Die Leistung einer Suche bezieht sich in der Regel auf das Top-K, das sich auf die Anzahl der Datensätze bezieht, die die Suche zurückgibt. Wenn es um die Leistung geht, ist Folgendes zu beachten:

• Bei einer Suche mit einem kleinen Top-K (z.B. 2.000), die eine hohe Recall-Rate erfordert, sind graphbasierte Indextypen besser als IVF-Varianten.

• Bei einer Suche mit einem großen Top-K (im Vergleich zur Gesamtzahl der Vektoreinbettungen) sind IVF-Varianten die bessere Wahl als graphbasierte Indextypen.

• Für eine Suche mit einem mittleren Top-K und einem hohen Filterverhältnis sind IVF-Varianten die bessere Wahl.

Entscheidungsmatrix: Auswahl des am besten geeigneten Indextyps

Die folgende Tabelle ist eine Entscheidungsmatrix, auf die Sie sich bei der Wahl eines geeigneten Indextyps beziehen können.

Szenario	Empfohlener Index	Hinweise
Rohdaten passen in den Speicher	HNSW, IVF + Verfeinerung	Verwenden Sie HNSW für niedrigek/high recall.
Rohdaten auf Festplatte, SSD	DiskANN	Optimal für latenzempfindliche Abfragen.
Rohdaten auf der Festplatte, begrenzter RAM	IVFPQ/SQ + mmap	Gleicht Speicher- und Festplattenzugriff aus.
Hohes Filterverhältnis (>95%)	Brute-Force (FLAT)	Vermeidet Index-Overhead für kleine Kandidatengruppen.
Große k (≥1% des Datensatzes)	IVF	Cluster Pruning reduziert den Rechenaufwand.
Extrem hohe Wiederfindungsrate (>99%)	Brute-Force (FLAT) + GPUs	--

Schätzung des Speicherverbrauchs

Der Speicherverbrauch eines Indexes wird durch seine Datenstruktur, die Komprimierungsrate durch Quantisierung und den verwendeten Refiner beeinflusst. Im Allgemeinen haben graphenbasierte Indizes aufgrund der Struktur des Graphen (z. B. HNSW) einen höheren Speicherbedarf, was in der Regel einen spürbaren Overhead pro Vektor mit sich bringt. Im Gegensatz dazu sind IVF und seine Varianten speichereffizienter, da sie weniger Speicherplatz pro Vektor beanspruchen. Fortgeschrittene Techniken wie DiskANN ermöglichen es jedoch, Teile des Index, wie den Graphen oder den Refiner, auf der Festplatte zu speichern, wodurch die Speicherbelastung bei gleichbleibender Leistung verringert wird.

Die Speichernutzung eines Indexes kann wie folgt berechnet werden:

IVF-Index-Speicherverbrauch

IVF-Indizes schaffen ein Gleichgewicht zwischen Speichereffizienz und Suchleistung, indem sie die Daten in Cluster aufteilen. Nachfolgend eine Aufschlüsselung des Speicherverbrauchs von 1 Million 128-dimensionaler Vektoren, die mit IVF-Varianten indiziert wurden.

1. Berechnen Sie den von den Zentroiden verwendeten Speicherplatz.

   IVF-Indizierungstypen ermöglichen es Milvus, Vektoren mit Hilfe von Zentroid-basierter Partitionierung in Buckets zu clustern. Jeder Zentroid ist im Index der rohen Vektoreinbettung enthalten. Wenn Sie die Vektoren in 2.000 Cluster unterteilen, kann der Speicherverbrauch wie folgt berechnet werden:

   2,000 clusters × 128 dimensions × 4 bytes = 1.0 MB
   

2. Berechnen Sie den von den Clusterzuweisungen verwendeten Speicher.

   Jede Vektoreinbettung wird einem Cluster zugewiesen und als ganzzahlige IDs gespeichert. Bei 2.000 Clustern reicht eine 2-Byte-Ganzzahl aus. Der Speicherverbrauch kann wie folgt berechnet werden:

   1,000,000 vectors × 2 bytes = 2.0 MB
   

3. Berechnen Sie die durch die Quantisierung verursachte Kompression.

   IVF-Varianten verwenden in der Regel PQ und SQ8, und der Speicherbedarf kann wie folgt geschätzt werden:

   • Verwendung von PQ mit 8 Unterquantisierern

     1,000,000 vectors × 8 bytes = 8.0 MB
     

   • Verwendung von SQ8

     1,000,000 vectors × 128 dimensions × 1 byte = 128 MB 
     

   In der folgenden Tabelle ist der geschätzte Speicherverbrauch bei verschiedenen Konfigurationen aufgeführt:

   Konfiguration	Speicher Schätzung	Gesamtspeicher
   IVF-PQ (keine Verfeinerung)	1,0 MB + 2,0 MB + 8,0 MB	11,0 MB
   IVF-PQ + 10% Rohverfeinerung	1,0 MB + 2,0 MB + 8,0 MB + 51,2 MB	62,2 MB
   IVF-SQ8 (keine Verfeinerung)	1,0 MB + 2,0 MB + 128 MB	131,0 MB
   IVF-FLAT (vollständige rohe Vektoren)	1,0 MB + 2,0 MB + 512 MB	515,0 MB

4. Berechnen Sie den Verfeinerungs-Overhead.

   IVF-Varianten werden oft mit einem Verfeinerer kombiniert, um die Kandidaten neu zu ordnen. Für eine Suche, die die 10 besten Ergebnisse mit einer Expansionsrate von 5 abruft, kann der Verfeinerungs-Overhead wie folgt geschätzt werden:

   10 (topK) x 5 (expansion rate) = 50 candidates
   50 candidates x 128 dimensions x 4 bytes = 25.6 KB
   

Graph-basierter Index-Speicherverbrauch

Graphenbasierte Indextypen wie HNSW benötigen viel Speicherplatz, um sowohl die Graphenstruktur als auch die Rohvektoreinbettungen zu speichern. Es folgt eine detaillierte Aufschlüsselung des Speicherverbrauchs von 1 Million 128-dimensionaler Vektoren, die mit dem HNSW-Indextyp indiziert werden.

1. Berechnen Sie den von der Graphenstruktur verwendeten Speicherplatz.

   Jeder Vektor in HNSW unterhält Verbindungen zu seinen Nachbarn. Bei einem Graphengrad (Kanten pro Knoten) von 32 kann der Speicherverbrauch wie folgt berechnet werden:

   1,000,000 vectors × 32 links × 4 bytes (for 32-bit integer storage) = 128 MB  
   

2. Berechnen Sie den von den rohen Vektoreinbettungen verwendeten Speicher.

   Der durch die Speicherung unkomprimierter FP32-Vektoren verbrauchte Speicher kann wie folgt berechnet werden:

   1,000,000 vectors × 128 dimensions × 4 bytes = 512 MB  
   

   Wenn Sie HNSW verwenden, um die 1 Million 128-dimensionalen Vektoreinbettungen zu indizieren, würde der gesamte verwendete Speicher 128 MB (Graph) + 512 MB (Vektoren) = 640 MB betragen.

3. Berechnen Sie die durch die Quantisierung verursachte Kompression.

   Die Quantisierung reduziert die Vektorgröße. Beispielsweise führt die Verwendung von PQ mit 8 Unterquantisierern (8 Byte pro Vektor) zu einer drastischen Kompression. Der von den komprimierten Vektoreinbettungen verbrauchte Speicher kann wie folgt berechnet werden:

   1,000,000 vectors × 8 bytes = 8 MB
   

   Im Vergleich zu den unkomprimierten Vektoreinbettungen wird eine 64-fache Komprimierungsrate erreicht, und der Gesamtspeicherverbrauch des Index-Typs HNSWPQ würde 128 MB (Graph) + 8 MB (komprimierter Vektor) = 136 MB betragen.

4. Berechnen Sie den Verfeinerungs-Overhead.

   Bei der Verfeinerung, z. B. bei der Neueinordnung mit Rohvektoren, werden vorübergehend hochpräzise Daten in den Speicher geladen. Für eine Suche, die die 10 besten Ergebnisse mit einer Expansionsrate von 5 abruft, kann der Verfeinerungs-Overhead wie folgt geschätzt werden:

   10 (topK) x 5 (expansion rate) = 50 candidates
   50 candidates x 128 dimensions x 4 bytes = 25.6 KB
   

Weitere Überlegungen

Während IVF und graphenbasierte Indizes die Speichernutzung durch Quantisierung optimieren, befassen sich memory-mapped files (mmap) und DiskANN mit Szenarien, in denen Datensätze den verfügbaren Arbeitsspeicher (RAM) übersteigen.

DiskANN

DiskANN ist ein auf einem Vamana-Graphen basierender Index, der Datenpunkte für eine effiziente Navigation während der Suche miteinander verbindet und gleichzeitig PQ anwendet, um die Größe der Vektoren zu reduzieren und eine schnelle Berechnung des ungefähren Abstands zwischen Vektoren zu ermöglichen.

Der Vamana-Graph wird auf der Festplatte gespeichert, so dass DiskANN große Datensätze verarbeiten kann, die andernfalls nicht in den Speicher passen würden. Dies ist besonders nützlich für Datensätze mit Milliarden von Punkten.

Speicherabbildende Dateien (mmap)

Memory-Mapping (Mmap) ermöglicht den direkten Speicherzugriff auf große Dateien auf der Festplatte, so dass Milvus Indizes und Daten sowohl im Speicher als auch auf den Festplatten speichern kann. Dieser Ansatz trägt zur Optimierung von E/A-Vorgängen bei, indem er den Overhead von E/A-Aufrufen auf der Grundlage der Zugriffshäufigkeit reduziert und so die Speicherkapazität für Sammlungen erweitert, ohne die Suchleistung wesentlich zu beeinträchtigen.

Insbesondere können Sie Milvus so konfigurieren, dass die Rohdaten in bestimmten Feldern im Speicher abgebildet werden, anstatt sie vollständig in den Speicher zu laden. Auf diese Weise erhalten Sie direkten Speicherzugriff auf die Felder, ohne sich über Speicherprobleme Gedanken machen zu müssen, und können die Kapazität der Sammlung erweitern.