Collaborative Research: III: Small: High-Performance Scheduling for Modern Database Systems

这个项目的目标是开发和测试调度可并行数据库查询流的算法。挑战在于查询是非常异构的。它们的并行性不同，并且它们的并行性水平也会随着时间的推移而变化。它们的固有工作量也有所不同。由于资源有限，如何在不同的查询之间分配这些资源并不明显。该项目开发模型来优化现代数据库中这些可并行查询的调度。除了开发新的建模工具外，该项目还包括开发新的计算机科学课程，向未来的研究人员教授建模。本项目旨在通过随机建模方法改进现代数据库的查询调度。大多数当前系统以先到先得的顺序提供查询，这种策略可能导致排队时间过长。此外，这个简单的调度策略没有考虑到不同类型查询的并行性和服务需求的不同级别。利用随机模型和排队理论，该项目开发了新的调度策略，最大限度地利用系统资源，如计算和内存，以大大减少查询延迟。该项目的目标是在固定的硬件集和云中进行调度，云中可以动态缩放资源以满足用户需求。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The goal of this project is to develop and test algorithms for scheduling a stream of parallelizable database queries. The challenge is that queries are very heterogeneous. They differ in how parallelizable they are, and their level of parallelizability can also change over time. They also differ in their inherent amount of work. Given limited resources, it is not obvious how to allocate these resources across the different queries over time. This project develops models to optimize the scheduling of these parallelizable queries in modern databases. In addition to developing new modeling tools, this project includes the development of new computer science courses to teach modeling to future researchers.This project aims to improve query scheduling in modern databases via a stochastic modeling approach. Most current systems serve queries in a First-Come-First-Served order, a policy that can lead to excessive queueing times. Furthermore, this simple scheduling policy does not account for the differing levels of parallelizability and service requirements of different types of queries. Using stochastic models and queueing theory, the project develops new scheduling policies that maximize the utilization of system resources such as compute and memory in order to greatly reduce query latencies. The project targets scheduling both on a fixed set of hardware and in the cloud where resources can be scaled dynamically to meet user demand.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.