{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:53:07Z","timestamp":1773481987417,"version":"3.50.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>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 efficient 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%.<\/jats:p>","DOI":"10.1145\/3588706","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-26","source":"Crossref","is-referenced-by-count":6,"title":["Transaction Scheduling: From Conflicts to Runtime Conflicts"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7984-3219","authenticated-orcid":false,"given":"Yang","family":"Cao","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5149-2656","authenticated-orcid":false,"given":"Wenfei","family":"Fan","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Computing Sciences; University of Edinburgh; BDBC; &amp; Beihang University, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1996-5439","authenticated-orcid":false,"given":"Weijie","family":"Ou","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Computing Sciences, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5253-5137","authenticated-orcid":false,"given":"Rui","family":"Xie","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Computing Sciences, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2941-2658","authenticated-orcid":false,"given":"Wenyue","family":"Zhao","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"[n. d.]. Atomic Builtins - Using the GNU Compiler Collection (GCC). https:\/\/gcc.gnu.org\/onlinedocs\/gcc\/_005f_005fatomic-Builtins.html."},{"key":"e_1_2_2_2_1","unstructured":"[n. d.]. DBx1000. https:\/\/github.com\/yxymit\/DBx1000."},{"key":"e_1_2_2_3_1","unstructured":"[n. d.]. H-Store. https:\/\/github.com\/apavlo\/h-store."},{"key":"e_1_2_2_4_1","unstructured":"[n. d.]. Strife. https:\/\/github.com\/zhr1201\/STRIFE-public."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3181853"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/32204.32220"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00742-4"},{"key":"e_1_2_2_8_1","volume-title":"O'Neil","author":"Berenson Hal","year":"1995","unstructured":"Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O'Neil, and Patrick E. O'Neil. 1995. A Critique of ANSI SQL Isolation Levels. In SIGMOD. 1--10."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/356842.356846"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/319996.319998"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.234182"},{"key":"e_1_2_2_12_1","volume-title":"Grigorev","author":"Burdakov Aleksey V.","year":"2020","unstructured":"Aleksey V. Burdakov, Victoria Proletarskaya, Andrey D. Ploutenko, Oleg Ermakov, and Uriy A. Grigorev. 2020. Predicting SQL Query Execution Time with a Cost Model for Spark Platform. In IoTBDS. 279--287."},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Brian F. Cooper Adam Silberstein Erwin Tam Raghu Ramakrishnan and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In SoCC. 143--154.","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_2_14_1","volume-title":"Granola: Low-Overhead Distributed Transaction Coordination. In USENIX ATC. 223--235.","author":"Cowling James","year":"2012","unstructured":"James Cowling and Barbara Liskov. 2012. Granola: Low-Overhead Distributed Transaction Coordination. In USENIX ATC. 223--235."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920853"},{"key":"e_1_2_2_16_1","volume-title":"Amir Shaikhha, and Christoph Koch.","author":"Dashti Mohammad","year":"2016","unstructured":"Mohammad Dashti, Sachin Basil John, Amir Shaikhha, and Christoph Koch. 2016. Repairing Conflicts among MVCC Transactions. CoRR abs\/1603.00542 (2016)."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282502"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/360363.360369"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055553"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809981"},{"key":"e_1_2_2_21_1","unstructured":"Hector Garcia-Molina Jeffrey D. Ullman and Jennifer Widom. 2002. Database systems - the complete book (international edition). Pearson Education."},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Evan P. C. Jones Daniel J. Abadi and Samuel Madden. 2010. Low overhead concurrency control for partitioned main memory databases. In SIGMOD. 603--614.","DOI":"10.1145\/1807167.1807233"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454211"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882905"},{"key":"e_1_2_2_25_1","volume-title":"FOEDUS: OLTP Engine for a Thousand Cores and NVRAM. In SIGMOD. 691--706.","author":"Kimura Hideaki","year":"2015","unstructured":"Hideaki Kimura. 2015. FOEDUS: OLTP Engine for a Thousand Cores and NVRAM. In SIGMOD. 691--706."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319567"},{"key":"e_1_2_2_27_1","volume-title":"Eris: Coordination-free consistent transactions using in-network concurrency control. In SOSP. 104--120.","author":"Li Jialin","year":"2017","unstructured":"Jialin Li, Ellis Michael, and Dan RK Ports. 2017. Eris: Coordination-free consistent transactions using in-network concurrency control. In SOSP. 104--120."},{"key":"e_1_2_2_28_1","volume-title":"Andersen","author":"Lim Hyeontaek","year":"2017","unstructured":"Hyeontaek Lim, Michael Kaminsky, and David G. Andersen. 2017. Cicada: Dependably Fast Multi-Core In-Memory Transactions. In SIGMOD. 21--35."},{"key":"e_1_2_2_29_1","volume-title":"International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 97--104","author":"Lonc Zbigniew","year":"1991","unstructured":"Zbigniew Lonc. 1991. On complexity of some chain and antichain partition problems. In International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 97--104."},{"key":"e_1_2_2_30_1","unstructured":"Microsoft. [n. d.]. In-Memory OLTP overview and usage scenarios. https:\/\/docs.microsoft.com\/en-us\/sql\/relational-databases\/in-memory-oltp\/overview-and-usage-scenarios?view=sql-server-ver16#usage-scenarios-for-."},{"key":"e_1_2_2_31_1","unstructured":"Mutrace. [n. d.]. Measuring Lock Contention. http:\/\/0pointer.de\/blog\/projects\/mutrace.html."},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Thomas Neumann Tobias M\u00fchlbauer and Alfons Kemper. 2015. Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems. In SIGMOD. 677--689.","DOI":"10.1145\/2723372.2749436"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920959"},{"key":"e_1_2_2_34_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H","unstructured":"Christos H Papadimitriou. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_2_2_35_1","volume-title":"Carlo Curino, and Stanley B. Zdonik","author":"Pavlo Andrew","year":"2012","unstructured":"Andrew Pavlo, Carlo Curino, and Stanley B. Zdonik. 2012. Skew-aware automatic database partitioning in shared-nothing, parallel OLTP systems. In SIGMOD. 61--72."},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Guna Prasaad Alvin Cheung and Dan Suciu. 2020. Handling Highly Contended OLTP Workloads Using Fast Dynamic Partitioning. In SIGMOD. 527--542.","DOI":"10.1145\/3318464.3389764"},{"key":"e_1_2_2_37_1","volume-title":"Qadah and Mohammad Sadoghi","author":"Thamir","year":"2018","unstructured":"Thamir M. Qadah and Mohammad Sadoghi. 2018. QueCC: A Queue-oriented, Control-free Concurrency Architecture. In Middleware. ACM, 13--25."},{"key":"e_1_2_2_38_1","volume-title":"Angela Demke Brown, and Ashvin Goel","author":"Qin Dai","year":"2021","unstructured":"Dai Qin, Angela Demke Brown, and Ashvin Goel. 2021. Caracal: Contention Management with Deterministic Concurrency Control. In SIGOPS. 180--194."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452427"},{"key":"e_1_2_2_40_1","volume-title":"Abadi","author":"Ren Kun","year":"2016","unstructured":"Kun Ren, Jose M. Faleiro, and Daniel J. Abadi. 2016. Design Principles for Scaling Multi-core OLTP Under High Contention. In SIGMOD. 1583--1598."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732955"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733006"},{"key":"e_1_2_2_43_1","first-page":"1","article-title":"Scheduling OLTP transactions via learned abort prediction. In aiDM","volume":"1","author":"Sheng Yangjun","year":"2019","unstructured":"Yangjun Sheng, Anthony Tomasic, Tieying Zhang, and Andrew Pavlo. 2019. Scheduling OLTP transactions via learned abort prediction. In aiDM. ACM, 1:1--1:8.","journal-title":"ACM"},{"key":"e_1_2_2_44_1","volume-title":"Nambiar","author":"Singhal Rekha","year":"2016","unstructured":"Rekha Singhal and Manoj K. Nambiar. 2016. Predicting SQL Query Execution Time for Large Data Volume. In IDEAS. 378--385."},{"key":"e_1_2_2_45_1","doi-asserted-by":"crossref","unstructured":"Chunzhi Su Natacha Crooks Cong Ding Lorenzo Alvisi and Chao Xie. 2017. Bringing Modular Concurrency Control to the Next Level. In SIGMOD. 283--297.","DOI":"10.1145\/3035918.3064031"},{"key":"e_1_2_2_46_1","volume-title":"Elmore","author":"Tang Dixin","year":"2018","unstructured":"Dixin Tang and Aaron J. Elmore. 2018. Toward Coordination-free and Reconfigurable Mixed Concurrency Control. In USENIX ATC 18. USENIX Association, 809--822."},{"key":"e_1_2_2_47_1","volume-title":"Elmore","author":"Tang Dixin","year":"2017","unstructured":"Dixin Tang, Hao Jiang, and Aaron J. Elmore. 2017. Adaptive Concurrency Control: Despite the Looking Glass, One Concurrency Control Does Not Fit All. In CIDR."},{"key":"e_1_2_2_48_1","volume-title":"BigData","author":"Tedeschi Enrico","unstructured":"Enrico Tedeschi, Tor-Arne S. Nordmo, Dag Johansen, and Hrule(a)vard D. Johansen. 2019. Predicting Transaction Latency with Deep Learning in Proof-of-Work Blockchains. In BigData. IEEE, 4223--4231."},{"key":"e_1_2_2_49_1","volume-title":"Calvin: Fast distributed transactions for partitioned database systems. In SIGMOD. 1--12.","author":"Thomson Alexander","year":"2012","unstructured":"Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, and Daniel J Abadi. 2012. Calvin: Fast distributed transactions for partitioned database systems. In SIGMOD. 1--12."},{"key":"e_1_2_2_50_1","unstructured":"Transaction Processing Performance Council. [n. d.]. TPC-C Benchmark. http:\/\/www.tpc.org\/tpcc\/."},{"key":"e_1_2_2_51_1","doi-asserted-by":"crossref","unstructured":"Stephen Tu Wenting Zheng Eddie Kohler Barbara Liskov and Samuel Madden. 2013. Speedy transactions in multicore in-memory databases. In SIGOPS. 18--32.","DOI":"10.1145\/2517349.2522713"},{"key":"e_1_2_2_52_1","volume-title":"Polyjuice: High-Performance Transactions via Learned Concurrency Control. In OSDI. 198--216.","author":"Wang Jia-Chen","year":"2021","unstructured":"Jia-Chen Wang, Ding Ding, Huan Wang, Conrad Christensen, Zhaoguo Wang, Haibo Chen, and Jinyang Li. 2021. Polyjuice: High-Performance Transactions via Learned Concurrency Control. In OSDI. 198--216."},{"key":"e_1_2_2_53_1","first-page":"3","article-title":"Towards self-tuning memory management for data servers","volume":"22","author":"Weikum Gerhard","year":"1999","unstructured":"Gerhard Weikum, Arnd Christian Koenig, Achim Kraiss, and Markus Sinnwell. 1999. Towards self-tuning memory management for data servers. IEEE Data Eng. Bull. 22, 2 (1999), 3--11.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067427"},{"key":"e_1_2_2_55_1","volume-title":"Chee Yong Chan, and Kian-Lee Tan","author":"Wu Yingjun","year":"2016","unstructured":"Yingjun Wu, Chee Yong Chan, and Kian-Lee Tan. 2016. Transaction Healing: Scaling Optimistic Concurrency Control on Multicores. In SIGMOD. ACM, 1689--1704."},{"key":"e_1_2_2_56_1","doi-asserted-by":"crossref","unstructured":"Chao Xie Chunzhi Su Cody Littley Lorenzo Alvisi Manos Kapritsos and Yang Wang. 2015. High-performance ACID via modular concurrency control. In SOSP. 279--294.","DOI":"10.1145\/2815400.2815430"},{"key":"e_1_2_2_57_1","unstructured":"Yahoo! [n. d.]. YCSB Core Workloads. https:\/\/github.com\/brianfrankcooper\/YCSB\/wiki\/Core-Workloads."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735511"},{"key":"e_1_2_2_59_1","unstructured":"Xiangyao Yu Andrew Pavlo Daniel S\u00e1nchez and Srinivas Devadas. 2016. TicToc: Time Traveling Optimistic Concurrency Control. In SIGMOD. 1629--1642."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904121.2904126"},{"key":"e_1_2_2_61_1","volume-title":"Chiller: Contention-Centric Transaction Execution and Data Partitioning for Modern Networks. In SIGMOD. 511--526.","author":"Zamanian Erfan","year":"2020","unstructured":"Erfan Zamanian, Julian Shun, Carsten Binnig, and Tim Kraska. 2020. Chiller: Contention-Centric Transaction Execution and Data Partitioning for Modern Networks. In SIGMOD. 511--526."},{"key":"e_1_2_2_62_1","doi-asserted-by":"crossref","unstructured":"Tieying Zhang Anthony Tomasic Yangjun Sheng and Andrew Pavlo. 2018. Performance of OLTP via Intelligent Scheduling. In ICDE. 1288--1291.","DOI":"10.1109\/ICDE.2018.00132"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588706","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588706","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:14Z","timestamp":1750178834000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588706"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588706"],"URL":"https:\/\/doi.org\/10.1145\/3588706","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}