Invited talk: Communication Cost in Parallel Query Processing

Fix a full, conjunctive query, and consider the following problem: what is the amount of communication required to compute the query in parallel on p servers, over a large database instance? We define the Massively Parallel Communication (MPC) model, where the computation proceeds in rounds consisting of local computations followed by a global reshuffling of the data. Servers have unlimited computational power and are allowed to exchange any data, the only cost parameters are the number of rounds and the maximum amount of communication per server. There is a tradeoff between these two parameters. I will describe tight bounds on the amount of communication for the case of a single round, expressed in terms of a fractional edge packing of the query expression, and will given some weaker results for multi-round algorithms. Both these settings assume data with no skew. Finally, I will briefly discuss the single round, skewed-data case. Joint work with Paul Beame and Paris Koutris. 10: 00 10: 30 Breakfast & coffee

Authors

• Dan Suciu

Keywords

No keywords are indexed for this paper.