{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T21:09:31Z","timestamp":1775596171825,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["U24A20232"],"award-info":[{"award-number":["U24A20232"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62272106"],"award-info":[{"award-number":["62272106"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>Recent advancements in Binned Scan Index have demonstrated significant potential for accelerating scan operators in main memory analytical databases. This capability stems from the Draft-Refine paradigm \u2013 a two-phase approach that first generates approximate draft results, then refines them using auxiliary metadata stored in the index. Despite achieving state-of-the-art scan performance, current designs still suffer from two major inefficiencies: (1) Refinement-phase overhead: While modern techniques improve draft accuracy to reduce refinement iterations, each refinement operation incurs substantial random memory access costs, and (2) Dynamic data inefficiency: When considering MVCC, scan operators need to determine the visible version of records for current transaction. The overhead of visibility checking is substantially greater than the cost of predicate evaluation. Consequently, leveraging a Binned Scan Index for scans yields only marginal improvements in total execution time.<\/jats:p>\n                  <jats:p>We propose LiveBin, a localized and version-aware Binned Scan Index that addresses these challenges through two key techniques: (1) Localization partitions a complete index into logically independent sub-indexes. While prior work strives to reduce refinement frequency through more complex draft generation, LiveBin employs Localization to decrease per-refinement random memory access overhead. This effectively reduces refinement-phase overhead while maintaining efficient draft generation. (2) Version-aware indexing embeds a hierarchical versioning structure, which extends the Draft-Refine paradigm to visibility checking. This integration consequently minimizes visibility validation and version chain traversal overhead. Experimental results demonstrate that LiveBin achieves 2.2\u20132.6\u00d7 faster scan performance than state-of-the-art methods under identical memory budgets. We further integrated LiveBin into DuckDB, and the enhanced system achieved end-to-end speedups of 2.4\u20135.0\u00d7 compared to the original DuckDB on TPC-H Q6 and SSB Q1 queries.<\/jats:p>","DOI":"10.1145\/3786664","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["LiveBin: A Localized and Version-Aware Binned Scan Index"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-3986-2920","authenticated-orcid":false,"given":"Zikang","family":"Liu","sequence":"first","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7647-506X","authenticated-orcid":false,"given":"Linwei","family":"Li","sequence":"additional","affiliation":[{"name":"Tencent, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-6850-3087","authenticated-orcid":false,"given":"Fei","family":"Ye","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2926-4814","authenticated-orcid":false,"given":"Zhenying","family":"He","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1169-8032","authenticated-orcid":false,"given":"Yinan","family":"Jing","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8217-869X","authenticated-orcid":false,"given":"Wen","family":"He","sequence":"additional","affiliation":[{"name":"Tencent, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1879-3583","authenticated-orcid":false,"given":"Huichao","family":"Duan","sequence":"additional","affiliation":[{"name":"Tencent, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-2848-1390","authenticated-orcid":false,"given":"Lixiong","family":"Zheng","sequence":"additional","affiliation":[{"name":"Tencent, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9059-3713","authenticated-orcid":false,"given":"X. Sean","family":"Wang","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733094"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915964"},{"key":"e_1_2_1_3_1","unstructured":"Philip A Bernstein Vassos Hadzilacos Nathan Goodman et al. 1987. Concurrency control and recovery in database systems. Vol. 370. Addison-wesley Reading."},{"key":"e_1_2_1_4_1","first-page":"882","article-title":"Sqlite: Light database system","volume":"44","author":"Bhosale Satish Tanaji","year":"2015","unstructured":"Satish Tanaji Bhosale, Tejaswini Patil, and Pooja Patil. 2015. Sqlite: Light database system. Int. J. Comput. Sci. Mob. Comput, Vol. 44, 4 (2015), 882-885.","journal-title":"Int. J. Comput. Sci. Mob. Comput"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0507-8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364328"},{"key":"e_1_2_1_7_1","volume-title":"International Workshop on In-Memory Data Management and Analytics. Springer, 97-111","author":"Broneske David","year":"2013","unstructured":"David Broneske, Sebastian Bre\u00df, and Gunter Saake. 2013. Database scan variants on modern CPUs: A performance study. In International Workshop on In-Memory Data Management and Analytics. Springer, 97-111."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1620585.1620587"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDBM.2007.24"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276336"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639312"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747642"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00559-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196911"},{"key":"e_1_2_1_16_1","first-page":"68","volume-title":"CIDR","volume":"7","author":"Idreos Stratos","year":"2007","unstructured":"Stratos Idreos, Martin L Kersten, Stefan Manegold, et al., 2007. Database Cracking.. In CIDR, Vol. 7. 68-78."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0406-1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2884714"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453925"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064049"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319567"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882925"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2903734"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380563"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920990"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465322"},{"key":"e_1_2_1_29_1","volume-title":"Small materialized aggregates: A light weight index structure for data warehousing. None","author":"Moerkotte Guido","year":"1998","unstructured":"Guido Moerkotte. 1998. Small materialized aggregates: A light weight index structure for data warehousing. None (1998)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749436"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747645"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2914836"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_1_34_1","unstructured":"Hongchan Roh Sanghyun Park Sungho Kim Mincheol Shin and Sang-Won Lee. 2011. B-tree Index Optimization by Exploiting Internal Parallelism of Flash-based Solid State Drives. arXiv:1201.0227 [cs.DB] https:\/\/arxiv.org\/abs\/1201.0227"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465306"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610515"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2020.3047972"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3705829.3705854"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589785"},{"key":"e_1_2_1_40_1","unstructured":"Thomas Willhalm Ismail Oukid Ingo M\u00fcller and Franz Faerber. 2013. Vectorizing Database Column Scans with Complex Predicates.. In ADMS@ VLDB. 1-12."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687671"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067427"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Per \u00c5ke Larson Spyros Blanas Cristian Diaconu Craig Freedman Jignesh M. Patel and Mike Zwilling. 2011. High-Performance Concurrency Control Mechanisms for Main-Memory Databases. arXiv:1201.0228 [cs.DB] https:\/\/arxiv.org\/abs\/1201.0228","DOI":"10.14778\/2095686.2095689"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786664","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:02:58Z","timestamp":1775592178000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786664"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786664"],"URL":"https:\/\/doi.org\/10.1145\/3786664","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}