AitF: FULL: Query Processing with Optimal Communication Cost

大数据分析正在以两种方式改变传统的查询处理。首先是从单服务器或小规模并行关系数据库转向大规模分布式体系结构，其中在计算单个查询期间使用数百或数千台服务器。第二个是正在发出的查询的复杂性增加，从单连接或星型连接到复杂的类似图的结构化查询。该项目为大型分布式系统的查询处理开发了新的算法，这些算法针对通信成本进行了优化，然后在开源大数据管理系统和服务中实现和评估这些算法。该项目研究了一种新的查询计算方法，该方法一次计算整个查询，取代了传统的基于查询计划的方法。这个项目的理论部分建立在一个新的模型上，称为大规模并行通信模型（MPC），其中通信是唯一的成本。系统的开发是在Myria大数据管理系统和服务上进行的。该项目的智力价值在于推进了现代大规模无共享集群中查询评估的理论和系统方法的最新水平。它开发了新的基本算法，用于处理大规模分布式架构上的查询，具有可证明的最佳通信成本。该项目在一个系统中实现和部署这些算法，验证并告知理论模型。特别是，该项目做出了以下贡献：它为倾斜数据开发了可证明的最优单轮算法；研究了如何以及何时使用多轮来进一步降低通信成本；它在多达1000个工作进程的集群上实验这些新算法；提出了一种新的基于异构硬件的大型无共享架构的通信成本理论模型。该项目的更广泛影响是为大规模并行查询处理提供一个新的体系结构，其中传统的多步骤、单连接查询计算方法被新的、单步骤、多连接算法所取代。这一变化有可能带来更高效的大数据分析引擎，使数据分析师能够更有效地探索大型数据集。作为即时应用，该项目将影响已经使用Myria大数据管理系统和服务的领域科学家。这个项目中的所有算法发现都将在Myria系统中实现，并将显著提高查询性能，允许领域科学家对他们的数据进行更复杂的分析和探索。

Big Data analytics is changing traditional query processing in two ways. The first is a shift from single server or small-scale parallel relational databases to massively distributed architectures, where hundreds or thousands of servers are used during the computation of a single query. The second is an increased complexity in the queries being issued, from single- or star-joins, to complex graph-like structured queries. This project develops new algorithms for query processing over large distributed systems, which are optimized for the cost of communication, then implements and evaluates these algorithms in an open-source big data management system and service.The project studies a new approach to query evaluation that computes the entire query at once, replacing the traditional approach based on a query plan. The theoretical part of this project builds on a new model, called the Massively Parallel Communication model (MPC), where the communication is the only cost. The system development is performed over the Myria big data management system and service.The Intellectual Merit of the project consists in advancing the state of the art in both the theory and systems approaches to query evaluation in modern, massive-scale shared-nothing clusters. It develops new, fundamental algorithms for processing queries over massively distributed architectures, with a provably optimal communication cost. The project implements and deploys these algorithms in a system, validating and informing the theoretical model. In particular, the project makes the following contributions: it develops provably optimal, one-round algorithms for skewed data; it studies how and when multiple rounds can be used to further reduce the communication cost; it experiments with these novel algorithms on clusters with up to 1000 worker processes; and it develops a new theoretical model for the communication cost on large shared-nothing architectures with heterogeneous hardware.The Broader Impact of the project is to contribute to a new architecture for massively parallel query processing, where the traditional multi-step, single-join query evaluation approaches are replaced with novel, single-step, multi-join algorithms. This change has the potential to lead to more efficient big data analytics engines, allowing data analysts to explore large datasets more efficiently. As an immediate application, the project will impact the domain scientists who already use the Myria big data management system and service. All algorithmic discoveries in this project will be implemented in the Myria system, and will significantly improve query performance, allowing domain scientists to conduct more complex analytics and explorations over their data.