Wang, Y. R., Khamis, M. A., Ngo, H. Q., Pichler, R., & Suciu, D. (2022). Optimizing Recursive Queries with Progam Synthesis. In SIGMOD ’22: Proceedings of the 2022 International Conference on Management of Data (pp. 79–93). Association for Computing Machinery (ACM). https://doi.org/10.1145/3514221.3517827
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
Published in:
SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data
-
ISBN:
978-1-4503-9249-5
-
Date (published):
11-Jun-2022
-
Event name:
2022 ACM SIGMOD/PODS International Conference on Management of Data
en
Event date:
12-Jun-2022 - 17-Jun-2022
-
Event place:
Philadelphia, PA, United States of America (the)
-
Number of Pages:
15
-
Publisher:
Association for Computing Machinery (ACM), New York, NY, United States
-
Peer reviewed:
Yes
-
Keywords:
Datalog; Recursive Aggregate; Program Synthesis; Semirings
en
Abstract:
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
en
Project title:
HyperTrac: hypergraph Decompositions and Tractability: P30930-N35 (Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
CC BY 4.0
