Menu:

Query Optimization

Overview of query optimization approaches

Declarative query languages such as SQL allow users to simply describe the data they need instead of specifying how to generate it. Such languages are based on query optimizer components that translate declarative queries into executable query plans. The goal of query optimization is generally to find an optimal query plan for a given query (e.g., a plan with minimal execution time). The query optimization problem has been introduced in the 70's and is perhaps the optimization problem in the database community that most work has been published on. However, the context of query optimization is continuously changing which leads to novel challenges. For instance, modern execution engines have many more tuning parameters than before and motivate us to compare alternative query plans according to multiple cost metrics instead of only one. Both makes optimization more challenging. On the other hand, novel optimization platforms are nowadays available that can be exploited for query optimization.

We have recently addressed several extended variants of query optimization for which no practical algorithms were previously available. We have shown how to optimize queries in traditional query optimization that are by far too large for prior methods. In several recent publications, we have proposed a variety of approaches for making query optimization more efficient that can be categorized into three high-level ideas, as illustrated in the overview figure above. First, if queries correspond to query templates that are known in advance, we can make optimization a pre-processing step. Even though optimization may take a long time, it does not add any run time overhead. Second, we can speed up optimization by relaxing optimality guarantees. We have published approximation schemes, incremental algorithms, and randomized algorithms for novel query optimization variants. Finally, we can decrease optimization time by leveraging novel software and hardware platforms for optimization. We have recently shown how to leverage integer programming solvers, massively parallel computation clusters, and quantum annealers for query optimization variants. In several scenarios, our approaches reduce optimization times from hours or even days to just minutes or even seconds.

Publications

2016

Immanuel Trummer. "From Massive Parallelization to Quantum Computing: Seven Novel Approaches to Query Optimization." Dissertation.

Immanuel Trummer and Christoph Koch. "A Fast Randomized Algorithm for Multi-Objective Query Optimization." SIGMOD 2016
Paper  Poster  Video

Immanuel Trummer and Christoph Koch. "Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer." VLDB 2016
Paper  Poster  Video

Immanuel Trummer and Christoph Koch. "Parallelizing Query Optimization on Shared-Nothing Architectures." VLDB 2016
Paper  Poster

2015

Immanuel Trummer and Christoph Koch. "Multi-Objective Parametric Query Optimization." VLDB 2015
Invited to "Best of VLDB 2015" VLDBJ Issue
Selected as ACM SIGMOD Research Highlight
Paper  Poster  Video

Immanuel Trummer and Christoph Koch. "An Incremental Anytime Algorithm for Multi-Objective Query Optimization." SIGMOD 2015
Paper  Poster  Video

Immanuel Trummer and Christoph Koch. "Solving the Join Ordering Problem via Mixed Integer Linear Programming." Technical Report
Paper

Immanuel Trummer and Christoph Koch. "Probably Approximately Optimal Query Optimization." Technical Report
Paper

2014

Immanuel Trummer and Christoph Koch. "Approximation Schemes for Many-Objective Query Optimization." SIGMOD 2014
Paper