David T. McWherter

Sharing DBMS among Multiple Users while Providing Performance Isolation: Analysis and Implementation Degree Type: Ph.D. in Computer Science
Advisor(s): Mor Harchol-Balter
Graduated: August 2008

Abstract:

Database Management Systems (DBMS) are at the core of many modern applications, ranging from e-Commerce (e.g. Amazon.COM), web applications (e.g. flickr), online banking, telephony, and even traditional brick-and-mortar retailers. DBMS can be a significant source of delay in these applications, making DBMS the performance bottleneck: users can spend orders of magnitude more time waiting for the DBMS than for anything else (e.g. the web server). Delays often frustrate users, which hurts companies' profits, since frustrated users buy less and are more likely to take their business elsewhere. Adding more capacity (hardware) can reduce delays, but it is usually both more difficult and costly to add capacity to DBMS than to other computer systems (e.g. web servers). Without adding capacity, prioritization can exploit the fact that some users (or queries) are more important than others. Prioritization can give better performance and less delay to high-priority (important) users at the expense of low-priority (less important) users. While prioritization is usually easy in computer systems, prioritization in DBMS is extremely difficult due to complexities inherent to DBMS architectures. As a result, many basic questions concerning DBMS prioritization remain open.

This thesis studies the implementation of prioritization in DBMS (commonly in commercial applications) with high- and low-priority users. The goal is to provide high-priority users with performance isolation, whereby high-priority response times are not affected by low-priority users. I consider common approaches to provide prioritization and experiment with real-world DBMS and benchmark workloads to ensure that the results are applicable to real-world systems. The heart of this work is a performance evaluation of common prioritization approaches, coupled with in-depth statistical analyses to reveal each approach's deficiencies. Our evaluations reveal previously unknown and non-intuitive performance trends about DBMS prioritization, and our analyses provide insight for developing new algorithms and new models for more effective DBMS prioritization. Key algorithmic and modeling contributions of this thesis include the Preempt-On-Wait (POW) lock prioritization algorithm, and the Isolated Demand Decomposition (IDD) modeling method.

Thesis Committee:
Mor Harchol-Balter (Chair)
Christos Faloutsos
Bruce M. Maggs
Hans Zeller

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
DBMS, Databases, Multi-user system, Resource allocation, Query Prioritization