  Query plans are compared according to multiple cost metrics in
multi-objective query optimization. The goal is to find the set of Pareto plans
realizing optimal cost tradeoffs for a given query. So far, only algorithms
with exponential complexity in the number of query tables have been proposed
for multi-objective query optimization. In this work, we present the first
algorithm with polynomial complexity in the query size.
  Our algorithm is randomized and iterative. It improves query plans via a
multi-objective version of hill climbing that applies multiple transformations
in each climbing step for maximal efficiency. Based on a locally optimal plan,
we approximate the Pareto plan set within the restricted space of plans with
similar join orders. We maintain a cache of Pareto-optimal plans for each
potentially useful intermediate result to share partial plans that were
discovered in different iterations. We show that each iteration of our
algorithm performs in expected polynomial time based on an analysis of the
expected path length between a random plan and local optima reached by hill
climbing. We experimentally show that our algorithm can optimize queries with
hundreds of tables and outperforms other randomized algorithms such as the
NSGA-II genetic algorithm over a wide range of scenarios.
