This blog post details the development of datatoad, an interactive Datalog interpreter written in Rust, aiming for simplicity, usability, and performance. The author, motivated by a logic programming workshop, embarks on building a Datalog engine from the ground up, sharing insights into its design, implementation challenges, and optimization strategies. The core components covered include Datalog syntax parsing, efficient fact representation using columnar storage and a log-structured merge-tree (LSM-tree), and the application of rules through merge joins. Extensive experimentation with program analysis datasets (nullability and aliasing) reveals significant performance gains over prior tools, primarily through manual query optimization and strategic intermediate relation creation, highlighting the importance of query planning. The post concludes with a roadmap for future enhancements like disk spilling, scaling, and streaming.
Summarizing Datalog in Rust
(Note: As this is a text transcript, not a video, "starting timestamps" refer to the approximate beginning of a conceptual section or heading in the text.)
Introduction/Motivation: The author, Frank McSherry, shares insights from a logic programming workshop, emphasizing the struggle with existing Datalog tools and the aspiration to build a simple, usable, and performant interactive Datalog interpreter in Rust, available in the datatoad repository.
Introducing Datalog: Datalog is presented as a language for deriving consequences from logical Horn clauses (rules) and facts. It emphasizes properties like monotonicity (facts only increase) and confluence (order of rules doesn't change outcome), making it appealing for interactive use.
How to Represent Facts and Rules:
Structure: Rules consist of a "head" (inferred facts) and a "body" (conditions). Atoms have a name and terms (variables or literals).
Efficient Fact Storage: Instead of Vec<Vec<String>>, facts are stored in Columnar containers (a flat Vec<u8> with offsets for efficient memory management).
Fact Management: A log-structured merge-tree (FactLSM) is used to add new facts efficiently by merging layers of FactContainers.
Fact Lifecycle:FactSet manages facts through three stages: to_add (new, potentially repeated), recent (distinct, to be processed), and stable (fully processed), using advance() for deduplication.
How to Parse Rules from Text: A "not-great" but functional Datalog parser is detailed, including tokenize (converting characters to symbols like ., ,, :-, ?) and parse (recursively extracting rules, atoms, and terms). Variables are distinguished by ?.
How to Apply Rules to Facts (Joins):
Datalog Rules as Joins: Rules like the triangle rule are fundamentally equijoins in relational databases.
Join Plan: A "right-linear" join plan strategy is used, processing body atoms right-to-left, transforming and joining relations to produce results for the head.
Incremental Joins: The system supports both "full" (for new rules) and "incremental" (only new derivations) joins to avoid recomputing stable facts.
Implementation: The process involves applying JoinPlan::bodys to prepare input relations and then sequentially applying merge joins via join_with and join functions, which utilize gallop for efficient skipping.
Experimentation (Nullability Analysis):
Initial n(?a, ?c) :- n(?a, ?b), e(?b, ?c) rule on httpd data takes 15s (faster than Graspan's 684s).
Identifies temp relations created due to reordering n for joins.
Optimizes by transposing n into m (m(?b, ?a) :- n(?a, ?b) .) and then iterating on m, reducing time to ~8s.
Compares datatoad (8.43s-55.01s) favorably against Graspan (684s-42840s) but notes datafrog (1.30s-8.03s) is still faster, attributing the difference to variable-length facts and literals.
Experimentation (Aliasing Analysis):
Introduces complex alias analysis rules (M, V, F) from Zheng and Rugina, including transpose (^T), optional (^?), and repeated (^*) operators.
Initial direct implementation leads to very long runtimes and 50.13GB memory usage for the lnx_kernel dataset.
Query Optimization: Inlines V into M (eliminating the large V relation), reducing memory to 18.96GB.
Further Optimization: Introduces intermediate relations like Fd (Fd(?v3, ?l2) :- F(?v3, ?v2), d(?v2, ?l2).) and MFd, leading to a final memory usage of 5.32GB and total runtime of ~120s (a ~10x improvement in both memory and time from the initial attempt at this query).
Conclusion & Future Plans:
The datatoad experiment successfully demonstrates significant performance improvements through manual query optimization, showing the power of query optimizers.
The ability to name and form intermediate results (like Fd) allows for flexible bushy-tree join plans.
Future work includes spilling facts to disk, horizontal scaling, streaming facts, specializing to compiled code/custom logic, and implementing "demand-driven" queries (magic sets).
Summarizing Hacker News Discussion:
Differential Datalog & Feldera: Many comments revolve around VMware's Differential Datalog (DDlog), its shift to Feldera, and its use cases (real-time strategy games, data quality pipelines, streaming SQL with UDFs). Feldera is praised for its batch/streaming SQL capabilities, though some note its Apache Calcite-inherited syntax differences from Postgres.
Datalog vs. SQL: Discussants largely agree Datalog is superior for recursive queries, being less verbose and guaranteeing termination (unlike SQL's Turing-complete recursive CTEs, which are often clumsy). Datalog's readability for data quality issues is highlighted.
Rust Datalog Implementations: Mention of other Rust-based Datalog engines: ascent, crepe (using proc-macros for static queries), mangle (disk-based, slow), and cozodb (inactive but tinkerable).
Join Algorithms: A sub-discussion emerges on the trade-offs between binary join plans and worst-case optimal join (WCOJ) algorithms, with arguments for each depending on workload and scalability needs.
Community & Conferences: Observations about the small attendance at Datalog 2.0 workshop in Dallas, but a general sentiment that a core group of Datalog enthusiasts persists and innovations continue (e.g., HydroFlow, Dusa, Egglog).
Praise for the Post: The blog post itself receives high praise for its engaging opening, technical depth, and clear, fun-to-read prose ("detective story" feel for optimization journey).