Recursive query processing has experienced a recent resurgence, as a result
of its use in many modern application domains, including data integration,
graph analytics, security, program analysis, networking and decision making.
Due to the large volumes of data being processed, several research efforts,
across multiple communities, have explored how to scale up recursive queries,
typically expressed in Datalog. Our experience with these tools indicated that
their performance does not translate across domains (e.g., a tool design for
large-scale graph analytics does not exhibit the same performance on
program-analysis tasks, and vice versa). As a result, we designed and
implemented a general-purpose Datalog engine, called RecStep, on top of a
parallel single-node relational system. In this paper, we outline the different
techniques we use in RecStep, and the contribution of each technique to overall
performance. We also present results from a detailed set of experiments
comparing RecStep with a number of other Datalog systems using both graph
analytics and program-analysis tasks, summarizing pros and cons of existing
techniques based on the analysis of our observations. We show that RecStep
generally outperforms the state-of-the-art parallel Datalog engines on complex
and large-scale Datalog program evaluation, by a 4-6X margin. An additional
insight from our work is that we show that it is possible to build a
high-performance Datalog system on top of a relational engine, an idea that has
been dismissed in past work in this area.

本文提出了一种名为 RecStep 的通用 Datalog 引擎，该引擎基于并行单节点关系型系统，通过对多种技术的运用，在大规模数据处理方面表现非常出色，相较于现有并行 Datalog 引擎有 4-6 倍的性能提升，同时证明了过去的质疑，表明在关系引擎之上可以构建高性能的 Datalog 系统。