Einen interaktiven Datalog-Engine mit Rust bauen

 (github.com/frankmcsherry)
1 Punkte von GN⁺ 2025-06-16 | 1 Kommentare | Auf WhatsApp teilen
  • Ausgehend von den im Workshop für logische Programmierung sichtbar gewordenen Grenzen bei Nutzbarkeit und Performance von Datalog-Tools begann das Experiment datatoad, einer Rust-basierten interaktiven Datalog-Shell
  • datatoad zielt auf eine Struktur, in der sich während der Laufzeit Regeln hinzufügen und fortlaufend neue Fakten ableiten lassen, und senkt mit columnar-Speicherung und LSM-Schichten die Kosten für die Deduplizierung von Faktmengen
  • Die Regelauswertung verarbeitet Datalog-Bodies, indem sie sie in Join-Probleme umwandelt, und trennt je nach stable-Status zwischen vollständiger Auswertung und inkrementeller Auswertung, um bereits berechnete stable-stable-Joins zu vermeiden
  • In Experimenten mit dem Graspan-Datensatz sank die Alias-Analyse allein durch manuelles Umschreiben von Regeln und die Einführung von Zwischenrelationen von 736,34 Sekunden und 50,13 GB auf 119,34 Sekunden und 5,32 GB
  • Weitere Arbeiten führen zu e-graph-basierter Join-Plan-Optimierung, layered trie, Byte-Repräsentationen mit fester Breite, Disk-Spill, verteilter Auswertung, Streaming-Joins und demand transform

Das Problem, das datatoad lösen will

  • Beim Workshop für logische Programmierung am Memorial-Day-Wochenende traten die Unbequemlichkeiten von Datalog-Tools für Programmanalyse deutlich hervor; das war der Ausgangspunkt für den Versuch einer einfachen, brauchbaren und schnellen Datalog-Implementierung
  • Das Ziel der Implementierung ist kein statischer Beispiel-Runner, sondern eine interaktive Datalog-Shell
    • Sie kann große Mengen an Fakten laden
    • Sie kann während der Laufzeit neue Regeln hinzufügen
    • Sie spiegelt die Ergebnisse hinzugefügter Regeln fortlaufend in den bestehenden Zustand ein
  • Der Code lässt sich im datatoad repository nachvollziehen
  • Das bestehende datafrog liefert die Kernalgorithmen einer Datalog-Engine, erfordert aber direkte Verdrahtung durch den Nutzer; datatoad organisiert dieselben Ideen daher in einer leichter nutzbaren Form neu
  • Im Nullability-Beispiel des httpd-Dataflow-Graphen benötigte datatoad mit Vec<String>-Daten und nicht kompilierten Abfragen 8,3 Sekunden und war damit rund viermal langsamer als das datafrog-Beispiel mit (u32, u32)-Daten, das etwa 2 Sekunden brauchte
  • Beim Reachability-Problem erzeugte es dieselbe Zahl an Ausgabe-Tupeln wie die datafrog-Implementierung, eine allgemeine Korrektheitsprüfung ist jedoch noch nicht abgeschlossen

Datalog-Modell und Shell-Struktur

  • Datalog ist eine Sprache, in der man einfache logische Regeln schreibt und daraus alle durch diese Regeln erreichbaren Fakten ableitet
  • Regeln bestehen aus Head und Body
    • Beispiel: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
    • tri und edge sind Relationen, a, b, c sind Variablen
    • Variablen, die im Head vorkommen, müssen auch im Body stehen
  • Fakten werden als Regeln mit leerem Body behandelt
    • Beispiel: edge(1, 2) :- .
    • Mit mehreren Heads lassen sich mehrere Fakten gleichzeitig schreiben
  • Aufgrund der Monotonie von Datalog wird die Menge wahrer Fakten durch das Hinzufügen von Regeln oder Fakten nicht kleiner, und dieselbe Eingabemenge an Regeln erreicht unabhängig von der Regelreihenfolge dasselbe Ergebnis
  • Im Rust-Modell stehen drei Strukturen im Zentrum: Rule, Atom, Term
    • Rule { head: Vec<Atom>, body: Vec<Atom> }
    • Atom { name: String, terms: Vec<Term> }
    • Term::Var(String) oder Term::Lit(String)
  • Für die Speicherung von Literalen wird statt String Vec<u8> verwendet
    • Benötigt werden nur Literal-Gleichheit und eine beliebige Sortierreihenfolge
    • Ob die Bytes String, (u32, u32) oder eine andere Bedeutung haben, bleibt dem Nutzer überlassen
  • Der Interpreter-Zustand speichert Regeln und Fakten gemeinsam
    • rules: Vec<Rule>
    • facts: facts::Facts
  • Wenn die Shell eine Eingabezeile als Datalog parst, ruft sie State::extend und State::update auf und gibt mit dem Befehl .list jeden Relationsnamen und die Zahl seiner Fakten aus

Parsing und Faktenspeicherung

  • Der Parser befindet sich in parse.rs und verwendet eine aus der Soufflé-Grammatik übernommene Form
  • Variablen beginnen mit ?
  • Tokens sind auf ., ,, (, ), :-, ? beschränkt; übriger Text wird als Atom- oder Term-Name behandelt
  • Der Tokenizer entfernt Leerraum und ersetzt :- durch ←, um es wie ein einzelnes Symbol zu scannen
  • Das Parsen von Regeln liest Head-Atome bis zum Turnstile und Body-Atome bis zum Punkt
    • Ein Atom besteht aus Name, linker Klammer, Term-Liste und rechter Klammer
    • Ein Term ist mit ? eine Variable, sonst ein Literal
  • Ungültige Regeln geben None zurück; derzeit wird nicht genauer erklärt, welcher Teil falsch ist
  • Um Negationsregeln hinzuzufügen, wäre ein Exclamation-Token nötig, das bisher aber nicht behandelt wird

