Paper Info
Title
Adaptive Optimization of Very Large Join Queries.
Abstract
The use of business intelligence tools and other means to generate queries has led to great variety in the size of join queries. While most queries are reasonably small, join queries with up to a hundred relations are not that exotic anymore, and the distribution of query sizes has an incredible long tail. The largest real-world query that we are aware of accesses more than 4,000 relations. This large spread makes query optimization very challenging. Join ordering is known to be NP-hard, which means that we cannot hope to solve such large problems exactly. On the other hand most queries are much smaller, and there is no reason to sacrifice optimality there. This paper introduces an adaptive optimization framework that is able to solve most common join queries exactly, while simultaneously scaling to queries with thousands of joins. A key component there is a novel search space linearization technique that leads to near-optimal execution plans for large classes of queries. In addition, we describe implementation techniques that are necessary to scale join ordering algorithms to these extremely large queries. Extensive experiments with over 10 different approaches show that the new adaptive approach proposed here performs excellent over a huge spectrum of query sizes, and produces optimal or near-optimal solutions for most common queries.
Year
DOI
Venue
2018
10.1145/3183713.3183733
SIGMOD/PODS '18: International Conference on Management of Data Houston TX USA June, 2018
Field
DocType
ISSN
Query optimization,Data mining,Joins,Adaptive optimization,Computer science,Business intelligence,Linearization
Conference
0730-8078
ISBN
Citations 
PageRank 
978-1-4503-4703-7
2
0.36
References 
Authors
16
2
Name
Order
Citations
PageRank
Thomas Neumann12523156.50
Bernhard Radke2141.86