Créer un moteur Datalog interactif en Rust

 (github.com/frankmcsherry)
1 points par GN⁺ 2025-06-16 | 1 commentaires | Partager sur WhatsApp
  • Les limites d’utilisabilité et de performance des outils Datalog, mises en évidence lors d’un atelier sur la programmation logique, ont motivé le lancement de l’expérimentation datatoad, un shell Datalog interactif basé sur Rust
  • datatoad vise une architecture permettant d’ajouter des règles pendant l’exécution et de continuer à dériver de nouveaux faits ; le stockage columnar et une hiérarchie LSM réduisent le coût du traitement des doublons dans les ensembles de faits
  • L’évaluation des règles transforme le corps Datalog en problème de jointure et sépare l’évaluation complète de l’évaluation incrémentale selon le caractère stable, afin d’éviter les jointures stable-stable déjà calculées
  • Dans des expériences sur le jeu de données Graspan, une simple réécriture manuelle des règles et l’introduction de relations intermédiaires ont fait passer l’analyse d’aliasing de 736,34 s et 50,13 Go à 119,34 s et 5,32 Go
  • Les travaux suivants se poursuivent avec l’optimisation des plans de jointure basée sur les e-graphs, les layered tries, la représentation en octets de largeur fixe, le spill sur disque, l’évaluation distribuée, les jointures en streaming et la demand transform

Le problème que datatoad cherche à résoudre

  • Lors d’un atelier de programmation logique le week-end du Memorial Day, l’inconfort d’utilisation des outils Datalog pour l’analyse de programmes est apparu clairement, ce qui a motivé une tentative d’implémentation Datalog simple, utilisable et rapide
  • La cible n’est pas un exécuteur statique d’exemples, mais un shell Datalog interactif
    • Il peut charger des faits en masse
    • Il peut ajouter de nouvelles règles pendant l’exécution
    • Il continue à intégrer les résultats des règles ajoutées à l’état existant
  • Le code peut être suivi dans le dépôt datatoad
  • datafrog, existant, fournit les algorithmes cœur d’un moteur Datalog, mais sous une forme que l’utilisateur doit câbler lui-même ; datatoad réorganise les mêmes idées dans une forme plus facile à utiliser
  • Dans l’exemple de nullability du graphe de dataflow httpd, datatoad a pris 8,3 secondes avec des données Vec<String> et des requêtes non compilées, soit environ 4 fois plus que les quelque 2 secondes de l’exemple datafrog utilisant des données (u32, u32)
  • Sur le problème de reachability, il a produit le même nombre de tuples en sortie que l’implémentation datafrog, mais la validation générale de l’exactitude n’est pas encore terminée

Modèle Datalog et structure du shell

  • Datalog est un langage dans lequel on écrit des règles logiques simples, puis tous les faits atteignables à partir de ces règles sont dérivés
  • Une règle se compose d’une head et d’un body
    • Exemple : tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
    • tri et edge sont des relations, tandis que a, b et c sont des variables
    • Les variables qui apparaissent dans la head doivent aussi apparaître dans le body
  • Les faits sont traités comme des règles dont le body est vide
    • Exemple : edge(1, 2) :- .
    • Plusieurs faits peuvent être écrits en une seule fois en utilisant plusieurs heads
  • En raison de la monotonie de Datalog, l’ajout de règles ou de faits ne réduit pas l’ensemble des faits vrais, et un même ensemble de règles d’entrée atteint le même résultat quel que soit l’ordre des règles
  • La représentation Rust s’articule autour de trois structures : Rule, Atom et Term
    • Rule { head: Vec<Atom>, body: Vec<Atom> }
    • Atom { name: String, terms: Vec<Term> }
    • Term::Var(String) ou Term::Lit(String)
  • Pour stocker les littéraux, Vec<u8> est utilisé au lieu de String
    • Les propriétés nécessaires sont l’égalité des littéraux et un ordre de tri arbitraire
    • Le fait que les octets représentent une String, un (u32, u32) ou une autre sémantique est laissé à l’utilisateur
  • L’état de l’interpréteur conserve ensemble les règles et les faits
    • rules: Vec<Rule>
    • facts: facts::Facts
  • Lorsque le shell parse une ligne d’entrée comme du Datalog, il appelle State::extend et State::update, et la commande .list affiche chaque nom de relation ainsi que le nombre de faits

Parsing et stockage des faits

  • Le parseur se trouve dans parse.rs et utilise une forme issue de la syntaxe Soufflé
  • Les variables commencent par ?
  • Les tokens sont limités à ., ,, (, ), :- et ?, le reste du texte étant traité comme un nom d’atom ou de term
  • Le tokenizer supprime les espaces et remplace :- par ← pour le scanner comme un symbole unique
  • Le parsing des règles lit les atoms de head jusqu’au turnstile, puis les atoms de body jusqu’au point
    • Un atom se compose d’un nom, d’une parenthèse gauche, d’une liste de terms et d’une parenthèse droite
    • Un term est une variable s’il y a ?, sinon un littéral
  • Les règles invalides renvoient None et, pour l’instant, n’indiquent pas précisément quelle partie est incorrecte
  • Pour ajouter des règles négatives, il faudrait un token Exclamation, mais ce cas n’est pas encore traité

