Au cœur même d’openCypher, le MATCH La clause vous permet de spécifier des modèles de requête simples pour récupérer les relations à partir d’une base de données de graphes. Un modèle de longueur variable est couramment utilisé pour décrire les chemins et c’est la première tentative de Nebula Graph d’obtenir nGQL compatible avec openCypher dans le MATCH clause.
Comme on peut le voir dans les articles précédents de cette série, un plan d’exécution est composé d’opérateurs physiques. Chaque opérateur est responsable de l’exécution d’une logique de calcul unique. Pour mettre en œuvre le MATCH clause, les opérateurs tels que GetNeighbors, GetVertices, Join, Project, Filter, et Loop, qui ont été introduites dans les articles précédents, sont nécessaires. Contrairement à l’arborescence d’une base de données relationnelle, le processus d’exécution exprimé par un plan d’exécution dans Nebula Graph est un graphe cyclique. Comment transformer un motif de longueur variable en un plan physique dans Nebula Graph est au centre du planificateur. Dans cet article, nous allons présenter comment la correspondance de motifs de longueur variable est implémentée dans Nebula Graph.
Analyse du problème
Modèle à longueur fixe
Dans un MATCH clause, un modèle de longueur fixe est couramment utilisé pour rechercher une relation. Si un motif de longueur fixe est considéré comme un cas particulier du motif de longueur variable, c’est-à-dire un motif décrivant un chemin d’une longueur spécifiée, les implémentations des deux peuvent être unifiées. Voici les exemples.
// Fixed-length pattern MATCH (v)-[e]-(v2)Les exemples précédents diffèrent les uns des autres par le type de e variable. Dans le modèle de longueur fixe, e représente une arête, tandis que dans la longueur variable, e représente une liste d’arêtes de longueur 1.
Connexion de motifs de longueur variable
Selon la syntaxe d’openCypher, un MATCH La clause vous permet de spécifier une combinaison de divers modèles pour décrire des chemins compliqués. Par exemple, deux motifs de longueur variable peuvent être connectés comme suit.
MATCH (v)-[e*1..3]-(v2)-[ee*2..4]-(v3)La combinaison de motifs dans l’exemple précédent est extensible, ce qui signifie qu’en connectant des motifs de longueur variable et de longueur fixe de différentes manières, divers chemins compliqués peuvent être interrogés. Par conséquent, nous devons trouver un modèle pour générer un plan d’exécution afin d’itérer l’ensemble du processus de manière récursive. Les conditions suivantes doivent être prises en compte :
- Le chemin de longueur variable suivant dépend du précédent.
- Les variables du modèle suivant dépendent du modèle précédent.
- Avant la prochaine étape de parcours, le sommet de départ doit être dédupliqué.
A partir de l’exemple suivant, vous pouvez voir que tant qu’un plan d’exécution peut être généré pour la partie de ()-[:like*m..n]-, des combinaisons et des itérations peuvent être appliquées pour générer des plans pour les parties suivantes.
()-[:like*m..n]- ()-[:like*k..l]- ()
____________/ ____________/ _/
Pattern1 Pattern2 Pattern3Plan d’exécution
Dans cette section, nous allons présenter comment le ()-[:like*m..n]- partie de l’exemple précédent est transformée en un plan d’exécution physique dans Nebula Graph. Ce modèle décrit un graphique d’un minimum de m houblon et un maximum de n houblon.
Dans Nebula Graph, un parcours en une étape est complété par le GetNeighbors opérateur. Pour implémenter un parcours en plusieurs étapes, chaque étape de parcours doit appeler le GetNeighbors à nouveau sur la base de l’étape précédente, et lorsque le parcours de toutes les étapes est terminé, tous les sommets et arêtes récupérés sont connectés bout à bout pour former un seul chemin.
Ce dont les utilisateurs ont besoin, ce sont les chemins de m à n des relations. Cependant, dans le processus d’exécution, les chemins de longueur 1 à longueur n sont interrogés et stockés pour la sortie ou pour le prochain parcours, mais seuls les chemins de longueur m à n sont récupérés.
Traversée en une étape
Voyons à quoi ressemble la traversée en une étape. Dans Nebula Graph, le sommet source est stocké avec ses arêtes sortantes, de sorte que leur récupération n’a pas besoin d’accéder aux données entre les partitions. Cependant, le sommet de destination et ses arêtes entrantes sont stockés dans des partitions différentes, donc GetVertices est nécessaire pour récupérer les propriétés du sommet. De plus, pour éviter l’analyse répliquée du stockage, les sommets source doivent être dédupliqués avant le parcours. Le plan d’exécution d’un parcours en une étape est présenté comme suit.
Traversée en plusieurs étapes
Le processus d’un parcours en plusieurs étapes est la répétition d’un parcours en une étape. Cependant, nous pouvons voir que le GetNeighbors L’opérateur peut récupérer les propriétés du sommet source d’une arête, de sorte que le GetVertices L’opérateur peut être omis à l’étape précédente. Voici un plan d’exécution d’un parcours en deux étapes.
Mémorisation des chemins
Les chemins récupérés à chaque étape de parcours peuvent être nécessaires à la fin du parcours, donc tous les chemins doivent être stockés. Les chemins pour une traversée en deux étapes sont reliés par le Join opérateur. Dans le résultat de l’exemple ()-[e:like*m..n]-, e représente une liste de données (arêtes), donc Union est nécessaire pour fusionner les résultats de chaque étape de parcours. Le plan d’exécution sera développé comme suit.
Connexion de motifs de longueur variable
Après la mise en œuvre du processus précédent, un plan physique sera généré pour le ()-[e:like*m..n]- modèle. Si plusieurs modèles similaires sont connectés ensemble, un tel processus est itéré. Cependant, avant l’itération, les résultats du processus précédent doivent être filtrés pour obtenir les chemins de longueur m à la longueur n. L’ensemble de données récupéré du processus précédent implique les chemins de longueur 1 à longueur n, il est donc nécessaire de les filtrer par longueur de chemin. Lorsque les motifs de longueur variable sont connectés ensemble, le plan d’exécution devient le suivant.
Après la décomposition pas à pas des patterns, le plan d’exécution attendu pour le MATCH la clause est finalement générée. Comme vous pouvez le voir, il faut beaucoup d’efforts pour transformer un modèle compliqué en interfaces sous-jacentes pour une traversée. Bien entendu, le plan d’exécution peut être optimisé, comme le parcours en plusieurs étapes peut être encapsulé en utilisant l’opérateur Loop et le sous-plan d’un parcours en une étape peut être réutilisé, ce qui ne sera pas détaillé dans cet article. Si vous êtes intéressé, veuillez vous référer au code source de Nebula Graph.
Sommaire
Cet article a démontré le processus de génération d’un plan d’exécution pour un MATCH clause avec un motif de longueur variable. En lisant l’article, vous vous posez peut-être cette question : pourquoi une requête de chemin aussi simple et basique génère-t-elle un plan d’exécution aussi compliqué dans Nebula Graph ? Ce n’est pas comme Neo4j, où seuls quelques opérateurs sont nécessaires pour effectuer le même travail. Dans Nebula Graph, des graphes acycliques orientés compliqués (DAG) sont générés.
La réponse est que dans Nebula Graph, les opérateurs sont plus proches des interfaces sous-jacentes et il y a un manque d’abstractions sémantiques pour les opérations graphiques de niveau supérieur. La granularité de l’opérateur est trop fine, donc trop de détails doivent être pris en compte pour mettre en œuvre l’optimisation de la couche supérieure. Nous étudierons plus en détail les opérateurs d’exécution pour améliorer progressivement la fonctionnalité et les performances du MATCH clause.
Si vous rencontrez des problèmes lors de l’utilisation de Nebula Graph, veuillez vous reporter au manuel de la base de données Nebula Graph pour résoudre le problème. Il enregistre en détail les points de connaissance et l’utilisation spécifique de la base de données de graphes et de la base de données de graphes Nebula Graph.