Joglekar, Manas R. ;
Ré, Christopher M.
It's All a Matter of Degree: Using Degree Information to Optimize Multiway Joins
Abstract
We optimize multiway equijoins on relational tables using degree information. We give a new bound that uses degree information to more tightly bound the maximum output size of a query. On real data, our bound on the number of triangles in a social network can be up to 95 times tighter than existing worst case bounds. We show that using only a constant amount of degree information, we are able to obtain join algorithms with a running time that has a smaller exponent than existing algorithms  for any database instance. We also show that this degree information can be obtained in nearly linear time, which yields asymptotically faster algorithms in the serial setting and lower communication algorithms in the MapReduce setting.
In the serial setting, the data complexity of join processing can be expressed as a function O(IN^x + OUT) in terms of input size IN and output size OUT in which x depends on the query. An upper bound for x is given by fractional hypertreewidth. We are interested in situations in which we can get algorithms for which x is strictly smaller than the fractional hypertreewidth. We say that a join can be processed in subquadratic time if x < 2. Building on the AYZ algorithm for processing cycle joins in quadratic time, for a restricted class of joins which we call 1seriesparallel graphs, we obtain a complete decision procedure for identifying subquadratic solvability (subject to the 3SUM problem requiring quadratic time). Our 3SUM based quadratic lower bound is tight, making it the only known tight bound for joins that does not require any assumption about the matrix multiplication exponent omega. We also give a MapReduce algorithm that meets our improved communication bound and handles essentially optimal parallelism.
BibTeX  Entry
@InProceedings{joglekar_et_al:LIPIcs:2016:5780,
author = {Manas R. Joglekar and Christopher M. R{\'e}},
title = {{It's All a Matter of Degree: Using Degree Information to Optimize Multiway Joins}},
booktitle = {19th International Conference on Database Theory (ICDT 2016)},
pages = {11:111:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770026},
ISSN = {18688969},
year = {2016},
volume = {48},
editor = {Wim Martens and Thomas Zeume},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5780},
URN = {urn:nbn:de:0030drops57800},
doi = {10.4230/LIPIcs.ICDT.2016.11},
annote = {Keywords: Joins, Degree, MapReduce}
}
2016
Keywords: 

Joins, Degree, MapReduce 
Seminar: 

19th International Conference on Database Theory (ICDT 2016)

Issue date: 

2016 
Date of publication: 

2016 