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's 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.

156 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu