<div class="csl-bib-body">
<div class="csl-entry">Schlaipfer, M., Rajan, K., Lal, A., & Samak, M. (2017). Optimizing Big-Data Queries Using Program Synthesis. In <i>Proceedings of the 26th Symposium on Operating Systems Principles</i>. https://doi.org/10.1145/3132747.3132773</div>
</div>
The final publication is available via <a href="https://doi.org/10.1145/3132747.3132773" target="_blank">https://doi.org/10.1145/3132747.3132773</a>.
-
dc.description.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.<br /><br />Program synthesis is an undecidable problem in general and often difficult to scale, even for bounded inputs. Blitz therefore uses a series of analyses to judiciously use program synthesis and incrementally construct complex operators.<br /><br />We integrated Blitz with existing big-data query languages by embedding the synthesized operators back into the query as User Defined Operators. We evaluated Blitz on several production queries from Microsoft running on two state-of-the-art query engines: SparkSQL as well as Scope, the big-data engine of Microsoft. Blitz produces correct optimizations despite the synthesis being bounded. The resulting queries have much more succinct query plans and demonstrate significant performance improvements on both big-data systems (1.3x --- 4.7x).
en
dc.description.sponsorship
Austrian Science Funds (FWF)
-
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Program Synthesis
en
dc.subject
Query Optimization
en
dc.subject
User-Defined Operators
en
dc.title
Optimizing Big-Data Queries Using Program Synthesis
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Urheberrechtsschutz
de
dc.rights.license
In Copyright
en
dc.relation.publication
Proceedings of the 26th Symposium on Operating Systems Principles