Document Server@UHasselt >
Research >
Research publications >

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 J.
Geck, Gaetano
Ketsman, Bas
Neven, Frank
Schwentick, Thomas
Issue Date: 2016
Citation: 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.
URI: http://hdl.handle.net/1942/21801
DOI: 10.1145/2949741.2949750
ISI #: 000377814200008
ISSN: 0163-5808
Category: A1
Type: Journal Contribution
Validation: ecoom, 2017
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
published version478.22 kBAdobe PDF
Peer-reviewed author version386.34 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.