Logo des Repositoriums
 
Textdokument

LinDP++: Generalizing Linearized DP to Crossproducts and Non-Inner Joins

Lade...
Vorschaubild

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2019

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Quelle

Verlag

Gesellschaft für Informatik, Bonn

Zusammenfassung

Choosing the best join order is one of the main tasks of query optimization, as join ordering can easily affect query execution times by large factors. Finding the optimal join order is NP-hard in general, which means that the best known algorithms have exponential worst case complexity. As a consequence only relatively modest problems can be solved exactly, which is a problem for today’s large, machine generated queries. Two developments have improved the situation: If we disallow crossproducts, graph-based DP algorithms have pushed the boundary of solvable problems to a few dozen relations. Beyond that, the linearized DP strategy, where an optimal left-deep plan is used to linearize the search space of a subsequent DP, has proven to work very well up to a hundred relations or more. However, these strategies have limitations: Graph-based DP intentionally does not consider implicit crossproducts, which is almost always ok but sometimes undesirable, as in some cases such crossprod-ucts are beneficial. Even more severe, linearized DP can handle neither crossproducts nor non-inner joins, which is a serious limitation. Large queries with, e. g., outer joins are quite common and having to fall back on simple greedy heuristics in this case is highly undesirable. In this work we remove both limitations: First, we generalize the underlying linearization strategy to handle non-inner joins, which allows us to linearize the search space of arbitrary queries. And second, we explicitly recognize potential crossproduct opportunities, and expose them to the join ordering strategies by augmenting the query graph. This results in a very generic join ordering framework that can handle arbitrary queries and produces excellent results over the whole range of query sizes.

Beschreibung

Radke, Bernhard; Neumann, Thomas (2019): LinDP++: Generalizing Linearized DP to Crossproducts and Non-Inner Joins. BTW 2019. DOI: 10.18420/btw2019-05. Gesellschaft für Informatik, Bonn. PISSN: 1617-5468. ISBN: 978-3-88579-683-1. pp. 57-76. Wissenschaftliche Beiträge. Rostock. 4.-8. März 2019

Schlagwörter

Zitierform

Tags