Cycle de vie des ensembles de faits

  • Un stockage simple en Vec<Vec<String>> implique des allocations imbriquées et est défavorable à la gestion mémoire
  • datatoad utilise columnar pour transformer des types Rust en un petit nombre d’allocations linéaires avec une mise en page aplatie
    • Les octets des chaînes, les limites des chaînes et les limites des faits sont stockés dans des tableaux séparés
  • FactContainer enveloppe une liste de faits triée et dédupliquée ; en tant que wrapper type, il suggère l’invariant de tri et de déduplication
  • Le conteneur columnar étant de fait append-only et peu adapté aux modifications intermédiaires, l’ajout de nouveaux faits utilise une forme de log-structured merge-tree (LSM)
    • FactLSM { layers: Vec<FactContainer> }
    • Les tailles des couches sont gérées pour croître géométriquement
    • Les couches dont les tailles sont à un facteur 2 près sont fusionnées afin de maintenir l’état trié et dédupliqué
  • FactBuilder contient à la fois une zone active, non triée et pouvant contenir des doublons, et des layers triées et dédupliquées
  • Les faits de chaque relation passent par trois étapes
    • to_add : faits nouvellement arrivés, dont on n’a pas encore vérifié s’ils sont novel
    • recent : faits distincts qui restent à traiter
    • stable : faits distincts déjà entièrement traités
  • FactSet::advance déplace recent vers stable, puis retire de to_add les faits déjà présents dans stable pour produire le nouveau recent

L’évaluation des règles est un problème de jointure

  • Le corps d’une règle Datalog peut être vu comme une equi-join de base de données relationnelle
  • L’exemple de règle de triangle est le suivant
    • tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
  • Énumérer directement toutes les affectations de variables donnerait un volume trop important, même s’il est fini ; on trie donc sur les colonnes clés des variables communes, puis on fusionne
  • L’implémentation réduit le body de droite à gauche
    • Elle joint les deux dernières relations pour créer une relation intermédiaire, puis la joint à nouveau avec la relation de gauche
    • S’il n’y a qu’un seul atom dans le body, elle ne fait que le convertir dans la forme de la head
  • JoinPlan contient les informations suivantes
    • bodys, qui réorganise et filtre les atoms du body pour la jointure
    • joins, qui contient l’arity des clés de chaque jointure intermédiaire et la projection de sortie
    • heads, qui indique les coordonnées ou les littéraux à insérer dans les atoms de head
    • l’arity de la dernière jointure de génération de head
  • Le plan actuel est un simple right-linear join plan
  • Lors de la génération de JoinPlan, les positions leftmost et rightmost de chaque variable sont utilisées pour déterminer jusqu’à quand conserver la valeur de cette variable, puis les colonnes des atoms du body sont séparées en colonnes dead, key et value
  • La fonction centrale est implement_plan(rule, plan, pos, stable, facts)
    • Lorsqu’une nouvelle règle est ajoutée, elle démarre avec stable = true sur l’ensemble des faits
    • Lors de l’application répétée de règles existantes, elle calcule uniquement les nouvelles dérivations avec stable = false

Jointures incrémentales et merge join

  • Une jointure est bilinéaire et se décompose donc comme suit
    • (A + a) ⋈ (B + b) = A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
  • Il n’est pas nécessaire de recalculer A ⋈ B, déjà produit entre éléments stables
  • Si l’on ne veut que les nouvelles dérivations, il suffit d’effectuer trois jointures
    • A ⋈ b
    • a ⋈ B
    • a ⋈ b
  • join_with inclut ou exclut la jointure stable-stable selon le flag stable
  • La véritable opération join est un merge join qui parcourt séquentiellement deux entrées triées
    • Lorsque les clés sont identiques, elle appelle action sur toutes les combinaisons correspondant à cette clé
    • Lorsque les clés diffèrent, elle utilise gallop pour sauter rapidement jusqu’au prochain point de correspondance possible
  • gallop est une idée reprise d’EmptyHeaded : on avance exponentiellement tant qu’une condition monotone est vraie, puis on resserre la recherche par dichotomie

Expérience d’analyse de nullability

  • Les données expérimentales proviennent du projet Graspan et sont encore disponibles sur Google Drive
  • L’entrée de l’analyse de dataflow comporte deux relations, e et n
    • n(?a, ?b) : la valeur ?a peut être utilisée à l’emplacement ?b
    • e(?a, ?b) : la valeur d’un emplacement ?a peut être déplacée vers un autre emplacement ?b
  • La règle de reachability est la suivante
    • n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
  • Sur l’entrée httpd, la commande initiale .list affiche
    • e : 9 905 624
    • n : 138 331
  • L’exécution directe de la règle prend environ 15 secondes, et n atteint 9 393 283 éléments
  • L’une des raisons de cette lenteur est que la relation temporaire .temp-0-0-in, qui réorganise n selon la clé de jointure, grossit jusqu’à 9 393 283 éléments
  • Les performances s’améliorent si l’utilisateur réécrit la règle
    • m(?loc, ?val) :- n(?val, ?loc) .
    • m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
  • Sur la même entrée httpd, après réécriture, la deuxième règle s’exécute en environ 8,43 secondes
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 8.43s 24.33s 55.01s
datafrog 1.30s 4.06s 8.03s
  • Le chiffre Graspan pour lnx_kernel est marqué d’un * : l’article rapportait le temps total, et des collisions d’identifiants d’entrée rendent difficile de le considérer comme exactement la même exécution
  • Pour une comparaison avec les outils utilisés en pratique, Soufflé pourrait être une cible plus pertinente

