Oatlog: A performant ahead-of-time compiled e-graph engine
summary
Oatlog compiles egglog theories ahead-of-time Rust proc macro into generated Rust code, represents e-nodes as rows in operator-specific relations, and implements worst-case optimal joins plus semi-naive evaluation to make e-matching incremental and cache-friendly. Benchmarks on math, boolean-adder and fueled-math workloads show large speedups over egglog for small-to-moderate e-graphs (up to ~10^5 e-nodes) and avoid interpreter overhead, but several egglog features (rule sets, containers, extraction) are unimplemented and a relaxed mode changes intermediate e-graph contents until saturation.
AI-written summary · about
chapters (18)
- 0:00Oatlog goals
- 0:21Egraph implementation
- 3:28Relational query planning
- 5:39Egglog performance
- 6:00AOT compilation design
- 7:25Rust code generation
- 8:06Benchmark vs egglog
- 9:13Why Oatlog faster
- 10:16Novel optimizations
- 12:25Limitations and future
- 13:48Oatlog vs egglog semantics
- 14:31Oatlog availability
- 15:13Q&A: Dynamic rules
- 16:36Q&A: vs Datalog engines
- 17:40Q&A: Herby integration
- 18:24Q&A: Rust function interfacing
- 19:06Q&A: Hash joins factors
- 20:15Q&A: Language interoperability
related talks
30megg: Fast and Extensible Equality Saturation
17mBetter Together: Unifying Datalog and Equality Saturation
57mHigh-Performance Logic Programming on Servers, Clusters, and GPUs
25mA Semi-Persistent E-Graph with Native AC Canonization and Leapfrog AC Matching.
23mVersioned E-Graphs
23mPerformant Dynamically Typed E-Graphs in Pure Julia
20mEquality Saturation and Joins
22mAutomated Proof Generation for Associative and Distributive Rewriting with E-Graphs