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 conflicting objectives such as minimizing execution time and minimizing monetary fees in a Cloud scenario. A previously proposed exhaustive MOQO algorithm needs hours to op-timize even simple TPC-H queries. This is why we pro-pose several approximation schemes for MOQO that gener-ate guaranteed near-optimal plans in seconds where exhaus-tive optimization takes hours. We integrated all MOQO algorithms into the Postgres op-timizer 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 iden-tify properties that hold for a broad range of objectives and can be exploited for the design of future MOQO algorithms. 1