Lune

PLDI2021Top-tier venue

An efficient interpreter for Datalog by de-specializing relations

Xiaowen Hu, David Zhao, Herbert Jordan, Bernhard Scholz

Abstract

Datalog is becoming increasingly popular as a standard tool for a variety of use cases. Modern Datalog engines can achieve high performance by specializing data structures for relational operations. For example, the Datalog engine Soufflé achieves high performance with a synthesizer that specializes data structures for relations. However, the synthesizer cannot always be deployed, and a fast interpreter is required.

This work introduces the design and implementation of the Soufflé Tree Interpreter (STI). Key for the performance of the STI is the support for fast operations on relations. We obtain fast operations by de-specializing data structures so that they can work in a virtual execution environment. Our new interpreter achieves a competitive performance slowdown between 1.32 and 5.67× when compared to synthesized code. If compile time overheads of the synthesizer are also considered, the interpreter can be 6.46× faster on average for the first run.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • The Incredible Shrinking Context... in a Decompiler Near You cites Precise Static Identification of Ethereum Storage Variables
  • Precise Static Identification of Ethereum Storage Variables cites The Incredible Shrinking Context... in a Decompiler Near You
  • The Incredible Shrinking Context... in a Decompiler Near You cites Datalog Disassembly
  • FlowLog: Efficient and Extensible Datalog via Incrementality cites Datalog Disassembly
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. A fast in-place interpreter for WebAssemblyBen L. TitzerOOPSLA 2022 · 44 citations
  2. Precise Static Identification of Ethereum Storage VariablesSifis Lagouvardos, Yannis Bollanos, Michael Debono, Neville Grech et al.ICSE 2026 · 2 citations
  3. Finding Cross-Rule Optimization Bugs in Datalog EnginesChi Zhang, Linzhang Wang, Manuel RiggerOOPSLA 2024 · 2 citations
  4. The Incredible Shrinking Context... in a Decompiler Near YouSifis Lagouvardos, Yannis Bollanos, Neville Grech, Yannis SmaragdakisISSTA 2025 · 1 citation
  5. FlowLog: Efficient and Extensible Datalog via IncrementalityHangdong Zhao, Zhenghong Yu, Srinag Rao, Simon Frisk et al.VLDB 2026

Builds on1

  1. Datalog DisassemblyAntonio Flores-Montoya, Eric M. SchulteUSENIX Security 2020

Related papers

  1. Flan: An Expressive and Efficient Datalog Compiler for Program AnalysisSupun Abeysinghe, Anxhelo Xhebraj, Tiark RompfPOPL 2024 · 9 citations
  2. Making Formulog Fast: An Argument for Unconventional Datalog EvaluationAaron Bembenek, Michael Greenberg, Stephen ChongOOPSLA 2024 · 3 citations
  3. Datalog with First-Class FactsThomas Gilray, Arash Sahebolamri, Yihao Sun, Sowmith Kunapaneni et al.VLDB 2025 · 3 citations
  4. Interactive Debugging of Datalog ProgramsAndré Pacak, Sebastian ErdwegOOPSLA 2023 · 4 citations
  5. Column-Oriented Datalog on the GPUYihao Sun, Sidharth Kumar, Thomas Gilray, Kristopher K. MicinskiAAAI 2025 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines