Présentation de l'index Milvus Ngram : Correspondance plus rapide des mots-clés et requêtes LIKE pour les charges de travail des agents

Dans les systèmes d'agents, la recherche de contexte est un élément fondamental de l'ensemble de la chaîne de production, qui sert de base au raisonnement, à la planification et à l'action en aval. La recherche vectorielle aide les agents à récupérer un contexte sémantiquement pertinent qui capture l'intention et le sens dans des ensembles de données vastes et non structurés. Cependant, la pertinence sémantique seule n'est souvent pas suffisante. Les pipelines d'agents s'appuient également sur la recherche plein texte pour appliquer des contraintes de mots-clés exacts, tels que les noms de produits, les appels de fonctions, les codes d'erreur ou les termes juridiquement significatifs. Cette couche d'appui garantit que le contexte récupéré n'est pas seulement pertinent, mais qu'il répond aussi explicitement à des exigences textuelles strictes.

Les charges de travail réelles reflètent systématiquement ce besoin :

• Les assistants du service clientèle doivent trouver des conversations mentionnant un produit ou un ingrédient spécifique.

• Les copilotes de codage recherchent des extraits contenant le nom exact d'une fonction, un appel API ou une chaîne d'erreur.

• Les agents juridiques, médicaux et universitaires filtrent les documents à la recherche de clauses ou de citations qui doivent apparaître mot pour mot.

Traditionnellement, les systèmes gèrent cela avec l'opérateur SQL LIKE. Une requête telle que name LIKE '%rod%' est simple et largement supportée, mais en cas de forte concurrence et de grands volumes de données, cette simplicité entraîne des coûts de performance importants.

• Sans index, une requête LIKE parcourt l'ensemble de la mémoire contextuelle et applique le filtrage ligne par ligne. Avec des millions d'enregistrements, une seule requête peut prendre quelques secondes, ce qui est beaucoup trop lent pour des interactions en temps réel avec un agent.

• Même avec un index inversé conventionnel, il est difficile d'optimiser les modèles de caractères génériques tels que %rod%, car le moteur doit toujours parcourir l'ensemble du dictionnaire et exécuter le filtrage sur chaque entrée. L'opération évite les balayages de lignes mais reste fondamentalement linéaire, ce qui n'entraîne que des améliorations marginales.

Cela crée une lacune évidente dans les systèmes de recherche hybrides : la recherche vectorielle traite efficacement la pertinence sémantique, mais le filtrage des mots clés exacts devient souvent l'étape la plus lente du pipeline.

Milvus prend en charge de manière native la recherche vectorielle et plein texte hybride avec filtrage des métadonnées. Pour remédier aux limites de la correspondance par mots clés, Milvus introduit l'index Ngram, qui améliore les performances de LIKE en divisant le texte en petites sous-chaînes et en les indexant pour une recherche efficace. Cela réduit considérablement la quantité de données examinées lors de l'exécution de la requête, ce qui permet d'obtenir des requêtes LIKE des dizaines, voire des centaines de fois plus rapides dans les charges de travail agentiques réelles.

Le reste de ce billet explique comment fonctionne l'index Ngram dans Milvus et évalue ses performances dans des scénarios réels.

Qu'est-ce que l'index Ngram ?

Dans les bases de données, le filtrage de texte est généralement exprimé à l'aide de SQL, le langage de requête standard utilisé pour récupérer et gérer les données. L'un des opérateurs de texte les plus utilisés est LIKE, qui prend en charge les correspondances de chaînes basées sur des motifs.

Les expressions LIKE peuvent être regroupées en quatre types de motifs courants, en fonction de la manière dont les caractères génériques sont utilisés :

• Correspondance infixe (name LIKE '%rod%') : Correspond aux enregistrements dans lesquels la sous-chaîne rod apparaît n'importe où dans le texte.

• Correspondance préfixe (name LIKE 'rod%') : Recherche les enregistrements dont le texte commence par rod.

• Correspondance avec le suffixe (name LIKE '%rod') : Recherche les enregistrements dont le texte se termine par rod.

• Correspondance par caractères génériques (name LIKE '%rod%aab%bc_de') : Combine plusieurs conditions de sous-chaînes (%) avec des caractères génériques uniques (_) dans un seul modèle.