Analyse d’aliasing et optimisation manuelle

  • La deuxième analyse correspond à l’analyse d’aliasing de Zheng et Rugina, reprise par Graspan
  • Il y a deux relations d’entrée
    • A(?val, ?loc) : ?loc <- ?val
    • D(?val, ?loc) : ?loc est utilisé sous la forme *?val
  • L’objectif est de calculer les alias mémoire et les alias de valeur
    • Alias mémoire : deux expressions lvalue peuvent pointer vers le même emplacement mémoire
    • Alias de valeur : deux expressions peuvent s’évaluer au même pointeur
  • La notation de l’article fait apparaître ^T, ^? et ^*
    • ^T : transposée de relation
    • ^? : terme optionnel
    • ^* : répétition zéro ou plusieurs fois
  • En Datalog, ^? est exprimé en séparant la règle en deux, tandis que ^* est traité en ajoutant explicitement la relation identité
  • L’exécution initiale des règles est longue
    • Après l’entrée des deux dernières règles d’initialisation d’identité, elle prend 686,57 secondes puis 736,34 secondes
    • Le processus utilise 50,13 Go
    • V : 361 947 256
    • M : 92 806 768
    • F : 2 669 647
  • En utilisant explicitement les relations transposées -V, -M, -a et -d, on élimine les relations temporaires -in
    • Total : 815,92 secondes, soit environ 13,6 minutes
    • Mémoire : 31,96 Go
  • L’approche de Zheng et Rugina étant demand-driven et, en pratique, seul M étant nécessaire, V est inliné dans M
    • Les 361 947 256 éléments de -V ne sont pas générés
    • La mémoire tombe à 18,96 Go
  • Le fragment de jointure répété est nommé Fd pour être réutilisé, puis Fd est calculé directement à la place de F, ce qui réduit aussi le problème lié à l’identité
  • La forme finale, qui introduit la relation intermédiaire MFd, donne les résultats suivants
    • Temps d’exécution : 119,34 secondes
    • Mémoire : 5,32 Go
    • -M : 92 806 768
    • Fd : 1 858 986
    • MFd : 73 474 947
  • La seule réécriture manuelle améliore presque d’un facteur 10 la mémoire et le temps d’exécution par rapport à la première tentative
  • Créer des résultats intermédiaires nommés permet, dans une certaine mesure, de construire soi-même le bushy-tree join plan souhaité, mais si l’on nomme une relation dont on n’a pas réellement besoin, comme V, elle sera produite à grand coût

Requêtes demand-driven et magic sets

  • Une requête demand-driven consiste à n’explorer que les parties nécessaires à un fait cible précis
  • Les magic sets peuvent servir de solution approximative
    • Il s’agit d’une transformation qui intègre le littéral cible dans la requête
    • On peut imaginer une formulation qui ne part pas de tous les d, mais seulement des d qui nous intéressent ; appliquée naïvement, toutefois, elle peut être incorrecte
  • Les magic sets ne constituent pas la réponse optimale, et l’auteur prévoit de lire davantage d’articles connexes pour trouver une approche potentiellement plus efficace
  • Les liens associés sont les suivants

Optimisation des plans de jointure et IR data-parallel

  • L’intérêt de Datalog réside moins dans les clauses de Horn elles-mêmes que dans le fait qu’il met clairement en évidence le problème central du calcul data-parallel : le data rendezvous
  • La règle h(x, y, z) :- b1(x, y), b2(y, z) . peut être vue comme le problème consistant à rassembler en un même endroit les x et z associés à chaque y
  • L’opération de base du calcul data-parallel consiste à regrouper les enregistrements par clé pour les transmettre à la logique utilisateur, et la jointure exprime une forme de routage sélectif
  • Un IR simple utilise les opcodes suivants
    • Var(String) : collection nommée
    • Map(Action) : filtre, permutation, projection
    • Key(usize) : marque les premières colonnes comme clé
    • Mul(usize) : combine plusieurs collections ayant la même longueur de clé
  • Par la suite, Map et Key sont fusionnés dans Action.key_arity
  • Action contient des filtres sur littéraux, des filtres d’égalité entre variables, une projection et la key arity
  • Le point de départ le plus simple consiste à effectuer le cross join de tous les atomes du corps, puis à ajouter un filtre et une projection pour chaque tête ; cela produit bien la bonne réponse, mais les performances sont très mauvaises

