Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/21801
Title: | Data partitioning for single-round multi-join evaluation in massively parallel systems | Authors: | AMELOOT, Tom GECK, Gaetano KETSMAN, Bas NEVEN, Frank Schwentick, Thomas |
Issue Date: | 2016 | Publisher: | ASSOC COMPUTING MACHINERY | Source: | SIGMOD RECORD, 45 (1), p. 33-40 | Abstract: | A dominant cost for query evaluation in modern massively distributed systems is the number of communication rounds. For this reason, there is a growing interest in single-round multiway join algorithms where data is first reshuffled over many servers and then evaluated in a parallel but communication-free way. The reshuffling itself is specified as a distribution policy. We introduce a correctness condition, called parallel-correctness, for the evaluation of queries w.r.t. a distribution policy. We provide a semantical characterization for when conjunctive queries (and extensions thereof) are parallel-correct and give matching complexity bounds for the associated decision problem. Motivated by scenarios for workload optimization, we further consider the problem of parallel-correctness transfer from a query Q to a query Q', that is, whether Q' is parallel-correct for all distribution policies for which Q is parallel-correct. In this case, Q' can always be evaluated after Q without repartitioning the data. We provide a semantical characterization for parallel-correctness transfer and provide matching complexity bounds for the associated decision problem for conjunctive queries (and extensions). Finally, we investigate restrictions of queries and families of distribution policies with better complexities, including, for instance, the Hypercube distributions. | Notes: | [Ameloot, Tom J.; Ketsman, Bas; Neven, Frank] Hasselt Univ, Hasselt, Belgium. [Ameloot, Tom J.; Ketsman, Bas; Neven, Frank] Transnat Univ Limburg, Limburg, Belgium. [Geck, Gaetano; Schwentick, Thomas] TU Dortmund Univ, Dortmund, Germany. [Ameloot, Tom J.; Ketsman, Bas] Flanders FWO, Res Fdn, Brussels, Belgium. | Document URI: | http://hdl.handle.net/1942/21801 | ISSN: | 0163-5808 | e-ISSN: | 1943-5835 | DOI: | 10.1145/2949741.2949750 | ISI #: | 000377814200008 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2017 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
p33-ameloot.pdf Restricted Access | Published version | 478.22 kB | Adobe PDF | View/Open Request a copy |
sigmodrecord.pdf | Peer-reviewed author version | 355.02 kB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
6
checked on Oct 12, 2024
Page view(s)
82
checked on Sep 6, 2022
Download(s)
262
checked on Sep 6, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.