Lebenszyklus der Faktmenge

  • Eine einfache Speicherung als Vec<Vec<String>> führt zu verschachtelten Allokationen und ist daher ungünstig für das Speichermanagement
  • datatoad nutzt columnar, um Rust-Typen in ein flaches Layout mit wenigen linearen Allokationen zu transformieren
    • String-Bytes, String-Grenzen und Faktgrenzen werden in separaten Arrays gespeichert
  • FactContainer kapselt eine sortierte und deduplizierte Liste von Fakten; der Wrapper-Typ signalisiert die Invarianten von Sortierung und Deduplizierung
  • Da der spaltenorientierte Container faktisch append-only ist und sich nicht für Änderungen in der Mitte eignet, verwendet das Hinzufügen neuer Fakten eine log-structured merge-tree (LSM)-Form
    • FactLSM { layers: Vec<FactContainer> }
    • Die Schichtgrößen werden so verwaltet, dass sie geometrisch wachsen
    • Schichten mit höchstens doppelter Größe werden zusammengeführt, um Sortierung und Deduplizierung zu erhalten
  • FactBuilder enthält sowohl einen unsortierten, potenziell duplizierten active-Bereich als auch sortierte, deduplizierte layers
  • Die Fakten jeder Relation durchlaufen drei Phasen
    • to_add: neu eingetroffene Fakten, bei denen noch nicht geprüft ist, ob sie novel sind
    • recent: distincte Fakten, die noch verarbeitet werden müssen
    • stable: distincte Fakten, die bereits vollständig verarbeitet wurden
  • FactSet::advance verschiebt recent nach stable und entfernt aus to_add bereits in stable vorhandene Fakten, um ein neues recent zu bilden

Regelauswertung ist ein Join-Problem

  • Der Body einer Datalog-Regel lässt sich als Equi-Join in einer relationalen Datenbank betrachten
  • Das Dreiecksregel-Beispiel lautet wie folgt
    • tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
  • Würde man alle Variablenbelegungen direkt aufzählen, wären es trotz Endlichkeit zu viele; daher wird anhand der Schlüsselspalten gemeinsamer Variablen sortiert und anschließend gemergt
  • Die Implementierung reduziert den Body von rechts nach links
    • Die letzten beiden Relationen werden gejoint, um eine Zwischenrelation zu erzeugen, und anschließend erneut mit der linken Relation gejoint
    • Wenn der Body nur aus einem Atom besteht, wird nur in die Head-Form transformiert
  • JoinPlan enthält folgende Informationen
    • bodys zum Umordnen und Filtern von Body-Atomen für den Join
    • joins mit der Key-Arität jedes Zwischen-Joins und der Ausgabeprojektion
    • heads, die Koordinaten oder Literale für das Einfügen in Head-Atome darstellen
    • die Arität des letzten Head-erzeugenden Joins
  • Der aktuelle Plan ist ein einfacher right-linear join plan
  • Beim Erzeugen von JoinPlan wird anhand der Position des jeweils ersten und letzten Auftretens jeder Variablen entschieden, welche Variablenwerte bis wann erhalten bleiben müssen; dabei werden die Spalten der Body-Atome in dead-, key- und value-Spalten aufgeteilt
  • Die zentrale Funktion ist implement_plan(rule, plan, pos, stable, facts)
    • Wenn eine neue Regel hinzugefügt wird, startet sie mit stable = true über alle Fakten
    • Bei wiederholter Anwendung bestehender Regeln berechnet sie mit stable = false nur neue Ableitungen

Inkrementelle Joins und Merge Join

  • Joins sind bilinear und lassen sich daher wie folgt zerlegen
    • (A + a) ⋈ (B + b) = A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
  • Das bereits zwischen stabilen Relationen gebildete A ⋈ B muss nicht erneut berechnet werden
  • Wenn nur neue Ableitungen benötigt werden, werden nur drei Joins ausgeführt
    • A ⋈ b
    • a ⋈ B
    • a ⋈ b
  • join_with schließt den Stable-Stable-Join je nach stable-Flag ein oder aus
  • Der eigentliche join ist ein Merge Join, der zwei sortierte Eingaben sequentiell durchläuft
    • Wenn die Schlüssel gleich sind, wird action für alle Kombinationen zu diesem Schlüssel aufgerufen
    • Wenn die Schlüssel verschieden sind, wird mit gallop schnell bis zur nächsten möglichen Matching-Position weitergesprungen
  • gallop ist eine von EmptyHeaded übernommene Idee: Solange die monotone Bedingung erfüllt ist, wird exponentiell vorgerückt und danach per binärer Suche eingegrenzt

