Spiegazione dell'indice
Un indice è una struttura aggiuntiva costruita sopra i dati. La sua struttura interna dipende dall'algoritmo di ricerca approssimativa dei vicini in uso. Un indice accelera la ricerca, ma comporta tempi di preelaborazione, spazio e RAM aggiuntivi durante la ricerca. Inoltre, l'uso di un indice di solito riduce il tasso di richiamo (anche se l'effetto è trascurabile, è comunque importante). Pertanto, questo articolo spiega come minimizzare i costi dell'uso di un indice massimizzandone i benefici.
Panoramica
In Milvus, gli indici sono specifici per i campi e i tipi di indice applicabili variano a seconda dei tipi di dati dei campi di destinazione. In quanto database vettoriale professionale, Milvus si concentra sul miglioramento delle prestazioni delle ricerche vettoriali e del filtraggio scalare, per questo offre diversi tipi di indice.
La tabella seguente elenca la relazione di mappatura tra i tipi di dati del campo e i tipi di indice applicabili.
Tipo di dati del campo |
Tipi di indice applicabili |
|---|---|
|
|
VETTORE BINARIO |
|
SPARSE_FLOAT_VECTOR |
INDICE SPARSE_INVERTITO |
VARCHAR |
|
BOOL |
|
|
|
|
INVERTITO |
ARRAY (elementi dei tipi BOOL, INT8/16/32/64 e VARCHAR) |
BITMAP (consigliato) |
ARRAY (elementi dei tipi BOOL, INT8/16/32/64, FLOAT, DOUBLE e VARCHAR) |
INVERTITO |
JSON |
INVERTITO |
Questo articolo si concentra su come selezionare gli indici vettoriali appropriati. Per i campi scalari, è sempre possibile utilizzare il tipo di indice consigliato.
La scelta di un tipo di indice appropriato per una ricerca vettoriale può avere un impatto significativo sulle prestazioni e sull'utilizzo delle risorse. Quando si sceglie un tipo di indice per un campo vettoriale, è essenziale considerare vari fattori, tra cui la struttura dei dati sottostante, l'uso della memoria e i requisiti di prestazione.
Anatomia dell'indice vettoriale
Come illustrato nel diagramma seguente, un tipo di indice in Milvus è costituito da tre componenti fondamentali: la struttura dei dati, la quantizzazione e il raffinatore. La quantizzazione e il raffinatore sono opzionali, ma sono ampiamente utilizzati grazie a un significativo equilibrio tra guadagni e costi.
Anatomia dell'indice vettoriale
Durante la creazione dell'indice, Milvus combina la struttura dei dati e il metodo di quantizzazione scelti per determinare un tasso di espansione ottimale. Al momento dell'interrogazione, il sistema recupera topK × expansion rate vettori candidati, applica il raffinatore per ricalcolare le distanze con maggiore precisione e infine restituisce i risultati topK più accurati. Questo approccio ibrido bilancia velocità e precisione limitando il raffinamento, che richiede molte risorse, a un sottoinsieme filtrato di candidati.
Struttura dei dati
La struttura dei dati costituisce il livello fondamentale dell'indice. I tipi più comuni sono:
File invertito (IVF)
I tipi di indice della serie IVF consentono a Milvus di raggruppare i vettori in bucket attraverso un partizionamento basato sui centroidi. In genere si può presumere che tutti i vettori di un bucket siano vicini al vettore di interrogazione se il centroide del bucket è vicino al vettore di interrogazione. Sulla base di questa premessa, Milvus analizza solo le incorporazioni vettoriali nei bucket in cui i centroidi sono vicini al vettore di interrogazione, invece di esaminare l'intero set di dati. Questa strategia riduce i costi computazionali mantenendo un'accuratezza accettabile.
Questo tipo di struttura dei dati dell'indice è ideale per i dataset di grandi dimensioni che richiedono un throughput veloce.
Struttura a grafo
Una struttura di dati a grafo per la ricerca vettoriale, come Hierarchical Navigable Small World(HNSW), costruisce un grafo a strati in cui ogni vettore si collega ai suoi vicini più prossimi. Le query navigano in questa gerarchia, partendo dai livelli superiori più grossolani e passando per quelli inferiori, consentendo un'efficiente complessità di ricerca in tempo logaritmico.
Questo tipo di struttura dei dati dell'indice eccelle negli spazi ad alta dimensionalità e negli scenari che richiedono query a bassa latenza.
Quantizzazione
La quantizzazione riduce l'ingombro di memoria e i costi di calcolo grazie a una rappresentazione più grossolana:
Laquantizzazione scalare (ad esempio SQ8) consente a Milvus di comprimere ogni dimensione vettoriale in un singolo byte (8 bit), riducendo l'utilizzo della memoria del 75% rispetto ai float a 32 bit, pur mantenendo una ragionevole precisione.
La quantizzazione del prodotto(PQ) consente a Milvus di dividere i vettori in sottovettori e di codificarli utilizzando un clustering basato su codebook. In questo modo si ottengono rapporti di compressione più elevati (ad esempio, 4-32x) al costo di un richiamo marginalmente ridotto, rendendolo adatto ad ambienti con limitazioni di memoria.
Raffinatore
La quantizzazione è intrinsecamente soggetta a perdite. Per mantenere il tasso di richiamo, la quantizzazione produce costantemente un numero di candidati top-K superiore al necessario, consentendo ai raffinatori di utilizzare una maggiore precisione per selezionare ulteriormente i risultati top-K da questi candidati, migliorando il tasso di richiamo.
Ad esempio, il raffinatore FP32 opera sui risultati di ricerca restituiti dalla quantizzazione ricalcolando le distanze utilizzando la precisione FP32 anziché i valori quantizzati.
Ciò è fondamentale per le applicazioni che richiedono un compromesso tra efficienza della ricerca e precisione, come la ricerca semantica o i sistemi di raccomandazione, dove piccole variazioni di distanza hanno un impatto significativo sulla qualità dei risultati.
Sintesi
Questa architettura a livelli - filtraggio grossolano tramite strutture di dati, calcolo efficiente tramite quantizzazione e regolazione della precisione tramite raffinamento - consente a Milvus di ottimizzare il compromesso accuratezza-prestazioni in modo adattivo.
Scambi di prestazioni
Quando si valutano le prestazioni, è fondamentale bilanciare il tempo di compilazione, le query al secondo (QPS) e il tasso di richiamo. Le regole generali sono le seguenti:
I tipi di indice basati su grafi di solito superano le varianti FIV in termini di QPS.
Le varianti IVF sono particolarmente adatte agli scenari con un topK elevato (ad esempio, oltre 2.000).
PQ offre in genere un tasso di richiamo migliore a tassi di compressione simili rispetto a SQ, anche se quest'ultimo offre prestazioni più veloci.
L'utilizzo di dischi rigidi per una parte dell'indice (come in DiskANN) aiuta a gestire grandi insiemi di dati, ma introduce anche potenziali colli di bottiglia IOPS.
Capacità
La capacità di solito riguarda il rapporto tra le dimensioni dei dati e la RAM disponibile. Quando si parla di capacità, si consideri quanto segue:
Se un quarto dei dati grezzi si inserisce nella memoria, considerare DiskANN per la sua latenza stabile.
Se tutti i dati grezzi entrano in memoria, considerare i tipi di indice basati sulla memoria e mmap.
È possibile utilizzare i tipi di indice applicati alla quantizzazione e mmap per scambiare la precisione con la massima capacità.
Mmap non è sempre la soluzione. Quando la maggior parte dei dati è su disco, DiskANN offre una latenza migliore.
Richiamo
Il richiamo di solito coinvolge il rapporto di filtraggio, che si riferisce ai dati che vengono filtrati prima delle ricerche. Quando si tratta di richiamo, considerare quanto segue:
Se il rapporto di filtraggio è inferiore all'85%, i tipi di indice basati su grafi superano le varianti FIV.
Se il rapporto di filtraggio è compreso tra l'85% e il 95%, utilizzare le varianti FIV.
Se il rapporto di filtraggio è superiore al 98%, utilizzare Brute-Force (FLAT) per ottenere risultati di ricerca più accurati.
Le voci di cui sopra non sono sempre corrette. Si consiglia di sintonizzare il richiamo con diversi tipi di indice per determinare quale tipo di indice funziona.
Prestazioni
Le prestazioni di una ricerca riguardano solitamente il top-K, che si riferisce al numero di record restituiti dalla ricerca. Quando si parla di prestazioni, si deve considerare quanto segue:
Per una ricerca con un top-K piccolo (ad esempio, 2.000) che richiede un alto tasso di richiamo, i tipi di indice a grafo superano le varianti FIV.
Per una ricerca con un top-K elevato (rispetto al numero totale di incorporazioni vettoriali), le varianti IVF sono una scelta migliore rispetto ai tipi di indice basati su grafi.
Per una ricerca con un top-K medio e un elevato rapporto di filtraggio, le varianti FIV sono la scelta migliore.
Matrice decisionale: Scelta del tipo di indice più appropriato
La tabella seguente è una matrice decisionale a cui fare riferimento per la scelta del tipo di indice più appropriato.
Scenario |
Indice consigliato |
Note |
|---|---|---|
I dati grezzi sono memorizzabili |
HNSW, FIV + raffinamento |
Utilizzare HNSW per un basso |
Dati grezzi su disco, SSD |
DiscoANN |
Ottimale per le query sensibili alla latenza. |
Dati grezzi su disco, RAM limitata |
IVFPQ/SQ + mmap |
Bilancia l'accesso alla memoria e al disco. |
Alto rapporto di filtraggio (>95%) |
Forza bruta (FLAT) |
Evita l'overhead dell'indice per piccoli insiemi di candidati. |
Grande |
FIV |
Il pruning dei cluster riduce i calcoli. |
Tasso di richiamo estremamente elevato (>99%) |
Forza bruta (FLAT) + GPU |
-- |
Stima dell'utilizzo della memoria
Questa sezione si concentra sul calcolo del consumo di memoria di un tipo specifico di indice e include molti dettagli tecnici. È possibile saltare tranquillamente questa sezione se non corrisponde ai propri interessi.
Il consumo di memoria di un indice è influenzato dalla sua struttura di dati, dal tasso di compressione tramite quantizzazione e dal raffinatore in uso. In generale, gli indici basati su grafi hanno un ingombro di memoria più elevato a causa della struttura del grafo (ad esempio, HNSW), che di solito implica un notevole sovraccarico di spazio per vettore. Al contrario, la FIV e le sue varianti sono più efficienti dal punto di vista della memoria, poiché l'overhead di spazio per vettore è minore. Tuttavia, tecniche avanzate come DiskANN consentono a parti dell'indice, come il grafico o il raffinatore, di risiedere su disco, riducendo il carico di memoria e mantenendo le prestazioni.
In particolare, l'utilizzo della memoria di un indice può essere calcolato come segue:
Utilizzo della memoria dell'indice IVF
Gli indici FIV bilanciano l'efficienza della memoria con le prestazioni di ricerca partizionando i dati in cluster. Di seguito è riportata una ripartizione della memoria utilizzata da 1 milione di vettori a 128 dimensioni indicizzati con le varianti FIV.
Calcolo della memoria utilizzata dai centroidi.
I tipi di indice della serie IVF consentono a Milvus di raggruppare i vettori in bucket utilizzando un partizionamento basato sui centroidi. Ogni centroide è incluso nell'indice nell'incorporazione vettoriale grezza. Quando si dividono i vettori in 2.000 cluster, l'utilizzo della memoria può essere calcolato come segue:
2,000 clusters × 128 dimensions × 4 bytes = 1.0 MBCalcolo della memoria utilizzata dalle assegnazioni ai cluster.
Ogni incorporazione vettoriale viene assegnata a un cluster e memorizzata come ID intero. Per 2.000 cluster è sufficiente un numero intero di 2 byte. L'utilizzo della memoria può essere calcolato come segue:
1,000,000 vectors × 2 bytes = 2.0 MBCalcolare la compressione causata dalla quantizzazione.
Le varianti della FIV utilizzano tipicamente PQ e SQ8 e l'utilizzo della memoria può essere stimato come segue:
Utilizzo di PQ con 8 subquantizzatori
1,000,000 vectors × 8 bytes = 8.0 MBUtilizzo di SQ8
1,000,000 vectors × 128 dimensions × 1 byte = 128 MB
La tabella seguente elenca l'utilizzo di memoria stimato con diverse configurazioni:
Configurazione
Stima della memoria
Memoria totale
FIV-PQ (senza affinamento)
1,0 MB + 2,0 MB + 8,0 MB
11,0 MB
FIV-PQ + 10% di raffinazione grezza
1,0 MB + 2,0 MB + 8,0 MB + 51,2 MB
62,2 MB
FIV-SQ8 (senza raffinazione)
1,0 MB + 2,0 MB + 128 MB
131,0 MB
FIV-FLAT (vettori grezzi completi)
1,0 MB + 2,0 MB + 512 MB
515,0 MB
Calcolare l'overhead di raffinamento.
Le varianti FIV sono spesso abbinate a un raffinatore per riordinare i candidati. Per una ricerca che recupera i primi 10 risultati con un tasso di espansione di 5, il refinement overhead può essere stimato come segue:
10 (topK) x 5 (expansion rate) = 50 candidates 50 candidates x 128 dimensions x 4 bytes = 25.6 KB
Utilizzo della memoria degli indici a grafo
Gli indici basati su grafi, come HNSW, richiedono una memoria significativa per memorizzare sia la struttura del grafo sia le incorporazioni vettoriali grezze. Di seguito è riportata una ripartizione dettagliata della memoria consumata da 1 milione di vettori a 128 dimensioni indicizzati con il tipo di indice HNSW.
Calcolo della memoria utilizzata dalla struttura del grafo.
Ogni vettore in HNSW mantiene le connessioni con i suoi vicini. Con un grado del grafo (bordi per nodo) di 32, la memoria consumata può essere calcolata come segue:
1,000,000 vectors × 32 links × 4 bytes (for 32-bit integer storage) = 128 MBCalcolare la memoria utilizzata dalle incorporazioni vettoriali grezze.
La memoria consumata dalla memorizzazione di vettori FP32 non compressi può essere calcolata come segue:
1,000,000 vectors × 128 dimensions × 4 bytes = 512 MBQuando si usa HNSW per indicizzare 1 milione di embeddings vettoriali a 128 dimensioni, la memoria totale utilizzata è di 128 MB (grafico) + 512 MB (vettori) = 640 MB.
Calcolare la compressione causata dalla quantizzazione.
La quantizzazione riduce le dimensioni dei vettori. Ad esempio, utilizzando PQ con 8 subquantizzatori (8 byte per vettore) si ottiene una drastica compressione. La memoria consumata dalle incorporazioni vettoriali compresse può essere calcolata come segue:
1,000,000 vectors × 8 bytes = 8 MBIn questo modo si ottiene un tasso di compressione di 64 volte rispetto alle incorporazioni vettoriali grezze, e la memoria totale utilizzata dal tipo di indice HNSWPQ sarebbe di 128 MB (grafico) + 8 MB (vettore compresso) = 136 MB.
Calcolare il refinement overhead.
Il raffinamento, come la ri-classificazione con vettori grezzi, carica temporaneamente in memoria dati ad alta precisione. Per una ricerca che recupera i primi 10 risultati con un tasso di espansione di 5, il refinement overhead può essere stimato come segue:
10 (topK) x 5 (expansion rate) = 50 candidates 50 candidates x 128 dimensions x 4 bytes = 25.6 KB
Altre considerazioni
Mentre la FIV e gli indici a grafo ottimizzano l'uso della memoria attraverso la quantizzazione, i file mappati in memoria (mmap) e DiskANN affrontano scenari in cui gli insiemi di dati superano la memoria ad accesso casuale (RAM) disponibile.
DiskANN
DiskANN è un indice basato sul grafo Vamana che collega i punti di dati per una navigazione efficiente durante la ricerca, applicando al contempo PQ per ridurre le dimensioni dei vettori e consentire un rapido calcolo approssimativo della distanza tra i vettori.
Il grafo di Vamana è memorizzato su disco, il che consente a DiskANN di gestire insiemi di dati di grandi dimensioni che altrimenti sarebbero troppo grandi per essere memorizzati. Ciò è particolarmente utile per gli insiemi di dati da un miliardo di punti.
File mappati in memoria (mmap)
La mappatura della memoria (Mmap) consente l'accesso diretto alla memoria a file di grandi dimensioni su disco, permettendo a Milvus di memorizzare indici e dati sia nella memoria che sul disco rigido. Questo approccio consente di ottimizzare le operazioni di I/O riducendo l'overhead delle chiamate di I/O in base alla frequenza di accesso, ampliando così la capacità di archiviazione delle raccolte senza incidere significativamente sulle prestazioni di ricerca.
In particolare, è possibile configurare Milvus per mappare in memoria i dati grezzi di alcuni campi invece di caricarli completamente in memoria. In questo modo, è possibile ottenere l'accesso diretto alla memoria dei campi senza preoccuparsi dei problemi di memoria ed estendere la capacità della raccolta.