Title: Optimizing Big-Data Queries Using Program Synthesis
Language: English
Authors: Schlaipfer, Matthias
Rajan, Kaushik 
Lal, Akash 
Samak, Malavika 
Issue Date: 2017
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.

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.

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).
Keywords: Program Synthesis; Query Optimization; User-Defined Operators
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:3-3341
http://hdl.handle.net/20.500.12708/885
Library ID: AC11365316
ISBN: 9781450350853
Organisation: E192 - Institut für Informationssysteme 
Publication Type: Inproceedings
Konferenzbeitrag
Appears in Collections:Conference Paper

Files in this item:


Page view(s)

115
checked on Jul 27, 2021

Download(s)

218
checked on Jul 27, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.