Bien que ces modèles diffèrent en termes d'apparence et d'expressivité, l'index Ngram de Milvus les accélère tous en utilisant la même approche sous-jacente.

Avant de construire l'index, Milvus divise chaque valeur textuelle en courtes sous-chaînes se chevauchant de longueurs fixes, connues sous le nom de n-grammes. Par exemple, lorsque n = 3, le mot "Milvus" est décomposé en trois grammes : "Mil", "ilv", "lvu" et "vus". Chaque n-gramme est ensuite stocké dans un index inversé qui associe la sous-chaîne à l'ensemble des identifiants des documents dans lesquels elle apparaît. Au moment de l'interrogation, les conditions de LIKE sont traduites en combinaisons de recherches de n-grammes, ce qui permet à Milvus de filtrer rapidement la plupart des enregistrements non concordants et d'évaluer le modèle par rapport à un ensemble de candidats beaucoup plus restreint. C'est ce qui permet de transformer les balayages de chaînes coûteux en requêtes efficaces basées sur un index.

Deux paramètres contrôlent la manière dont l'index Ngram est construit : min_gram et max_gram. Ensemble, ils définissent la plage de longueurs de sous-chaînes que Milvus génère et indexe.

• min_gram: La longueur de sous-chaîne la plus courte à indexer. Dans la pratique, ce paramètre définit également la longueur minimale des sous-chaînes de la requête qui peuvent bénéficier de l'index Ngram

• max_gram: La plus longue longueur de sous-chaîne à indexer. Au moment de l'interrogation, il détermine en outre la taille maximale de la fenêtre utilisée pour diviser les chaînes de requête plus longues en n-grammes.

En indexant toutes les sous-chaînes contiguës dont la longueur se situe entre min_gram et max_gram, Milvus établit une base cohérente et efficace pour accélérer tous les types de motifs LIKE pris en charge.

Comment fonctionne l'index Ngram ?

Milvus met en œuvre l'index Ngram dans un processus en deux phases :

• Construire l'index : Générer des n-grammes pour chaque document et construire un index inversé pendant l'ingestion des données.

• Accélérer les requêtes : Utiliser l'index pour restreindre la recherche à un petit ensemble de candidats, puis vérifier les correspondances exactes LIKE sur ces candidats.

Un exemple concret facilite la compréhension de ce processus.

Phase 1 : Construction de l'index

Décomposer le texte en n-grammes :

Supposons que nous indexions le texte "Apple" avec les paramètres suivants :

• min_gram = 2

• max_gram = 3

Dans ce cadre, Milvus génère toutes les sous-chaînes contiguës de longueur 2 et 3 :

• 2-grammes : Ap, pp, pl, le

• 3-grammes : App, ppl, ple

Construire un index inversé :

Considérons maintenant un petit ensemble de données de cinq enregistrements :

• Document 0: Apple

• Document 1: Pineapple

• Document 2: Maple

• Document 3: Apply

• Document 4: Snapple

Lors de l'ingestion, Milvus génère des n-grammes pour chaque enregistrement et les insère dans un index inversé. Dans cet index :

• lesclés sont des n-grammes (sous-chaînes)

• Lesvaleurs sont des listes d'ID de documents où le n-gramme apparaît.

"Ap"  -> [0, 3]
"App" -> [0, 3]
"Ma"  -> [2]
"Map" -> [2]
"Pi"  -> [1]
"Pin" -> [1]
"Sn"  -> [4]
"Sna" -> [4]
"ap"  -> [1, 2, 4]
"apl" -> [2]
"app" -> [1, 4]
"ea"  -> [1]
"eap" -> [1]
"in"  -> [1]
"ine" -> [1]
"le"  -> [0, 1, 2, 4]
"ly"  -> [3]
"na"  -> [4]
"nap" -> [4]
"ne"  -> [1]
"nea" -> [1]
"pl"  -> [0, 1, 2, 3, 4]
"ple" -> [0, 1, 2, 4]
"ply" -> [3]
"pp"  -> [0, 1, 3, 4]
"ppl" -> [0, 1, 3, 4]

L'index est maintenant entièrement construit.

Phase 2 : Accélérer les requêtes

