AitF: FULL: Query Processing with Optimal Communication Cost

AitF：FULL：具有最佳通信成本的查询处理

基本信息

批准号：
1535565
负责人：
Dan Suciu
金额：
$ 72万
依托单位：
University of Washington
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2015
资助国家：
美国
起止时间：
2015-08-15 至 2020-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1535565&HistoricalAwards=false
关键词：
AitF FULL Query Processing Optimal

项目摘要

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.

大数据分析正在通过两种方式更改传统查询处理。第一个是从单个服务器或小规模并行关系数据库转移到大量分布的架构，在计算单个查询期间，使用了数百或数千台服务器。第二个是从单一或星际连接到复杂的图形结构化查询的要查询的复杂性提高。该项目开发了针对大型分布式系统查询处理的新算法，这些算法是针对通信成本进行了优化的，然后在开源大数据管理系统和服务中实施并评估这些算法的。项目研究的新方法来查询评估，以基于查询计划替换了基于查询计划的整个疑问，以替代了整个疑问。该项目的理论部分建立在一个新模型的基础上，称为“大规模并行通信模型”（MPC），其中通信是唯一的成本。该系统开发是通过米里亚大数据管理系统和服务进行的。该项目的智力优点在于在理论和系统方法中都在现代，大规模的共享集群中提高最新技术的状态。它开发了新的，基本的算法，用于处理大量分布的架构的查询，并具有最佳的沟通成本。该项目将这些算法实现并部署在系统中，从而验证和告知理论模型。特别是，该项目做出了以下贡献：它为偏斜数据开发了可证明的最佳单轮算法；它研究了如何以及何时使用多个回合来进一步降低沟通成本；它可以在最多1000个工作过程的簇上使用这些新型算法进行实验；它开发了一种新的理论模型，用于与具有异质硬件的大型共享架构的通信成本。该项目的更广泛影响是为新的建筑做出贡献，用于大规模平行的查询处理，传统的多步，单步质量查询评估方法由小说，单步，单型，多型 - join Algoriths代替。这种变化有可能导致更有效的大数据分析引擎，从而使数据分析师更有效地探索大型数据集。作为立即应用，该项目将影响已经使用Myria Big Data Management System和Service的领域科学家。该项目中的所有算法发现都将在Myria系统中实施，并将大大提高查询性能，从而使域科学家能够对其数据进行更复杂的分析和探索。