# Approximation Schemes for Many-Objective Query Optimization

arXiv: https://arxiv.org/abs/1404.0046 · HTML: https://mlsanity.com/paper/1404.0046/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Mar 2014.

## Built on by (most cited first, 1 of 1)

- [Semantic-Guided RL for Interpretable Feature Engineering](https://mlsanity.com/paper/2410.02519/) (2024)

## Abstract (arXiv)

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.