Lorsqu'un filtre LIKE est exécuté, Milvus utilise l'index Ngram pour accélérer l'évaluation de la requête grâce aux étapes suivantes :

1. Extraire le terme de la requête : Les sous-chaînes contiguës sans caractères génériques sont extraites de l'expression LIKE (par exemple, '%apple%' devient apple).

2. Décomposition du terme de la requête : Le terme de la requête est décomposé en n-grammes sur la base de sa longueur (L) et des mots configurés min_gram et max_gram.

3. Recherche de chaque gramme et intersection : Milvus recherche les n-grammes de la requête dans l'index inversé et intersecte leurs listes d'ID de documents pour produire un petit ensemble de candidats.

4. Vérifier et renvoyer les résultats : La condition originale LIKE est appliquée uniquement à cet ensemble de candidats pour déterminer le résultat final.

Dans la pratique, la manière dont une requête est divisée en n-grammes dépend de la forme du motif lui-même. Pour voir comment cela fonctionne, nous nous concentrerons sur deux cas courants : les correspondances infixes et les correspondances de caractères génériques. Les correspondances préfixes et suffixes se comportent de la même manière que les correspondances infixes, nous ne les aborderons donc pas séparément.

Correspondance infixe

Pour une correspondance infixe, l'exécution dépend de la longueur de la sous-chaîne littérale (L) par rapport à min_gram et max_gram.

1. min_gram ≤ L ≤ max_gram (par exemple, strField LIKE '%ppl%')

La chaîne littérale ppl se situe entièrement dans la plage de n-grammes configurée. Milvus recherche directement le n-gramme "ppl" dans l'index inversé, ce qui produit les ID de documents candidats [0, 1, 3, 4].

Le littéral étant lui-même un n-gramme indexé, tous les candidats satisfont déjà à la condition d'infixation. L'étape de vérification finale n'élimine aucun enregistrement et le résultat reste [0, 1, 3, 4].

2. L > max_gram (par exemple, strField LIKE '%pple%')

Le sous-chaîne littéral pple est plus long que max_gram, il est donc décomposé en n-grammes qui se chevauchent en utilisant une taille de fenêtre de max_gram. Avec max_gram = 3, on obtient les n-grammes "ppl" et "ple".

Milvus recherche chaque n-gramme dans l'index inversé :

• "ppl" → [0, 1, 3, 4]

• "ple" → [0, 1, 2, 4]

L'intersection de ces listes donne l'ensemble de candidats [0, 1, 4]. Le filtre original LIKE '%pple%' est ensuite appliqué à ces candidats. Les trois candidats satisfont à la condition, de sorte que le résultat final reste [0, 1, 4].

3. L < min_gram (par exemple, strField LIKE '%pp%')

La chaîne littérale est plus courte que min_gram et ne peut donc pas être décomposée en n-grammes indexés. Dans ce cas, l'index Ngram ne peut pas être utilisé et Milvus revient au chemin d'exécution par défaut, en évaluant la condition LIKE par le biais d'un balayage complet avec correspondance de motifs.

Correspondance de caractères génériques (par exemple, strField LIKE '%Ap%pple%')

Ce motif contient plusieurs caractères génériques, Milvus le divise donc d'abord en littéraux contigus : "Ap" et "pple".

Milvus traite ensuite chaque littéral indépendamment :

• "Ap" a une longueur de 2 et se situe dans l'intervalle du n-gramme.

• "pple" est plus long que max_gram et est décomposé en "ppl" et "ple".

La requête est ainsi réduite aux n-grammes suivants :

• "Ap" → [0, 3]

• "ppl" → [0, 1, 3, 4]

• "ple" → [0, 1, 2, 4]

L'intersection de ces listes produit un seul candidat : [0].

Enfin, le filtre original LIKE '%Ap%pple%' est appliqué au document 0 ("Apple"). Étant donné qu'il ne satisfait pas au modèle complet, l'ensemble de résultats final est vide.

Limites et compromis de l'index des ngrammes

Bien que l'index Ngram puisse améliorer de manière significative les performances des requêtes LIKE, il introduit des compromis qui doivent être pris en compte dans les déploiements réels.

• Augmentation de la taille de l'index

