Explication de l'index

Un index est une structure supplémentaire construite au-dessus des données. Sa structure interne dépend de l'algorithme de recherche approximative du plus proche voisin utilisé. Un index accélère la recherche, mais entraîne un surcroît de temps de prétraitement, d'espace et de mémoire vive au cours de la recherche. En outre, l'utilisation d'un index diminue généralement le taux de rappel (bien que l'effet soit négligeable, il a tout de même son importance). C'est pourquoi cet article explique comment minimiser les coûts liés à l'utilisation d'un index tout en maximisant les avantages.

Vue d'ensemble

Dans Milvus, les index sont spécifiques aux champs et les types d'index applicables varient en fonction des types de données des champs cibles. En tant que base de données vectorielle professionnelle, Milvus se concentre sur l'amélioration des performances des recherches vectorielles et du filtrage scalaire, c'est pourquoi il propose différents types d'index.

Le tableau suivant répertorie la relation de correspondance entre les types de données de champ et les types d'index applicables.

Type de données de champ	Types d'index applicables
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
BINARY_VECTOR	BIN_FLAT BIN_IVF_FLAT MINHASH_LSH
SPARSE_FLOAT_VECTOR	SPARSE_INVERTED_INDEX
VARCHAR	INVERTED (recommandé) BITMAP Trie
BOOL	BITMAP (Recommandé) INVERTED
INT8 INT16 INT32 INT64	INVERTE STL_SORT
FLOAT DOUBLE	INVERTED
ARRAY (éléments des types BOOL, INT8/16/32/64 et VARCHAR)	BITMAP (recommandé)
ARRAY (éléments de type BOOL, INT8/16/32/64, FLOAT, DOUBLE et VARCHAR)	INVERTE
JSON	INVERTE

Cet article se concentre sur la manière de sélectionner les index vectoriels appropriés. Pour les champs scalaires, vous pouvez toujours utiliser le type d'index recommandé.

Le choix d'un type d'index approprié pour une recherche vectorielle peut avoir un impact significatif sur les performances et l'utilisation des ressources. Lors du choix d'un type d'index pour un champ vectoriel, il est essentiel de prendre en compte différents facteurs, notamment la structure de données sous-jacente, l'utilisation de la mémoire et les exigences en matière de performances.

Anatomie de l'index vectoriel

Comme le montre le diagramme ci-dessous, un type d'index dans Milvus se compose de trois éléments principaux, à savoir la structure de données, la quantification et l'affineur. La quantification et le raffineur sont facultatifs, mais ils sont largement utilisés en raison de l'équilibre entre les gains et les coûts.

Anatomie de l'index vectoriel

Lors de la création de l'index, Milvus combine la structure de données et la méthode de quantification choisies pour déterminer un taux d'expansion optimal. Au moment de l'interrogation, le système récupère topK × expansion rate vecteurs candidats, applique le raffineur pour recalculer les distances avec une plus grande précision et renvoie finalement les résultats topK les plus précis. Cette approche hybride permet d'équilibrer la vitesse et la précision en limitant l'affinage à un sous-ensemble de candidats filtrés, ce qui nécessite beaucoup de ressources.

Structure des données

La structure des données constitue la couche fondamentale de l'index. Les types les plus courants sont les suivants

• Fichier inversé (IVF)

  Les types d'index de la série IVF permettent à Milvus de regrouper les vecteurs en godets par le biais d'un partitionnement basé sur les centroïdes. On peut généralement supposer que tous les vecteurs d'un godet sont susceptibles d'être proches du vecteur de la requête si le centroïde du godet est proche du vecteur de la requête. Sur la base de cette hypothèse, Milvus analyse uniquement les vecteurs intégrés dans les godets dont les centroïdes sont proches du vecteur de la requête, plutôt que d'examiner l'ensemble des données. Cette stratégie permet de réduire les coûts de calcul tout en maintenant une précision acceptable.

  Ce type de structure de données d'index est idéal pour les ensembles de données à grande échelle nécessitant un débit rapide.

• Structure basée sur un graphe

  Une structure de données basée sur un graphe pour la recherche vectorielle, telle que Hierarchical Navigable Small World(HNSW), construit un graphe en couches où chaque vecteur est relié à ses voisins les plus proches. Les requêtes naviguent dans cette hiérarchie, en commençant par les couches supérieures grossières et en passant par les couches inférieures, ce qui permet d'obtenir une complexité de recherche efficace en temps logarithmique.

  Ce type de structure de données d'index excelle dans les espaces à haute dimension et dans les scénarios exigeant des requêtes à faible latence.

Quantification

La quantification réduit l'empreinte mémoire et les coûts de calcul grâce à une représentation plus grossière :

• Laquantification scalaire (par exemple SQ8) permet à Milvus de comprimer chaque dimension vectorielle en un seul octet (8 bits), ce qui réduit l'utilisation de la mémoire de 75 % par rapport aux nombres flottants de 32 bits, tout en préservant une précision raisonnable.

• Laquantification par produit(PQ) permet à Milvus de diviser les vecteurs en sous-vecteurs et de les coder à l'aide d'un regroupement basé sur un livre de codes. Cela permet d'obtenir des taux de compression plus élevés (par exemple, 4-32x) au prix d'une réduction marginale du rappel, ce qui le rend adapté aux environnements à mémoire limitée.

Affineur

La quantification entraîne intrinsèquement des pertes. Pour maintenir le taux de rappel, la quantification produit systématiquement plus de candidats top-K que nécessaire, ce qui permet aux raffineurs d'utiliser une plus grande précision pour sélectionner davantage les résultats top-K parmi ces candidats, améliorant ainsi le taux de rappel.

Par exemple, le raffineur FP32 opère sur les candidats aux résultats de recherche renvoyés par la quantification en recalculant les distances à l'aide de la précision FP32 plutôt qu'à l'aide des valeurs quantifiées.

Ceci est essentiel pour les applications nécessitant un compromis entre l'efficacité de la recherche et la précision, telles que la recherche sémantique ou les systèmes de recommandation, où des variations mineures de distance ont un impact significatif sur la qualité des résultats.

Résumé

Cette architecture à plusieurs niveaux - filtrage grossier via les structures de données, calcul efficace via la quantification et réglage de la précision via le raffinement - permet à Milvus d'optimiser le compromis précision-performance de manière adaptative.

Compromis de performance

Lors de l'évaluation des performances, il est essentiel de trouver un équilibre entre le temps de construction, le nombre de requêtes par seconde (QPS) et le taux de rappel. Les règles générales sont les suivantes :

• Lestypes d'index basés sur les graphes sont généralement plus performants que les variantes FVI en termes de QPS.

• Les variantesFVI sont particulièrement adaptées aux scénarios avec un topK important (par exemple, plus de 2 000).

• LePQ offre généralement un meilleur taux de rappel à des taux de compression similaires par rapport au SQ, bien que ce dernier offre des performances plus rapides.

• L'utilisation de disques durs pour une partie de l'index (comme dans DiskANN) aide à gérer les grands ensembles de données, mais elle introduit également des goulets d'étranglement potentiels en termes d'IOPS.

Capacité

La capacité implique généralement la relation entre la taille des données et la mémoire vive disponible. Lorsqu'il s'agit de capacité, considérez ce qui suit :

• Si un quart de vos données brutes est stocké en mémoire, optez pour DiskANN en raison de sa latence stable.

• Si toutes vos données brutes tiennent dans la mémoire, pensez aux types d'index basés sur la mémoire et à mmap.

• Vous pouvez utiliser les types d'index appliqués à la quantification et mmap pour échanger la précision contre la capacité maximale.

Rappel

Le rappel implique généralement le ratio de filtrage, qui fait référence aux données filtrées avant les recherches. En ce qui concerne le rappel, il convient de tenir compte des éléments suivants :

• Si le taux de filtrage est inférieur à 85 %, les types d'index basés sur les graphes sont plus performants que les variantes IVF.

• Si le taux de filtrage est compris entre 85 % et 95 %, utilisez les variantes du FVI.

• Si le taux de filtrage est supérieur à 98 %, utilisez Brute-Force (FLAT) pour obtenir les résultats de recherche les plus précis.

Performance de la recherche

Les performances d'une recherche concernent généralement le top-K, c'est-à-dire le nombre d'enregistrements renvoyés par la recherche. En ce qui concerne les performances, il convient de tenir compte des éléments suivants :

• Pour une recherche avec un petit top-K (par exemple, 2 000) nécessitant un taux de rappel élevé, les types d'index basés sur les graphes sont plus performants que les variantes FIV.

• Pour une recherche avec un top-K important (par rapport au nombre total d'intégrations vectorielles), les variantes IVF sont un meilleur choix que les types d'index basés sur les graphes.

• Pour une recherche avec un top-K de taille moyenne et un ratio de filtrage élevé, les variantes de FVI sont de meilleurs choix.

Matrice de décision : Choisir le type d'index le plus approprié

Le tableau suivant est une matrice de décision à laquelle vous pouvez vous référer pour choisir un type d'index approprié.

Scénario	Indice recommandé	Remarques
Les données brutes tiennent dans la mémoire	HNSW, FIV + raffinement	Utiliser HNSW pour une faiblek/ une forte mémorisation.
Données brutes sur disque, SSD	DiskANN	Optimal pour les requêtes sensibles à la latence.
Données brutes sur disque, RAM limitée	IVFPQ/SQ + mmap	Équilibre l'accès à la mémoire et au disque.
Taux de filtrage élevé (>95%)	Force brute (FLAT)	Évite la surcharge de l'index pour les petits ensembles de candidats.
Grandes k (≥1% de l'ensemble de données)	IVF	L'élagage des clusters réduit les calculs.
Taux de rappel extrêmement élevé (>99%)	Brute-Force (FLAT) + GPUs	--

Estimation de l'utilisation de la mémoire

La consommation de mémoire d'un index est influencée par sa structure de données, le taux de compression par quantification et le raffineur utilisé. D'une manière générale, les index basés sur les graphes ont une empreinte mémoire plus importante en raison de la structure du graphe (par exemple, HNSW), ce qui implique généralement un surcoût d'espace notable par vecteur. En revanche, le FVI et ses variantes sont plus efficaces en termes de mémoire, car l'encombrement par vecteur est moindre. Toutefois, des techniques avancées telles que DiskANN permettent à certaines parties de l'index, comme le graphe ou le raffineur, de résider sur le disque, ce qui réduit la charge de mémoire tout en maintenant les performances.

Plus précisément, l'utilisation de la mémoire d'un index peut être calculée comme suit :

Utilisation de la mémoire de l'index FVI

Les index FVI équilibrent l'efficacité de la mémoire et les performances de recherche en partitionnant les données en grappes. Vous trouverez ci-dessous une ventilation de la mémoire utilisée par 1 million de vecteurs à 128 dimensions indexés à l'aide de variantes IVF.

1. Calculez la mémoire utilisée par les centroïdes.

   Les types d'index de la série IVF permettent à Milvus de regrouper les vecteurs en buckets à l'aide d'un partitionnement basé sur les centroïdes. Chaque centroïde est inclus dans l'index dans l'intégration vectorielle brute. Lorsque vous divisez les vecteurs en 2 000 clusters, l'utilisation de la mémoire peut être calculée comme suit :

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

2. Calculez la mémoire utilisée par les affectations de grappes.

   Chaque intégration vectorielle est affectée à une grappe et stockée sous forme d'ID entiers. Pour 2 000 grappes, un nombre entier de 2 octets suffit. L'utilisation de la mémoire peut être calculée comme suit :

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

3. Calculer la compression causée par la quantification.

   Les variantes de la FIV utilisent généralement PQ et SQ8, et l'utilisation de la mémoire peut être estimée comme suit :

   • Utilisation de PQ avec 8 sous-quantifieurs

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

   • Utilisation de SQ8

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

   Le tableau suivant indique l'utilisation estimée de la mémoire pour différentes configurations :

   Configuration	Estimation de la mémoire	Mémoire totale
   IVF-PQ (pas de raffinement)	1,0 MB + 2,0 MB + 8,0 MB	11,0 MO
   IVF-PQ + 10 % de raffinement brut	1,0 MB + 2,0 MB + 8,0 MB + 51,2 MB	62,2 MO
   FIV-SQ8 (pas de raffinement)	1,0 MB + 2,0 MB + 128 MB	131,0 MO
   IVF-FLAT (vecteurs bruts complets)	1,0 MB + 2,0 MB + 512 MB	515,0 MO

4. Calculer la surcharge de raffinement.

   Les variantes du FVI sont souvent associées à un affineur pour reclasser les candidats. Pour une recherche extrayant les 10 premiers résultats avec un taux d'expansion de 5, le surcoût lié à l'affinage peut être estimé comme suit :

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

Utilisation de la mémoire des index basés sur les graphes

Les types d'index basés sur les graphes tels que HNSW nécessitent une mémoire importante pour stocker à la fois la structure du graphe et les intégrations vectorielles brutes. Vous trouverez ci-dessous une ventilation détaillée de la mémoire consommée par 1 million de vecteurs à 128 dimensions indexés à l'aide du type d'index HNSW.

1. Calculez la mémoire utilisée par la structure du graphe.

   Chaque vecteur dans HNSW maintient des connexions avec ses voisins. Avec un degré de graphe (arêtes par nœud) de 32, la mémoire consommée peut être calculée comme suit :

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

2. Calculer la mémoire utilisée par les encastrements de vecteurs bruts.

   La mémoire consommée par le stockage des vecteurs FP32 non compressés peut être calculée comme suit :

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

   Lorsque vous utilisez HNSW pour indexer les 1 million d'intégrations vectorielles à 128 dimensions, la mémoire totale utilisée est de 128 Mo (graphique) + 512 Mo (vecteurs) = 640 Mo.

3. Calculez la compression causée par la quantification.

   La quantification réduit la taille des vecteurs. Par exemple, l'utilisation de PQ avec 8 sous-quantificateurs (8 octets par vecteur) conduit à une compression drastique. La mémoire consommée par les intégrations vectorielles compressées peut être calculée comme suit :

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

   Cela permet d'obtenir un taux de compression 64 fois supérieur à celui des vecteurs bruts, et la mémoire totale utilisée par le type d'index HNSWPQ serait de 128 Mo (graphique) + 8 Mo (vecteur compressé) = 136 Mo.

4. Calculer la surcharge de raffinement.

   L'affinage, tel que le reclassement avec des vecteurs bruts, charge temporairement des données de haute précision en mémoire. Pour une recherche permettant d'extraire les 10 premiers résultats avec un taux d'expansion de 5, le surcoût lié à l'affinage peut être estimé comme suit :

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

Autres considérations

Alors que les index IVF et basés sur les graphes optimisent l'utilisation de la mémoire grâce à la quantification, les fichiers mappés en mémoire (mmap) et DiskANN traitent les scénarios dans lesquels les ensembles de données dépassent la mémoire vive disponible (RAM).

DiskANN

DiskANN est un index basé sur un graphe de Vamana qui relie les points de données pour une navigation efficace pendant la recherche, tout en appliquant le PQ pour réduire la taille des vecteurs et permettre un calcul rapide de la distance approximative entre les vecteurs.

Le graphe de Vamana est stocké sur le disque, ce qui permet à DiskANN de traiter de grands ensembles de données qui seraient autrement trop volumineux pour être stockés en mémoire. Cela est particulièrement utile pour les ensembles de données d'un milliard de points.

Fichiers mappés en mémoire (mmap)

Le mappage de la mémoire (Mmap) permet un accès direct de la mémoire aux grands fichiers sur disque, ce qui permet à Milvus de stocker les index et les données à la fois dans la mémoire et sur les disques durs. Cette approche permet d'optimiser les opérations d'E/S en réduisant les frais généraux des appels d'E/S en fonction de la fréquence d'accès, augmentant ainsi la capacité de stockage des collections sans affecter de manière significative les performances de recherche.

Plus précisément, vous pouvez configurer Milvus pour mapper en mémoire les données brutes dans certains champs au lieu de les charger entièrement en mémoire. De cette manière, vous pouvez obtenir un accès direct à la mémoire des champs sans vous soucier des problèmes de mémoire et étendre la capacité de la collection.