ACM通信

大规模并行系统单轮多连接评估的数据分区推理

在大数据时代，评估对大量数据的查询是一个主要的挑战。现代大规模并行系统(如Spark)将查询回答组织为一系列轮，每个轮由一个不同的通信阶段和一个计算阶段组成。通信阶段在可用服务器上重新分配数据，而在随后的计算阶段，每个服务器对其本地数据执行实际的计算。人们对评估多路连接的单轮算法越来越感兴趣，在这种算法中，数据首先在服务器上重新洗刷，然后以并行但无通信的方式进行评估。由于在这样的系统中，由数据重组引起的通信量是主要成本，我们引入了一个关于数据分区的推理框架，以检测何时可以避免数据重组步骤。具体地，我们形式化了决策问题的并行正确性和并行正确性的传递，提供了语义表征，并获得了紧密的复杂性边界。

回到顶部

1.简介

这项工作的后台场景是大规模数据分析，利用大量的并行性来回答多个数据库表上的复杂连接查询。例如，正如Chu等人所描述的，⁷数据分析引擎面临着新的工作负载类型，其中多个大型表被连接起来，或者查询图有周期。此外，最近的内存系统(例如Refs。^{11，13，19，23})可以利用多台服务器将数据放入主存。Koutris和Suciu¹²引入了大规模并行通信(MPC)模型，以促进对无共享并行架构上查询处理复杂性的理解。对于这类系统，性能不再像传统系统那样由对外部内存的I/O请求数量决定，而是由查询执行期间重新洗刷数据的通信成本决定。当需要在几轮中对查询进行评估时，这种重新划分可能会对整个数据库进行重新划分，因此代价非常昂贵。

在传统的分布式查询计算中，多连接查询在连接树上分几个阶段计算，每一步都可能通过网络传输数据，而我们只关注MPC模型中的查询计算算法一个一轮沟通。该算法由两个阶段组成:a分布相(其中数据在服务器上重新分区或重新洗牌)，然后是计算阶段，其中每个服务器通过在不进行任何进一步通信的情况下评估交付本地数据的查询来独立地贡献查询答案。我们将这种算法称为通用的一轮算法。Afrati和Ullman¹控件中计算多连接查询的算法单沟通。该算法使用的技术可以追溯到Ganguly等人。⁹Beame et al。^4，5改进算法，命名超立方体，证明了它是一种用于单轮分布式连接查询计算的通信最优算法。

通用的单轮HyperCube算法需要对基本数据进行重新洗牌每一个单独的查询。由于重新洗牌引起的通信量是巨大的，所以检测何时可以避免重新洗牌步骤是很重要的。我们提出了一个关于数据分区的推理框架，用于通用的一回合算法的查询求值任意的分发策略，而不仅仅是HyperCube算法产生的策略。为了以尽可能广泛的重新划分策略为目标，初始分发阶段因此被建模为一个分发策略任何从事实到服务器子集的映射。

优化框架由两个具体场景推动。在第一个场景中，我们假设数据已经在服务器上分区，我们想知道给定的查询是否可以在给定的数据分布上正确地计算不需要重新洗牌数据。在第二种场景中，数据分布可能是未知的或隐藏的，但是可以知道它允许正确地计算以前的查询在这里，我们询问这个知识是否能保证给定(下一个)查询不需要重新洗牌就能被正确计算。为此，我们形式化了以下决策问题:

• Parallel-Correctness:给定一个分布策略和一个查询，我们能否确保相应的通用一轮算法总是正确地计算出查询结果，不管实际数据是多少?
• Parallel-Correctness传输:给定两个查询

  ---

  没有发现记录