Le coût principal de l'index Ngram est l'augmentation des frais généraux de stockage. Étant donné que l'index stocke toutes les sous-chaînes contiguës dont la longueur est comprise entre min_gram et max_gram, le nombre de n-grammes générés augmente rapidement à mesure que cette plage s'élargit. Chaque longueur de n-gramme supplémentaire ajoute en effet un autre ensemble complet de sous-chaînes qui se chevauchent pour chaque valeur de texte, ce qui augmente à la fois le nombre de clés d'index et leurs listes d'affichage. Dans la pratique, l'extension de la plage d'un seul caractère peut approximativement doubler la taille de l'index par rapport à un index inversé standard.

• Pas efficace pour toutes les charges de travail

L'index Ngram n'accélère pas toutes les charges de travail. Si les modèles de requête sont très irréguliers, s'ils contiennent des littéraux très courts ou s'ils ne parviennent pas à réduire l'ensemble de données à un petit ensemble de candidats lors de la phase de filtrage, l'avantage en termes de performances peut être limité. Dans de tels cas, l'exécution de la requête peut encore s'approcher du coût d'un balayage complet, même si l'index est présent.

Évaluation des performances de l'index Ngram sur les requêtes LIKE

L'objectif de ce test de référence est d'évaluer l'efficacité avec laquelle l'index Ngram accélère les requêtes LIKE dans la pratique.

Méthodologie des tests

Pour replacer les performances de l'index Ngram dans leur contexte, nous le comparons à deux modes d'exécution de base :

• Master: Exécution brute sans index.

• Maître-inversé: Exécution à l'aide d'un index inversé conventionnel.

Nous avons conçu deux scénarios de test pour couvrir différentes caractéristiques de données :

• Ensemble de données textuelles Wiki: 100 000 lignes, chaque champ de texte étant tronqué à 1 Ko.

• Ensemble de données à mot unique: 1 000 000 lignes, où chaque ligne contient un seul mot.

Dans les deux scénarios, les paramètres suivants sont appliqués de manière cohérente :

• Les requêtes utilisent le modèle de correspondance infixe (%xxx%).

• L'index Ngram est configuré avec min_gram = 2 et max_gram = 4

• Pour isoler les coûts d'exécution des requêtes et éviter les frais généraux de matérialisation des résultats, toutes les requêtes renvoient count(*) au lieu d'ensembles de résultats complets.

Résultats

Test pour wiki, chaque ligne est un texte wiki dont la longueur du contenu est tronquée par 1000, 100K lignes

	Littéral	Temps (ms)	Accélération	Compter
Maître	stade	207.8		335
Maître inversé		2095		335
Nogramme		1.09	190 / 1922	335
Maître	école secondaire	204.8		340
Maître inversé		2000		340
Nogramme		1.26	162.5 / 1587	340
Master	est un établissement d'enseignement secondaire mixte.	223.9		1
Master-inversé		2100		1
Nogramme		1.69	132.5 / 1242.6	1

Test pour les mots simples, 1M lignes

	Littéral	Temps (ms)	Accélération	Comptage
Maître	na	128.6		40430
Maître inversé		66.5		40430
Nogramme		1.38	93.2 / 48.2	40430
Maître	nat	122		5200
Maître-inversé		65.1		5200
Nogramme		1.27	96 / 51.3	5200
Maître	nati	118.8		1630
Maître inversé		66.9		1630
Nogramme		1.21	98.2 / 55.3	1630
Maître	natio	118.4		1100
Maître inversé		65.1		1100
Nogramme		1.33	89 / 48.9	1100
Maître	nation	118		1100
Maître inversé		63.3		1100
Nogramme		1.4	84.3 / 45.2	1100

Note : Ces résultats sont basés sur des tests effectués en mai. Depuis lors, la branche Master a fait l'objet d'optimisations de performance supplémentaires, de sorte que l'écart de performance observé ici devrait être plus faible dans les versions actuelles.

Les résultats des tests de référence mettent en évidence un schéma clair : l'index Ngram accélère considérablement les requêtes LIKE dans tous les cas, et la rapidité d'exécution des requêtes dépend fortement de la structure et de la longueur des données textuelles sous-jacentes.

