Approximation schemes for many-objective query optimization

The goal of multi-objective query optimization (MOQO) is to find query plans that realize a good compromise between conicting 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 pro-posed 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. © 2014 ACM.

Published in:
Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data - SIGMOD '14, 1299-1310
Presented at:
SIGMOD 2014, Snowbird, Utah, USA, June 22-27, 2014
New York, New York, USA, ACM Press

 Record created 2016-07-14, last modified 2018-11-26

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)