Loading...

SIGMOD 2016 Talk by Trummer: A Fast, Randomized Algorithm for Multi-Objective Query Optimization

273 views

Loading...

Loading...

Transcript

The interactive transcript could not be loaded.

Loading...

Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Jul 15, 2016

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.

Loading...


to add this to Watch Later

Add to

Loading playlists...