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. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1145/3514221.3517827 | PROCEEDINGS OF THE 2022 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA (SIGMOD '22) |
Keywords | DocType | ISSN |
Datalog, Recursive Aggregate, Program Synthesis, Semirings | Conference | 0730-8078 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yisu Remy Wang | 1 | 1 | 1.70 |
Mahmoud Abo Khamis | 2 | 38 | 7.66 |
Hung Q. Ngo | 3 | 670 | 56.62 |
Reinhard Pichler | 4 | 338 | 29.21 |
Dan Suciu | 5 | 9625 | 1349.54 |