Parallel-Correctness and Transferability for Conjunctive Queries

In traditional database systems, the complexity of query processing for large datasets is mainly determined by the number of IO requests to external memory. A factor dominating complexity in modern massively distributed database systems, however, is the number of communication steps. Motivated by recent in-memory systems like Spark and Shark, Koutris and Suciu introduced the massively parallel communication model (MPC) where computation proceeds in a sequence of parallel steps each followed by global synchronization of all servers. In this model, evaluation of conjunctive queries and skyline queries has been considered. Of particular interest in the MPC model are the queries that can be evaluated in one round of communication. To this end, data is first redistributed among the nodes, according to some distribution policy, and then each node computes a partial result on its own. We considered the correctness of this particular evaluation algorithm: a query Q is parallel-correct for a given distribution policy P, if for any instance I, the evaluation of Q(I) equals the union of the evaluation of Q on the nodes' local instances as induced by P. We studied the complexity of deciding parallel-correctness. For various representations of distribution policies, we obtained an upper bound of \Pi^p_2. For a simple (explicit) representation, we could also provide a matching lower bound via a reduction from \Pi_2-QBF. One-round evaluation algorithms redistribute data for the evaluation of every query. In an attempt to minimize the amount of necessary communication, it is natural to also consider parallel-correctness transfer from a query Q to another query Q', i. e. when Q' is parallel-correct under every distribution policy that Q is parallel-correct under. Again, we studied the complexity of deciding parallel-correctness transfer from Q to Q' and obtained an upper bound of \Pi^p_3. Also, we obtained a matching lower bound via a reduction from \Pi_3-QBF. We note that the evaluation algorithm on which our results are based, is---for a specific family of distribution policies---well-known as the hypercube algorithm.

Authors

• Gaetano Geck

Keywords

No keywords are indexed for this paper.