Building a Join Optimizer for Soufflé

Abstract Datalog has grown in popularity as a domain-specific language (DSL) for real-world applications. Crucial to its resurgence has been the advent of high-performance Datalog compilers, including Soufflé. Yet this high performance is unobtainable for users unless they provide performance hints such as join orders for rules. In this paper, we develop a join optimizer for Soufflé that automatically computes high-quality join orders using a feedback-directed optimization strategy: In a profiling stage, the compiler obtains join size estimates, and in a join ordering stage, an offline join optimizer derives cost-optimal join orders. The performance of the automatically optimized joins is demonstrated using complex real-world applications, including DOOP, DDISASM, and VPC, surpassing the performance of un-tuned join orders by a geometric mean speedup of \(12. 07\times \).

Authors

• Samuel Arch
• Xiaowen Hu
• David Zhao 0001
• Pavle Subotic
• Bernhard Scholz

Keywords

No keywords are indexed for this paper.