Optimizing Big-Data Queries Using Program Synthesis
2017pp. 631–646
Citations Over TimeTop 10% of 2017 papers
Abstract
Classical query optimization relies on a predefined set of rewrite rules to re-order and substitute SQL operators at a logical level. This paper proposes Blitz, a system that can synthesize efficient query-specific operators using automated program reasoning. Blitz uses static analysis to identify sub-queries as potential targets for optimization. For each sub-query, it constructs a template that defines a large space of possible operator implementations, all restricted to have linear time and space complexity. Blitz then employs program synthesis to instantiate the template and obtain a data-parallel operator implementation that is functionally equivalent to the original sub-query up to a bound on the input size.
Related Papers
- → A rule-based view of query optimization(1987)165 cited
- → A rule-based view of query optimization(1987)22 cited
- Processing and Optimization of UMQL-based Multimedia Queries(2009)
- Analysis of Query Optimizers(2021)