Communication Steps for Parallel Query Processing

Understand

We consider the problem of computing a relational query $q$ on a large input database of size $n$, using a large number $p$ of servers.

• The computation is performed in rounds, and each server can receive only $O(n/p^{1-\varepsilon})$ bits of data, where $\varepsilon \in [0,1]$ is a parameter that controls replication.
• We examine how many global communication steps are needed to compute $q$.
• We establish both lower and upper bounds, in two settings.