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.