An efficient interpreter for Datalog by de-specializing relations
This is the paper An efficient interpreter for Datalog by de-specializing relations. It was published in the PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. The paper describes several optimization approaches to implement an efficient interpreter for Datalog language and presents result on the Soufflé interpreter.
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.