  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.
