Transaction Scheduling: From Conflicts to Runtime Conflicts

Yang Cao, Wenfei Fan, Weijie Ou, Rui Xie, Wenyue Zhao

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

This paper studies how to improve the performance of main memory multicore OLTP systems for executing transactions with conflicts. A promising approach is to partition transaction workloads into mutually conflict-free clusters, and distribute the clusters to different cores for concurrent execution. We show that if transactions in each cluster are properly scheduled, transactions that are traditionally considered conflicting can be executed without conflicts at runtime. In light of this, we propose to schedule transactions and reduce runtime conflicts, instead of partitioning based on the conventional notion of conflicts. We formulate the transaction scheduling problem to minimize runtime conflicts, and show that the problem is NP-complete. This said, we develop an effcient scheduling algorithm to improve parallelism. Moreover, for transactions that are not packed in batches, we show that runtime conflict analysis also helps reduce conflict penalties, by proposing a proactive deferring method. Using standard and enhanced benchmarks, we show that on average our scheduling and proactive deferring methods improve the throughput of existing partitioners and concurrency control protocols by 131% and 109%, respectively, up to 294% and 152%.
Original languageEnglish
Article number26
Pages (from-to)1-26
JournalProceedings of the ACM on Management of Data
Issue number1
Publication statusPublished - 30 May 2023
EventACM SIGMOD International Conference on Management of Data 2023 - Seattle, United States
Duration: 18 Jun 202323 Jun 2023

Keywords / Materials (for Non-textual outputs)

  • transaction scheduling
  • transaction processing
  • concurrency control


Dive into the research topics of 'Transaction Scheduling: From Conflicts to Runtime Conflicts'. Together they form a unique fingerprint.

Cite this