License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2016.8
URN: urn:nbn:de:0030-drops-57771
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5777/
Go to the corresponding LIPIcs Volume Portal

Koutris, Paraschos ; Beame, Paul ; Suciu, Dan

Worst-Case Optimal Algorithms for Parallel Query Processing

pdf-format:
7.pdf (0.6 MB)

Abstract

In this paper, we study the communication complexity for the problem of computing a conjunctive query on a large database in a parallel setting with p servers. In contrast to previous work, where upper and lower bounds on the communication were specified for particular structures of data (either data without skew, or data with specific types of skew), in this work we focus on worst-case analysis of the communication cost. The goal is to find worst-case optimal parallel algorithms, similar to the work of (Ngo et al. 2012) for sequential algorithms.

We first show that for a single round we can obtain an optimal worst-case algorithm. The optimal load for a conjunctive query q when all relations have size equal to M is O(M/p^{1/psi^*}), where psi^* is a new query-related quantity called the edge quasi-packing number, which is different from both the edge packing number and edge cover number of the query hypergraph. For multiple rounds, we present algorithms that are optimal for several classes of queries. Finally, we show a surprising connection to the external memory model, which allows us to translate parallel algorithms to external memory algorithms. This technique allows us to recover (within a polylogarithmic factor) several recent results on the I/O complexity for computing join queries, and also obtain optimal algorithms for other classes of queries.

BibTeX - Entry

@InProceedings{koutris_et_al:LIPIcs:2016:5777,
  author =	{Paraschos Koutris and Paul Beame and Dan Suciu},
  title =	{{Worst-Case Optimal Algorithms for Parallel Query Processing}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Wim Martens and Thomas Zeume},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5777},
  URN =		{urn:nbn:de:0030-drops-57771},
  doi =		{10.4230/LIPIcs.ICDT.2016.8},
  annote =	{Keywords: conjunctive query, parallel computation, worst-case bounds}
}

Keywords: conjunctive query, parallel computation, worst-case bounds
Collection: 19th International Conference on Database Theory (ICDT 2016)
Issue Date: 2016
Date of publication: 14.03.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI