Source-linked AI summary
Communication Steps for Parallel Query Processing
Paul Beame, Paraschos Koutris, Dan Suciu
TL;DR
The paper studies communication complexity in parallel relational query processing, where communication rather than disk access is the main bottleneck. It develops lower and upper bounds for one-round general communication and multi-round tuple-based communication, characterizing space-exponent requirements and round–replication tradeoffs.
Problem
Communication is a central bottleneck in large-scale query processing, motivating a complexity analysis of relational queries executed across many servers.
Method
The paper establishes lower and upper bounds for full conjunctive queries in a one-round model allowing arbitrary messages and a multi-round tuple-based MPC model with restricted later-round communication and routing.
Results
For connected queries in one round, the space exponent must satisfy ε ≥ 1 − 1/τ∗(q), while tree-like queries in tuple-based MPC require at least ⌈log_kε(diam(q))⌉ rounds and admit nearly matching algorithms.
Takeaways & Limitations
The results characterize one-round replication through fractional vertex cover and establish a near-matched tradeoff between rounds and replication for multi-round tuple-based computation.
Takeaways & Limitations
The upper bounds hold only on matching databases, and the one-round lower-bound theorem assumes queries have no unary relations.
Abstract
from arXiv · showhide
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. For a single round of communication, we give lower bounds in the strongest possible model, where arbitrary bits may be exchanged; we show that any algorithm requires $\varepsilon \geq 1-1/τ^*$, where $τ^*$ is the fractional vertex cover of the hypergraph of $q$. We also give an algorithm that matches the lower bound for a specific class of databases. For multiple rounds of communication, we present lower bounds in a model where routing decisions for a tuple are tuple-based. We show that for the class of tree-like queries there exists a tradeoff between the number of rounds and the space exponent $\varepsilon$. The lower bounds for multiple rounds are the first of their kind. Our results also imply that transitive closure cannot be computed in O(1) rounds of communication.
1 Introduction
The paper studies communication as the central bottleneck in massively parallel query processing, exposing tradeoffs between communication rounds and per-server data. It develops strong one-round and multi-round lower bounds with matching or nearly matching algorithms.
- Motivation: Communication steps and exchanged data are the dominant complexity parameters in big-data query processing.Global reshuffling requires synchronization and can be slowed by stragglers or node failures.
- One-round results: A tuple-independent algorithm matches the one-round lower bound on matching databases by using an optimal fractional vertex cover to split input data.For example, the path query L2 has ε = 0, while the cycle query C3 has ε = 1/3.
- One-round results: ε ≥ 1 − 1/τ*(q) is required for one-round computation of every connected conjunctive query, even with arbitrary bit messages.The bound holds over matching databases and is optimal there.
- Multi-round results: For tree-like queries, the number of tuple-based communication rounds trades off with ε through the query-plan depth.The lower bound is nearly matched by a tuple-based algorithm, and the framework yields the first lower bounds for multiple MapReduce rounds.
- Multi-round results: For sparse undirected graphs, transitive closure and connected components require Ω(log p) rounds when ε < 1.This contrasts with two-round MapReduce algorithms for sufficiently dense graphs.
2 Preliminaries
The MPC model evaluates full conjunctive queries using p workers, with communication rounds and a space exponent controlling per-round replication. The preliminaries define query structure, input distributions, and query characteristics used in subsequent bounds.
- Massively Parallel Communication: The MPC(ε) model uses p workers, distributes N input bits evenly, and measures complexity by the number of communication rounds.Each round alternates local computation with global communication.
- Massively Parallel Communication: The space exponent ε measures replication: each round exchanges O(p^ε) times the input size, with ε = 0 meaning no replication.ε = 1 is degenerate because each server can receive the entire input.
- Massively Parallel Communication: The model permits shared random bits and small input-independent failure probability; randomized lower bounds use Yao’s Lemma.Yao’s Lemma converts deterministic distributional failures into failures of randomized algorithms on some input.
- Conjunctive Queries: The paper studies full conjunctive queries without self-joins, represented by a hypergraph whose nodes are variables and hyperedges are atom variable sets.Queries may be evaluated by JOIN-REPORTING or JOIN-WITNESS.
- Query Structure: A query’s characteristic is χ(q) = k + ℓ − ∑j aj − c; tree-like queries are connected queries with χ(q) = 0, and connected subqueries remain tree-like.Contraction q/M contracts selected hypergraph edges and supports inductive arguments about query structure.
- Vertex Cover and Edge Packing: The fractional covering number τ*(q) is the common optimum of the fractional vertex-cover and dual edge-packing LPs.A vertex cover assigns nonnegative weights to variables so every atom receives total weight at least 1.
- Input Distribution: Matching databases remove skew, but the paper’s upper bounds apply only to them, whereas its lower bounds also hold for arbitrary instances.Each relation has n tuples and every attribute contains each domain value exactly once.
3 One Communication Step
The section defines the one-step space exponent and presents HYPERCUBE, which achieves the optimal exponent for matching databases. It also proves matching lower bounds, characterizes zero-replication queries, and extends hardness to JOIN-WITNESS.
- The space exponent is the smallest ε allowing computation in one communication step in the MPC(ε) model.
- Algorithm for One Round: HYPERCUBE assigns share exponents from a fractional vertex cover and hashes each variable to partition tuples across servers.Each tuple is sent to servers matching its hashes on present attributes and replicated across the remaining dimensions; servers then output locally derivable answers.
- Algorithm for One Round: For matching databases, HYPERCUBE computes any connected conjunctive query in one round with ε = 1 − 1/τ*, with failure probability at most exp(−O(n/p^ε)).Here τ* is the fractional vertex-cover value used to set the share exponents.
- Lower Bound for One Round: Any randomized one-round algorithm requires ε ≥ 1 − 1/τ* for connected conjunctive queries, even on matching databases.Below this threshold, deterministic algorithms report only O(E[|q(I)|]/p^{τ*(1−ε)−1}) answers in expectation, and randomized algorithms fail with probability n^{-O(1)}.
- Extensions: A query has space exponent zero exactly when a variable occurs in every atom, although this characterization is restricted to matching databases and excludes unary relations.The lower-bound framework assumes no unary relations; the stated condition need not characterize one-round computation on arbitrary inputs.
- Extensions: The lower bounds extend to JOIN-WITNESS: the query R(w), S1(w, x), S2(x, y), S3(y, z), T(z) has no one-round MPC(ε) algorithm for ε < 1/2.
4 Multiple Communication Steps
The paper develops upper and lower bounds for multi-round relational query processing, using tuple-based communication to relate rounds, replication, and query structure. For tree-like queries, the bounds are nearly matching, while connected-component computation requires Ω(log p) rounds for fixed ε < 1.
- Tuple-Based MPC: Tuple-based MPC permits unrestricted first-round communication, then restricts later messages to join tuples with content-dependent routing.The model captures multi-round MapReduce-style algorithms while preventing arbitrary information from being encoded through unrestricted tuple routing.
- Upper Bounds: Queries with an r-round plan can be computed in r rounds on matching databases using operators that are each computable in one step.The paper defines query classes recursively by substituting one-step-computable views into a query plan.
- Upper Bounds: For ε = 1/2, L16 is computed in 2 rounds by computing four L4 subqueries in parallel and then joining their results.Each L4 subquery has fractional vertex cover 2 and is computable in one step under this ε.
- Upper Bounds: Two rounds with replication O(1) compute SPk under MPC(0), whereas one round requires replication O(p1−1/k).The two-round plan first computes each local join qi and then joins all qi on the common variable z.
- Lower Bounds: For tree-like queries, the lower bound ⌈log_kε(diam(q))⌉ and upper bound ⌈log_kε(rad(q))⌉ + 1 differ by at most one round.When ε < 1/2, the bounds match because kε = 2 and the diameter-radius relationship is tighter for tree-like queries.
- Lower Bounds: For fixed ε < 1, CONNECTED-COMPONENTS cannot be computed in o(log p) rounds in tuple-based MPC.The theorem applies to arbitrary input graphs; the paper also notes a one-round gap for the exact number of rounds for C5 when ε = 0.
5 Conclusion
The paper characterizes communication-round and replication tradeoffs for relational queries. It gives matching or nearly matching simple algorithms and lower bounds, with multi-round bounds applying to the restricted tuple-based model.
- Conclusion: The one-round space exponent is governed by the fractional vertex-cover number, ε = 1 − 1/τ∗.For multiple rounds, the paper derives a tree-like-query tradeoff between r and ε and gives matching or nearly matching upper bounds.