Comment la base de données comprend-elle et exécute-t-elle votre requête ?

Image de couverture

Cet article est transcrit par Angela Ni.

Une requête vectorielle dans Milvus est le processus de récupération de vecteurs via un filtrage scalaire basé sur une expression booléenne. Avec le filtrage scalaire, les utilisateurs peuvent limiter les résultats de leurs requêtes en appliquant certaines conditions aux attributs des données. Par exemple, si un utilisateur recherche des films sortis entre 1990 et 2010 et dont le score est supérieur à 8,5, seuls les films dont les attributs (année de sortie et score) remplissent la condition.

Ce billet a pour but d'examiner comment une requête est complétée dans Milvus, de la saisie d'une expression de requête à la génération d'un plan de requête et à l'exécution de la requête.

Aller à :

• Expression de requête
• Génération du plan AST
• Exécution de la requête

Expression de la requête

L'expression d'une requête avec filtrage d'attributs dans Milvus adopte la syntaxe EBNF (Extended Backus-Naur form). L'image ci-dessous présente les règles d'expression dans Milvus.

Syntaxe d'expression

Les expressions logiques peuvent être créées en combinant des opérateurs logiques binaires, des opérateurs logiques unaires, des expressions logiques et des expressions simples. La syntaxe EBNF étant elle-même récursive, une expression logique peut être le résultat de la combinaison ou d'une partie d'une expression logique plus grande. Une expression logique peut contenir de nombreuses sous-expressions logiques. La même règle s'applique à Milvus. Si un utilisateur doit filtrer les attributs des résultats avec de nombreuses conditions, il peut créer son propre ensemble de conditions de filtrage en combinant différents opérateurs et expressions logiques.

Expression booléenne

L'image ci-dessus montre une partie des règles d'expression booléenne dans Milvus. Des opérateurs logiques unaires peuvent être ajoutés à une expression. Actuellement, Milvus ne prend en charge que l'opérateur logique unaire "not", qui indique que le système doit prendre les vecteurs dont les valeurs du champ scalaire ne satisfont pas aux résultats du calcul. Les opérateurs logiques binaires comprennent "and" et "or". Les expressions simples comprennent les expressions de terme et les expressions de comparaison.

Les calculs arithmétiques de base tels que l'addition, la soustraction, la multiplication et la division sont également pris en charge lors d'une requête dans Milvus. L'image suivante illustre la priorité des opérations. Les opérateurs sont énumérés de haut en bas par ordre de priorité décroissante.

Ordre de préséance

Comment une expression de requête sur certains films est-elle traitée dans Milvus ?

Supposons qu'il y ait une abondance de données de films stockées dans Milvus et que l'utilisateur souhaite interroger certains films. Par exemple, chaque film stocké dans Milvus comporte les cinq champs suivants : ID du film, année de sortie, type de film, score et affiche. Dans cet exemple, le type de données de l'ID du film et de l'année de sortie est int64, tandis que les scores des films sont des données à virgule flottante. De même, les affiches de films sont stockées sous forme de vecteurs à virgule flottante, et le type de film sous forme de données de type chaîne. La prise en charge des données de type chaîne est une nouvelle fonctionnalité de Milvus 2.1.

Par exemple, si un utilisateur souhaite interroger les films dont les scores sont supérieurs à 8,5. Les films doivent également être sortis entre une décennie avant 2000 et une décennie après 2000 ou être de type comédie ou film d'action, l'utilisateur doit saisir l'expression prédicat suivante : score > 8.5 && (2000 - 10 < release_year < 2000 + 10 || type in [comedy,action]).

Après avoir reçu l'expression de la requête, le système l'exécutera dans l'ordre suivant :

1. Recherche de films dont le score est supérieur à 8,5. Les résultats de la requête sont appelés "result1".
2. Calculer 2000 - 10 pour obtenir "result2" (1990).
3. Calculer 2000 + 10 pour obtenir "result3" (2010).
4. Recherchez les films dont la valeur de release_year est supérieure à "result2" et inférieure à "result3". En d'autres termes, le système doit rechercher les films sortis entre 1990 et 2010. Les résultats de la requête sont appelés "result4".
5. Recherche de films qui sont soit des comédies, soit des films d'action. Les résultats de la requête sont appelés "result5".
6. Combinez "result4" et "result5" pour obtenir des films qui sont sortis entre 1990 et 2010 ou qui appartiennent à la catégorie des comédies ou des films d'action. Les résultats sont appelés "résultat6".
7. Prenez la partie commune dans "résultat1" et "résultat6" pour obtenir les résultats finaux satisfaisant toutes les conditions.

Exemple de film

Génération de plans AST

