Publications
Koch, Christoph. Abstraction without Regret in Data Management Systems (pdf). Proc. CIDR 2013.
Klonatos, Ioannis; Nötzli, Andres; Spielmann, Andrej; Koch, Christoph; Kuncak, Viktor.
Automatic Synthesis of Out-of-Core Algorithms (pdf).
ACM SIGMOD International Conference on Management of Data, New York, NY, USA, June 22-27, 2013.
Abstract:
We present a system for the automatic synthesis of efficient algorithms specialized for a particular memory hierarchy and a set of storage devices. The developer provides two independent inputs: 1) an algorithm that ignores memory hierarchy and external storage aspects; and 2) a description of the target memory hierarchy, including its topology and parameters. Our system is able to automatically synthesize memory-hierarchy and storage-device-aware algorithms out of those specifications, for tasks such as joins and sorting. The framework is extensible and allows developers to quickly synthesize custom out-of-core algorithms as new storage technologies become available.
Trummer, Immanuel; Koch, Christoph.
Approximation Schemes for Many-Objective Query Optimization (pdf).
ACM SIGMOD International Conference on Management of Data, Snowbird, Utah, USA, 2014.
Abstract:
The goal of multi-objective query optimization (MOQO) is to find query plans that realize a good compromise between conflicting objectives such as minimizing execution time and minimizing monetary fees in a Cloud scenario. A previously proposed exhaustive MOQO algorithm needs hours to optimize even simple TPC-H queries. This is why we propose several approximation schemes for MOQO that generate guaranteed near-optimal plans in seconds where exhaustive optimization takes hours. We integrated all MOQO algorithms into the Postgres optimizer and present experimental results for TPC-H queries; we extended the Postgres cost model and optimize for up to nine conflicting objectives in our experiments. The proposed algorithms are based on a formal analysis of typical cost functions that occur in the context of MOQO. We identify properties that hold for a broad range of objectives and can be exploited for the design of future MOQO algorithms.
Project members
Alumni
- Andrei Spielmann
- Andres Noetzli
Acknowledgments
This project is supported by ERC grant 279804 ALGILE.