CRII: III: Partition-aware Parallel Query Processing

社会正变得越来越受数据驱动。为了有效地处理不断增加的数据量，当前的数据管理系统被设计为通过有效地扩展到数千个计算单元来支持大规模并行。这些系统成功的一个关键因素是，它们在处理之前将输入实例划分为特定的布局。分区的目标是提高数据的局部性，即，经常一起处理的数据应该位于同一物理机器中。现代分布式大规模系统采用几种类型的简单分区方案，但这些方案的简单性限制了可以实现的数据局部性。该项目旨在研究-理论和实践-更先进的分区策略如何进一步加速并行查询处理，并加快跨多个领域的各种应用程序中的数据到知识管道。它将重新思考数据分区，并在现代数据处理的背景下，在一个更全面的框架中检查它。这个项目的目的是执行一个端到端的调查如何设计先进的数据分区技术可以影响精确和近似并行查询处理。为了实现这一研究目标，本项目侧重于三个相互关联的方向。第一个重点是建立数据分区技术的正式基础，并研究分区理论上如何影响精确的查询处理。特别是，这个推力将调查系统参数之间的理论权衡，如存储开销，工作负载平衡，并在分区实例上执行查询的效率。第二个重点将探讨如何近似查询处理可以受益于智能分区方法以及。最后，第三个重点将开发和实施新的分区策略，旨在填补现有技术的设计差距，并解决现有分区技术的一些缺点。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

Society is becoming increasingly data-driven. In order to efficiently handle the increasing amount of data, current data management systems are designed to support massive parallelism by scaling effectively to thousands of computing units. A critical component in the success of these systems is that they partition the input instance in specific layouts prior to processing. The goal of the partitioning is to improve data locality, i.e., data that is often processed together should be located in the same physical machine. Modern distributed large-scale systems adopt several types of simple partitioning schemes, but the simplicity of these schemes limits the data locality that can be achieved. This project aims to study - both theoretically and in practice - how more advanced partitioning strategies can further accelerate parallel query processing and speed up the data-to-knowledge pipeline in various applications across multiple domains. It will rethink data partitioning from the ground up, and examine it in a more holistic framework in the context of modern data processing.This project aims to perform an end-to-end investigation of how the design of advanced data partitioning techniques can impact both exact and approximate parallel query processing. To achieve this research goal, this project focuses on three interconnected directions. The first thrust focuses on establishing formal foundations for data partitioning techniques, and study how partitioning theoretically impacts exact query processing. In particular, this thrust will investigate the theoretical tradeoffs between system parameters such as storage overhead, workload balancing, and efficiency for query execution over the partitioned instance. The second thrust will explore how approximate query processing can be benefited from smart partitioning methods as well. Finally, the third thrust will develop and implement novel partitioning strategies that aim to fill design gaps in existing techniques and address some of the drawbacks of existing partitioning techniques.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.