Milvus utilise l'outil open-source ANTLR (ANother Tool for Language Recognition) pour la génération d'AST (abstract syntax tree) de plans. ANTLR est un puissant générateur d'analyseur syntaxique pour la lecture, le traitement, l'exécution ou la traduction de fichiers texte ou binaires structurés. Plus précisément, ANTLR peut générer un analyseur syntaxique pour construire et parcourir des arbres d'analyse basés sur une syntaxe ou des règles prédéfinies. L'image suivante est un exemple dans lequel l'expression d'entrée est "SP=100 ;". LEXER, la fonctionnalité de reconnaissance du langage intégrée à ANTLR, génère quatre tokens pour l'expression d'entrée - "SP", "=", "100" et " ;". L'outil analyse ensuite les quatre tokens pour générer l'arbre d'analyse correspondant.

arbre d'analyse

Le mécanisme de parcours est un élément crucial de l'outil ANTLR. Il est conçu pour parcourir tous les arbres d'analyse afin d'examiner si chaque nœud obéit aux règles syntaxiques ou de détecter certains mots sensibles. Certaines des API pertinentes sont énumérées dans l'image ci-dessous. Étant donné qu'ANTLR part du nœud racine et parcourt chaque sous-nœud jusqu'en bas, il n'est pas nécessaire de différencier l'ordre de parcours de l'arbre d'analyse.

Le marcheur de l'arbre d'analyse

Milvus génère le PlanAST pour les requêtes d'une manière similaire à ANTLR. Cependant, l'utilisation de l'ANTLR nécessite la redéfinition de règles syntaxiques assez compliquées. Par conséquent, Milvus adopte l'une des règles les plus répandues - les règles d'expression booléenne - et dépend du paquetage Expr ouvert sur GitHub pour interroger et analyser la syntaxe des expressions de requête.

Lors d'une requête avec filtrage d'attributs, Milvus génère un arbre de plan primitif non résolu à l'aide de ant-parser, la méthode d'analyse fournie par Expr, dès réception de l'expression de la requête. L'arbre de plan primitif que nous obtiendrons est un arbre binaire simple. L'arbre de plan est ensuite affiné par Expr et l'optimiseur intégré à Milvus. L'optimiseur de Milvus est assez similaire au mécanisme de marcheur mentionné plus haut. Étant donné que la fonctionnalité d'optimisation de l'arborescence fournie par Expr est assez sophistiquée, la charge de l'optimiseur intégré de Milvus est allégée dans une large mesure. En fin de compte, l'analyseur analyse l'arbre de plan optimisé de manière récursive pour générer un plan AST dans la structure des tampons de protocole (protobuf).

Flux de travail du plan AST

Exécution de la requête

L'exécution de la requête est à la base l'exécution du plan AST généré dans les étapes précédentes.

Dans Milvus, un plan AST est défini dans une structure proto. L'image ci-dessous est un message avec la structure protobuf. Il existe six types d'expressions, dont l'expression binaire et l'expression unaire, qui peuvent être complétées par une expression logique binaire et une expression logique unaire.

protobuf1

protobuf2

L'image ci-dessous est une image UML de l'expression de requête. Elle montre la classe de base et la classe dérivée de chaque expression. Chaque classe est accompagnée d'une méthode acceptant les paramètres du visiteur. Il s'agit d'un modèle de conception typique des visiteurs. Milvus utilise ce modèle pour exécuter le plan AST car son principal avantage est que les utilisateurs n'ont rien à faire avec les expressions primitives mais peuvent accéder directement à l'une des méthodes des modèles pour modifier certaines classes d'expression de requête et les éléments pertinents.

UML

Lors de l'exécution d'un plan AST, Milvus reçoit d'abord un nœud de plan de type prototype. Un nœud de plan de type segcore est ensuite obtenu via l'analyseur syntaxique proto C++ interne. Après avoir obtenu les deux types de nœuds de plan, Milvus accepte une série d'accès aux classes, puis modifie et exécute la structure interne des nœuds de plan. Enfin, Milvus recherche tous les nœuds de plan d'exécution pour obtenir les résultats filtrés. Les résultats finaux sont présentés sous la forme d'un masque de bits. Un masque de bits est un tableau de nombres de bits ("0" et "1"). Les données qui satisfont aux conditions de filtrage sont marquées d'un "1" dans le masque de bits, tandis que celles qui ne satisfont pas aux exigences sont marquées d'un "0" dans le masque de bits.

exécuter le flux de travail

À propos de la série Deep Dive

Avec l'annonce officielle de la disponibilité générale de Milvus 2.0, nous avons orchestré cette série de blogs Milvus Deep Dive afin de fournir une interprétation approfondie de l'architecture et du code source de Milvus. Les sujets abordés dans cette série de blogs sont les suivants

• Vue d'ensemble de l'architecture Milvus
• API et SDK Python
• Traitement des données
• Gestion des données
• Requête en temps réel
• Moteur d'exécution scalaire
• Système d'assurance qualité
• Moteur d'exécution vectoriel