Optimisation basée sur les e-graphs

  • L’optimisation utilise les e-graphs et l’equality saturation
  • Les ressources de référence utilisées sont la page web d’egg, un article précédent et egg
  • Le term graph est représenté comme une map de ENode<T> associés à des Id, et partage les nœuds identiques afin de représenter le programme plus concisément
  • Trois règles d’e-graph ont été appliquées
    • MulPermute : rend équivalentes les permutations des entrées de Mul(k)
    • MulPartition : rend équivalentes plusieurs façons de découper Mul(k)
    • MapPushdown : pousse Map sous Mul(2) afin de produire une forme de jointure avec clés
  • La règle d’exemple est la suivante
    • head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
  • Après l’equality saturation, des coûts sont attribués lors de l’étape d’extraction
    • Le coût de Map est le nombre de colonnes en sortie
    • Le coût de Mul est la somme du nombre de colonnes clés et du nombre de colonnes non clés des entrées
    • Le coût de Var est 0
    • En cas d’égalité, on minimise le nombre de Map, puis le nombre de Mul
  • Dans l’exemple, le plan choisi est trouvé dans la wave two, avec au plus deux colonnes non corrélées
    • Un map sur les entrées a et b
    • Une jointure
    • Une projection intermédiaire
    • Une jointure avec lui-même
    • Une projection finale
  • Cette recherche de plan prend environ 40 ms même en release build, et la majeure partie du temps est consacrée à l’equivalence saturation

Mise à jour de l’exécution des plans optimisés

  • La mise à jour du 2025-06-29 a implémenté l’exécution des plans optimisés
  • Le plan sort sous forme de Vec<ENode<Op>>, mais l’exécution réelle n’exécute pas chaque nœud indépendamment
  • Le mode d’exécution prévu est le suivant
    • Pour chaque Var, appliquer plusieurs Map dépendants lors d’un seul scan de la collection externe
    • Pour chaque Mul, appliquer plusieurs Map dépendants lors d’un seul scan de jointure
  • Op::Map(action) est davantage une tâche mise en file d’attente sur une opération dépendante qu’une opération exécutée directement
  • Pour cela, TempAction est introduit
    • Filtre sur les littéraux
    • Filtre d’égalité entre variables
    • Projection pouvant contenir une référence de colonne ou un littéral chaîne
  • L’étape de préparation du plan d’exécution sépare le body et la head, puis regroupe les actions Map par nœud d’entrée
  • Lors de l’exécution de Var, le traitement des noms se divise en trois cas
    • La génération de head utilise le nom de la relation head
    • La transformation identity réutilise le nom d’entrée existant
    • Les transformations non triviales sont stockées sous des noms temporaires .temp-*
  • L’exécution de Mul(2) vérifie la key arity et les noms des deux entrées, puis appelle join_with pour accumuler les résultats dans plusieurs builders
  • Sur un exemple complexe d’aliasing, l’exécution du plan optimisé prend 114,28 s, soit environ 5 s de moins que les plus de 119 s précédentes, mais la raison n’est pas claire
  • L’optimisation multi-rule n’est pas encore implémentée, et il pourrait même être nécessaire de repenser l’approche par plans

Optimisation de la représentation des faits

  • La mémoire est passée de 50 Go à 5 Go, mais elle reste considérée comme environ 10 fois supérieure au nécessaire
  • La plus grande layer de la grande relation -M contient 57 289 225 faits et utilise environ 2 098 253 766 octets
    • Bornes des faits : 458 313 800 octets
    • Bornes des terms : 916 627 600 octets
    • Données d’octets réelles : 723 312 366 octets
  • La première optimisation exploite le fait que l’arity est constante
    • Si tous les faits ont 2 colonnes, les bornes des faits peuvent être représentées uniquement par un stride et une longueur
    • Les quelque 458 Mo de données de bornes sont ainsi quasiment éliminés
  • La deuxième optimisation consiste à rendre la longueur des terms identique
    • Si les nombres sont convertis en chaînes à largeur fixe de 7 chiffres, les bornes des terms peuvent aussi être représentées par un stride et une longueur
    • En contrepartie, le nombre réel d’octets peut augmenter
  • La troisième optimisation consiste à représenter les nombres en binaire plutôt qu’en texte
    • Un nombre à 7 chiffres tient dans un u32 de 4 octets
    • Il tient aussi dans 3 octets, ce qui donne 57,289,225 × 2 × 3 = 343,735,350 octets
    • On passe d’environ 2 Go à environ 350 Mo, soit une réduction d’environ 6,10 fois
  • Compresser la répétition du premier term réduit encore davantage la taille
    • Il y a 57 289 225 faits, mais seulement 1 147 612 premiers terms distincts
    • En stockant sous la forme (Term, [Term]) au lieu de (Term, Term), la plus grande layer descend à environ 184 491 407 octets
    • Cela représente une réduction d’environ 11,37 fois par rapport aux 2 Go initiaux
  • Dans la mise à jour du 2025-07-02, la première optimisation a été appliquée
    • Le plus grand batch atteint 343 735 382 octets, soit la valeur théorique de 343 735 350 octets plus 32 octets
    • Le temps d’exécution passe d’environ 115 s à environ 95 s, soit une amélioration d’environ 20 %

