Improving Preemptive Prioritization via Statistical Characterizationof OLTP LockingDavid T. McWherter Bianca Schroeder Anastassia Ailamaki∗Mor Harchol-Balter†AbstractOLTP and transactional workloads are increas-ingly common in computer systems, ranging from e-commerce to warehousing to inventory management.It is valuable to provide priority scheduling in thesesystems, to reduce the response time for the most im-portant clients, e.g. the “big spenders”. Two-phaselocking, commonly used in DBMS, makes prioritiza-tion difficult, as transactions wait for locks held by oth-ers regardless of priority. Common lock scheduling so-lutions, including non-preemptive priority inheritanceand preemptive abort, have performance drawbacks forTPC-C type workloads.The contributions of this paper are two-fold: (i) Weprovide a detailed statistical analysis of locking in TPC-C workloads with priorities under several common pre-emptive and non-preemptive lock prioritization policies.We determine why non-preemptive policies fail to suf-ficiently help high-priority transactions, and why pre-emptive policies excessively hurt low-priority transac-tions. (ii) We propose and implement a policy, POW,that provides all the benefits of preemptive prioritiza-tion without its penalties.1 IntroductionLong delays and the accompanying unpredictablylarge response times1are a source of frustration in on-line transaction processing (OLTP) database systems.In many applications, consistently low response timesare essential for users. Consider, for example, an onlinestock market with significant price volatility. A traderissues trade orders based on constantly varying market∗Supported by NSF grants CCR-0113660, IIS-0133686, CCR-0205544, and BES-0329549†Supported by NSF grants CCR-0133077, CCR-0311383,0313148, and by IBM via 2003 Pittsburgh Digital GreenhouseGrant.1Response time is defined as the time from when a transactionis submitted until it completes, including restarts.prices, and any delay creates potential for huge profitloss.Minimizing delay and its unpredictability is muchmore valuable for some users than for others. A tradermaking thousands of large-volume trades a day may bewilling to pay more for reduced delays on trades. Onthe other hand, a trader making only one trade a monthmay accept much more variable response times. Thus,we divide transactions into two classes: high- and low-priority, based on whether the transaction is issued bya high- or low-paying customer. Our primary goal is toprioritize high-priority transactions to execute as if inisolation of low-priority transactions, and ensure low-priority transactions do not delay high-priority trans-actions. Second, low-priority transactions must not beexcessively penalized.Transaction prioritization can be important incountless contexts. In commercial OLTP, for instance,customers who experience many excessive delays maybecome frustrated, and take their business elsewhere.Giving high-priority service to customers who rou-tinely buy expensive merchandise will maximize thecompany’s profits. As a testament to the impor-tance of transaction prioritization, it is provided inmost major commercial DBMS: DB2 offers db2gov andQueryPatroller[13, 4] and Oracle offers DRM [15]. Wehave previously shown that CPU scheduling is ineffec-tive for prioritization in OLTP applications (such asTPC-C), while lock scheduling is highly effective [14].Unfortunately, all the above commercial systems focuson CPU, not lock prioritization. Additionally, there islittle research on lock scheduling in fully implementedgeneral-purpose DBMS, as most are analytical or sim-ulation studies, or focus on RTDBMS.Many open questions remain for lock scheduling ingeneral-purpose DBMS. Of these, we focus on whetherthe DBMS should use a preemptive or a non-preemptivescheduling policy. Each type of policy has advantagesand disadvantages, and there is no consensus as towhich is best. While preemptive policies allow high-priority transactions to reduce lock waiting time by1killing other lock holders, rollbacks and re-executionsmay be too costly. Non-preemptive policies avoid thesepreemptive overheads, but high-priority transactionsmay wait for low-priority transactions to complete be-fore making progress.The first contribution of our paper is a perfor-mance evaluation and in-depth statistical analysis oflock activity in TPC-C, for common scheduling poli-cies. For non-preemptive policies, such as queue re-ordering (NPrio) and priority inheritance (NPrioin-her), high-priority transactions are poorly isolatedfrom low-priority transactions, resulting in variable andhigh response times. By contrast, preemptive policies(PAbort) yield good high-priority performance, but ex-cessively penalize low-priority transactions.To determine why non-preemptive policies fail toisolate high-priority transactions, we address four ques-tions: (i) How many lock requests do transactions waitfor? (ii) How long are lock waits? (iii) How long dotransactions wait for current lock holders versus forother waiting transactions? (iv) How do lock waits af-fect response time? We show that the common policiesprimarily fail to eliminate wait excess: the time spentwaiting for current lock holders to release locks. To de-termine why preemptive policies devastate low-prioritytransactions, we investigate potential reasons: (i) roll-back costs (ii) preemption frequency, and (iii) wastedwork per preemption. Surprisingly, we find that mostof these issues are largely relevant, and wasted workper preemption dominates exclusively.The second contribution of our paper is a demonstra-tion that a little-known and unevaluated lock schedul-ing policy from the field of distributed databases,Preempt-On-Wait [16] (POW), excels over all the abovepolicies. It combines the excellent high-priority perfor-mance of preemptive policies with the small penalty tolow-priority transactions typical with non-preemptivepolicies.The intuition behind POW is that if a high-prioritytransaction H needs a lock held by a low-priority trans-action L, H should only preempt L if L will hold thelock a long time. We find that whether or not L waitsin another lock queue is a highly accurate indicator ofL’s remaining holding time. Thus, POW only preemptslow-priority transactions that both wait for a lock andblock a high-priority transaction.Our evaluation focuses on the TPC-C OLTP work-load with Shore [3] (a modern prototype with transac-tion management, 2PL, and