Type: Research Highlight
Title: Multi-Objective Parametric Query Optimization
Immanuel Trummer, Christoph Koch
Available in: PDF
We propose a generalization of the classical database query optimization problem: multi-objective parametric query optimization (MPQ). MPQ compares alternative processing plans according to multiple execution cost metrics. It also models missing pieces of information on which plan costs depend upon as parameters. Both features are crucial to model query processing on modern data processing platforms. MPQ generalizes previously proposed query optimization variants such as multi-objective query optimization, parametric query optimization, and traditional query optimization. We show however that the MPQ problem has di↵erent properties than prior variants and solving it requires novel methods. We present an algorithm that solves the MPQ problem and finds for a given query the set of all relevant query plans. This set contains all plans that realize optimal execution cost tradeo↵s for any combination of parameter values. Our algorithm is based on dynamic programming and recursively constructs relevant query plans by combining relevant plans for query parts. We assume that all plan execution cost functions are piecewise-linear in the parameters. We use linear programming to compare alternative plans and to identify plans that are not relevant. We present a complexity analysis of our algorithm and experimentally evaluate its performance.
Immanuel Trummer recently finished a PhD at EPFL under the supervision of Christoph Koch. His research led to various publications at the main database conferences, VLDB and SIGMOD. His papers were invited for publication into the VLDB Journal (“Best of VLDB 2015”) and selected for the ACM SIGMOD Research Highlight Award 2015. He received the European Google PhD Fellowship in structured data analysis and is alumnus of the German National Academic Foundation (“Studienstiftung des deutschen Volkes”). His dissertation was recently nominated for the EPFL thesis award.
Immanuel Trummer’s research interests cover query optimization and opinion mining. In addition, he recently obtained a research grant giving him access to a D-Wave adiabatic quantum annealer to study the use of quantum computing for database-related optimization problems. Prior to his dissertation, Immanuel Trummer obtained a French-German double diploma in computer science and engineering with distinction. More information on Immanuel Trummer’s research can be found at www.itrummer.org.
Christoph Koch is a professor of Computer Science at EPFL, specializing in data management. He has won Best Paper Awards at PODS 2002, ICALP 2005, SIGMOD 2011, and VLDB 2014, an Outrageous Ideas and Vision Paper Award at CIDR 2013, a Google Research Award (in 2009), and an ERC Grant (in 2011). He is a PI of NCCR MARVEL, a Swiss national research center for materials research. He (co-)chaired the program committees of DBPL 2005, WebDB 2008, ICDE 2011, VLDB 2013, and was PC vice-chair of ICDE 2008 and ICDE 2009. He has served on the editorial board of ACM Transactions on Internet Technology and as Editor-in-Chief of PVLDB.