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'e 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'e Tree Interpreter (STI). Key for the performance of the STI is the support for fast operations on \emph{relations}. We obtain fast operations by \emph{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\times$ when compared to synthesized code. If compile time overheads of the synthesizer are also considered, the interpreter can be 6.46$\times$ faster on average for the first run.