Experiment zur Nullability-Analyse

  • Die experimentellen Daten stammen aus dem Projekt Graspan und liegen auch noch auf Google Drive
  • Die Eingabe für die Dataflow-Analyse enthält zwei Relationen, e und n
    • n(?a, ?b): Der Wert ?a kann an Position ?b geschrieben werden
    • e(?a, ?b): Der Wert an einer Position ?a kann an eine andere Position ?b weitergegeben werden
  • Die Reachability-Regel lautet wie folgt
    • n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
  • In der httpd-Eingabe zeigt die anfängliche .list Folgendes
    • e: 9,905,624
    • n: 138,331
  • Das direkte Ausführen der Regel dauert etwa 15 Sekunden, und n wächst auf 9,393,283 Einträge an
  • Einer der Gründe für die Langsamkeit ist, dass die nach dem Join-Schlüssel umgeordnete temporäre Relation .temp-0-0-in auf 9,393,283 Einträge anwächst
  • Wenn der Nutzer die Regel umschreibt, verbessert sich die Performance
    • m(?loc, ?val) :- n(?val, ?loc) .
    • m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
  • Mit derselben httpd-Eingabe läuft die zweite Regel nach der Umschreibung in etwa 8.43 Sekunden
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 8.43s 24.33s 55.01s
datafrog 1.30s 4.06s 8.03s
  • Die Graspan-Zahl für lnx_kernel ist mit * markiert; das Paper berichtet die Gesamtzeit zusammen, und wegen Kollisionen bei den Eingabe-Identifikatoren ist es schwer, das als exakt denselben Lauf zu betrachten
  • Für einen Vergleich mit einem in der Praxis verwendeten Tool wäre Soufflé möglicherweise ein geeigneteres Ziel

Aliasing-Analyse und manuelle Optimierung

  • Die zweite Analyse ist die von Zheng und Rugina übernommene Aliasing-Analyse aus Graspan
  • Es gibt zwei Eingaberelationen
    • A(?val, ?loc): ?loc <- ?val
    • D(?val, ?loc): ?loc wird in der Form *?val verwendet
  • Ziel ist es, Memory Alias und Value Alias zu bestimmen
    • Memory Alias: zwei lvalue-Ausdrücke können auf dieselbe Speicherposition verweisen
    • Value Alias: zwei Ausdrücke können zu demselben Pointer-Wert ausgewertet werden
  • In der Notation des Papers kommen ^T, ^? und ^* vor
    • ^T: Transposition der Relation
    • ^?: optionaler Term
    • ^*: Wiederholung ab 0-mal
  • In Datalog wird ^? dargestellt, indem es auf zwei Regeln aufgeteilt wird, und ^*, indem die Identity-Relation explizit eingefügt wird
  • Die Ausführung der anfänglichen Regeln dauert lange
    • Nach Eingabe der letzten beiden Identity-Initialisierungsregeln dauert es 686.57 Sekunden bzw. 736.34 Sekunden
    • Der Prozess verwendet 50.13GB
    • V: 361,947,256
    • M: 92,806,768
    • F: 2,669,647
  • Durch explizite Verwendung der transponierten Relationen -V, -M, -a, -d werden die temporären -in-Relationen entfernt
    • Insgesamt 815.92 Sekunden, also etwa 13.6 Minuten
    • Speicher: 31.96GB
  • Der Ansatz von Zheng und Rugina ist demand-driven, und tatsächlich wird nur M benötigt, daher wird V in M inline eingebettet
    • -V mit 361,947,256 Einträgen wird nicht erzeugt
    • Der Speicher sinkt auf 18.96GB
  • Das wiederkehrende Join-Fragment wird als Fd benannt und wiederverwendet; anschließend wird F direkt statt über Fd berechnet, was auch das Identity-Problem reduziert
  • Die endgültige Form mit der eingeführten Zwischenrelation MFd liefert folgende Ergebnisse
    • Laufzeit: 119.34 Sekunden
    • Speicher: 5.32GB
    • -M: 92,806,768
    • Fd: 1,858,986
    • MFd: 73,474,947
  • Allein durch manuelle Umschreibungen verbessern sich Speicherverbrauch und Laufzeit gegenüber dem ersten Versuch fast um das Zehnfache
  • Wenn benannte Zwischenergebnisse erzeugt werden, lässt sich der gewünschte Bushy-Tree-Join-Plan bis zu einem gewissen Grad direkt aufbauen; wenn jedoch Relationen wie V, die tatsächlich nicht benötigt werden, benannt werden, entstehen hohe Kosten durch ihre Erzeugung

Demand-driven-Abfragen und Magic Sets

  • Demand-driven-Abfragen untersuchen nur die Teile, die für ein bestimmtes Zielfaktum erforderlich sind
  • Als näherungsweise Lösung können Magic Sets verwendet werden
    • Dabei handelt es sich um eine Transformation, die das Target-Literal in die Abfrage einbettet
    • Man könnte sich überlegen, nicht bei allen d, sondern nur bei den interessierenden d zu starten, aber eine naive Anwendung kann falsch sein
  • Magic Sets sind nicht zwingend die optimale Antwort, und es ist geplant, weitere einschlägige Papers zu lesen, um effizientere Ansätze zu finden
  • Die zugehörigen Links sind wie folgt

Optimierung der Join-Planung und datenparalleles IR

  • Der Reiz von Datalog liegt weniger in der Horn-Klausel selbst als darin, dass es das Kernproblem datenparalleler Berechnung, nämlich Data Rendezvous, in reiner Form sichtbar macht
  • Die Regel h(x, y, z) :- b1(x, y), b2(y, z) . kann als Problem verstanden werden, für jedes y die zugehörigen x und z an einem Ort zusammenzuführen
  • Das Grundverhalten datenparalleler Berechnung besteht darin, Records nach Schlüsseln zu gruppieren und an benutzerdefinierte Logik zu übergeben; Joins drücken dabei selektives Routing aus
  • Ein einfaches IR verwendet die folgenden Opcodes
    • Var(String): benannte Collection
    • Map(Action): Filter, Permutation, Projection
    • Key(usize): markiert die ersten Spalten als Schlüssel
    • Mul(usize): kombiniert mehrere Collections mit derselben Schlüssellänge
  • Später werden Map und Key in Action.key_arity zusammengeführt
  • Action enthält Literal-Filter, Variablengleichheits-Filter, Projection und Key-Arity
  • Der einfachste Ausgangspunkt wäre, alle Body-Atome per Cross Join zu verbinden und auf jeden Head Filter und Projection zu legen; das liefert zwar die richtige Antwort, ist aber in der Performance sehr schlecht

e-graph-basierte Optimierung

  • Für die Optimierung werden e-graph und Equality Saturation verwendet
  • Als Referenzen dienen die egg webpage, ein früherer Artikel und egg
  • Der Term-Graph wird als Map von ENode<T> mit Id dargestellt, wobei identische Knoten gemeinsam genutzt werden, um Programme kompakter darzustellen
  • Es wurden drei e-graph-Regeln angewendet
    • MulPermute: macht Eingabepermutationen von Mul(k) äquivalent
    • MulPartition: teilt Mul(k) auf verschiedene Arten auf und macht sie äquivalent
    • MapPushdown: schiebt Map unter Mul(2), um eine Join-Form mit Schlüssel zu erzeugen
  • Die Beispielregel lautet wie folgt
    • head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
  • Nach der Equality Saturation werden im Extraktionsschritt Kosten zugewiesen
    • Die Kosten von Map entsprechen der Anzahl der Ausgabespalten
    • Die Kosten von Mul sind die Summe aus der Anzahl der Schlüsselspalten und der Anzahl der Nicht-Schlüsselspalten der Eingaben
    • Die Kosten von Var sind 0
    • Bei Gleichstand werden zuerst die Anzahl der Map, dann die Anzahl der Mul minimiert
  • Im Beispiel wurde der ausgewählte Plan in Wave Two mit höchstens zwei unkorrelierten Spalten gefunden
    • Map für die Eingaben a und b
    • ein Join
    • eine Zwischenprojektion
    • ein Join mit sich selbst
    • eine abschließende Projektion
  • Diese Plansuche dauert selbst im Release-Build etwa 40 ms, wobei der Großteil der Zeit für die Equivalence Saturation verwendet wird

Update zur Ausführung optimierter Pläne

  • Im Update vom 2025-06-29 wurde die Ausführung optimierter Pläne implementiert
  • Der Plan wird als Vec<ENode<Op>> erzeugt, aber bei der tatsächlichen Ausführung wird nicht jeder Knoten unabhängig ausgeführt
  • Die beabsichtigte Ausführungsweise ist wie folgt
    • Für jedes Var werden mehrere abhängige Map in einem einzigen Scan der externen Collection angewendet
    • Für jedes Mul werden mehrere abhängige Map in einem einzigen Join-Scan angewendet
  • Op::Map(action) ist weniger eine direkt ausgeführte Operation als vielmehr eine Aufgabe, die für abhängige Operationen in die Queue gestellt wird
  • Dafür wurde TempAction eingeführt
    • Literal-Filter
    • Variablen-Gleichheitsfilter
    • Projektion, die Spaltenreferenzen oder String-Literale enthalten kann
  • In der Vorbereitungsphase des Ausführungsplans werden Body und Head getrennt und Map-Aktionen pro Eingabeknoten gesammelt
  • Bei der Ausführung von Var wird die Namensbehandlung in drei Fälle aufgeteilt
    • Die Erzeugung des Head verwendet den Namen der Head-Relation
    • Eine Identity-Transformation verwendet den vorhandenen Eingabenamen wieder
    • Eine nicht-triviale Transformation wird unter einem temporären Namen .temp-* gespeichert
  • Die Ausführung von Mul(2) prüft die Key-Arity und die Namen der beiden Eingaben und ruft join_with auf, um Ergebnisse in mehrere Builder zu schreiben
  • Im komplexen Aliasing-Beispiel dauerte die Ausführung des optimierten Plans 114,28 Sekunden und war damit etwa 5 Sekunden schneller als zuvor mit 119 Sekunden, der Grund dafür ist jedoch unklar
  • Multi-Rule-Optimierung ist noch nicht implementiert, und möglicherweise muss der Plan-Ansatz selbst noch einmal überdacht werden

Optimierung der Faktendarstellung

  • 50 GB wurden auf 5 GB reduziert, dennoch wird offenbar noch etwa zehnmal mehr Speicher verwendet als eigentlich nötig
  • Die größte Layer der großen Relation -M enthält 57.289.225 Fakten und verwendet etwa 2.098.253.766 Byte
    • Faktengrenzen: 458.313.800 Byte
    • Term-Grenzen: 916.627.600 Byte
    • Tatsächliche Byte-Daten: 723.312.366 Byte
  • Die erste Optimierung nutzt aus, dass die Arity konstant ist
    • Wenn alle Fakten 2 Spalten haben, lassen sich Faktengrenzen allein durch Stride und Länge darstellen
    • Dadurch werden Grenzdaten im Umfang von etwa 458 MB praktisch eliminiert
  • Die zweite Optimierung besteht darin, die Term-Länge zu vereinheitlichen
    • Wenn Zahlen als Strings mit fester Breite von 7 Stellen dargestellt werden, lassen sich auch Term-Grenzen durch Stride und Länge ausdrücken
    • Dafür kann die tatsächliche Zahl der Bytes steigen
  • Die dritte Optimierung besteht darin, Zahlen nicht als Text, sondern binär darzustellen
    • Eine 7-stellige Zahl passt in 4 Byte eines u32
    • Sie passt auch in 3 Byte, sodass 57,289,225 × 2 × 3 = 343,735,350 Byte entstehen
    • Damit sinkt der Bedarf von etwa 2 GB auf etwa 350 MB, also um etwa den Faktor 6,10
  • Wenn die Wiederholung des ersten Terms komprimiert wird, sinkt der Bedarf weiter
    • Es gibt 57.289.225 Fakten, aber nur 1.147.612 unterschiedliche erste Terme
    • Wenn statt (Term, Term) die Form (Term, [Term]) gespeichert wird, sinkt die größte Layer auf etwa 184.491.407 Byte
    • Gegenüber den ursprünglichen 2 GB entspricht das einer Reduktion um etwa den Faktor 11,37
  • Im Update vom 2025-07-02 wurde die erste Optimierung angewendet
    • Das größte Batch hat 343.735.382 Byte, also den theoretischen Wert von 343.735.350 Byte plus 32 Byte
    • Die Laufzeit sank von etwa 115 Sekunden auf etwa 95 Sekunden, also um rund 20 %

Layered-Trie-Darstellung

  • Im Update vom 2025-07-20 wurde layered trie funktionsfähig
  • Es wird die row-orientierte Darstellung mit der column-orientierten layered-trie-Darstellung verglichen
    • 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
  • Ein layered trie unterdrückt Wiederholungen früherer Spalten in einer sortierten Row-Darstellung
  • Jede Spalte ist eine Liste von Wertelisten
    • Jede Liste ist eine sortierte Liste unterschiedlicher Werte, die einem Prefix der vorherigen Spalten entspricht
    • Die Anzahl der Listen einer Spalte entspricht der Gesamtzahl der Elemente der vorherigen Spalte
  • Es lässt sich wie ein Baum betrachten, die tatsächliche Implementierung bleibt jedoch spaltenbasiert
  • Der Vorteil besteht darin, dass Suche, Join, Differenzmenge und Merge auf Prefix-Ebene ausgeführt werden können
  • Wenn es fast keine unterschiedlichen Werte gibt und es günstiger ist, ganze Zeilen auf einmal zu betrachten, kann ein row-orientierter Ansatz vorteilhafter sein
  • Als gemeinsame Abstraktion wurde das Trait FactContainer eingeführt
    • form
    • len
    • apply
    • join
    • except
    • merge
  • apply verfolgt statt Rekursion mit einem expliziten Stack den Bereich jeder Layer, erzeugt Zeilen und übergibt sie an die Aktion
  • align ist ein gemeinsamer Helfer, um die Prefixe zweier layered tries aufeinander abzustimmen
    • Ordering::Less: ein Bereich, der nur in self vorkommt
    • Ordering::Greater: ein Bereich, der nur in other vorkommt
    • Ordering::Equal: ein Prefix der Länge der Arity, das auf beiden Seiten gemeinsam ist
  • join, except und merge sind alle auf align aufgebaut
    • join entfaltet bei gemeinsamem Prefix die verbleibenden Erweiterungen und führt einen Cross Join aus
    • except pfropft Bereiche, die nur in self vorhanden sind, mit TrieBuilder an
    • merge pfropft self-only-, other-only- und equal-Bereiche jeweils passend genau einmal an

Optimierung mit fester Breite und Performance

  • Wenn ein Upgrade auf feste Breite [u8; 4] möglich ist, verbessert sich die Vergleichsleistung deutlich
  • Da layered tries Optimierungen mit fester Breite pro Spalte anwenden können, könnten sie langfristig gegenüber row-Darstellungen im Vorteil sein
  • Auf except und merge ließen sich upgrade und downgrade leicht anwenden, bei join war die Anwendung wegen Rust-Typproblemen schwieriger
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
  • Derzeit werden etwa zwei Drittel der Laufzeit unter join verbraucht
  • Bei der Join-Optimierung dürfte noch mindestens ungefähr ein zusätzlicher Faktor 2 möglich sein
  • Ein einfacher Versuch, nur die innere Schleife neu anzuordnen, brachte keine messbare Verbesserung

Auf die Ebene des kompilierten Codes spezialisieren

  • Wenn Terme gleicher Länge und Fakten gleicher Arität erkannt werden, kann Vec<u8> wie Vec<[[u8; B]; T]> behandelt werden
  • In dieser Form kennt Rust die Datenstruktur besser, wodurch Kosten für Bounds- und Längenprüfungen sinken und insbesondere Vergleiche sehr billig werden
  • Vergleiche werden an mehreren Stellen in datatoad verwendet
    • Sortieren und Deduplicating von Fakt-Batches
    • Mergen von Batches
    • Mergen von Join-Schlüsseln
    • Filtern neuer Fakten durch Vergleich mit bestehenden Fakten
  • Die Benchmark-Ergebnisse sehen wie folgt aus
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
  • Die Sortieroptimierung wurde experimentell umgesetzt, indem Vec<u8> per unsafe transmute in Vec<[u8; 8]> umgewandelt und dann sortiert sowie dedupliziert wurde
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
  • Die Merge-Optimierung wurde als einfache Methode implementiert, bei der beide Eingaben zusammengehängt und anschließend sortiert sowie dedupliziert werden
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
  • Die kompilierte Performance von datafrog ist noch nicht erreicht
  • Verbleibende Vergleichskosten gibt es auch bei join und antijoin; beim Wechsel zu trie-basierten Strukturen sollen dieselben Optimierungsmöglichkeiten erneut betrachtet werden
  • Es wird nach einem Weg gesucht, unsafe zu entfernen, und zusätzlich wird das Fazit gezogen, dass unsafe-Code vermieden werden sollte

Noch offene Arbeit

  • Spill auf Festplatte

    • Der columnar-Speicher besteht aus wenigen großen Allokationen
    • Beim Erzeugen kann statt in den Speicher in eine Datei geschrieben und diese anschließend per Memory-Mapping wiederverwendet werden

  • Verteilte Auswertung

    • Join, Deduplicating und Distinctness-Checks basieren auf Schlüsselgleichheit
    • Schlüssel und die zugehörigen Daten lassen sich auf mehrere Worker verteilen
    • Mit timely_communication lässt sich das auf mehrere Prozesse erweitern

  • Streaming-Regelauswertung

    • Der aktuelle Join verwendet binäre Joins und materialisierte Ausgaben
    • Wenn die nötigen Indizes vorhanden sind, lässt sich ein Plan erstellen, der keinen internen Zustand materialisiert
    • Worst-case-optimal Join soll hier ebenfalls behandelt werden

  • Spezialisierung auf benutzerdefinierte Repräsentationen

    • Es gibt die Idee, transitive closure zu erkennen und auf strongly connected component decomposition zu spezialisieren
    • Für equivalence relation kann eine Union-Find-Datenstruktur verwendet werden
    • bddbddb und factorized databases behandeln ebenfalls verwandte Themen

  • Suche nach relevanten Fakten

    • demand transform muss verstanden und angewendet werden
    • Für interaktive Datalog-Erkundung wird das als notwendige Transformation angesehen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-06-16
