Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Neumann, Thomas

dblp



Editor(s):

Binning, Carsten
Dageville, Benoit

dblp
dblp

Not MPII Editor(s):

Binning, Carsten
Dageville, Benoit

BibTeX cite key*:

Neumann2009SIGMODa

Title, Booktitle

Title*:

Query Simplification: Graceful Degradation for Join-Order Optimization

Booktitle*:

SIGMOD-PODS'09 : Compilation Proceedings of the International Conference on Management of Data & 28th Symposium on Principles of Database Systems

Event, URLs

URL of the conference:

http://www.sigmod09.org/

URL for downloading the paper:

http://doi.acm.org/10.1145/1559845.1559889

Event Address*:

Providence, USA

Language:

English

Event Date*
(no longer used):


Organization:

Association for Computing Machinery (ACM)

Event Start Date:

29 June 2009

Event End Date:

2 July 2009

Publisher

Name*:

ACM

URL:


Address*:

New York, NY

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

June

Pages:

403-414

Year*:

2009

VG Wort Pages:

38

ISBN/ISSN:

978-1-60558-554-3

Sequence Number:


DOI:

10.1145/1559845.1559889



Note, Abstract, ©


(LaTeX) Abstract:

Join ordering is one of the most important, but also
most challenging problems of query optimization. In general finding the optimal
join order is NP-hard. Existing dynamic programming algorithms
exhibit exponential runtime even for the restricted, but highly relevant
class of star joins. Therefore, it is infeasible to find the optimal join order
when the query includes a large number of joins.
Existing approaches for large queries switch to greedy heuristics
or randomized algorithms at some point, which can degrade query execution
performance by orders of magnitude.

We propose a new paradigm for optimizing large queries: when a query is
too complex to be optimized exactly, we simplify the query's join graph until
the optimization problem becomes tractable within a given time budget.
During simplification, we apply safe simplifications before more
risky ones. This way join ordering problems are solved optimally if possible,
and gracefully degrade with increasing query complexity.

This paper presents a general framework for query simplification and a
strategy for directing the simplification process. Extensive
experiments with different kinds of queries, different join-graph
structures, and different cost functions indicate that query
simplification is very robust and outperforms previous
methods for join-order optimization.



Download
Access Level:

Institute

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Databases and Information Systems Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Neumann2009SIGMODa,
AUTHOR = {Neumann, Thomas},
EDITOR = {Binning, Carsten and Dageville, Benoit},
TITLE = {Query Simplification: Graceful Degradation for Join-Order Optimization},
BOOKTITLE = {SIGMOD-PODS'09 : Compilation Proceedings of the International Conference on Management of Data & 28th Symposium on Principles of Database Systems},
PUBLISHER = {ACM},
YEAR = {2009},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {403--414},
ADDRESS = {Providence, USA},
MONTH = {June},
ISBN = {978-1-60558-554-3},
DOI = {10.1145/1559845.1559889},
}


Entry last modified by Anja Becker, 03/17/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
03/23/2009 04:26:01 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Anja Becker
Anja Becker
Thomas Neumann
Martin Theobald
Martin Theobald
Edit Dates
17.03.2011 16:10:03
23.03.2010 11:58:14
01/26/2010 04:38:40 PM
04/16/2009 01:56:26 PM
04/16/2009 01:56:12 PM