It's All a Matter of Degree: Using Degree Information to Optimize Multiway Joins

Authors Manas R. Joglekar, Christopher M. Ré



PDF
Thumbnail PDF

File

LIPIcs.ICDT.2016.11.pdf
  • Filesize: 0.57 MB
  • 17 pages

Document Identifiers

Author Details

Manas R. Joglekar
Christopher M. Ré

Cite AsGet BibTex

Manas R. Joglekar and Christopher M. Ré. It's All a Matter of Degree: Using Degree Information to Optimize Multiway Joins. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICDT.2016.11

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 1-series-parallel graphs, we obtain a complete decision procedure for identifying subquadratic solvability (subject to the 3-SUM problem requiring quadratic time). Our 3-SUM 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.
Keywords
  • Joins
  • Degree
  • MapReduce

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. F. Afrati, M. Joglekar, C. Ré, S. Salihoglu, and J. Ullman. GYM: A multiround join algorithm in mapreduce. CoRR, abs/1410.4156, 2014. URL: http://arxiv.org/abs/1410.4156.
  2. F. N. Afrati and J. D. Ullman. Optimizing Multiway Joins in a Map-Reduce Environment. IEEE TKDE, 23, 2011. Google Scholar
  3. N. Alon, I. Newman, A. Shen, G. Tardos, and N. Vereshchagin. Partitioning multi-dimensional sets in a small number of "uniform" parts. Eur. J. Comb., 28, 2007. Google Scholar
  4. N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles (extended abstract). In Proceedings of the Second Annual European Symposium on Algorithms, ESA'94, pages 354-364, London, UK, 1994. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=647904.739463.
  5. A. Atserias, M. Grohe, and D. Marx. Size Bounds and Query Plans for Relational Joins. SIAM J. Comput., 42, 2013. Google Scholar
  6. Ilya Baran, ErikD. Demaine, and Mihai Patrascu. Subquadratic algorithms for 3sum. In F. Dehne, A. Lopez-Ortiz, and J. Sack, editors, Algorithms and Data Structures, volume 3608 of Lecture Notes in Computer Science, pages 409-421. Springer Berlin Heidelberg, 2005. URL: http://dx.doi.org/10.1007/11534273_36.
  7. P. Beame, P. Koutris, and D. Suciu. Communication Steps for Parallel Query Processing. In PODS, 2013. Google Scholar
  8. P. Beame, P. Koutris, and D. Suciu. Skew in Parallel Query Processing. In PODS, 2014. Google Scholar
  9. C. Chekuri and A. Rajaraman. Conjunctive Query Containment Revisited. TCS, 239, 2000. Google Scholar
  10. G. Gottlob, M. Grohe, M. Nysret, S. Marko, and F. Scarcello. Hypertree Decompositions: Structure, Algorithms, and Applications. In WG, 2005. Google Scholar
  11. J. Gross, J. Yellen, and P. Zhang. Handbook of Graph Theory, Second Edition. Chapman &Hall/CRC, 2nd edition, 2013. Google Scholar
  12. M. Joglekar and C. Ré. It’s all a matter of degree: Using degree information to optimize multiway joins. CoRR, abs/1508.01239, 2015. URL: http://arxiv.org/abs/1508.01239.
  13. P. Koutris and D. Suciu. Parallel evaluation of conjunctive queries. In Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS'11, pages 223-234, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1989284.1989310.
  14. J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection, June 2014. URL: http://snap.stanford.edu/data.
  15. D. Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM, 60, 2013. Google Scholar
  16. H. Ngo, E. Porat, C. Ré, and A. Rudra. Worst-case optimal join algorithms: [extended abstract]. In Proceedings of the 31st Symposium on Principles of Database Systems, PODS'12, pages 37-48, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2213556.2213565.
  17. H. Ngo, C. Ré, and A. Rudra. Skew Strikes Back: New Developments in the Theory of Join Algorithms. SIGMOD, 42, 2014. Google Scholar
  18. T. Veldhuizen. Leapfrog triejoin: a worst-case optimal join algorithm. CoRR, abs/1210.0481, 2012. URL: http://arxiv.org/abs/1210.0481.
  19. M. Yannakakis. Algorithms for Acyclic Database Schemes. In VLDB, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail