Modern Datalog on the GPU

现代演绎数据库引擎（例如LogicBlox和Soufflé）使用户能够编写声明性查询，计算关于外延数据的递归推导，将高性能的操作（查询计划、半朴素求值和并行化）留给引擎。这些引擎是现代高吞吐量应用程序（如静态分析、安全审计、社交媒体挖掘和业务分析）的支柱。最先进的引擎基于显式表示（例如BTrees和tries）上的嵌套循环连接，并广泛使用范围索引来加速迭代连接。在这项工作中，我们介绍了GDlog：一种基于GPU的演绎分析引擎（实现为CUDA库），与先前系统相比实现了显着的性能提升（5-10倍或更多）。GDlog采用一种新颖的范围索引SIMD数据结构：哈希索引排序数组（HISA）。我们对GDlog进行了广泛的评估，将其与CPU和GPU基于哈希表和Datalog引擎进行比较，并使用它支持一系列大规模的演绎查询，包括可达性、同代、上下文敏感程序分析等。我们的实验表明，GDlog的性能与现代SIMD哈希表相当，并在运行时比以前的工作快一个数量级，同时提供更有利的内存占用。

本论文旨在解决高吞吐量应用中的递归推断查询的性能问题。

GDlog是一个基于GPU的推理分析引擎，使用哈希索引排序数组（HISA）数据结构实现高效的范围索引。

GDlog相较于现有系统具有更高的性能和更优秀的内存占用率。论文使用大规模的推理查询进行了广泛的评估，并与CPU和GPU的哈希表和Datalog引擎进行了比较。

现有的推理引擎如LogicBlox和Soufflé都是基于显式表示的嵌套循环连接和范围索引加速迭代连接。