Représentation en layered trie

  • Dans la mise à jour du 2025-07-20, le layered trie est devenu fonctionnel
  • Comparaison entre la représentation row-oriented et la représentation layered trie column-oriented
    • toad-row
    • toad-col
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
toad-row 3.88s 11.30s 25.67s
toad-col 3.47s 11.94s 23.09s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
toad-row 28.21s 28.25s 7.62s
toad-col 19.39s 21.96s 9.48s
datafrog UNK UNK UNK
  • Le layered trie supprime les répétitions des premières colonnes dans une représentation en lignes triées
  • Chaque colonne est une liste de listes de valeurs
    • Chaque liste correspond à une liste triée de valeurs distinctes pour le préfixe de la colonne précédente
    • Le nombre de listes d’une colonne est égal au nombre total d’items de la colonne précédente
  • On peut le voir comme un trie, mais l’implémentation réelle reste organisée en colonnes
  • Son avantage est de permettre recherche, jointure, différence et fusion au niveau des préfixes
  • Quand il y a très peu de valeurs distinctes et qu’il est préférable de consulter une ligne entière d’un coup, une approche row-oriented peut être plus avantageuse
  • Le trait FactContainer est introduit comme abstraction commune
    • form
    • len
    • apply
    • join
    • except
    • merge
  • apply utilise une stack explicite plutôt que la récursion pour suivre les ranges de chaque layer, construire les lignes et les transmettre à l’action
  • align est un helper commun qui aligne les préfixes de deux layered tries
    • Ordering::Less : range présent uniquement dans self
    • Ordering::Greater : range présent uniquement dans other
    • Ordering::Equal : préfixe de longueur arity commun aux deux côtés
  • join, except et merge sont tous implémentés au-dessus de align
    • join déplie les extensions restantes à partir du préfixe commun et effectue un cross join
    • except greffe dans TrieBuilder les ranges présents uniquement dans self
    • merge greffe une seule fois, comme il convient, les ranges self-only, other-only et equal

Optimisation à largeur fixe et performances

  • Lorsque l’on peut passer à une largeur fixe [u8; 4], les performances de comparaison s’améliorent fortement
  • Le layered trie permet d’appliquer l’optimisation à largeur fixe colonne par colonne, ce qui pourrait le rendre plus avantageux que le row à long terme
  • except et merge ont facilement pu appliquer upgrade/downgrade, mais l’application à join a été plus difficile en raison de problèmes de types Rust
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
toad-row 3.88s 11.30s 25.67s
^-- +opt 3.11s 9.49s 19.83s
toad-col 3.47s 11.94s 23.09s
^-- +opt 2.55s 9.13s 15.95s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
toad-row 28.21s 28.25s 7.62s
^-- +opt 23.31s 23.08s 6.73s
toad-col 19.39s 21.96s 9.48s
^-- +opt 14.26s 16.45s 8.33s
datafrog UNK UNK UNK
  • Environ 2/3 du temps actuel sont passés sous join
  • Il estime qu’il reste au moins une marge d’optimisation supplémentaire d’environ 2× pour les jointures
  • Une tentative consistant simplement à réordonner l’inner loop n’a pas produit d’amélioration mesurable

Spécialisation au niveau du code compilé

  • Lorsqu’on détecte des termes de même longueur et des faits de même arité, on peut voir un Vec<u8> comme un Vec<[[u8; B]; T]>
  • Cette forme permet à Rust de mieux connaître la forme des données, réduit le coût des vérifications de bounds et de longueur, et rend les comparaisons particulièrement peu coûteuses
  • Les comparaisons sont utilisées à plusieurs endroits dans datatoad
    • Tri et déduplication des batchs de faits
    • Fusion des batchs
    • Fusion des clés de jointure
    • Filtrage des nouveaux faits en les comparant aux faits existants
  • Les performances de référence sont les suivantes
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 7.44s 17.26s 42.25s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
datatoad 101.24s 96.36s 20.20s
datafrog UNK UNK UNK
  • L’optimisation du tri a été expérimentée en effectuant un transmute unsafe de Vec<u8> vers Vec<[u8; 8]> pour faire sort·dedup
dataflow httpd psql lnx_kernel
dt-orig 7.44s 17.26s 42.25s
dt-sort 4.99s 13.55s 32.15s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
dt-orig 101.24s 96.36s 20.20s
dt-sort 52.99s 53.19s 11.20s
datafrog UNK UNK UNK
  • L’optimisation de la fusion est implémentée de façon simple, en concaténant les deux entrées puis en appliquant sort·dedup
dataflow httpd psql lnx_kernel
dt-orig 7.44s 17.26s 42.25s
dt-sort 4.99s 13.55s 32.15s
dt-both 3.71s 11.23s 23.58s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
dt-orig 101.24s 96.36s 20.20s
dt-sort 52.99s 53.19s 11.20s
dt-both 31.32s 30.08s 8.56s
datafrog UNK UNK UNK
  • Les performances compilées de datafrog ne sont pas encore atteintes
  • Le coût de comparaison restant se trouve aussi dans join et antijoin, et il prévoit de revisiter les mêmes opportunités d’optimisation en migrant vers une structure basée sur des tries
  • Il cherche un moyen d’éliminer unsafe, et ajoute en conclusion qu’il faut éviter le code unsafe