Hacker-News-Kommentare

  • Interessant, dass dieser Beitrag auf Platz 1 gelandet ist
    Ich baue gerade mit Differential Datalog und Rust ein Echtzeit-Strategiespiel und lasse die Spiellogik von DDL verwalten
    Größtenteils ist es eher ein Vorwand, um eine neue Idee kennenzulernen und mich in endloses Yak-Shaving zu stürzen
    https://github.com/vmware-archive/differential-datalog

    • Klingt nach einer coolen Demo mit ddlog
      Zur Einordnung: Das ddlog-Team hat inzwischen Feldera gegründet, und es könnte sich lohnen, DBSP direkt aus Rust heraus zu verwenden
      https://github.com/feldera/feldera
    • Ich frage mich, ob man aus dem Repository des Originalbeitrags und salsa, der Crate, die den Rust-Analyzer antreibt, eine Art Frankenstein-Differential-Datalog bauen könnte
      https://github.com/salsa-rs/salsa
    • Ich bin gespannt, wie der Implementierungsstand ist und wie weit man damit gehen kann
      DDLog wird nicht mehr aktiv gepflegt, was es noch interessanter macht

  • „Ich, der berüchtigte Schurke, war eingeladen worden und war halb überzeugt, dass ich unterwegs war, die längst fällige Vergeltung zu empfangen.“ — die beste erste Zeile eines technischen Blogposts, die ich dieses Jahr gelesen habe
    Auch die Einschübe des Erzählers waren großartig; selten liest sich ein Beitrag so technisch tiefgehend und zugleich so unterhaltsam
    Die Reise zur Optimierung von Alias-Abfragen fühlte sich an wie ein Krimi, und man stöhnt als Leser mit über die 50 GB Speicherverbrauch und jubelt dann, als es auf 5 GB heruntergeht
    Sowohl Code als auch Text sind hervorragend

  • Ich habe ein wenig daran gearbeitet, mangle datalog nach Rust zu portieren
    Es liegt unter https://github.com/google/mangle/tree/main/rust und befindet sich im selben Repository wie die Go-Implementierung
    Es hat keine hohe Priorität, und dazu kommt noch Second-System-Syndrome, daher geht es nur langsam voran
    Mangle Rust zielt darauf ab, Daten beliebiger Größe zu verarbeiten, indem Fakten per Memory Mapping von der Platte gelesen und geschrieben werden; die Go-Implementierung arbeitet dagegen im Speicher
    Dieser Beitrag ist gut, weil er Datalog parst und auch LSM-Trees behandelt, und er ist deutlich leichter nachzuvollziehen als Materialien zu datafrog
    In Rust gibt es viele Datalog-Implementierungen mit prozeduralen Makros, etwa ascent und crepe, aber sie haben den Nachteil, dass es schwierig ist, Abfragen zur Laufzeit entgegenzunehmen
    Für statische Analysen mit festen Abfragen und Programmen kann der Ansatz mit prozeduralen Makros allerdings besser sein

  • Auch wenn die aktuelle Datalog-Renaissance etwas nachzulassen scheint, ist es schön zu sehen, dass der harte Kern der Enthusiasten weiter durchhält
    Die jüngste Datalog-2.0-Konferenz war deutlich kleiner als früher, und auch auf der zweiten HYTRADBOI-Konferenz spielte Datalog eine geringere Rolle
    Bei der ersten HYTRADBOI hatte ein Viertel der Einreichungen mit Datalog zu tun
    Es ist ermutigend, dass andere ihre aktuellen Datalog-Projekte teilen
    Ich bereite derzeit eine große Softwaremigration vor und baue dafür eine Datenqualitäts-Pipeline für eine Legacy-SQL-Datenbank
    Wenn man Abfragen gut strukturiert, sind sie sehr gut lesbar; zum Identifizieren und Auffinden von Datenqualitätsproblemen halte ich Datalog für deutlich nützlicher als SQL

    • Auch wenn ich der großen Richtung zustimme, ist die geringe Teilnehmerzahl bei Datalog 2.0 schwerlich ein repräsentatives Beispiel für einen Niedergang von Datalog
      Datalog 2.0 ist ein Satelliten-Workshop der in Europa eher weniger bekannten Konferenz LPNMR, und diese Konferenz fand zufällig in Dallas statt
      Als ich selbst dort war, wirkte die Veranstaltung ebenfalls etwas leer; ich hatte auch ein Paper im Workshop, sah aber nicht viele Leute aus dem Feld
      Auffällig waren als Ausnahme die Leute aus Europa, die den Nemo-Solver vorstellten
      Dass dieses Jahr so wenige teilnahmen, zeigt meiner Ansicht nach eher, dass es ein Satelliten-Workshop einer ohnehin nicht besonders renommierten Konferenz war und dass die Hauptveranstaltung zudem ICLP war, als dass es mangelndes Interesse an Datalog-Implementierungen belegt
      Natürlich will ich damit nicht der größeren These widersprechen, dass bei Implementierungen reiner Datalog-Engines kaum noch Neues übrig ist
      Der Forschungsraum ist längst weitergezogen, hin zu exotischeren Problemen wie Streaming (HydroFlow), Choice (Dusa) und Dingen, die einem allgemeinen Chase nahekommen (die Chase-Engine von Egglog)
      Dass Vanilla-Datalog langweilig ist, dürfte weitgehend unstrittig sein; monotone Vorwärts-Sättigung und Horn-Klauseln sind aber eine reichhaltige Baseline mit gut verstandener Performance-Engineering-Landschaft, auf der sich interessantere Theorien wie Semiringe oder Z-Sets gut aufbauen lassen

  • Wenn dir die Zustandsmaschine und der Parsing-Teil gefallen haben, empfehle ich auch Rob Pikes alten Vortrag Lexical Scanning in Go
    https://www.youtube.com/watch?v=HxaD_trXwRE
    Er ist in Go, aber das meiste lässt sich leicht auf andere Sprachen übertragen
    Schön, dass moderne Sprachen wie Rust, Zig und Go Unicode/Rune/Graphem nativ unterstützen
    Im Vergleich zu Java, .NET, C++ oder Skriptsprachen verschwinden dadurch viele Probleme einfach

  • Ich mag die Datalog-Arbeit des Autors insgesamt, aber ich wünschte, in Einführungen würden keine binären Joins gelehrt
    Sobald man die Idealfälle verlässt, wird das Innenleben schnell unübersichtlich, und Methoden für allgemeine Joins ließen sich in meinem Kopf viel leichter verallgemeinern
    https://en.wikipedia.org/wiki/Worst-case_optimal_join_algorithm

  • Vor langer Zeit bin ich im Studium ein wenig mit Prolog in Berührung gekommen, und ich weiß grob, wofür es verwendet wird und wobei es nützlich ist, aber wirklich tief verstanden habe ich es nicht.
    Seitdem höre ich immer wieder, dass Datalog großartig sei, aber ich bekomme nicht richtig zu fassen, was Datalog gegenüber Prolog verbessert.
    Ich habe gerade die Datalog-Seite auf Wikipedia überflogen; danach scheint Prolog vergleichsweise schlechte Performance zu haben, während Datalog Ausdrucksstärke und Funktionen reduziert und dafür die Performance deutlich verbessert, sodass größere Datensätze und stärker parallelisierte Verarbeitung möglich werden.
    Offenbar gehört auch dazu, dass die Turing-Vollständigkeit wegfällt; ich frage mich, ob das der Kern ist oder ob ich damit völlig danebenliege.

    • Soweit ich weiß, wirkt Prolog deklarativ, als müsse man nur Relationen codieren und es finde die Antwort, tatsächlich hängt es aber stark von der Reihenfolge der Regeln ab und braucht zusätzliche Anweisungen wie „cut“.
      cut verhindert nicht nur unnötige Berechnungen, sondern kann auch das Ergebnis beeinflussen.
      Datalog hingegen ist im Großen und Ganzen eher wie eine relationale Datenbank mit anderer Syntax.
    • Datalog ist einfacher, nicht Turing-vollständig und verwendet, soweit ich mich erinnere, Vorwärtsverkettung, was sich kaskadenartig auf Performance- und Speichereigenschaften auswirkt.
      Ein trivialer, aber riesiger Suchraum in Prolog kann in Datalog so viel Speicher verbrauchen, dass er sich gar nicht ausdrücken lässt.
      Datalog ist ein Pendlerauto mit CVT, Prolog eher ein F1-Wagen.
      Es ist weniger eine Verbesserung als vielmehr eine teilweise Kastration von Prolog, damit sich die Leute nicht selbst den Fuß wegschießen, und außerdem ist es viel einfacher, es in andere Anwendungen zu implementieren und einzubetten.
      Wer mit Prolog vertraut ist, wird Datalog meist als einschränkend empfinden.
      Es gibt kein call/3, keine term/goal expansion, und im Grunde ist Datalog darauf ausgelegt, den kleinsten gemeinsamen Funktionsumfang von Prolog herauszuziehen und für interaktive Datenbanksuchen zu verwenden.
      Schnellen Datalog-Code zu schreiben ist leicht, aber die Obergrenze liegt auch deutlich niedriger.
      Prolog kann ebenfalls so geschrieben werden, dass es Nebenläufigkeit zulässt, aber das ist eine Aufgabe für Fortgeschrittene, bei der man die Implementierung verstehen muss.
      Guarded Horn Clauses und davon abgeleitete Sprachen wurden entwickelt, um solche Aspekte zu formalisieren, aber die Entwicklungen in Japan nach Prolog sind sehr schwer zugänglich.
      Die Performance von Prolog hängt stark vom Programmierer, der verwendeten Implementierung und dem Einsatzort ab.
      Wie Lisp kann auch Prolog zur Compile-Zeit aus einer DSL nativen Maschinencode erzeugen.
      Wenn man versteht, wie die zugrunde liegende Implementierung arbeitet, und den Code entsprechend schreibt, ist es ausreichend schnell.
      Dafür muss man allerdings über Jahre hinweg Prolog-Code mit ein und derselben Implementierung schreiben.
      Es gibt auch viel Forschung zu Optimierungen von Prolog-Compilern und proprietäre Implementierungen.
      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/

  • Wenn man Datalog und Rust verwenden möchte: cozodb ist in Rust geschrieben und bietet auch eine Datalog-Abfragesyntax.

    • Cozodb sieht interessant aus, wirkt aber nahezu inaktiv.
      Als ich es etwa im November 2024 angeschaut habe, habe ich ein paar naheliegende Verbesserungsmöglichkeiten im SQLite-Storage-Backend gefunden.
      https://github.com/cozodb/cozo/issues/285
    • Cozodb funktionierte gemäß der Dokumentation im Großen und Ganzen gut, und die Arbeit damit war angenehm.
      Ich habe es auch für statische Programmanalyse verwendet; intern nutzt es Sortierbäume und Typtechniken.
      Die Dokumentation ist ausreichend, sodass man sie mit den schrittweisen Erklärungen im Blog vergleichen kann, und besonders die Arbeit an der Query-Optimierung ist interessant.
      Allerdings sind die Kosten für Datenserialisierung hoch, wenn man nicht in Rust im Speicher arbeitet, und das Projekt ist bestenfalls ruhig.

  • Früher sagten Clojure-Fans, Datalog sei besser als SQL, und es sei schade, dass relationale Datenbanken alle SQL verwenden.
    Ich habe nie gründlich genug nachgeforscht, warum sie das dachten.

    • Grundsätzlich ist Datalog deutlich weniger ausschweifend als SQL, die Kosten für das Auslagern von Views sind viel geringer, und transitive Abschlüsse werden überragend gut unterstützt.
      http://canonical.org/~kragen/binary-relations begann als einfache nicht-rekursive Abfrage, aber die SQL-Übersetzung ist schon kriminell, und eine sauber getrennte SQL-Lösung wäre ein Kapitalverbrechen.
      In jüngerer Zeit wurden ANSI SQL rekursive Funktionen hinzugefügt, sodass es nicht mehr völlig unmöglich ist, aber es gibt drei große Nachteile.
      Erstens hat man SQL versehentlich Turing-vollständig gemacht; Datalog-Abfragen hingegen terminieren garantiert.
      Zweitens ist es weiterhin furchtbar schwerfällig zu benutzen.
      Drittens wird es wegen des ersten Punkts oft nicht vollständig implementiert, sodass man sich nur schwer darauf verlassen kann.
    • Der Clojure/Datomic-Dialekt ist schwer zu verstehen, aber der grundsätzlichen Richtung stimme ich zu.
      Wenn man Datalog online in einer freundlichen Notebook-Umgebung ausprobieren möchte, empfehle ich Percival.
      https://percival.ink/
      Für Datalog-Implementierungen insgesamt gibt es keinen Standard, der „ANSI SQL“ entspräche, aber wenn man die Kernideen verstanden hat, sind andere Datalog-Varianten auch nicht allzu schwierig.
      Ich habe auch einen Percival-Fork begonnen, der Datalog nach SQLite kompiliert; wer sehen möchte, wie beide dasselbe ausdrücken, kann ihn sich ansehen.
      https://percival.jake.tl/
      Aggregationen und fortgeschrittenere Joins sind noch unvollständig, aber die Grundform funktioniert gut.
      Logica ist ein deutlich ernsthafterer und ausgereifterer Datalog→SQL-Compiler von Google-Forschern; er kompiliert nach BigTable, DuckDB und in einige SQL-Dialekte.
      https://logica.dev/
      Der Bereich, in dem Datalog um mehr als eine Größenordnung einfacher wird, sind rekursive Abfragen/Regeln.
      In SQL ist das auch möglich, fühlt sich aber eher an, als würde man Play-Doh durch einen Strohhalm trinken.
      Bei Franks Materialize.com gibt es eine SQL-Form „WITH MUTUALLY RECURSIVE“, die viel besser ist als der alte rekursive ANSI-SQL-Ansatz und bei Notion für Page-Load-Abfragen und Datensynchronisierung evaluiert wird.
      https://materialize.com/blog/recursion-in-materialize/
      Feldera hat für rekursive Views ebenfalls eine ähnliche Form.
      https://www.feldera.com/blog/recursive-sql-queries-in-feldera
      Mir gefällt an Feldera, dass man jede „Regel“ oder Unter-View als eigene Anweisung formulieren kann, statt alles in eine riesige Anweisung packen zu müssen.
      Der wichtigste Nachteil, den ich beim Testen gesehen habe, ist, dass Felderas SQL-Dialekt ziemlich viele Einschränkungen von Apache Calcite geerbt hat; der Materialize-SQL-Dialekt dagegen bemüht sich sehr stark um PostgreSQL-Kompatibilität.

  • Ein neuer McSharry-Artikel, hervorragend.
    Als ich zuletzt nachgesehen habe, schien sich VMWare von differential datalog entfernt zu haben.

    • Das Differential-Datalog-Team hat Feldera gegründet.
      https://www.feldera.com/
      Es sieht so aus, als seien sie von differential Datalog zu differential SQL gewechselt, vermutlich weil ihnen klar wurde, dass Datalog wirklich schwer zu verkaufen ist.