CRII: III: Partition-aware Parallel Query Processing

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

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.