Optimizing Recursive Queries with Progam Synthesis
Optimizing Recursive Queries with Progam Synthesis
复制标题
DOI：
10.1145/3514221.3517827
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Y. Wang;Mahmoud Abo Khamis;H. Ngo;R. Pichler;Dan Suciu
中科院分区：
文献类型：
--
作者：
Y. Wang;Mahmoud Abo Khamis;H. Ngo;R. Pichler;Dan Suciu
查询优化的大多数工作都集中在无环的查询上。但是，当今数据科学和机器学习工作负载通常涉及递归或迭代计算。在这项工作中，我们提出了一个新型框架，用于使用程序合成方法优化递归查询。特别是，我们引入了一个简单而强大的优化规则，称为“ FGH规则”，该规则旨在找到一种评估递归程序的更快方法。通过使用功能强大的工具，例如程序合成器，SMT-Solver和Equality Atatreation System，可以找到该解决方案。我们通过证明FGH规则可以在三个已经优化的数据组系统上导致高达4个数量级的加速度来证明优化的强度。
Most work on query optimization has concentrated on loop-free queries. However, data science and machine learning workloads today typically involve recursive or iterative computation. In this work, we propose a novel framework for optimizing recursive queries using methods from program synthesis. In particular, we introduce a simple yet powerful optimization rule called the "FGH-rule" which aims to find a faster way to evaluate a recursive program. The solution is found by making use of powerful tools, such as a program synthesizer, an SMT-solver, and an equality saturation system. We demonstrate the strength of the optimization by showing that the FGH-rule can lead to speedups up to 4 orders of magnitude on three, already optimized Datalog systems.