• Pour les champs de texte longs, tels que les documents de type wiki tronqués à 1 000 octets, les gains de performance sont particulièrement prononcés. Par rapport à une exécution brute sans index, l'index Ngram permet d'obtenir des gains de vitesse de l'ordre de 100 à 200×. Par rapport à un index inversé classique, l'amélioration est encore plus spectaculaire, atteignant 1 200 à 1 900 fois. En effet, les requêtes LIKE sur des textes longs sont particulièrement coûteuses pour les approches d'indexation traditionnelles, alors que les recherches de n-grammes peuvent rapidement réduire l'espace de recherche à un très petit ensemble de candidats.

• Sur les ensembles de données constitués d'entrées d'un seul mot, les gains sont moindres mais restent substantiels. Dans ce scénario, l'index Ngram est environ 80 à 100 fois plus rapide que l'exécution brute et 45 à 55 fois plus rapide qu'un index inversé conventionnel. Bien qu'un texte plus court soit intrinsèquement moins coûteux à analyser, l'approche basée sur les n-grammes évite toujours les comparaisons inutiles et réduit systématiquement le coût des requêtes.

Conclusion

L'index Ngram accélère les requêtes LIKE en décomposant le texte en n-grammes de longueur fixe et en les indexant à l'aide d'une structure inversée. Cette conception transforme l'appariement coûteux des sous-chaînes en recherches efficaces de n-grammes suivies d'une vérification minimale. Par conséquent, les balayages de texte intégral sont évités et la sémantique exacte de LIKE est préservée.

Dans la pratique, cette approche est efficace pour un large éventail de charges de travail, avec des résultats particulièrement probants pour la correspondance floue sur de longs champs de texte. L'index Ngram est donc bien adapté aux scénarios en temps réel tels que la recherche de codes, les agents d'assistance à la clientèle, la recherche de documents juridiques et médicaux, les bases de connaissances d'entreprise et la recherche universitaire, où la correspondance précise des mots clés reste essentielle.

En même temps, l'index Ngram bénéficie d'une configuration minutieuse. Le choix des valeurs appropriées de min_gram et max_gram est essentiel pour équilibrer la taille de l'index et la performance des requêtes. Lorsqu'il est réglé de manière à refléter les modèles de requête réels, l'index Ngram constitue une solution pratique et évolutive pour les requêtes LIKE à haute performance dans les systèmes de production.

Pour plus d'informations sur l'index Ngram, consultez la documentation ci-dessous :

• Ngram Index | Milvus Documentation

Vous avez des questions ou souhaitez approfondir une fonctionnalité de la dernière version de Milvus ? Rejoignez notre canal Discord ou déposez des questions sur GitHub. Vous pouvez également réserver une session individuelle de 20 minutes pour obtenir des informations, des conseils et des réponses à vos questions dans le cadre des Heures de bureau Milvus.

En savoir plus sur les fonctionnalités de Milvus 2.6

• Présentation de Milvus 2.6 : recherche vectorielle abordable à l'échelle du milliard

• Présentation de la fonction d'intégration : Comment Milvus 2.6 rationalise la vectorisation et la recherche sémantique

• Déchiquetage JSON dans Milvus : filtrage JSON 88,9 fois plus rapide et flexible

• Déverrouiller la véritable recherche au niveau de l'entité : Nouvelles fonctionnalités Array-of-Structs et MAX_SIM dans Milvus

• Rapprocher le filtrage géospatial et la recherche vectorielle avec les champs géométriques et RTREE dans Milvus 2.6

• Présentation d'AISAQ dans Milvus : la recherche vectorielle à l'échelle du milliard vient d'être 3 200 fois moins coûteuse en mémoire

• Optimisation de NVIDIA CAGRA dans Milvus : une approche hybride GPU-CPU pour une indexation plus rapide et des requêtes moins coûteuses

• MinHash LSH dans Milvus : l'arme secrète pour lutter contre les doublons dans les données d'entraînement LLM

• La compression vectorielle à l'extrême : comment Milvus répond à 3× plus de requêtes avec RaBitQ

• Les benchmarks mentent - les bases de données vectorielles méritent un vrai test

• Nous avons remplacé Kafka/Pulsar par un Woodpecker pour Milvus