Travail restant

  • Spill sur disque

    • Le stockage columnar est constitué d’un petit nombre de grosses allocations
    • Lors de la création, il peut être écrit dans un fichier plutôt qu’en mémoire, puis réutilisé via memory map

  • Évaluation distribuée

    • Les jointures, la déduplication et les distinctness checks reposent sur l’égalité des clés
    • Les clés et les données correspondantes peuvent être réparties entre plusieurs workers
    • timely_communication permet d’étendre cela à plusieurs processus

  • Évaluation de règles en streaming

    • Les jointures actuelles utilisent des jointures binaires et une sortie matérialisée
    • S’il existe les index nécessaires, il est possible de construire un plan qui ne matérialise pas l’état interne
    • Les worst-case optimal joins seront aussi traités ici

  • Spécialisation par custom representation

    • Il existe une idée consistant à détecter une transitive closure et à se spécialiser pour une strongly connected component decomposition
    • Une equivalence relation peut utiliser une structure de données union-find
    • bddbddb et les factorized databases sont également abordés comme sujets connexes

  • Recherche de faits pertinents

    • Il faut comprendre et appliquer le demand transform
    • Il est considéré comme une transformation nécessaire pour l’exploration interactive de Datalog

À lire aussi

1 commentaires

 
GN⁺ 2025-06-16
Avis sur Hacker News

  • C’est amusant de voir cet article arriver en tête
    Je suis justement en train de créer un jeu de stratégie en temps réel avec Differential Datalog et Rust, en laissant DDL gérer la logique du jeu
    Pour l’essentiel, c’est plutôt une excuse pour découvrir de nouvelles idées et me lancer dans un yak shaving sans fin
    https://github.com/vmware-archive/differential-datalog

    • Ça ressemble à une super démo réalisée avec ddlog
      À noter que l’équipe ddlog a depuis fondé Feldera, et qu’utiliser DBSP directement depuis Rust peut aussi valoir le coup
      https://github.com/feldera/feldera
    • Je me demande si, en mélangeant le dépôt de l’article original avec salsa, le crate qui fait tourner l’analyseur Rust, on pourrait créer une sorte de differential datalog à la Frankenstein
      https://github.com/salsa-rs/salsa
    • Je me demande où en est l’implémentation, et jusqu’où elle pourra aller
      DDLog n’étant plus activement maintenu, c’est d’autant plus intéressant

  • « Moi, le méchant notoire, j’ai été invité en étant à moitié convaincu que j’allais recevoir le châtiment que je méritais depuis longtemps. » — la meilleure première phrase d’un billet de blog technique que j’ai lue cette année
    Les apartés du narrateur étaient excellents aussi, et il est rare de lire un texte aussi profond techniquement tout en restant aussi plaisant
    Le parcours d’optimisation des requêtes d’alias ressemblait à un roman policier, et le lecteur gémit lui aussi devant les 50 Go d’utilisation mémoire, puis exulte quand ça tombe à 5 Go
    Le code comme le texte sont excellents

  • J’ai un peu avancé sur le portage de mangle datalog vers Rust
    Il se trouve dans https://github.com/google/mangle/tree/main/rust, dans le même dépôt que l’implémentation Go
    Ce n’est pas très prioritaire, et il y a aussi un peu de syndrome du deuxième système, donc ça progresse lentement
    Mangle Rust s’oriente vers la lecture et l’écriture de faits sur disque via memory mapping, pour manipuler des données de taille arbitraire, tandis que l’implémentation Go fonctionne en mémoire
    Cet article est appréciable parce qu’il traite à la fois du parsing de Datalog et des arbres LSM, et il est bien plus facile à suivre que les ressources sur datafrog
    En Rust, beaucoup d’implémentations Datalog comme ascent ou crepe utilisent des macros procédurales, mais elles ont l’inconvénient de rendre difficile la réception de requêtes à l’exécution
    Pour des usages d’analyse statique où les requêtes et le programme sont fixes, l’approche par macros procédurales peut toutefois être préférable

  • Même si la renaissance de Datalog actuelle semble s’essouffler, il est réjouissant de voir le noyau de passionnés tenir bon
    La récente conférence Datalog 2.0 était nettement plus petite qu’avant, et la deuxième conférence HYTRADBOI comportait aussi moins de Datalog
    Lors de la première HYTRADBOI, un quart des soumissions étaient liées à Datalog
    Il est aussi encourageant de voir d’autres personnes partager des projets Datalog récents
    En ce moment, je prépare une migration logicielle à grande échelle en construisant un pipeline de qualité des données pour une base SQL legacy
    Quand les requêtes sont bien structurées, elles deviennent très lisibles, et je trouve Datalog bien plus utile que SQL pour identifier et localiser les problèmes de qualité des données

    • Même si je suis d’accord avec la tendance générale, il est difficile de faire du faible nombre de participants à Datalog 2.0 un exemple représentatif du déclin de Datalog
      Datalog 2.0 est un workshop satellite de LPNMR, une conférence européenne relativement peu connue, qui se trouvait par hasard organisée à Dallas
      Même en y assistant en personne, l’événement m’a semblé assez clairsemé, et bien que j’aie soumis un article au workshop, je n’y ai pas vu beaucoup de personnes du domaine
      Exception notable : les Européens venus présenter le solveur Nemo étaient bien visibles
      À mon avis, le faible nombre de participants cette année montre surtout qu’il s’agissait d’un workshop satellite d’une conférence déjà peu prestigieuse, et que l’événement principal était ICLP, plutôt qu’un manque d’intérêt pour les implémentations de Datalog
      Bien sûr, je ne cherche pas à contester l’argument général selon lequel il reste peu de nouveauté dans l’implémentation de moteurs Datalog purs
      L’espace de recherche est déjà allé bien plus loin, vers des problèmes plus exotiques comme le streaming (HydroFlow), le choix (Dusa) ou des choses plus proches du chase général (le moteur de chase d’Egglog)
      Il y a globalement consensus sur le fait que le Datalog vanilla est ennuyeux, mais la saturation avant monotone et les clauses de Horn constituent une base riche et bien comprise du point de vue de l’ingénierie des performances, sur laquelle il est intéressant de bâtir des théories plus stimulantes comme les semi-anneaux ou les Z-set

  • Si les parties sur les machines à états et le parsing vous ont intéressé, je recommande aussi l’ancienne présentation de Rob Pike, Lexical Scanning in Go
    https://www.youtube.com/watch?v=HxaD_trXwRE
    C’est en Go, mais l’essentiel s’applique facilement à d’autres langages
    C’est agréable que des langages modernes comme Rust, Zig et Go prennent en charge nativement Unicode/rune/graphème
    Par rapport à Java, .NET, C++ ou aux langages de script, beaucoup de problèmes disparaissent tout simplement

  • J’aime globalement le travail de l’auteur sur Datalog, mais j’aimerais qu’on n’enseigne pas les jointures binaires dans les ressources d’introduction
    Dès qu’on sort du cas idéal, l’intérieur devient vite désordonné, et les méthodes de jointure générales me semblaient bien plus faciles à généraliser mentalement
    https://en.wikipedia.org/wiki/Worst-case_optimal_join_algorithm

  • Il y a longtemps, pendant mes études, j’ai un peu touché à Prolog, et je vois à peu près à quoi cela sert et en quoi c’est utile, sans l’avoir compris en profondeur.
    Depuis, j’entends constamment dire que Datalog est formidable, mais je n’arrive pas vraiment à cerner ce que Datalog améliore par rapport à Prolog.
    Je viens de parcourir la page Wikipedia de Datalog : Prolog semble avoir des performances relativement mauvaises, tandis que Datalog réduirait l’expressivité et les fonctionnalités en échange d’un net gain de performance, rendant possibles de plus gros jeux de données et des traitements plus parallélisés.
    Il semble aussi que cela inclue la perte de la complétude de Turing ; je me demande si c’est là le point essentiel ou si je fais complètement fausse route.

    • D’après ce que j’en sais, Prolog ressemble à un langage déclaratif où il suffit d’encoder les relations pour obtenir des réponses, mais en pratique il dépend beaucoup de l’ordre des règles et nécessite aussi des directives supplémentaires comme le « cut ».
      Le cut ne sert pas seulement à éviter des calculs inutiles : il peut aussi influer sur le résultat.
      Datalog, en revanche, ressemble globalement davantage à une base de données relationnelle avec une syntaxe différente.
    • Datalog est plus simple, n’est pas Turing-complet et, si je me souviens bien, utilise le chaînage avant, ce qui a des effets en cascade sur les performances et les caractéristiques mémoire.
      Un espace de recherche trivialement énorme en Prolog peut, en Datalog, consommer tellement de mémoire qu’il devient impossible à exprimer.
      Datalog est une voiture de banlieue à CVT, tandis que Prolog se rapproche d’une F1.
      Plutôt qu’une amélioration, c’est davantage une version partiellement élaguée de Prolog pour éviter que les gens ne se tirent une balle dans le pied, et c’est aussi beaucoup plus facile à implémenter et à embarquer dans d’autres applications.
      Si vous êtes habitué à Prolog, Datalog vous semblera globalement frustrant.
      Il n’y a pas de call/3, pas de term/goal expansion, et Datalog est en gros conçu comme un plus petit dénominateur commun des fonctionnalités de Prolog, destiné à la recherche interactive dans des bases de données.
      Il est facile d’écrire du code Datalog rapide, mais le plafond est aussi bien plus bas.
      Prolog peut lui aussi être écrit de manière à autoriser la concurrence, mais c’est une tâche de niveau intermédiaire qui demande de comprendre l’implémentation.
      Les Guarded Horn Clauses et les langages qui en dérivent ont été développés pour formaliser cet aspect, mais les évolutions japonaises postérieures à Prolog sont très ardues.
      Les performances de Prolog dépendent fortement du programmeur, de l’implémentation utilisée et du contexte d’utilisation.
      Comme Lisp, Prolog peut servir à générer du code machine natif depuis un DSL au moment de la compilation.
      Si l’on comprend comment fonctionne l’implémentation sous-jacente et que l’on écrit le code dans ce sens, il peut être suffisamment rapide.
      Mais pour cela, il faut écrire du code Prolog pendant des années avec une même implémentation.
      Il existe aussi beaucoup de travaux de recherche sur l’optimisation des compilateurs Prolog, ainsi que des implémentations propriétaires.
      http://logicprogramming.stanford.edu/readings/ullman.pdf
      https://www.ueda.info.waseda.ac.jp/AITEC_ICOT_ARCHIVES/ICOT/Museum/IFS/abst/078.html
      https://www.sciencedirect.com/science/article/pii/S0743106696889813
      https://link.springer.com/content/pdf/10.1007/3-540-18024-9_26.pdf
      https://sicstus.sics.se/

  • Si vous voulez utiliser Datalog et Rust, cozodb est écrit en Rust et propose aussi une syntaxe de requête Datalog.

    • Cozodb a l’air intéressant, mais semble presque inactif.
      Vers novembre 2024, en l’examinant, j’ai trouvé quelques améliorations faciles dans le backend de stockage SQLite.
      https://github.com/cozodb/cozo/issues/285
    • Cozodb fonctionnait globalement bien conformément à la documentation, et il était agréable de travailler avec.
      Je l’ai aussi utilisé pour de l’analyse statique de programmes ; en interne, il utilise des arbres triés et des techniques de typage.
      La documentation est suffisamment complète pour être comparée aux explications pas à pas du blog, et le travail d’optimisation des requêtes est particulièrement intéressant.
      En revanche, si l’on ne travaille pas en mémoire depuis Rust, le coût de sérialisation des données est élevé, et le projet est, au mieux, discret.

  • Je me souviens qu’autrefois, les fans de Clojure disaient que Datalog était meilleur que SQL, et qu’il était regrettable que les bases de données relationnelles utilisent toutes SQL.
    Je n’ai jamais vraiment creusé suffisamment pour comprendre pourquoi ils pensaient cela.

    • Fondamentalement, Datalog est beaucoup moins verbeux que SQL, le coût de séparation des vues y est bien plus faible, et il prend en charge la fermeture transitive de façon écrasante.
      http://canonical.org/~kragen/binary-relations commence par une simple requête non récursive, mais la traduction SQL est déjà criminelle, et une solution SQL correctement séparée mériterait la peine de mort.
      Des fonctionnalités récursives ont récemment été ajoutées à ANSI SQL, donc ce n’est plus totalement impossible, mais il reste trois gros inconvénients.
      Premièrement, on a rendu SQL accidentellement Turing-complet, alors qu’à l’inverse les requêtes Datalog sont garanties de terminer.
      Deuxièmement, cela reste terriblement lourd à utiliser.
      Troisièmement, à cause du premier point, c’est souvent implémenté de façon incomplète, ce qui le rend difficile à utiliser en toute confiance.
    • Le dialecte Clojure/Datomic est difficile à comprendre, mais je suis d’accord avec la direction générale.
      Pour essayer Datalog en ligne dans un environnement notebook convivial, je recommande Percival.
      https://percival.ink/
      Il n’existe pas, pour les implémentations Datalog en général, de standard équivalent à « ANSI SQL », mais une fois les idées fondamentales assimilées, les autres Datalog ne sont pas très difficiles non plus.
      J’ai aussi commencé un fork de Percival qui compile Datalog vers SQLite ; si vous voulez voir comment les deux expriment la même chose, vous pouvez y jeter un œil.
      https://percival.jake.tl/
      Les agrégations et les jointures plus avancées ne sont pas encore terminées, mais la forme de base fonctionne bien.
      Logica est un compilateur Datalog→SQL bien plus sérieux et abouti, créé par un chercheur de Google ; il compile vers BigTable, DuckDB et quelques dialectes SQL.
      https://logica.dev/
      Le domaine où Datalog devient plus facile de plus d’un ordre de grandeur, c’est celui des requêtes/règles récursives.
      C’est possible aussi en SQL, mais cela donne plutôt l’impression d’aspirer de la pâte à modeler avec une paille.
      Chez Materialize.com, Frank propose une forme SQL « WITH MUTUALLY RECURSIVE », nettement meilleure que l’ancienne approche récursive ANSI SQL, et Notion l’évalue pour les requêtes de chargement de pages et la synchronisation de données.
      https://materialize.com/blog/recursion-in-materialize/
      Feldera propose aussi une forme similaire pour les vues récursives.
      https://www.feldera.com/blog/recursive-sql-queries-in-feldera
      J’aime le fait que Feldera permette de créer chaque « règle » ou sous-vue comme une instruction séparée, plutôt que de tout mettre dans une seule énorme instruction.
      Le principal inconvénient que j’ai observé en testant est que le dialecte SQL de Feldera hérite d’un certain nombre de contraintes d’Apache Calcite, tandis que le dialecte SQL de Materialize s’efforce très fortement d’être compatible avec PostgreSQL.

  • Un nouvel article de McSharry, excellent.
    La dernière fois que j’ai vérifié, VMWare semblait s’être éloigné de differential datalog.

    • L’équipe de Differential Datalog a fondé Feldera.
      https://www.feldera.com/
      Ils semblent être passés de differential Datalog à differential SQL ; à mon avis, c’est probablement parce qu’ils ont compris que Datalog est vraiment difficile à vendre.